Abstract
An adaptive regularization algorithm using high-order models is proposed for solving partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian 'q-norm regularization terms for q ϵ (0; 1). It is shown that the algorithm using a pth-order Taylor model for p odd needs in general at most O(ϵ -(p+1)=p) evaluations of the objective function and its derivatives (at points where they are defined) to produce an ϵ-approximate first-order critical point. This result is obtained either with Taylor models, at the price of requiring the feasible set to be kernel centered" (which includes bound constraints and many other cases of interest), or with non-Lipschitz models, at the price of passing the difficulty to the computation of the step. Since this complexity bound is identical in order to that already known for purely Lipschitzian minimization subject to convex constraints [C. Cartis, N. I. M. Gould, and Ph. L. Toint, IMA J. Numer. Anal., 32 (2012), pp. 1662-1695], the new result shows that introducing non-Lipschitzian singularities in the objective function may not affect the worst-case evaluation complexity order. The result also shows that using the problem's partially separable structure (if present) does not affect the complexity order either. A final (worse) complexity bound is derived for the case where Taylor models are used with a general convex feasible set.
| Original language | English |
|---|---|
| Pages (from-to) | 874-903 |
| Number of pages | 30 |
| Journal | SIAM Journal on Optimization |
| Volume | 29 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 15 Apr 2019 |
Fingerprint
Keywords
- Non_Lipschitz optimization
- Complexity theory
- partial separability
Cite this
}
Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities. / Chen, Xiaojun; Toint, Philippe; Wang, Hong.
In: SIAM Journal on Optimization, Vol. 29, No. 1, 15.04.2019, p. 874-903.Research output: Contribution to journal › Article
TY - JOUR
T1 - Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities
AU - Chen, Xiaojun
AU - Toint, Philippe
AU - Wang, Hong
PY - 2019/4/15
Y1 - 2019/4/15
N2 - An adaptive regularization algorithm using high-order models is proposed for solving partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian 'q-norm regularization terms for q ϵ (0; 1). It is shown that the algorithm using a pth-order Taylor model for p odd needs in general at most O(ϵ -(p+1)=p) evaluations of the objective function and its derivatives (at points where they are defined) to produce an ϵ-approximate first-order critical point. This result is obtained either with Taylor models, at the price of requiring the feasible set to be kernel centered" (which includes bound constraints and many other cases of interest), or with non-Lipschitz models, at the price of passing the difficulty to the computation of the step. Since this complexity bound is identical in order to that already known for purely Lipschitzian minimization subject to convex constraints [C. Cartis, N. I. M. Gould, and Ph. L. Toint, IMA J. Numer. Anal., 32 (2012), pp. 1662-1695], the new result shows that introducing non-Lipschitzian singularities in the objective function may not affect the worst-case evaluation complexity order. The result also shows that using the problem's partially separable structure (if present) does not affect the complexity order either. A final (worse) complexity bound is derived for the case where Taylor models are used with a general convex feasible set.
AB - An adaptive regularization algorithm using high-order models is proposed for solving partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian 'q-norm regularization terms for q ϵ (0; 1). It is shown that the algorithm using a pth-order Taylor model for p odd needs in general at most O(ϵ -(p+1)=p) evaluations of the objective function and its derivatives (at points where they are defined) to produce an ϵ-approximate first-order critical point. This result is obtained either with Taylor models, at the price of requiring the feasible set to be kernel centered" (which includes bound constraints and many other cases of interest), or with non-Lipschitz models, at the price of passing the difficulty to the computation of the step. Since this complexity bound is identical in order to that already known for purely Lipschitzian minimization subject to convex constraints [C. Cartis, N. I. M. Gould, and Ph. L. Toint, IMA J. Numer. Anal., 32 (2012), pp. 1662-1695], the new result shows that introducing non-Lipschitzian singularities in the objective function may not affect the worst-case evaluation complexity order. The result also shows that using the problem's partially separable structure (if present) does not affect the complexity order either. A final (worse) complexity bound is derived for the case where Taylor models are used with a general convex feasible set.
KW - Non_Lipschitz optimization
KW - Complexity theory
KW - partial separability
UR - http://www.scopus.com/inward/record.url?scp=85065443105&partnerID=8YFLogxK
U2 - 10.1137/18M1166511
DO - 10.1137/18M1166511
M3 - Article
VL - 29
SP - 874
EP - 903
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
SN - 1052-6234
IS - 1
ER -