Résumé
When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∈ can be obtained by a second-order method using cubic regularization in at most O(∈<sup>-3/2</sup> ) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear least-squares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∈<sup>-2</sup> )) evaluation-complexity bound for solving general nonconvexly constrained optimization problems.
| langue originale | Anglais |
|---|---|
| Pages (de - à) | 836-851 |
| Nombre de pages | 16 |
| journal | SIAM Journal on Numerical Analysis |
| Volume | 53 |
| Numéro de publication | 2 |
| Les DOIs | |
| état | Publié - 2015 |
Empreinte digitale
Citer ceci
}
On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe L.
Dans: SIAM Journal on Numerical Analysis, Vol 53, Numéro 2, 2015, p. 836-851.Résultats de recherche: Contribution à un journal/une revue › Article
TY - JOUR
T1 - On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods
AU - Cartis, Coralia
AU - Gould, Nicholas I M
AU - Toint, Philippe L.
PY - 2015
Y1 - 2015
N2 - When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∈ can be obtained by a second-order method using cubic regularization in at most O(∈-3/2 ) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear least-squares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∈-2 )) evaluation-complexity bound for solving general nonconvexly constrained optimization problems.
AB - When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∈ can be obtained by a second-order method using cubic regularization in at most O(∈-3/2 ) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear least-squares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∈-2 )) evaluation-complexity bound for solving general nonconvexly constrained optimization problems.
KW - Complexity theory
KW - Nonlinear optimization
KW - Constrained problems
KW - Least-squares problems
UR - http://www.scopus.com/inward/record.url?scp=84929414148&partnerID=8YFLogxK
U2 - 10.1137/130915546
DO - 10.1137/130915546
M3 - Article
VL - 53
SP - 836
EP - 851
JO - SIAM Journal on Numerical Analysis
JF - SIAM Journal on Numerical Analysis
SN - 0036-1429
IS - 2
ER -