Résumé
| langue originale | Anglais |
|---|---|
| Pages (de - à) | 1721-1739 |
| Nombre de pages | 19 |
| journal | SIAM Journal on Optimization |
| Volume | 21 |
| Numéro de publication | 4 |
| Les DOIs | |
| état | Publié - 1 janv. 2011 |
Empreinte digitale
Citer ceci
}
On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming. / Cartis, Coralia; Gould, Nick; Toint, Philippe.
Dans: SIAM Journal on Optimization, Vol 21, Numéro 4, 01.01.2011, p. 1721-1739.Résultats de recherche: Contribution à un journal/une revue › Article
TY - JOUR
T1 - On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming
AU - Cartis, Coralia
AU - Gould, Nick
AU - Toint, Philippe
N1 - Publication code : FP SB092/2011/06 ; SB04977/2011/06
PY - 2011/1/1
Y1 - 2011/1/1
N2 - 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(ε-2) function evaluations to reduce the size of a first-order criticality measure below ε. Specializing this result to the case when the composite objective is an exact penalty function allows us to consider the objective- and constraintevaluation 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 ε of a KKT point is at most O(ε-2) problem evaluations, which is the same in order as the function-evaluation complexity of steepest-descent methods applied to unconstrained, nonconvex smooth optimization. © 2011 Society for Industrial and Applied Mathematics.
AB - 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(ε-2) function evaluations to reduce the size of a first-order criticality measure below ε. Specializing this result to the case when the composite objective is an exact penalty function allows us to consider the objective- and constraintevaluation 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 ε of a KKT point is at most O(ε-2) problem evaluations, which is the same in order as the function-evaluation complexity of steepest-descent methods applied to unconstrained, nonconvex smooth optimization. © 2011 Society for Industrial and Applied Mathematics.
KW - nonlinear optimization
KW - composite minimization
KW - complexity
KW - nonconvex problems.
UR - http://www.scopus.com/inward/record.url?scp=84856057771&partnerID=8YFLogxK
U2 - 10.1137/11082381X
DO - 10.1137/11082381X
M3 - Article
VL - 21
SP - 1721
EP - 1739
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
SN - 1052-6234
IS - 4
ER -