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

doi:10.1090/mcom/3104

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 计算数学与科学工程计算研究所

	A SEQUENTIAL UPDATING SCHEME OF THE LAGRANGE MULTIPLIER FOR SEPARABLE CONVEX PROGRAMMING
	Dai, Yu-Hong1 ; Han, Deren 2; Yuan, Xiaoming 3; Zhang, Wenxing 4
刊名	MATHEMATICS OF COMPUTATION
	2017
卷号	86 期号:303 页码:315-343
关键词	Convex programming augmented Lagrangian method splitting method method of multipliers image processing
ISSN号	0025-5718
DOI	10.1090/mcom/3104
英文摘要	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.
资助项目	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
语种	英语
出版者	AMER MATHEMATICAL SOC
WOS记录号	WOS:000391543900010
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/24469]
专题	计算数学与科学工程计算研究所
通讯作者	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.