Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity

Xiaojun Chen, Philippe Toint, Hong Wang

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

Résumé

An adaptive regularization algorithm using high-order models is proposed for 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 an p-th 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 for 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 [9], 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 complexity order either. A final (worse) complexity bound is derived for the case where Taylor models are used with a general convex feasible set.
langue originaleAnglais
Pages (de - à)874-903
Nombre de pages30
journalSIAM Journal on Optimization
Volume29
Numéro de publication1
étatPublié - 15 avr. 2019

Empreinte digitale

Constrained optimization
Constrained Optimization
Singularity
Objective function
Regularization
Bound Constraints
Non-Lipschitz
Convex Constraints
Model
Evaluation
Adaptive algorithms
Nonlinear Optimization
Nonlinear Problem
Critical point
Odd
Higher Order
kernel
Optimization Problem
First-order
Derivatives

mots-clés

    Citer ceci

    @article{d0a831ad24394e3eb25c6a4994536b87,
    title = "Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity",
    abstract = "An adaptive regularization algorithm using high-order models is proposed for 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 an p-th 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 for 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 [9], 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 complexity order either. A final (worse) complexity bound is derived for the case where Taylor models are used with a general convex feasible set.",
    keywords = "Non_Lipschitz optimization, Complexity theory, partial separability",
    author = "Xiaojun Chen and Philippe Toint and Hong Wang",
    year = "2019",
    month = "4",
    day = "15",
    language = "English",
    volume = "29",
    pages = "874--903",
    journal = "SIAM Journal on Optimization",
    issn = "1052-6234",
    publisher = "Society for Industrial and Applied Mathematics",
    number = "1",

    }

    Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity. / Chen, Xiaojun; Toint, Philippe; Wang, Hong.

    Dans: SIAM Journal on Optimization, Vol 29, Numéro 1, 15.04.2019, p. 874-903.

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

    TY - JOUR

    T1 - Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity

    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 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 an p-th 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 for 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 [9], 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 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 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 an p-th 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 for 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 [9], 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 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

    M3 - Article

    VL - 29

    SP - 874

    EP - 903

    JO - SIAM Journal on Optimization

    JF - SIAM Journal on Optimization

    SN - 1052-6234

    IS - 1

    ER -