Alternating direction augmented Lagrangian methods for semidefinite programming
Alternating direction augmented Lagrangian methods for semidefinite programming
复制标题
DOI：
10.1007/s12532-010-0017-1
复制
发表时间：
2010-09
影响因子：
6.3
通讯作者：
Zaiwen Wen;D. Goldfarb;W. Yin
中科院分区：
文献类型：
--
作者：
Zaiwen Wen;D. Goldfarb;W. Yin
提出了一种求解标准形式半定规划问题的交替方向对偶增广拉格朗日方法。在每次迭代中，我们的基本算法顺序地最小化对偶SDP问题的增广拉格朗日函数，首先相对于与线性约束对应的对偶变量，然后相对于对偶松弛变量，而在每次最小化中保持其他变量固定，然后最后更新拉格朗日乘子（即，原始变量）。收敛性是通过使用一个不动点参数证明。对于具有不等式约束和正性约束的SDPs，我们的算法被扩展到分别最小化四组变量上的对偶增广拉格朗日函数。频率分配，最大稳定集和二进制整数二次规划问题的数值结果表明，我们的算法是强大的，非常有效的，由于他们的能力或利用特殊的结构，如稀疏性和约束正交性在这些问题。
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.