A smoothing SQP framework for a class of composite \(L_q\) minimization over polyhedron

详细信息    查看全文

• 作者：Ya-Feng Liu ; Shiqian Ma ; Yu-Hong Dai ; Shuzhong Zhang
• 刊名：Mathematical Programming
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：158
• 期：1-2
• 页码：467-500
• 全文大小：746 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646
• 卷排序：158

文摘

The composite \(L_q~(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 \(\epsilon \)-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 \(L_q\) minimization over a general polyhedron.KeywordsComposite \(L_q\) minimization\(\epsilon \)-KKT pointNonsmooth nonconvex non-Lipschitzian optimizationOptimality conditionSmoothing approximationWorst-case iteration complexity