Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/s12532-010-0017-1 | Math. Program. Comput. |
Keywords | Field | DocType |
fixed point,stable set,direct method,lagrange multiplier,quadratic program,augmented lagrangian method,augmented lagrangian | Convergence (routing),Discrete mathematics,Slack variable,Mathematical optimization,Lagrange multiplier,Orthogonality,Augmented Lagrangian method,Quadratic programming,Lagrangian relaxation,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
2 | 3-4 | 1867-2957 |
Citations | PageRank | References |
129 | 4.46 | 23 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zaiwen Wen | 1 | 934 | 40.20 |
Donald Goldfarb | 2 | 868 | 72.71 |
Wotao Yin | 3 | 5038 | 243.92 |