# A Novel Approach for Solving Semidefinite Programs

Authors: Hong-Wei Jiao; Ya-Kui Huang; Jing Chen
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

A novel linearizing alternating direction augmented Lagrangian approach is proposed for effectively solving semidefinite programs (SDP). For every iteration, by fixing the other variables, the proposed approach alternatively optimizes the dual variables and the dual slack variables; then the primal variables, that is, Lagrange multipliers, are updated. In addition, the proposed approach renews all the variables in closed forms without solving any system of linear equations. Global convergence of the proposed approach is proved under mild conditions, and two numerical problems are given to demonstrate the effectiveness of the presented approach.


---

## Body

## 1. Introduction

Minimizing a linear function of a symmetric positive semidefinite matrix subject to linear equality constraints is called semidefinite programs (SDP), whose form can be given as follows:(1)
min
⁡
〈
C
,
X
〉
s
.
t
.
A
(
X
)
=
b
,
X
⪰
0
,
where A
:
S
n
→
R
m is a linear operator, which can be expressed as
(2)
A
(
X
)
∶
=
(
〈
A
1
,
X
〉
,
…
,
〈
A
m
,
X
〉
)
T
.
C
,
A
i
∈
S
n
,
i
=
1
,
…
,
m, are all matrices, and b
∈
R
m is a vector, and X
⪰
0 stands for the fact that X is a symmetric positive semidefinite matrix. Here, S
n stands for the space of n
×
n symmetric matrices and 〈
X
,
Y
〉
=
trace
(
X
Y
) stands for the standard inner product in S
n. A
*
(
y
)
∶
=
∑
i
=
1
m
y
i
A
i stands for the adjoint operator A
*
:
R
m
→
S
n of A. The dual problem of (1) is
(3)
min
⁡
-
b
T
y
s
.
t
.
A
*
(
y
)
+
S
=
C
,
S
⪰
0
,
where y
∈
R
m and S
∈
S
n.SDP problem has been always a very active area in optimization research for many years. It has broad applications in many areas, for example, system and control theory [1], combinatorial optimization [2], nonconvex quadratic programs [3], and matrix completion problems [4]. We refer to the reference book [5] for theory and applications of SDP. Interior point approaches (IPMs) have been very successful for solving SDP in polynomial time [6–9]. For small and medium sized SDP problems such as n
≤
1,000 and m
≤
10,000, IPMs are generally efficient and robust. However, for large-scale SDP problems with large m and moderate n, IPMs become very slow due to the need of computing and factorizing the m
×
m Schur complement matrix. In order to improve this shortcoming, by using an iterative solver to compute a search direction at each iteration, [10, 11] proposed inexact IPMs which manage to solve certain types of SDP problems with m up to 125,000. Based on the augmented Lagrangian approach, many variants for SDP were proposed. For example, [12] introduced the so-called boundary point approach; using an eigenvalue decomposition to maintain complementarity, [13] presented a dual augmented Lagrangian approach. More recently, Huang and Xu [14] proposed a trust region algorithm for SDP problems by performing a number of conjugate gradient iterations to solve the subproblems. Zhao et al. [15] designed a Newton-CG augmented Lagrangian approach for solving SDP problems from the perspective of approximate semismooth Newton methods. Wen et al. [16] presented an alternating direction dual augmented Lagrangian approach for SDP. In [17], Wen et al. proposed a row-by-row approach for solving SDP problems based on solving a sequence of problems obtained by restricting the n-dimensional positive semidefinite constraint on the matrix X. In addition to the former reviewed methods, some related research works on the subject are given as follows. Xu et al. [18] presented a new algorithm for the box-constrained SDP based on the feasible direction method. Zhadan and Orlov [19] presented a dual interior point method for linear SDP problem. Lin [20] proposed an inexact spectral bundle method for convex quadratic SDP. Sun and Zhang [21] proposed a modified alternating direction method for solving convex quadratically constrained quadratic SDP, which requires much less computational effort per iteration than the second-order approaches. In [22], the authors presented penalty and barrier methods for convex SDP. In [23], an alternating direction method is proposed for solving convex SDP problems by Zhang et al., which only computes several metric projections at each iteration. In [24], Huang et al. presented a lower-order penalization approach to solve nonlinear SDP. In [25], Aroztegui et al. presented a feasible direction interior point algorithm for solving nonlinear SDP. Yang and Yu [26] proposed a homotopy method for nonlinear SDP. Kanzow et al. [27] presented successive linearization methods for solving nonlinear SDP. Yamashita et al. [28] presented a primal-dual interior point method for nonlinear SDP. Lu et al. [29] presented a saddle point mirror-prox algorithm for solving a large-scale SDP. In [30], Monteiro et al. presented a first-order block-decomposition method for solving two-easy-block structured SDP. In [31], an efficient low-rank stochastic gradient descent method is proposed for solving a class of SDP problems, which has clear computational advantages over the standard stochastic gradient descent method. Based on a new technique for finding the search direction and the strategy of the central path, Wang and Bai [32] presented a new primal-dual path-following interior-point algorithm for solving SDP problem. By reformulating the complementary conditions in the primal-dual optimality conditions as a projection equation, Yu [33] presented an alternating direction algorithm for the solution of SDP problems. However, most of these existing methods need to solve a system of linear equations for updating the variables which is time consuming especially for the large-scale case.In this paper, we present a novel linearizing alternating direction dual augmented Lagrangian approach for computing SDP problems. For every iteration, the proposed algorithm works on the augmented Lagrangian function for the dual SDP problem. Specially, for every iteration, by fixing the other variables the proposed algorithm alternatively optimizes the dual variables and the dual slack variables; then the primal variables, that is, Lagrange multipliers, are updated. The proposed algorithm is closely related to the alternating direction augmented Lagrangian approach in [16] but for updating the dual variables. In particular, the proposed algorithm renews the dual variables without solving any system of linear equations. Moreover, the proposed algorithm renews all the variables in closed forms. Numerical experimental results demonstrate that the performance of the proposed approach can be significantly better than that reported in [16].The remaining section of this paper is described as follows. In Section2 a novel linearizing alternating direction augmented Lagrangian approach is proposed for solving SDP problems. The convergence of the proposed approach is proved in Section 3. In Section 4, some implementation issues of the proposed approach are discussed. Two numerical examples for frequency assignment problem and binary integer quadratic programs problems are used to demonstrate the performance of the proposed approach in Section 5.Some notations:S
+
n represents the set of n
×
n symmetric positive semidefinite matrices. X
≻
0 represents the fact that X is positive definite. The notation ∥
·
∥ stands for the Euclidean norm and ∥
·
∥
F stands for the Frobenius norm. vec
⁡
(
X
) denotes a vector obtained by stacking X’s columns one by one. I denotes the identity matrix in proper order.


