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

• 成果类型: Article
• 署名作者: Liu, Ya-Feng; Ma, Shiqian; Dai, Yu-Hong; Zhang, Shuzhong
• 署名单位: Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese University of Hong Kong; University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0939-5
• 发表日期: 2016
• 页码: 467-500
• 关键词: reweighted least-squares; worst-case complexity; admission control; joint power; nonsmooth; signals; reconstruction; approximation; optimization

摘要

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.