The composite Lq(0<q<1) minimization problem over a general polyhedron has received various applications in machine learning, wireless communications, image restoration, signal reconstruction, etc. This paper aims to provide a theoretical study on this problem. First, we derive the Karush–Kuhn–Tucker (KKT) optimality conditions for local minimizers of the problem. Second, we propose a smoothing sequential quadratic programming framework for solving this problem. The framework requires a (approximate) solution of a convex quadratic program at each iteration. Finally, we analyze the worst-case iteration complexity of the framework for returning an ϵ-KKT point; i.e., a feasible point that satisfies a perturbed version of the derived KKT optimality conditions. To the best of our knowledge, the proposed framework is the first one with a worst-case iteration complexity guarantee for solving composite Lq minimization over a general polyhedron.
Bibliographical notePublisher Copyright:
© 2015, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
- Composite L minimization
- Nonsmooth nonconvex non-Lipschitzian optimization
- Optimality condition
- Smoothing approximation
- Worst-case iteration complexity
- ϵ-KKT point