## 2. Linearizing Alternating Direction Augmented Lagrangian Approach

In this section, a linearizing alternating direction augmented Lagrangian approach is proposed for solving (1) and (3).LetA
∶
=
(
vec
⁡
(
A
1
)
,
…
,
vec
⁡
(
A
m
)
)
T
∈
R
m
×
n
2. The expression A
(
X
)
=
b is equal to A
vec
⁡
(
X
)
=
b. A
(
A
*
(
y
)
)
=
A
A
T
y is called an operator A
A
*
:
R
m
→
R
m.Without loss of generality, we assume that matrixA is a full row rank and there exists a matrix X
~
≻
0 such that A
(
X
~
)
=
b. It is well known that, with the above assumption, a point (
X
,
y
,
S
) is optimal for SDP problems (1) and (3) if and only if
(4)
A
(
X
)
=
b
,
A
*
(
y
)
+
S
=
C
,
X
S
=
0
,
X
⪰
0
,
S
⪰
0
.Given a penalty parameterμ
>
0, the augmented Lagrangian function for the dual SDP (3) is defined as
(5)
L
μ
(
X
,
y
,
S
)
∶
=
-
b
T
y
+
〈
X
,
A
*
(
y
)
+
S
-
C
〉
+
1
2
μ
∥
A
*
(
y
)
+
S
-
C
∥
F
2
,
where X
∈
S
n. For given X
0
,
S
0
∈
S
n, the alternating direction augmented Lagrangian approach for solving problems (1) and (3) generates sequences {
y
k
}
⊂
R
m, {
S
k
}
⊂
S
n, and {
X
k
}
⊂
S
n as follows:
(6)
y
k
+
1
=
arg
min
⁡
y
∈
R
m
L
μ
(
X
k
,
y
,
S
k
)
,
(7)
S
k
+
1
=
arg
min
⁡
S
∈
S
n
L
μ
(
X
k
,
y
k
+
1
,
S
)
,
S
⪰
0
,
(8)
X
k
+
1
=
X
k
+
A
*
(
y
k
+
1
)
+
S
k
+
1
-
C
μ
.Apparently, we can obtainy
k
+
1 by solving the first-order optimality conditions for (6), which is a system of linear equations associated with A
A
T. Since A
A
T is a m
×
m matrix, it is difficult to get y
k
+
1 exactly when m is large. In order to alleviate this difficulty, we use the quadratic approximation of L
μ
(
X
k
,
y
,
S
k
) in (6) around y
kas follows:
(9)
L
μ
(
X
k
,
y
,
S
k
)
≈
L
μ
(
X
k
,
y
k
,
S
k
)
+
〈
g
k
,
y
-
y
k
〉
+
λ
k
2
μ
∥
y
-
y
k
∥
2
,
where λ
k
>
0 and
(10)
g
k
=
∇
y
L
μ
(
X
k
,
y
k
,
S
k
)
=
A
(
X
k
)
-
b
+
1
μ
A
(
A
*
(
y
k
)
+
S
k
-
C
)
.
We replace step (6) by
(11)
y
k
+
1
=
arg
min
⁡
y
∈
R
m
〈
g
k
,
y
-
y
k
〉
+
λ
k
2
μ
∥
y
-
y
k
∥
2
.
Then, we have
(12)
y
k
+
1
=
y
k
-
μ
λ
k
g
k
.As pointed out in [16], problem (7) is equivalent to
(13)
min
⁡
S
∈
S
n
∥
S
-
V
k
+
1
∥
F
2
,
S
⪰
0
,
where V
k
+
1
=
C
-
A
*
(
y
k
+
1
)
-
μ
X
k. Denote the spectral decomposition of the matrix V
k
+
1 by
(14)
Q
Σ
Q
T
=
(
Q
1
Q
2
)
(
Σ
+
0
0
Σ
-
)
(
Q
1
T
Q
2
T
)
,
where Σ
+ and Σ
- are the nonnegative and negative eigenvalues of V
k
+
1. We then obtain the fact that S
k
+
1
=
V
+
k
+
1
=
Q
1
Σ
+
Q
1. It follows from (8) that
(15)
X
k
+
1
=
X
k
+
A
*
(
y
k
+
1
)
+
S
k
+
1
-
C
μ
=
1
μ
(
S
k
+
1
-
V
k
+
1
)
=
1
μ
V
-
k
+
1
,
where V
-
k
+
1
=
-
Q
2
Σ
-
Q
2. Now we present the linearizing alternating direction augmented Lagrangian approach in Algorithm 1.Algorithm 1:Linearizing alternating direction augmented Lagrangian algorithm for SDP.
Initializey
0
∈
R
m, X
0
⪰
0, and S
0
⪰
0. Choose initial step size λ
0 greater than the
maximum eigenvalue of the matrixA
A
T.
For  k
=
0,1, … do
Computeg
k and y
k
+
1
=
y
k
-
μ
/
λ
_
k
g
k.
ComputeV
k
+
1 and its eigenvalue decomposition, and set S
k
+
1
=
V
+
k
+
1.
ComputeX
k
+
1
=
1
/
μ
(
S
k
+
1
-
V
k
+
1
).
Chooseλ
k
+
1 greater than the maximum eigenvalue of the matrix A
A
T.
endRemark 1.
We can chooseλ
k
+
1
=
∥
A
A
T
∥
F to satisfy the condition of Algorithm 1. If A
A
*
=
I and λ
k
=
1 for all k
≥
0, then Algorithm 1 is same as the approach proposed in [16].


