Journal
MATHEMATICAL PROGRAMMING
Volume 158, Issue 1-2, Pages 467-500Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-015-0939-5
Keywords
Composite L-q minimization; epsilon-KKT point; Nonsmooth nonconvex non-Lipschitzian optimization; Optimality condition; Smoothing approximation; Worst-case iteration complexity
Categories
Funding
- NSFC [11331012, 11301516, 71331001]
- Hong Kong Research Grants Council General Research Fund Early Career Scheme [CUHK 439513]
- China National Funds for Distinguished Young Scientists Grant [11125107]
- Chinese National Programs for Fundamental Research and Development Grant [2015CB856000]
- CAS Program for Cross & Cooperative Team of the Science & Technology Innovation
- NSF [CMMI-1462408]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1462408] Funding Source: National Science Foundation
Ask authors/readers for more resources
The composite 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 minimization over a general polyhedron.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available