On the complexity of finding first-order critical points in constrained nonlinear optimization

• 成果类型: Article
• 署名作者: Cartis, Coralia; Gould, Nicholas I. M.; Toint, Philippe L.
• 署名单位: University of Edinburgh; UK Research & Innovation (UKRI); Science & Technology Facilities Council (STFC); STFC Rutherford Appleton Laboratory; University of Namur
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0617-9
• 发表日期: 2014
• 页码: 93-106
• 关键词: cubic regularization; nonconvex; minimization; algorithms

摘要

The complexity of finding -approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply.