Solving semidefinite programming problems via alternating direction methods

被引：9
作者：
Yu, Zhensheng [1 ]
机构：
[1] Shanghai Univ Sci & Technol, Coll Sci, Shanghai 200093, Peoples R China
来源：
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS | 2006年 / 193卷 / 02期
基金：
中国国家自然科学基金;
关键词：
semidefinite programming; optimality condition; projection equation; alternating direction method;
D O I：
10.1016/j.cam.2005.07.002
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we consider an alternating direction algorithm for the solution of semidefinite programming problems (SDP). The main idea of our algorithm is that we reformulate the complementary conditions in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to make one projection and solve a linear system of equation with reduced dimension in each iterate. We prove that the generated sequence converges to the solution of the SDP under weak conditions. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：437 / 445
页数：9
相关论文
共 23 条
[1]   INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].
ALIZADEH, F .
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51
[2]   Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results [J].
Alizadeh, F ;
Haeberly, JPA ;
Overton, ML .
SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (03) :746-768
[3]  
Fortin M., 1983, AUGMENTED LAGRANGIAN
[4]  
Gabay D., 1976, Computers & Mathematics with Applications, V2, P17, DOI 10.1016/0898-1221(76)90003-1
[5]  
Glowinski R, 1984, NUMERICAL METHODS NO
[6]   Projection and contraction methods for semidefinite programming [J].
Han, QM .
APPLIED MATHEMATICS AND COMPUTATION, 1998, 95 (2-3) :275-289
[7]   A new inexact alternating directions method for monotone variational inequalities [J].
He, BS ;
Liao, LZ ;
Han, DR ;
Yang, H .
MATHEMATICAL PROGRAMMING, 2002, 92 (01) :103-118
[8]   A NEW METHOD FOR A CLASS OF LINEAR VARIATIONAL-INEQUALITIES [J].
HE, BS .
MATHEMATICAL PROGRAMMING, 1994, 66 (02) :137-144
[9]   SOLVING A CLASS OF LINEAR PROJECTION EQUATIONS [J].
HE, BS .
NUMERISCHE MATHEMATIK, 1994, 68 (01) :71-80
[10]   A modified alternating direction method for convex minimization problems [J].
He, BS ;
Zhou, J .
APPLIED MATHEMATICS LETTERS, 2000, 13 (02) :123-130
123