MATLAB Answers

0

fmincon: interior-point & SQP computational complexity

Asked by Andrea Bacilieri on 11 Mar 2019
Latest activity Commented on by Andrea Bacilieri on 6 May 2019
Hi! I have a very lage-scale optimization problem and I need to know the computational complexity of the interior-point algorithm as well as SQP so that I can estimate, roughly, the computational time of a given computer or cluster.
Thanks to all in advance!

  0 Comments

Sign in to comment.

1 Answer

Answer by Alan Weiss
on 11 Mar 2019

This question can probably be best estimated by scaling the problem from small to medium to lmedium-arge, running fmincon on all scales, and extrapolating, rather than by doing a theoretical computation. It matters very much what kinds of constraints you have (bounds, linear, nonlinear), and whether constraint matrices are sparse or not.
As explained here, there can be large differences in performance between the interior-point algorithm (which is large-scale) and the sqp algorithm (which is not large-scale). See fmincon Algorithms.
The algorithm descriptions can be found in Constrained Nonlinear Optimization Algorithms, but I think that you would have to work pretty hard to get the complexity estimates out of those descriptions. Sorry, I don't know anything else.
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation

  3 Comments

Thanks a lot for the suggestions. Unfortunately, I don't think extrapolation is a good solution since I would have to try it out for something that works on my laptop, like N={10, 100, 200}, and extrapolate for N=23,000^2 (worst case). However, I would then use a cluster. I tried to understand the computational complexity and it seems to me that, for the interior-point, the most costly operation is the LDL factorization that has a cost of N^2 or N^3, depending on the algorithm used by MATLAB. On the other hand, for SQP, the most costly step should be either the Hessian, O(N^2), or the QR fatorization, which has a cost of O(m^2*n), where the active set coefficient matrix is of size mxn.
Hi, thanks for the information! Can you share with us the references of the computational complexity of SQP?
You need to go on the last link posted by Alan,https://uk.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-algorithms.html#bsgppl4, where you can find the details of the algorithms along with the relevant literature. Bear in mind that you need to understand it yourself, there's no formal derivation.

Sign in to comment.