## 3. The Convergence of the Proposed Approach

In this section, we prove the convergence of Algorithm1 using the argument similar to the one in [34]. Let R
d
k
=
A
*
(
y
k
)
+
S
k
-
C; then we have the following proposition.Lemma 2.
Letw
k
=
(
X
k
,
y
k
,
S
k
) be generated by Algorithm 1 and let w
*
=
(
X
*
,
y
*
,
S
*
) be an optimal solution of (1) and (3); then one has
(16)
∥
w
k
-
w
*
∥
H
μ
2
-
∥
w
k
+
1
-
w
*
∥
H
μ
2
≥
∥
w
k
-
w
k
+
1
∥
H
μ
2
,
where
(17)
H
μ
=
(


μ
I
0
0
0
1
μ
(
λ
k
I
-
A
A
T
)
0
0
0
1
μ
I



)
,
∥
w
∥
H
2
=
〈
w
,
H
w
〉
.Proof.
From (8), there holds
(18)
〈
X
k
+
1
-
X
*
,
μ
(
X
k
-
X
k
+
1
)
〉
=
〈
X
*
-
X
k
+
1
,
R
d
k
+
1
〉
.
By (12), we know that
(19)
〈
y
*
-
y
k
+
1
,
g
k
+
λ
k
μ
(
y
k
+
1
-
y
k
)
〉
=
0
.
That is,
(20)
〈
y
*
-
y
k
+
1
,
A
(
X
k
)
-
b
+
1
μ
A
(
R
d
k
)
+
λ
k
μ
(
y
k
+
1
-
y
k
)
〉
=
0
.
By substituting (8) into the above equality, using the fact A
(
X
*
)
=
b, and rearranging the terms, one has
(21)
〈
y
k
+
1
-
y
*
,
1
μ
(
λ
k
I
-
A
A
*
)
(
y
k
-
y
k
+
1
)
〉
=
〈
A
*
(
y
k
+
1
-
y
*
)
,
X
k
+
1
-
X
*
〉
+
〈
A
*
(
y
k
+
1
-
y
*
)
,
1
μ
(
S
k
-
S
k
+
1
)
〉
.
Since X
k
+
1
S
k
+
1
=
0, we have
(22)
〈
S
-
S
k
+
1
,
X
k
+
1
〉
≥
0
,
∀
S
∈
S
+
n
.
By substituting S
=
S
* into (22), we get
(23)
〈
S
k
+
1
-
S
*
,
1
μ
(
S
k
-
S
k
+
1
)
〉
≥
〈
S
k
+
1
-
S
*
,
X
k
+
1
+
1
μ
(
S
k
-
S
k
+
1
)
〉
.
By adding (18), (21), and (23) together, we obtain
(24)
〈
w
k
+
1
-
w
*
,
H
μ
(
w
k
-
w
k
+
1
)
〉
≥
〈
X
*
-
X
k
+
1
,
R
d
k
+
1
〉
+
〈
A
*
(
y
k
+
1
-
y
*
)
,
X
k
+
1
-
X
*
〉
+
〈
A
*
(
y
k
+
1
-
y
*
)
,
1
μ
(
S
k
-
S
k
+
1
)
〉
+
〈
S
k
+
1
-
S
*
,
X
k
+
1
〉
+
〈
S
k
+
1
-
S
*
,
1
μ
(
S
k
-
S
k
+
1
)
〉
=
〈
X
*
-
X
k
+
1
,
S
k
+
1
-
S
*
〉
+
〈
S
k
-
S
k
+
1
,
1
μ
R
d
k
+
1
〉
+
〈
S
k
+
1
-
S
*
,
X
k
+
1
〉
=
〈
X
*
,
S
k
+
1
-
S
*
〉
+
〈
S
k
-
S
k
+
1
,
1
μ
R
d
k
+
1
〉
≥
〈
X
*
,
S
k
+
1
〉
-
〈
S
k
-
S
k
+
1
,
X
k
〉
=
〈
X
*
,
S
k
+
1
〉
+
〈
S
k
+
1
,
X
k
〉
,
where the last inequality comes from (8) and (22). Note that X
k, S
k
+
1, and X
* are semidefinite positive matrices; then
(25)
〈
w
k
+
1
-
w
*
,
H
μ
(
w
k
-
w
k
+
1
)
〉
≥
0
.
It follows (25) that
(26)
〈
w
k
-
w
*
,
H
μ
(
w
k
-
w
k
+
1
)
〉
=
〈
w
k
+
1
-
w
*
,
H
μ
(
w
k
-
w
k
+
1
)
〉
+
∥
w
k
-
w
k
+
1
∥
H
μ
2
≥
∥
w
k
-
w
k
+
1
∥
H
μ
2
.
By (26) and the fact that
(27)
∥
w
k
-
w
*
∥
H
μ
2
-
∥
w
k
+
1
-
w
*
∥
H
μ
2
=
2
〈
w
k
-
w
*
,
w
k
-
w
k
+
1
〉
-
∥
w
k
-
w
k
+
1
∥
H
μ
2
,
we have
(28)
∥
w
k
-
w
*
∥
H
μ
2
-
∥
w
k
+
1
-
w
*
∥
H
μ
2
≥
∥
w
k
-
w
k
+
1
∥
H
μ
2
,
which completes the proof.Theorem 3.
Let{
(
X
k
,
y
k
,
S
k
)
} be generated by Algorithm 1; then it converges to a solution of problems (1) and (3).Proof.
By (16), we know that the sequence {
w
k
} is bounded and the sequence {
∥
w
k
-
w
*
∥
H
μ
2

} is monotonically nonincreasing. Therefore,
(29)
lim
⁡
k
→
∞
∥
w
k
-
w
*
∥
H
μ
2
=
∥
w
¯
-
w
*
∥
H
μ
2
,
where w
¯
=
(
X
¯
,
y
¯
,
S
¯
) can be any limit point of {
w
k
}. It follows that
(30)
lim
⁡
k
→
∞
∥
w
k
-
w
k
+
1
∥
H
μ
2
=
0
.
Since λ
k are greater than the maximum eigenvalue of matrix A
A
T, then the matrix H
μ is positive definite. By the definition of w
k, we obtain
(31)
lim
⁡
k
→
∞
∥
X
k
-
X
k
+
1
∥
F
=
0
,
lim
⁡
k
→
∞
∥
y
k
-
y
k
+
1
∥
=
0
,
lim
⁡
k
→
∞
∥
S
k
-
S
k
+
1
∥
F
=
0
.
From the update formula (8), we have
(32)
lim
⁡
k
→
∞
∥
A
*
(
y
k
)
+
S
k
-
C
∥
F
=
0
.
By (12) and the definition of g
k, one has
(33)
lim
⁡
k
→
∞
∥
g
k
∥
=
∥
A
(
X
k
)
-
b
+
1
μ
A
(
A
*
(
y
k
)
+
S
k
-
C
)
∥
=
0
,
which together with (32) imply that
(34)
lim
⁡
k
→
∞
∥
A
(
X
k
)
-
b
∥
=
0
.
By combining (32), (34), X
k
S
k
=
0, and X
k
,
S
k
⪰
0 for all k
≥
1, we know that any limit point of {
w
k
}, say w
¯
=
(
X
¯
,
y
¯
,
S
¯
), satisfies
(35)
A
(
X
¯
)
=
b
,
A
*
(
y
¯
)
+
S
¯
-
C
=
0
,
X
¯
S
¯
=
0
,
X
¯
⪰
0
,
S
¯
⪰
0
,
which means w
¯ is a solution of problems (1) and (3). By Lemma 2, {
(
X
k
,
y
k
,
S
k
)
} converges to a solution of problems (1) and (3).


