Optimization Online


A Smoothing SQP Framework for a Class of Composite $L_q$ Minimization over Polyhedron

Ya-Feng Liu(yafliu***at***lsec.cc.ac.cn)
Shiqian Ma(sqma***at***se.cuhk.edu.hk)
Yu-Hong Dai(dyh***at***lsec.cc.ac.cn)
Shuzhong Zhang(zhangs***at***umn.edu)

Abstract: 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. Firstly, we show that for any fixed 0<q<1, finding the global minimizer of the problem, even its unconstrained counterpart, is strongly NP-hard. Secondly, we derive Karush-Kuhn-Tucker optimality conditions for local minimizers of the problem. Thirdly, we propose a smoothing sequential quadratic programming framework for solving this problem. The framework requires an (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.

Keywords: Composite $L_q$ minimization; nonsmooth nonconvex non-Lipschitzian optimization; worst-case iteration complexity

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 07/28/2014
Entry Accepted: 07/28/2014
Entry Last Modified: 07/28/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society