Abstract
The composite $L_q$ minimization problem ($0 < q < 1$) is a powerful tool for inducing sparsity in optimization, yet it presents significant computational challenges due to its non-convex and non-Lipschitz nature. This paper introduces a novel Smoothing Sequential Quadratic Programming (SSQP) framework designed to solve these problems over polyhedral constraints. We establish first-order optimality conditions (KKT points) and prove that the problem is strongly NP-hard. Our primary contribution is the first worst-case iteration complexity guarantee for this class of problems, showing that the SSQP framework reaches an $\epsilon$-KKT point in at most $O(\epsilon^{q-4})$ iterations.
Introduction: The Quest for Sparsity
In modern data science and signal processing, we frequently seek "sparse" solutions—models where only a small fraction of variables are non-zero. While the $L_1$ norm is the standard convex proxy for sparsity, the $L_q$ norm (where $0 < q < 1$) provides a much closer approximation to the true $L_0$ counting norm. However, this improved performance comes at a steep mathematical cost. $L_q$ minimization is non-convex, leading to numerous local minima, and non-Lipschitzian, meaning the gradient of the objective function approaches infinity as variables approach zero.
This research addresses the composite $L_q$ minimization problem specifically over a polyhedron—a feasible region defined by a set of linear inequalities. This structure is foundational to several high-impact applications, including soft-margin Support Vector Machines (SVMs), wireless network power control, and sparse error recovery in linear decoding.
Theoretical Foundations
Before proposing an algorithmic solution, the authors establish the theoretical boundaries of the problem. They prove that even the simplest version of composite $L_q$ minimization is strongly NP-hard by demonstrating a reduction from the 3-partition problem. This confirms that finding a global minimum is computationally intractable for large-scale instances.
To navigate this difficulty, the paper derives specific Karush-Kuhn-Tucker (KKT) optimality conditions tailored for non-Lipschitz functions. A critical theoretical bridge is established: the authors prove a one-to-one correspondence between the local minimizers of the original non-smooth problem and a better-behaved auxiliary problem, providing a rigorous target for algorithmic convergence.
The SSQP Framework
The proposed Smoothing Sequential Quadratic Programming (SSQP) framework utilizes three integrated strategies to handle the objective's irregularities:
- Smoothing Technique: The non-differentiable $L_q$ term is replaced with a smooth approximation $\tilde{F}(x, \mu)$, controlled by a parameter $\mu$. As the algorithm progresses, $\mu$ is reduced, ensuring the approximation converges to the original function.
- Sequential Quadratic Programming (SQP): Rather than tackling the non-convex objective directly, the algorithm solves a sequence of simpler Convex Quadratic Programs (QP). At each iteration, it constructs a quadratic upper bound of the smoothed objective and minimizes it over the polyhedral constraints.
- Adaptive Parameter Updates: The framework dynamically adjusts the estimated Lipschitz constant and the smoothing parameter $\mu$. This adaptive approach ensures the sequence of iterates moves steadily toward a point satisfying the KKT conditions.
Complexity and Performance
The most significant breakthrough of this work is the derivation of a worst-case iteration complexity. The authors prove that the SSQP algorithm will return an $\epsilon$-KKT point—a point that satisfies the optimality conditions within a tolerance of $\epsilon$—in at most $O(\epsilon^{q-4})$ iterations.
This result is notable for several reasons:
- First of its Kind: It provides the first complexity guarantee for composite $L_q$ minimization over general polyhedral constraints.
- Stronger Guarantees: The framework offers a more robust definition of an $\epsilon$-KKT point compared to previous methods like Smoothing Quadratic Regularization (SQR), leading to higher-quality solutions.
- Efficiency at the Limit: For the case where $q=1$, the complexity becomes $O(\epsilon^{-3})$, which is competitive with state-of-the-art specialized algorithms for $L_1$ optimization.
Applications
The utility of the SSQP framework is demonstrated through three primary motivating applications:
- Support Vector Machines (SVM): Enhancing feature selection in classification tasks by utilizing the $L_q$ penalty to produce sparser weight vectors.
- Joint Power and Admission Control: Optimizing power allocation in wireless networks to manage interference while maximizing the number of active users.
- Linear Decoding: Recovering sparse error vectors in communication systems to improve the reliability of data transmission.
Conclusion and Future Directions
The SSQP framework represents a significant step forward in non-convex optimization, providing both theoretical guarantees and a practical path for solving non-Lipschitz problems. While the algorithm focuses on local optimality due to the NP-hardness of the global problem, its complexity guarantees provide a reliable benchmark for performance. Future research may extend these smoothing and SQP techniques to Semidefinite Programming (SDP), potentially unlocking new solutions for complex matrix-based engineering problems.
Summary updated