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

doi:10.1007/s10107-015-0939-5

	A smoothing SQP framework for a class of composite minimization over polyhedron
	Liu, Ya-Feng1 ; Ma, Shiqian 2; Dai, Yu-Hong1 ; Zhang, Shuzhong 3
	2016-07-01
发表期刊	MATHEMATICAL PROGRAMMING
ISSN	0025-5610
卷号	158 期号:1-2 页码:467-500
摘要	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.
关键词	Composite L-q minimization epsilon-KKT point Nonsmooth nonconvex non-Lipschitzian optimization Optimality condition Smoothing approximation Worst-case iteration complexity
DOI	10.1007/s10107-015-0939-5
语种	英语
资助项目	NSFC[11331012] ; NSFC[11301516] ; NSFC[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]
WOS研究方向	Computer Science ; Operations Research & Management Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000378003300016
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/22925
专题	计算数学与科学工程计算研究所
通讯作者	Liu, Ya-Feng
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, ICMSEC, LSEC, Beijing 100190, Peoples R China 2.Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Shatin, Hong Kong, Peoples R China 3.Univ Minnesota, Dept Ind & Syst Engn, Minneapolis, MN 55455 USA
推荐引用方式 GB/T 7714	Liu, Ya-Feng,Ma, Shiqian,Dai, Yu-Hong,et al. A smoothing SQP framework for a class of composite minimization over polyhedron[J]. MATHEMATICAL PROGRAMMING,2016,158(1-2):467-500.
APA	Liu, Ya-Feng,Ma, Shiqian,Dai, Yu-Hong,&Zhang, Shuzhong.(2016).A smoothing SQP framework for a class of composite minimization over polyhedron.MATHEMATICAL PROGRAMMING,158(1-2),467-500.
MLA	Liu, Ya-Feng,et al."A smoothing SQP framework for a class of composite minimization over polyhedron".MATHEMATICAL PROGRAMMING 158.1-2(2016):467-500.