A smoothing SQP framework for a class of composite Lq minimization over polyhedron

Ya Feng Liu, Shiqian Ma, Yu Hong Dai, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)467-500
Number of pages34
JournalMathematical Programming
Volume158
Issue number1-2
DOIs
StatePublished - Jul 1 2016

Bibliographical note

Publisher Copyright:
© 2015, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

Keywords

  • Composite L minimization
  • Nonsmooth nonconvex non-Lipschitzian optimization
  • Optimality condition
  • Smoothing approximation
  • Worst-case iteration complexity
  • ϵ-KKT point

Fingerprint

Dive into the research topics of 'A smoothing SQP framework for a class of composite Lq minimization over polyhedron'. Together they form a unique fingerprint.

Cite this