fmincon: interior-point & SQP computational complexity

2019 3 11
1 个回答
更新时间：2019 5 6
8 次查看（30 天）

0 个投票

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!

请先登录，再回答此问题。

回答（1 个）

Alan Weiss
Alan Weiss 2019-3-11

1 个投票

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 个评论
显示 1更早的评论 隐藏 1更早的评论

Andrea Bacilieri
Andrea Bacilieri 2019-3-14
编辑：Andrea Bacilieri 2019-3-16
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
Carlo Cavicchia 2019-5-2
Hi, thanks for the information! Can you share with us the references of the computational complexity of SQP?
Andrea Bacilieri
Andrea Bacilieri 2019-5-6
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.

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by