MATLAB Answers

Translated by

このページのコンテンツは英語から自動翻訳されています。自動翻訳をオフにする場合は「<a class="turn_off_mt" href="#">ここ</a>」をクリックしてください。


fmincon: interior-point & SQP computational complexity

Andrea Bacilieri さんによって質問されました 2019 年 3 月 11 日
最新アクティビティ Andrea Bacilieri さんによって 編集されました 2019 年 3 月 16 日
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 件のコメント

サインイン to comment.

1 件の回答

回答者: Alan Weiss
2019 年 3 月 11 日

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 件のコメント

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.

サインイン to comment.

Translated by