5
$\begingroup$

I want to find a parallel computing method for general nonlinear convex optimization problems with constraints.

A parallel method that can solve a bundle of nonlinear convex problems simultaneously, where each convex optimization problem is unrelated to each other.

I am familiar with many convex solvers, like Matlab, Gurobi, Cvxpy. I don't believe none of them can solve many convex problems in a parallel manner.

My questions:

  1. Is there such a parallel approach to the study of convex optimization?
  2. What is the state-of-the-art of this research?
New contributor
dawen is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
4
  • 2
    $\begingroup$ If you have, e.g., 100 unrelated problems, you can spawn as many instances of Gurobi in parallel. Would that be satisfactory to your use case? $\endgroup$
    – mtanneau
    Jan 13 at 21:43
  • $\begingroup$ Hello @mtanneau, what I want is, to solve these 100 unrelated problems in parallel. Solve these 100 instances, with no for-loop of Gurobi, $\endgroup$
    – dawen
    Jan 13 at 21:46
  • 2
    $\begingroup$ This is what I described: solve them in parallel using <SolverName>, no for loop involved. If your problems are unrelated, then you can spawn as many jobs, e.g., you have 100 problems and you start 100 Gurobi processes in parallel. Each of these processes is independent, and you could even run them on their own machines. Bottom-line: you don't need parallelism in the algorithm itself. $\endgroup$
    – mtanneau
    Jan 14 at 1:31
  • $\begingroup$ But isn't it just similar to opening many computers to solve the jobs independently? For example, I opened 100 Gurobi to solve each of the 100 tasks separately, assuming that each task takes 1s when running independently. Perhaps with the parallel computing of the CPU, the total computation time is 80s, but this advantage comes from the CPU machine generally. I would like parallelism at the algorithm level specifically for convex problems, instead of parallelism at the machine level for general purposes. $\endgroup$
    – dawen
    Jan 14 at 13:18
7
$\begingroup$

Almost all convex optimization problems can be formulated as a conic optimization problem using only the cone types we can handle in practice. See the Mosek modeling cookbook for details. This often leads to the best solution time and you do not have to mess with derivatives. For instance Mosek can solve such conic optimization problems.

The upcoming Mosek version 10 (to be released spring 2022) will have a command called

optimizebatch

that will take an array of optimization problems. Those optimization problems will be solved in parallel using a pool of threads. Moreover, the thread pool can also be used to parallelize the solution of each problem. This implies a good load balancing (=efficient usage of the threads) even if the optimization problems are of vastly different size.

It is not that hard to solve multiple optimization problems in parallel as suggested in another reply. However, you easy use too many threads if you try to solve each optimization problem in parallel too. This will most likely lead to a performance degradation.

PS. I work for Mosek but does a lot of our paralleization.

$\endgroup$
2
  • $\begingroup$ Thank you for your reply. I am not an expert in this area. If I understand correctly, the optimizebatch makes better use of the CPU to get higher performance. But for every convex problem, use the same Interior-point method. Is that right? $\endgroup$
    – dawen
    Jan 14 at 13:44
  • $\begingroup$ It makes use of all cores in the CPU(s) to speed up the solution of the problems. For nonlinear problems there is only an interior-point alg. available in Mosek but it can be run in parallel too. $\endgroup$ Jan 14 at 15:09
3
$\begingroup$

solve a bundle of nonlinear convex problems simultaneously, where each convex optimization problem is unrelated to each other.

If you are using Linux this will do exactly what you want:

#!/bin/bash

max_jobs=8
problems=$(ls problems_folder)
    
for problem in $problems
do
    ipopt $problem &
    if [[ $(jobs -r -p | wc -l) -ge $max_jobs ]]; then
        wait -n; 
    fi
done

The & will run the command as a background process, so the Linux kernel will take care of the parallel runs. I also added a work limit (max_jobs) to avoid oversaturating your CPU. This is by far the simplest way to do this in Linux, but you can write similar scripts in most languages (e.g. Python).

You can substitute ipopt in the command for any solver you want.

$\endgroup$
1
  • 1
    $\begingroup$ It is probably worth mentioning that while the example code is for the bash shell, the approach is not limited to this at all. Almost any programming API or shell will have a way to implement the same approach. $\endgroup$ Jan 14 at 10:11
2
$\begingroup$

I would recommend using Gravity (https://github.com/coin-or/Gravity ) with Ipopt and just calling solve_parallel().

New contributor
Hassan Hijazi is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

dawen is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.