Constrained Optimization Involving Nonconvex 𝓁p Norms: Optimality Conditions, Algorithm and Convergence

Hao Wang, Yining Gao, Jiashan Wang, Hongying LiuarXiv 2021 · arXiv

TL;DR

This paper tackles the challenging problem of optimizing functions that include a non-convex $l_p$ norm (where $0 < p < 1$), which is crucial for promoting sparsity in various applications. The authors introduce novel optimality conditions and extend existing iterative reweighted algorithms to handle these constrained optimization problems, proving their convergence.

What Problem Does This Paper Address?

Many real-world problems, such as compressed sensing, biomedical engineering, and portfolio management, benefit from solutions that are sparse. Sparsity can lead to more robust and interpretable models. A common way to achieve sparsity is by incorporating $l_1$ or $l_0$ norms into optimization problems. However, recent research has shown that using non-convex $l_p$ norms (with $0 < p < 1$) can lead to even better performance in promoting sparsity.

The challenge is that these non-convex $l_p$ norms are both non-smooth and non-Lipschitz, making them notoriously difficult to analyze and solve using standard optimization techniques. While significant progress has been made for unconstrained $l_p$ minimization problems, the literature on constrained optimization problems involving these norms is sparse. This paper aims to fill this gap by developing a theoretical framework and practical algorithms for such constrained problems.

Methods

The core contributions of this paper lie in developing:

  • Optimality Conditions: The authors derive first-order necessary conditions and sequential optimality conditions for two general forms of constrained optimization problems involving $l_p$ norms:
  • (P1) $l_p$-regularized problems: where the $l_p$ norm appears as a penalty in the objective function.
  • (P2) $l_p$-ball constrained problems: where the $l_p$ norm is used as a constraint. They analyze these conditions under various constraint qualifications (CQs), including the Extended Mangasarian-Fromovitz Constraint Qualification (EMFCQ).

  • Algorithm Extension: The paper extends the well-known iteratively reweighted $l_1$ (IRL1) algorithms, which are effective for unconstrained $l_p$ minimization, to handle the constrained cases (P1). This involves reformulating the problem and constructing a smooth approximation and a convex local model at each iteration.

  • Convergence Analysis: The authors prove that the extended IRL1 algorithm converges to a point that satisfies the approximate Karush-Kuhn-Tucker (AKKT) conditions. Furthermore, under specific conditions (Extended Cone-Continuity Property - ECCP), they show that these AKKT conditions imply the desired Karush-Kuhn-Tucker (KKT) conditions, thus guaranteeing convergence to a stationary point.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithm design, with numerical experiments demonstrating performance on a portfolio optimization problem using historical stock price data.

Key Insights and Ideas

  • Bridging the Gap for Constrained $l_p$ Optimization: The paper provides a much-needed theoretical foundation for understanding and solving constrained optimization problems with non-convex $l_p$ norms, which are more widely applicable than their unconstrained counterparts.
  • Characterizing Non-Smoothness: The authors meticulously analyze the subgradients and normal cones of the $l_p$ norm and $l_p$ ball, which are crucial for deriving optimality conditions in the presence of non-smoothness.
  • Extending IRL1 to Constraints: The successful adaptation of IRL1 algorithms to constrained settings is a significant practical contribution, offering a viable method for solving these challenging problems.
  • Connecting AKKT to KKT: The introduction and analysis of sequential optimality conditions (AKKT) and their relationship to KKT conditions under ECCP provide a robust framework for algorithm convergence guarantees.

Key Results

  • The paper derives novel first-order necessary optimality conditions and sequential optimality conditions for constrained $l_p$ optimization problems (P1 and P2).
  • An iteratively reweighted $l_1$ algorithm is extended to solve constrained $l_p$ minimization problems (P1).
  • Global convergence of the proposed algorithm is proven, showing that limit points satisfy AKKT conditions, which imply KKT conditions under ECCP.
  • Numerical experiments on a portfolio optimization problem demonstrate the effectiveness of the algorithm, showing that increasing the regularization parameter leads to sparser solutions.

Limitations and Future Work

  • Constraint Qualifications: The paper relies on specific constraint qualifications (like EMFCQ and ECCP) for its theoretical results. Future work could explore optimality conditions under weaker CQs.
  • Algorithm Applicability: While the algorithm is extended for (P1), further research could focus on extending it to (P2) or other forms of constrained $l_p$ problems.
  • Numerical Performance: While numerical experiments are presented, a broader range of applications and comparisons with other state-of-the-art methods could be beneficial.
  • Second-Order Conditions: The paper primarily focuses on first-order conditions. Investigating second-order optimality conditions for these non-convex problems would be a valuable extension.

Summary updated

BibTeX
@misc{wang2021constrained,
  author = {Hao Wang and Yining Gao and Jiashan Wang and Hongying Liu},
  title = {{Constrained Optimization Involving Nonconvex 𝓁p Norms: Optimality Conditions, Algorithm and Convergence}},
  year = {2021},
  eprint = {2110.14127},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.14127},
}
Figure