A SEQUENTIAL UPDATING SCHEME OF THE LAGRANGE MULTIPLIER FOR SEPARABLE CONVEX PROGRAMMING

doi:10.1090/mcom/3104

	A SEQUENTIAL UPDATING SCHEME OF THE LAGRANGE MULTIPLIER FOR SEPARABLE CONVEX PROGRAMMING
	Dai, Yu-Hong1 ; Han, Deren 2; Yuan, Xiaoming 3; Zhang, Wenxing 4
	2017
发表期刊	MATHEMATICS OF COMPUTATION
ISSN	0025-5718
卷号	86 期号:303 页码:315-343
摘要	The augmented Lagrangian method (ALM) is a benchmark for solving convex minimization problems with linear constraints. Solving the augmented subproblems over the primal variables can be regarded as sequentially providing inputs for updating the Lagrange multiplier (i.e., the dual variable). We consider the separable case of a convex minimization problem where its objective function is the sum of more than two functions without coupled variables. When applying the ALM to this case, at each iteration we can (sometimes must) split the resulting augmented subproblem in order to generate decomposed subproblems which are often easy enough to have closed-form solutions. But the decomposition of primal variables only provides less accurate inputs for updating the Lagrange multiplier, and it points out the lack of convergence for such a decomposition scheme. To remedy this difficulty, we propose to update the Lagrange multiplier sequentially once each decomposed subproblem over the primal variables is solved. This scheme updates both the primal and dual variables in Gauss- Seidel fashion. In addition to the exact version which is useful enough for the case where the functions in the objective are all simple such that the decomposed subproblems all have closed- form solutions, we investigate an inexact version of this scheme which allows the decomposed subproblems to be solved approximately subject to certain inexactness criteria. Some preliminary numerical results when the proposed scheme is respectively applied to an image decomposition problem and an allocation problem are reported.
关键词	Convex programming augmented Lagrangian method splitting method method of multipliers image processing
DOI	10.1090/mcom/3104
语种	英语
资助项目	China National Funds for Distinguished Young Scientists Grant[11125107] ; Key Project of Chinese National Programs for Fundamental Research and Development Grant[2015CB856000] ; NSFC[11331012] ; NSFC[11371197] ; NSFC[11431002] ; NSFC[11301055] ; CAS Program for Cross & Cooperative Team of the Science & Technology Innovation ; PAPD of Jiangsu Higher Education Institutions ; General Research Fund of Hong Kong[HKBU203613]
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000391543900010
出版者	AMER MATHEMATICAL SOC
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/24470
专题	计算数学与科学工程计算研究所
通讯作者	Dai, Yu-Hong
作者单位	1.Chinese Acad Sci, Inst Computat Math, LSEC, POB 2719, Beijing 100190, Peoples R China 2.Nanjing Normal Univ, Jiangsu Key Lab NSLSCS, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China 3.Hong Kong Baptist Univ, Dept Math, Kowloon, Hong Kong, Peoples R China 4.Univ Elect Sci & Technol China, Sch Math Sci, Chengdu 611731, Peoples R China
推荐引用方式 GB/T 7714	Dai, Yu-Hong,Han, Deren,Yuan, Xiaoming,et al. A SEQUENTIAL UPDATING SCHEME OF THE LAGRANGE MULTIPLIER FOR SEPARABLE CONVEX PROGRAMMING[J]. MATHEMATICS OF COMPUTATION,2017,86(303):315-343.
APA	Dai, Yu-Hong,Han, Deren,Yuan, Xiaoming,&Zhang, Wenxing.(2017).A SEQUENTIAL UPDATING SCHEME OF THE LAGRANGE MULTIPLIER FOR SEPARABLE CONVEX PROGRAMMING.MATHEMATICS OF COMPUTATION,86(303),315-343.
MLA	Dai, Yu-Hong,et al."A SEQUENTIAL UPDATING SCHEME OF THE LAGRANGE MULTIPLIER FOR SEPARABLE CONVEX PROGRAMMING".MATHEMATICS OF COMPUTATION 86.303(2017):315-343.