MATLAB Answers


fmincon: interior-point & SQP computational complexity

Asked by Andrea Bacilieri on 11 Mar 2019
Latest activity Edited by Andrea Bacilieri on 16 Mar 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!


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

  1 Comment

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.

Sign in to comment.