On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming

Coralia Cartis, Nick Gould, Philippe Toint

Résultats de recherche: Contribution à un journal/une revueArticle

26 Downloads (Pure)

Résumé

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.
langue originaleAnglais
Pages (de - à)1721-1739
Nombre de pages19
journalSIAM Journal on Optimization
Volume21
Numéro de publication4
Les DOIs
étatPublié - 1 janv. 2011

Empreinte digitale

Nonconvex Programming
Function Minimization
Composite function
Function evaluation
Nonlinear programming
Nonlinear Programming
Steepest descent method
First-order
Constrained optimization
Composite materials
Evaluation
Evaluation Function
Composite
Exact Penalty
Exact Penalty Function
Steepest Descent Method
Trust Region
Penalty Method
Exact Method
Regularization Method

Citer ceci

@article{5ac8cbc632ea4bd299695730256141c3,
title = "On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming",
abstract = "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. {\circledC} 2011 Society for Industrial and Applied Mathematics.",
keywords = "nonlinear optimization, composite minimization, complexity, nonconvex problems.",
author = "Coralia Cartis and Nick Gould and Philippe Toint",
note = "Publication code : FP SB092/2011/06 ; SB04977/2011/06",
year = "2011",
month = "1",
day = "1",
doi = "10.1137/11082381X",
language = "English",
volume = "21",
pages = "1721--1739",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics",
number = "4",

}

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 revueArticle

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 -