Résumé
The complexity of finding e-Approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that O(e-2) 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. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
| langue originale | Anglais |
|---|---|
| Pages (de - à) | 93-106 |
| Nombre de pages | 14 |
| journal | Mathematical Programming |
| Volume | 144 |
| Numéro de publication | 1-2 |
| Les DOIs | |
| état | Publié - 2014 |
Empreinte digitale
Citer ceci
}
On the complexity of finding first-order critical points in constrained nonlinear optimization. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe L.
Dans: Mathematical Programming, Vol 144, Numéro 1-2, 2014, p. 93-106.Résultats de recherche: Contribution à un journal/une revue › Article
TY - JOUR
T1 - On the complexity of finding first-order critical points in constrained nonlinear optimization
AU - Cartis, Coralia
AU - Gould, Nicholas I M
AU - Toint, Philippe L.
N1 - Publication code : FP SB092/2011/13 ; SB04977/2011/13
PY - 2014
Y1 - 2014
N2 - The complexity of finding e-Approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that O(e-2) 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. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
AB - The complexity of finding e-Approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that O(e-2) 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. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
KW - Constrained nonlinear optimization
KW - Evaluation complexity
KW - Worst-case analysis
UR - http://www.scopus.com/inward/record.url?scp=84897112534&partnerID=8YFLogxK
U2 - 10.1007/s10107-012-0617-9
DO - 10.1007/s10107-012-0617-9
M3 - Article
VL - 144
SP - 93
EP - 106
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 1-2
ER -