期刊
SIAM JOURNAL ON OPTIMIZATION
卷 21, 期 4, 页码 1721-1739出版社
SIAM PUBLICATIONS
DOI: 10.1137/11082381X
关键词
nonlinear programming; nonsmooth optimization; steepest descent methods; trust region methods; quadratic regularization methods; exact penalty methods; global complexity bounds; global rate of convergence
资金
- Royal Society [14265]
- EPSRC [EP/E053351/1]
- EPSRC [EP/I013067/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/I013067/1, EP/E053351/1] Funding Source: researchfish
We estimate the worst-case complexity of minimizing an unconstrained, nonconvex composite objective with a structured nonsmooth term by means of some first-order methods. We find that it is unaffected by the nonsmoothness of the objective in that a first-order trust-region or quadratic regularization method applied to it takes at most O(epsilon(-2)) function evaluations to reduce the size of a first-order criticality measure below epsilon. Specializing this result to the case when the composite objective is an exact penalty function allows us to consider the objective-and constraint-evaluation worst-case complexity of nonconvex equality-constrained optimization when the solution is computed using a first-order exact penalty method. We obtain that in the reasonable case when the penalty parameters are bounded, the complexity of reaching within epsilon of a KKT point is at most O(epsilon(-2)) problem evaluations, which is the same in order as the function-evaluation complexity of steepest-descent methods applied to unconstrained, nonconvex smooth optimization.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据