文章基本信息

标题：Alternating direction augmented Lagrangian methods for semidefinite programming
其他标题：Alternating direction augmented Lagrangian methods for semidefinite programming
本地全文：下载
作者：Wen, Zaiwen ; Goldfarb, Donald ; Yin, Wotao 等
期刊名称：Mathematical Programming Computation
印刷版ISSN：1867-2957
出版年度：2010
卷号：3
期号：2
页码：203-230
DOI：10.1007/mpc.v3i2.40
语种：English
出版社：Mathematical Programming Computation
摘要：We present an alternating direction dual augmented Lagrangian method for solving semidefinite programming (SDP) problems in standard form. At each iteration, our basic algorithm minimizes the augmented Lagrangian function for the dual SDP problem sequentially, first with respect to the dual variables corresponding to the linear constraints, and then with respect to the dual slack variables, while in each minimization keeping the other variables fixed, and then finally it updates the Lagrange multipliers (i.e., primal variables). Convergence is proved by using a fixed-point argument. For SDPs with inequality constraints and positivity constraints, our algorithm is extended to separately minimize the dual augmented Lagrangian function over four sets of variables. Numerical results for frequency assignment, maximum stable set and binary integer quadratic programming problems demonstrate that our algorithms are robust and very efficient due to their ability or exploit special structures, such as sparsity and constraint orthogonality in these problems.
关键词：90C06; 90C22; 90C30; 90C35