fmincon: interior-point & SQP computational complexity

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!

Answer 1

[Alan Weiss]

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

[Andrea Bacilieri]

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.

[Carlo Cavicchia]

Hi, thanks for the information! Can you share with us the references of the computational complexity of SQP?

[Andrea Bacilieri]

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.