## 4. Implementation Issues

The proposed algorithm is carried out by modifying the code of the alternating direction approach in [16] which is referred to as SDPAD. Before presenting the numerical results, we discuss some implementation issues of Algorithm 1 in this section.In order to improve the computational performance of Algorithm1, using the similar method as many alternating direction approaches [35–37], we replace step (8) by
(36)
X
k
+
1
∶
=
X
k
+
ρ
A
*
(
y
k
+
1
)
+
S
k
+
1
-
C
μ
∶
=
(
1
-
ρ
)
X
k
+
ρ
μ
(
S
k
+
1
-
V
k
+
1
)
.
We can use an argument similar method to the one in [34] to prove the following theorem.Theorem 4.
LetA
λ
k
=
λ
k
I
-
A
A
T  (
X
*
,
y
*
,
S
*
) be an optimal solution of (1) and (3). For ρ
∈
(
0,1
], it holds that
(37)
∥
X
k
-
X
*
∥
F
2
+
ρ
μ
∥
y
k
-
y
*
∥
A
λ
k
2
+
ρ
μ
2
∥
S
k
-
S
*
∥
F
2
+
ρ
(
1
-
ρ
)
μ
2
∥
R
d
k
∥
F
2
≥
(
ρ
(
1
-
ρ
)
μ
2

∥
X
k
+
1
-
X
*
∥
F
2
+
ρ
μ
∥
y
k
+
1
-
y
*
∥
A
λ
k
2
+
ρ
μ
2
∥
S
k
+
1
-
S
*
∥
F
2
+
ρ
(
1
-
ρ
)
μ
2
∥
R
d
k
+
1
∥
F
2
)
+
ρ
μ
∥
y
k
-
y
k
+
1
∥
A
λ
k
2
+
ρ
μ
2
∥
R
d
k
+
1
∥
F
2
+
ρ
2
μ
2
∥
S
k
-
S
k
+
1
∥
F
2
.
For ρ
∈
(
1
,
(
1
+
5
)
/
2
), it holds that
(38)
∥
X
k
-
X
*
∥
F
2
+
ρ
μ
∥
y
k
-
y
*
∥
A
λ
k
2
+
ρ
μ
2
∥
S
k
-
S
*
∥
F
2
+
ρ
-
1
μ
2
∥
R
d
k
∥
F
2
≥
(
ρ
-
1
μ
2
∥
X
k
+
1
-
X
*
∥
F
2
+
ρ
μ
∥
y
k
+
1
-
y
*
∥
A
λ
k
2
+
ρ
μ
2
∥
S
k
+
1
-
S
*
∥
F
2
+
ρ
-
1
μ
2
∥
R
d
k
+
1
∥
F
2
)
+
ρ
μ
∥
y
k
-
y
k
+
1
∥
A
λ
k
2
+
1
+
ρ
-
ρ
2
ρ
(
ρ
μ
2
∥
R
d
k
+
1
∥
F
2
+
ρ
2
μ
2
∥
S
k
-
S
k
+
1
∥
F
2
)
.Based on Theorem4, it is not difficult to show that
(39)
lim
⁡
k
→
∞
∥
A
*
(
y
k
)
+
S
k
-
C
∥
F
=
0
,
lim
⁡
k
→
∞
∥
A
(
X
k
)
-
b
∥
=
0
,
lim
⁡
k
→
∞
∥
X
k
S
k
∥
F
=
0
.In our numerical experiments, we stop the algorithm when(40)
max
⁡
{
pinf
,
dinf
,
gap
⁡
}
≤
1
0
-
6
,
where
(41)
pinf
=
A
(
X
)
-
b
1
+
∥
b
∥
,
dinf
=
C
+
S
-
A
*
(
y
)
1
+
∥
C
∥
F
,
gap
⁡
=
|
b
T
y
-
〈
C
,
X
〉
|
1
+
|
〈
C
,
X
〉
|
+
|
b
T
y
|
.
We set the maximum number of iterations allowed in Algorithm 1 and SDPAD to 20,000.We use the same strategy for updating the parameterμ
>
0 SDPAD (beta 2). In particular, given some integer h
>
0, let
(42)
pvd
(
k
)
=
e
∑
j
=
k
-
h
+
1
k
ln
⁡
(
pinf
(
j
)
/
dinf
(
j
)
)
/
h
,
dvp
(
k
)
=
e
∑
j
=
k
-
h
+
1
k
ln
⁡
(
dinf
(
j
)
/
pinf
(
j
)
)
/
h
.
For k
=
h
,
2
h
,
…, if pvd
(
k
)
>
η, then set μ
=
max
⁡
{
min
⁡
{
μ
/
γ
,
μ
max
⁡
}
,
μ
min
⁡
}. Otherwise, if dvp
(
k
)
>
η, then set μ
=
max
⁡
{
min
⁡
{
γ
μ
,
μ
max
⁡
}
,
μ
min
⁡
}. Here 0
<
μ
min
⁡
<
μ
max
⁡
<
∞.We setμ
min
⁡
=
1
0
-
2,  μ
max
⁡
=
1
0
2,  γ
=
0.75, and η
=
1.5 for our test problems. The parameter ρ for updating X is set to 1.618. We choose the initial iterate y
0
=
0,  X
0
=
I, and S
0
=
0.Letf
(
y
,
S
)
=
(
1
/
2
)
∥
A
*
(
y
)
+
S
-
C
∥
F
2. Since the other parts of L
μ are linear, the choice of λ
k is mainly depending on f
(
y
,
S
). We set λ
0
=
∥
A
A
T
∥
F and choose λ
k
+
1 as the Barzilai-Borwein step size [38] of f
(
y
,
S
) with the following safeguard:
(43)
λ
k
+
1
=
{
∥
A
A
T
∥
F
,
if
p
k
T
z
k
≤
0
,
max
⁡
⁡
{
∥
z
k
∥
2
p
k
T
z
k
,
∥
A
A
T
∥
F
}
,
otherwise
,
where p
k
=
y
k
+
1
-
y
k, and z
k
=
∇
y
f
(
y
k
+
1
,
S
k
+
1
)
-
∇
y
f
(
y
k
,
S
k
). Clearly, this choice of λ
k ensures that the matrix λ
k
I
-
A
A
T is positive definite for any k
≥
1.


## 5. Numerical Results

In this section, we report our numerical results. We compare solutions obtained from Algorithm1 and SDPAD on the SDP relaxations of frequency assignment problems and binary integer quadratic programs problems. All the procedures were carried out by MATLAB 2011b on a 3.10 GHz Core i5 PC with 4 GB of RAM under Windows 7.In Tables1 and 2, the first column gives the problem name; some notations have been also used in column headers, n: the size of the matrix X;  m: the total number of equality and inequality constraints; “itr”: the number of iterations; “cpu”: the CPU time in the format of “hours, minutes, and seconds.”Table 1
Numerical results compared with [16] for computing frequency assignment problems.
Name
n
m
Algorithm1 in this paper
SDPAD
pinf
dinf
gap
itr
cpu
pinf
dinf
gap
itr
cpu
fap01
52
1378
9.34
e
-
7
2.47
e
-
7
4.71
e
-
5
622
1.13
9.77
e
-
7
1.22
e
-
7
5.61
e
-
5
653
0.67
fap02
61
1866
9.39
e
-
7
9.01
e
-
7
5.84
e
-
5
1399
1.67
9.98
e
-
7
8.92
e
-
7
7.27
e
-
5
1720
1.83
fap03
65
2145
7.54
e
-
7
4.75
e
-
7
5.82
e
-
6
914
1.06
9.84
e
-
7
4.88
e
-
7
3.97
e
-
5
870
0.98
fap04
81
3321
9.55
e
-
7
9.97
e
-
7
4.44
e
-
5
852
1.70
9.54
e
-
7
9.96
e
-
7
4.45
e
-
5
874
1.71
fap05
84
3570
9.83
e
-
7
8.53
e
-
7
3.68
e
-
6
1155
2.38
9.98
e
-
7
8.29
e
-
7
4.27
e
-
6
1198
2.37
fap06
93
4371
9.93
e
-
7
6.44
e
-
7
3.19
e
-
6
653
1.48
9.89
e
-
7
6.45
e
-
7
3.40
e
-
6
653
1.46
fap07
98
4851
9.97
e
-
7
8.44
e
-
7
1.00
e
-
5
648
1.50
9.99
e
-
7
8.20
e
-
7
9.76
e
-
6
667
1.52
fap08
120
7260
6.65
e
-
7
9.98
e
-
7
2.58
e
-
6
725
2.51
6.63
e
-
7
9.96
e
-
7
2.57
e
-
6
725
2.46
fap09
174
15225
9.98
e
-
7
4.34
e
-
7
8.42
e
-
7
438
3.05
9.90
e
-
7
3.04
e
-
7
1.02
e
-
6
464
3.17
fap10
183
14479
8.33
e
-
7
1.00
e
-
6
1.14
e
-
4
2278
21.55
9.17
e
-
7
1.00
e
-
6
1.29
e
-
4
2313
21.87
fap11
252
24292
9.60
e
-
7
9.99
e
-
7
2.53
e
-
4
2462
52.68
9.65
e
-
7
1.00
e
-
6
2.16
e
-
4
2585
54.54
fap12
369
26462
9.06
e
-
7
9.99
e
-
7
2.40
e
-
4
3197
2 : 28
7.61
e
-
7
1.00
e
-
6
2.20
e
-
4
3394
2 : 35
fap25
2118
322924
8.85
e
-
7
1.00
e
-
6
1.13
e
-
4
5152
7 : 54 : 54
1.00
e
-
6
9.67
e
-
7
1.13
e
-
4
5495
8 : 20 : 12
fap36
4110
1154467
9.93
e
-
7
9.78
e
-
7
3.08
e
-
5
4256
47 : 54 : 26
1.38
e
-
6
1.26
e
-
7
1.68
e
-
5
5000
116 : 28 : 06Table 2
Numerical results compared with [16] for computing binary integer quadratic programs problem.
Name
n
Algorithm1 in this paper
SDPAD
pinf
dinf
gap
itr
cpu
pinf
dinf
gap
itr
cpu
be100.1
101
9.37
e
-
7
9.96
e
-
7
5.52
e
-
7
1464
3.76
9.70
e
-
7
8.82
e
-
7
4.96
e
-
7
2012
4.79
be100.2
101
5.19
e
-
7
9.95
e
-
7
2.89
e
-
7
1322
3.24
1.00
e
-
6
9.05
e
-
7
2.81
e
-
7
1744
4.24
be120.3.1
121
9.96
e
-
7
8.66
e
-
7
5.77
e
-
7
2214
6.82
9.82
e
-
7
9.99
e
-
7
7.08
e
-
7
2447
7.45
be120.3.2
121
7.33
e
-
7
9.72
e
-
7
8.85
e
-
7
1968
6.20
8.60
e
-
7
9.99
e
-
7
1.08
e
-
6
2405
7.53
be120.8.1
121
9.95
e
-
7
9.99
e
-
7
7.24
e
-
7
1618
4.78
9.99
e
-
7
7.73
e
-
7
8.24
e
-
7
2006
5.87
be120.8.2
121
9.31
e
-
7
9.10
e
-
7
4.26
e
-
7
3033
9.56
5.63
e
-
7
1.00
e
-
6
9.99
e
-
7
3415
10.64
be150.3.1
151
4.33
e
-
7
9.96
e
-
7
8.89
e
-
7
2030
9.08
8.36
e
-
7
9.96
e
-
7
3.23
e
-
7
2557
11.36
be150.3.2
151
9.94
e
-
7
8.58
e
-
7
3.97
e
-
7
2244
10.16
9.45
e
-
7
9.98
e
-
7
5.42
e
-
7
3143
14.01
be150.8.1
151
9.85
e
-
7
8.08
e
-
7
3.84
e
-
7
1694
7.33
9.97
e
-
7
9.38
e
-
7
1.40
e
-
7
2255
9.63
be150.8.2
151
9.40
e
-
7
9.72
e
-
7
8.63
e
-
7
1829
8.10
9.98
e
-
7
7.46
e
-
7
6.61
e
-
7
2386
10.28
be200.3.1
201
5.48
e
-
7
9.97
e
-
7
9.56
e
-
7
2031
13.90
9.05
e
-
7
9.99
e
-
7
1.22
e
-
6
2840
19.19
be200.3.2
201
9.79
e
-
7
9.77
e
-
7
5.43
e
-
7
2254
16.03
8.03
e
-
7
9.99
e
-
7
5.73
e
-
7
3276
23.20
be200.8.1
201
5.64
e
-
7
9.98
e
-
7
6.72
e
-
7
3068
21.90
9.98
e
-
7
6.61
e
-
7
4.54
e
-
7
4154
29.47
be200.8.2
201
9.07
e
-
7
9.59
e
-
7
5.35
e
-
7
1817
11.98
7.72
e
-
7
9.98
e
-
7
4.65
e
-
7
2918
19.11
be250.1
251
8.78
e
-
7
9.90
e
-
7
4.90
e
-
7
3638
36.27
1.00
e
-
6
9.76
e
-
7
5.54
e
-
7
5336
52.52
be250.2
251
8.06
e
-
7
9.94
e
-
7
8.81
e
-
7
3280
32.22
9.99
e
-
7
7.95
e
-
7
5.36
e
-
7
5111
49.91
bqp50-1
51
9.65
e
-
7
9.57
e
-
7
1.21
e
-
7
3334
3.73
1.00
e
-
6
5.76
e
-
7
5.36
e
-
7
2800
3.08
bqp50-2
51
6.80
e
-
7
9.92
e
-
7
7.91
e
-
7
4278
4.15
1.00
e
-
6
6.85
e
-
7
4.32
e
-
7
6975
6.60
bqp100-1
101
5.06
e
-
7
9.96
e
-
7
3.33
e
-
7
1558
3.58
9.18
e
-
7
9.98
e
-
7
5.16
e
-
7
1917
4.32
bqp100-2
101
6.78
e
-
7
1.00
e
-
6
7.25
e
-
7
2887
6.43
9.99
e
-
7
9.57
e
-
7
6.68
e
-
7
3438
7.56
bqp250-1
251
8.36
e
-
7
9.48
e
-
7
8.33
e
-
7
3135
30.35
9.24
e
-
7
9.99
e
-
7
1.00
e
-
6
4943
48.14
bqp250-2
251
6.57
e
-
7
9.99
e
-
7
7.89
e
-
7
3467
32.96
9.86
e
-
7
1.00
e
-
6
7.41
e
-
7
5091
48.01
bqp500-1
501
6.09
e
-
7
9.98
e
-
7
1.33
e
-
6
4676
3 : 20
9.99
e
-
7
9.31
e
-
7
3.38
e
-
7
6931
4 : 54
bqp500-2
501
9.99
e
-
7
7.53
e
-
7
4.51
e
-
7
5307
3 : 49
6.01
e
-
7
9.99
e
-
7
1.01
e
-
7
10580
7 : 31
gka1a
51
9.98
e
-
7
2.77
e
-
7
3.16
e
-
8
2240
2.05
8.43
e
-
7
9.81
e
-
7
2.15
e
-
6
2635
2.33
gka2a
61
8.95
e
-
7
9.84
e
-
7
2.50
e
-
6
1326
1.36
5.88
e
-
7
9.98
e
-
7
2.39
e
-
6
2594
2.51
gka3a
71
9.04
e
-
7
8.92
e
-
7
5.39
e
-
7
1098
1.58
9.84
e
-
7
9.98
e
-
7
5.21
e
-
7
1328
1.88
gka4a
81
9.99
e
-
7
9.93
e
-
7
8.21
e
-
7
1371
2.14
9.98
e
-
7
8.02
e
-
7
5.02
e
-
7
2273
3.39
gka5a
51
8.14
e
-
7
9.83
e
-
7
1.29
e
-
7
1268
1.24
9.97
e
-
7
6.58
e
-
7
9.02
e
-
9
1392
1.33
gka6a
31
8.84
e
-
7
7.95
e
-
7
3.49
e
-
7
927
0.60
1.98
e
-
7
9.96
e
-
7
1.15
e
-
6
979
0.62
gka7a
31
9.12
e
-
7
9.96
e
-
7
9.07
e
-
7
948
0.65
1.00
e
-
6
7.50
e
-
7
7.33
e
-
7
1906
1.24
gka8a
101
8.56
e
-
7
9.94
e
-
7
2.51
e
-
6
2521
5.02
9.91
e
-
7
8.54
e
-
7
8.65
e
-
7
5804
10.91
gka9b
101
5.46
e
-
7
1.41
e
-
7
1.83
e
-
5
1263
3.02
6.45
e
-
7
1.73
e
-
7
1.88
e
-
5
1313
3.07
gka10b
126
9.93
e
-
7
8.92
e
-
7
2.83
e
-
5
1775
8.11
9.97
e
-
7
7.65
e
-
7
2.45
e
-
5
1810
8.32
gka6c
91
9.88
e
-
7
7.13
e
-
7
1.76
e
-
7
4002
7.92
5.56
e
-
7
9.99
e
-
7
4.07
e
-
7
5122
9.95
gka7c
101
8.70
e
-
7
9.96
e
-
7
1.06
e
-
7
4478
9.69
6.83
e
-
7
9.99
e
-
7
6.47
e
-
7
5314
11.45
gka9d
101
7.71
e
-
7
9.99
e
-
7
3.52
e
-
9
1091
2.69
9.92
e
-
7
8.58
e
-
7
1.04
e
-
7
1500
3.64
gka10d
101
5.17
e
-
7
9.95
e
-
7
3.44
e
-
8
1423
3.38
8.61
e
-
7
9.96
e
-
7
1.01
e
-
6
1798
4.23
gka4e
201
9.08
e
-
7
7.60
e
-
7
4.28
e
-
7
3534
24.79
1.00
e
-
6
7.22
e
-
7
5.43
e
-
7
4754
33.12
gka5e
201
8.25
e
-
7
9.91
e
-
7
3.67
e
-
7
3153
22.09
9.97
e
-
7
8.91
e
-
7
2.95
e
-
7
4157
28.95
gka4f
501
9.64
e
-
7
9.93
e
-
7
1.08
e
-
6
5153
4 : 14
9.98
e
-
7
7.23
e
-
7
4.24
e
-
7
7529
6 : 08
gka5f
501
7.66
e
-
7
9.97
e
-
7
8.13
e
-
7
4660
3 : 48
9.99
e
-
7
9.66
e
-
7
9.37
e
-
7
7023
5 : 41


### 5.1. Frequency Assignment Relaxation

In this subsection, we consider SDPs arising from semidefinite relaxation of frequency assignment problems (fap) [39]. The explicit description of the SDP form is given in [40]. For a given undirected graph G
=
(
V
,
E
) with vertex set V
=
{
1
,
…
,
r
} and edge set E
⊂
V
×
V, assume W
=
(
w
i
j
)
∈
S
r is a weight matrix for G. If the edge (
i
,
j
)
∉
E, we suppose w
i
j
=
w
j
i
=
0. For a given edge subset T
⊆
E, we can formulate the problem as
(44)
min
⁡
〈
1
2
k
Diag
(
W
e
)
+
k
-
1
2
k
W
,
X
〉
s
.
t
.
X
i
j
≥
-
1
k
-
1
,
∀
(
i
,
j
)
∈
E
∖
T
,
X
i
j
=
-
1
k
-
1
,
∀
(
i
,
j
)
∈
T
,
diag
⁡
(
X
)
=
e
,
X
⪰
0
,
where e
∈
R
r is the vector of all ones, Diag
(
x
) is a diagonal matrix with x as the diagonal entries, and diag
⁡
(
X
) is a vector of the diagonal entries of matrix X. The constraints X
i
j
=
-
1
/
(
k
-
1
) were replaced by X
i
j
/
2
=
-
1
/
(
2
(
k
-
1
)
) and X
i
j
≥
-
1
/
(
k
-
1
) by X
i
j
/
2
≥
-
1
/
(
2
(
k
-
1
)
). So we have A
A
*
=
I. We set h to 50 for updating the penalty parameter μ.We did not run SDPAD on our own computer on the problem “fap36” and the results presented here were taken from Table 1 in [16]. From Table 1, it can be observed that Algorithm 1 is often faster than SDPAD for achieving a duality gap of the same order. The infeasibility achieved by Algorithm 1 is satisfactory as well.


### 5.2. Binary Integer Quadratic Programs Problem

In this subsection, we present numerical results of Algorithm1 and SDPAD on binary integer quadratic (BIQ) problems [41] through SDP relaxations which have the following form:
(45)
min
⁡
〈
(
Q
0
0
0
)
,
X
〉
s
.
t
.
X
i
i
-
X
n
,
i
=
0
,
i
=
1
,
…
,
n
-
1
,
X
n
n
=
1
,
X
⪰
0
,
where Q
∈
R
(
n
-
1
)
×
(
n
-
1
). The constraints X
i
i
-
X
n
,
i
=
0 were replaced by 2
/
3
(
X
i
i
-
X
n
,
i
)
=
0 and the matrix Q was scaled by its Frobenious norm. We set h to 50 for updating the penalty parameter μ.Table2 lists the results of Algorithm 1 and SDPAD on the BIQ problems. By comparing the results in Table 2, we can conclude that Algorithm 1 applied to BIQ problems is superior to SDPAD in terms of CPU time and number of iterations. In addition, the accuracy of the approximate optimal solutions computed by Algorithm 1 is as good as that obtained by SDPAD.Figure1 shows the performance profiles [42] of Algorithm 1 and SDPAD for the number of iterations, Figure 1(a), and CPU time, Figure 1(b). We observe that Algorithm 1 is better than SDPAD in terms of number of iterations and CPU time.Performance profiles for SDPAD and the present method for number of iterations (a) and CPU time (b).
(a)
(b)


## 5.1. Frequency Assignment Relaxation

In this subsection, we consider SDPs arising from semidefinite relaxation of frequency assignment problems (fap) [39]. The explicit description of the SDP form is given in [40]. For a given undirected graph G
=
(
V
,
E
) with vertex set V
=
{
1
,
…
,
r
} and edge set E
⊂
V
×
V, assume W
=
(
w
i
j
)
∈
S
r is a weight matrix for G. If the edge (
i
,
j
)
∉
E, we suppose w
i
j
=
w
j
i
=
0. For a given edge subset T
⊆
E, we can formulate the problem as
(44)
min
⁡
〈
1
2
k
Diag
(
W
e
)
+
k
-
1
2
k
W
,
X
〉
s
.
t
.
X
i
j
≥
-
1
k
-
1
,
∀
(
i
,
j
)
∈
E
∖
T
,
X
i
j
=
-
1
k
-
1
,
∀
(
i
,
j
)
∈
T
,
diag
⁡
(
X
)
=
e
,
X
⪰
0
,
where e
∈
R
r is the vector of all ones, Diag
(
x
) is a diagonal matrix with x as the diagonal entries, and diag
⁡
(
X
) is a vector of the diagonal entries of matrix X. The constraints X
i
j
=
-
1
/
(
k
-
1
) were replaced by X
i
j
/
2
=
-
1
/
(
2
(
k
-
1
)
) and X
i
j
≥
-
1
/
(
k
-
1
) by X
i
j
/
2
≥
-
1
/
(
2
(
k
-
1
)
). So we have A
A
*
=
I. We set h to 50 for updating the penalty parameter μ.We did not run SDPAD on our own computer on the problem “fap36” and the results presented here were taken from Table 1 in [16]. From Table 1, it can be observed that Algorithm 1 is often faster than SDPAD for achieving a duality gap of the same order. The infeasibility achieved by Algorithm 1 is satisfactory as well.


## 5.2. Binary Integer Quadratic Programs Problem

In this subsection, we present numerical results of Algorithm1 and SDPAD on binary integer quadratic (BIQ) problems [41] through SDP relaxations which have the following form:
(45)
min
⁡
〈
(
Q
0
0
0
)
,
X
〉
s
.
t
.
X
i
i
-
X
n
,
i
=
0
,
i
=
1
,
…
,
n
-
1
,
X
n
n
=
1
,
X
⪰
0
,
where Q
∈
R
(
n
-
1
)
×
(
n
-
1
). The constraints X
i
i
-
X
n
,
i
=
0 were replaced by 2
/
3
(
X
i
i
-
X
n
,
i
)
=
0 and the matrix Q was scaled by its Frobenious norm. We set h to 50 for updating the penalty parameter μ.Table2 lists the results of Algorithm 1 and SDPAD on the BIQ problems. By comparing the results in Table 2, we can conclude that Algorithm 1 applied to BIQ problems is superior to SDPAD in terms of CPU time and number of iterations. In addition, the accuracy of the approximate optimal solutions computed by Algorithm 1 is as good as that obtained by SDPAD.Figure1 shows the performance profiles [42] of Algorithm 1 and SDPAD for the number of iterations, Figure 1(a), and CPU time, Figure 1(b). We observe that Algorithm 1 is better than SDPAD in terms of number of iterations and CPU time.Performance profiles for SDPAD and the present method for number of iterations (a) and CPU time (b).
(a)
(b)


## 6. Conclusion

In this paper, a novel linearizing alternating direction augmented Lagrangian approach is proposed for solving semidefinite programs (SDP). The algorithm updates the dual variables without solving any system of linear equations. Moreover, all the variables are updated in closed forms. Preliminary numerical results show the efficiency of the proposed algorithm. However, there are still some unsettled issues for implementation. For example, efficient strategies to update penalty parameterμ and choose step size λ
k deserve more work for applications of the algorithm.



---

*Source: 613205-2014-08-18.xml*