0
$\begingroup$

I need to solve an optimization problem with two nonlinear equality constraints. My function evaluation is very fast (less than a second) and I also provide fmincon with the gradients of my objective and constraint functions. However, when fmincon is slow when there are about 2000 variables, and it is very slow when there are 6000 variables. Considering my function evaluation is super fast, I guess the bottle neck is the speed of fmincon. How can I possibly speed up fmincon? If not, can anyone suggest any other optimization packages?

$\endgroup$
  • 3
    $\begingroup$ It would help if you could provide more details about (i) the optimization problem, (ii) which algorithm you select in fmincon. $\endgroup$ – Wolfgang Bangerth Apr 7 '15 at 12:31
  • $\begingroup$ You are likely running afoul of "the curse of dimensionality", that with increasing numbers of variables the solution space undergoes "combinatorial explosion". However you need to explicitly pose your problem in order to get specific suggestions on how to cope. $\endgroup$ – hardmath Apr 7 '15 at 13:48
  • 2
    $\begingroup$ Don't "guess" at what is the bottleneck, profile your code. Matlab makes this very easy. $\endgroup$ – horchler Apr 8 '15 at 3:48
4
$\begingroup$

Without knowing more about your problem, it's difficult to make specific recommendations. I've made some general recommendations about nonlinear programming solvers in this question. To summarize:

  • IPOPT is a good interior point method (IPM) solver
  • SNOPT is a good sequential quadratic programming (SQP) solver
  • CONOPT is a pretty good generalized reduced gradient (GRG) solver

In your case, if there are only two active constraints (not counting bound constraints), I'd think that a GRG solver might do reasonably well, and that SQP wouldn't be that helpful, but for a problem with 6000 variables, all of these methods are viable. These are all convex solvers, and since your problem has nonlinear equality constraints, it is likely that your problem is nonconvex, in which case these solvers will return locally optimal solutions. However, fmincon will also return a locally optimal solution.

If you want a globally optimal solution, you should instead look at global optimization solvers such as BARON, Couenne, Bonmin, and DICOPT.

If you have access, consider using a modeling environment such as GAMS or CVX, which will give you the option of posing your problem once, and selecting from many different solvers, to see which one works best for your problem.

From grepping around the MATLAB source code, it seems likely that fmincon is mostly implemented in pure MATLAB, which would explain why it is slow. It would be better to use a solver that implements the core mathematical algorithms in the solver in a compiled language, which would be (significantly) faster.

$\endgroup$

Your Answer

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.