High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms

Xiaojun Chen, Philippe Toint

Résultats de recherche: Papier de travailArticle de travail

3 Downloads (Pure)

Résumé

This paper studies high-order evaluation complexity for partially separable
convexly-constrained optimization involving non-Lipschitzian group sparsity
terms in a nonconvex objective function. We propose a partially separable
adaptive regularization algorithm using a p-th order Taylor model and show
that the algorithm can produce an (epsilon,delta)-approximate q-th-order
stationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of the
objective function and its first p derivatives (whenever they exist). Our
model uses the underlying rotational symmetry of the Euclidean norm function
to build a Lipschitzian approximation for the non-Lipschitzian group sparsity
terms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). The
new result shows that the partially-separable structure and non-Lipschitzian
group sparsity terms in the objective function may not affect the worst-case
evaluation complexity order.
langue originaleAnglais
EditeurArxiv
Pages1-27
Nombre de pages27
Volume1902.10767
étatPublié - 28 févr. 2019

Empreinte digitale

Constrained optimization
Constrained Optimization
Sparsity
Higher Order
Evaluation
Term
Objective function
Euclidean norm
Rotational symmetry
Regularization
Derivatives
Norm
Derivative
Approximation
Model

mots-clés

    Citer ceci

    @techreport{2daf4776868e412e987f04ba539b652d,
    title = "High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms",
    abstract = "This paper studies high-order evaluation complexity for partially separableconvexly-constrained optimization involving non-Lipschitzian group sparsityterms in a nonconvex objective function. We propose a partially separableadaptive regularization algorithm using a p-th order Taylor model and showthat the algorithm can produce an (epsilon,delta)-approximate q-th-orderstationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of theobjective function and its first p derivatives (whenever they exist). Ourmodel uses the underlying rotational symmetry of the Euclidean norm functionto build a Lipschitzian approximation for the non-Lipschitzian group sparsityterms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). Thenew result shows that the partially-separable structure and non-Lipschitziangroup sparsity terms in the objective function may not affect the worst-caseevaluation complexity order.",
    keywords = "complexity theory, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model",
    author = "Xiaojun Chen and Philippe Toint",
    year = "2019",
    month = "2",
    day = "28",
    language = "English",
    volume = "1902.10767",
    pages = "1--27",
    publisher = "Arxiv",
    type = "WorkingPaper",
    institution = "Arxiv",

    }

    High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms. / Chen, Xiaojun; Toint, Philippe.

    Arxiv, 2019. p. 1-27.

    Résultats de recherche: Papier de travailArticle de travail

    TY - UNPB

    T1 - High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms

    AU - Chen, Xiaojun

    AU - Toint, Philippe

    PY - 2019/2/28

    Y1 - 2019/2/28

    N2 - This paper studies high-order evaluation complexity for partially separableconvexly-constrained optimization involving non-Lipschitzian group sparsityterms in a nonconvex objective function. We propose a partially separableadaptive regularization algorithm using a p-th order Taylor model and showthat the algorithm can produce an (epsilon,delta)-approximate q-th-orderstationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of theobjective function and its first p derivatives (whenever they exist). Ourmodel uses the underlying rotational symmetry of the Euclidean norm functionto build a Lipschitzian approximation for the non-Lipschitzian group sparsityterms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). Thenew result shows that the partially-separable structure and non-Lipschitziangroup sparsity terms in the objective function may not affect the worst-caseevaluation complexity order.

    AB - This paper studies high-order evaluation complexity for partially separableconvexly-constrained optimization involving non-Lipschitzian group sparsityterms in a nonconvex objective function. We propose a partially separableadaptive regularization algorithm using a p-th order Taylor model and showthat the algorithm can produce an (epsilon,delta)-approximate q-th-orderstationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of theobjective function and its first p derivatives (whenever they exist). Ourmodel uses the underlying rotational symmetry of the Euclidean norm functionto build a Lipschitzian approximation for the non-Lipschitzian group sparsityterms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). Thenew result shows that the partially-separable structure and non-Lipschitziangroup sparsity terms in the objective function may not affect the worst-caseevaluation complexity order.

    KW - complexity theory, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model

    KW - nonlinear optimization

    KW - non-Lipschitz functions

    KW - partially-separable problems

    KW - group sparsity

    KW - isotropic model

    M3 - Working paper

    VL - 1902.10767

    SP - 1

    EP - 27

    BT - High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms

    PB - Arxiv

    ER -