{
  "id": "1407.7205",
  "version": "v1",
  "published": "2014-07-27T10:13:45.000Z",
  "updated": "2014-07-27T10:13:45.000Z",
  "title": "A Smoothing SQP Framework for a Class of Composite $L_q$ Minimization over Polyhedron",
  "authors": [
    "Ya-Feng Liu",
    "Shiqian Ma",
    "Yu-Hong Dai",
    "Shuzhong Zhang"
  ],
  "categories": [
    "math.OC"
  ],
  "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 (KKT) optimality conditions for local minimizers of the problem. Thirdly, 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-07-27T10:13:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C26",
      "90C30",
      "90C46",
      "65K05"
    ],
    "keywords": [
      "smoothing sqp framework",
      "minimization",
      "general polyhedron",
      "optimality conditions",
      "worst-case iteration complexity guarantee"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1407.7205L"
    }
  }
}