Department of Policy and Planning Sciences
Discussion Paper Series

No.1359

Polyhedral approximations of the semidefinite cone andtheir application

by
Yuzhu WANG, Akihiro TANAKA, and Akiko YOSHISE

May 2019
Revised December 2020

UNIVERSITY OF TSUKUBA
Tsukuba, Ibaraki 305-8573
JAPANPolyhedral approximations of the semidefinite cone and theirapplication∗
Yuzhu Wang†, Akihiro Tanaka‡and Akiko Yoshise§
May 2019
Revised December 2020

Abstract
We develop techniques to construct a series of sparse polyhedral approximations of the semidefinite cone. Motivated by the semidefinite (SD) bases proposed by Tanaka and Yoshise (2018), we
propose a simple expansion of SD bases so as to keep the sparsity of the matrices composing it.
We prove that the polyhedral approximation using our expanded SD bases contains the set of all
diagonally dominant matrices and is contained in the set of all scaled diagonally dominant matrices.
We also prove that the set of all scaled diagonally dominant matrices can be expressed using an
infinite number of expanded SD bases. We use our approximations as the initial approximation in
cutting plane methods for solving a semidefinite relaxation of the maximum stable set problem. It
is found that the proposed methods with expanded SD bases are significantly more efficient thanmethods using other existing approximations or solving semidefinite relaxation problems directly.

Key words: Semidefinite optimization problems; Conic optimization problems; Polyhedral approximation; Semidefinite bases; Expanded semidefinite bases.
AMS subject classifications: 90C05, 90C22, 90C25

1Introduction

A semidefinite optimization problem (SDP) is an optimization problem in variables in the space ofsymmetric matrices with a linear objective function and linear constraints over the semidefinite cone.
We denote the space of symmetric matrices as Sn := {X ∈ Rn×n | Xi,j = Xj,i (1 ≤ i < j ≤ n)} and the∗ An earlier version of this paper was entitled “Polyhedral approximations of the semidefinite cone and their applications.”
This research was supported by the Japan Society for the Promotion of Science through a Grant-in-Aid for Challenging
Exploratory Research (17K18946) and a Grant-in-Aid for Scientific Research ((B)19H02373) of the Ministry of Education,
Culture, Sports, Science and Technology of Japan.
† Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan.
email: s1930138@s.tsukuba.ac.jp‡ Central Research Institute of Electric Power Industry, Yokosuka, Kanagawa 240-0196, Japan.
email: atanaka@criepi.denken.or.jp§ Corresponding author. Faculty of Engineering, Information and Systems, University of Tsukuba, Tsukuba, Ibaraki
305-8573, Japan. email: yoshise@sk.tsukuba.ac.jp

1nsemidefinite cone as S+:= {X ∈ Sn | dT Xd ≥ 0 for any d ∈ Rn }. Accordingly, we can readily define an
SDP in the standard form, as

min hC, Xi
s.t. hAj , Xi = bj , j = 1, 2, . . . , m,

(1)n
X ∈ S+,

where C ∈ Sn , Aj ∈ Sn , bj ∈ R (j = 1, 2, . . . , m), and hA, Bi := Trace(AT B) =inner product over Sn .

Pni,j=1 Ai,j Bi,j is the

SDPs are powerful tools that provide convex relaxations for combinatorial and nonconvex optimizations,such as the max-cut problem (e.g., [19], [12]) and the k-equipartition problem (e.g., [46], [23]). Some ofthese relaxations can even attain the optimum, as shown in [31] and [24]. Interested readers may finddetails about SDPs and their relaxations in [46], [42] and [32].
A cone K ⊂ Sn is called proper if it has a non-empty interior and is closed, pointed (i.e., K ∩ −K = {O}),and convex. It is known that the SDP cone is a proper cone [9]. By replacing the semidefinite constraintn
X ∈ S+
with a general conic constraint X ∈ K in (1) (say, a proper cone K ⊂ Sn ), one can obtain ageneral class of problems, namely, conic optimization problems. The class of conic optimization problems
has been an active field of study because it contains many popular classes of problems, including linear
optimization problems (LPs), second-order cone programs (SOCPs), SDPs, and copositive programs.
Copositive programs have been shown capable of providing tight lower bounds for combinatorial andquadratic optimization problems, as described in the survey paper by Dür [17] and the recent workof Arima et al. [3], [25], [4], etc. It has been shown that a copositive relaxation sometimes gives ahighly accurate approximate solution for some combinatorial problems under certain conditions [5], [11].
However, the copositive program and its dual problem are both NP-hard (see, e.g., [16] and [36]).
SDPs are also attractive because they can be solved in polynomial time to any desired precision. There
are state-of-the-art solvers, such as SDPA [47], SeDuMi [40], SDPT3 [43], and Mosek [35], but their
computations become difficult when the size of the SDP becomes large. To overcome this deficiency,
for example, one may use preprocessing to reduce the size of the SDPs, which leads to facial reduction
methods [37], [38] and [44]. As another idea, one may generate relaxations of SDPs and solve them as
easily handled optimization problems, e.g., LPs and SOCPs, which leads to cutting plane methods. We
will focus on these latter methods.
The cutting plane method solves an SDP by transforming it into an optimization problem (e.g., an LPor an SOCP), adding cutting planes at each iteration to cut the current approximate solution out of thefeasible region in the next iterations and to get close to the optimal value. The cutting plane method
was first used on the traveling-salesman problem, by Dantzig, Fulkerson, and Johnson [13], [14] in 1954.
It was used in 1958 by Gomory [20] to solve integer linear programming problems. As SDPs became
popular, it came to be used on them as well; see, for instance, Krishnan and Mitchell [28], [30] and[29], and Konno et al. [27]. Kobayashi and Takano [26] applied it to a class of mixed-integer SDPs. In[1], Ahmadi, Dash, and Hall applied it to nonconvex polynomial optimization problems and copositive
programs.
n
In the above-mentioned cutting plane methods for SDPs, the semidefinite constraint X ∈ S+
in (1) isnn
first relaxed to X ∈ Kout , where S+ ⊆ Kout ⊆ S , and an initial relaxation of the SDP is obtained. If
Kout is polyhedral, the initial relaxation may give an LP; if Kout is given by second-order constraints,
the initial relaxation becomes an SOCP. To improve the performance of these cutting plane methods,
we consider generating initial relaxations for SDPs that are both tight and computationally efficient andnfocus on approximations of S+.

2nMany approximations of S+
have been proposed on the basis of its well-known properties. Kobayashi and
Takano [26] used the fact that the diagonal elements of semidefinite matrices are nonnegative. Konno
et al. [27] imposed an assumption that all diagonal elements of the variable X in the SDPs appearing
in their iterative algorithm are bounded by a constant. The sets of diagonally dominant matrices andnscaled diagonally dominant matrices are known to be cones contained in S+, (see, e.g., [22] and [1] fordetails). The inclusive relation among them has been studied in, e.g., [7] and [8]. Ahmadi et al. [1] and[2] used these sets as initial approximations of their cutting plane method. Boman et al. [10] defined
the factor width of a semidefinite matrix, and Permenter and Parrilo used it to generate approximationsnof S+, which they applied to facial reduction methods in [37].

semidefinite
Tanaka and Yoshise defined various bases of Sn , wherein each basis consists of n(n+1)
2nmatrices, called semidefinite (SD) bases, and used them to devise approximations of S+[41]. They
showed that the conical hull of SD bases and its dual cone give inner and outer polyhedral approximationsnof S+, respectively. On the basis of the SD bases, they also developed techniques to determine whethernna given matrix is in the semidefinite plus nonnegative cone S++ N n , which is the Minkowski sum of S+nand the nonnegative matrices cone N . In this paper, we focus on the fact that SD bases are sometimes
sparse, i.e., the number of nonzero elements in a matrix is relatively small, and hence, it is not socomputationally expensive to solve polyhedrally approximated problems in such SD bases. We call suchn
an approximation, a sparse polyhedral approximation, and propose efficient sparse approximations of S+.
n
The goal of this paper is to construct tight and sparse polyhedral approximations of S+
by using SD
nbases in order to solve hard conic optimization problems, e.g., doubly nonnegative (DNN, or S+∩ N n)nn
and semidefinite plus nonnegative (S+ + N ) optimization problems. The contributions of this paper
are summarized as follows.

• This paper gives the relation between the conical hull of sparse SD bases and the set of diagonallydominant matrices. We propose a simple expansion of SD bases without losing the sparsity of thenthat contains
matrices and prove that one can generate a sparse polyhedral approximation of S+
the set of diagonally dominant matrices and is contained in the set of scaled diagonally dominant
matrices.
• The expanded SD bases are used by cutting plane methods for a semidefinite relaxation of the
maximum stable set problem. It is found that the proposed methods with expanded SD bases
are significantly more efficient than methods using other approximations or solving semidefinite
relaxation problems directly.
nare introduced in section
The organization of this paper is as follows. Various approximations of S+
2, including those based on the factor width by Boman et al. [10], diagonal dominance by Ahmadi etal. [1], and SD bases by Tanaka and Yoshise [41]. The main results of this paper, i.e., an expansionof SD bases and an analysis of its theoretical properties, are provided in section 3. In section 4, wenintroduce the cutting plane method using different approximations of S+
for calculating upper boundsof the maximum stable set problem. We also describe the results of numerical experiments and evaluate
the efficiency of the proposed method with expanded SD bases.

32Some approximations of the semidefinite cone

2.1

Factor width approximation

In [10], Boman et al. defined a concept called factor width.
Definition 2.1. (Definition 1 in [10]) The factor width of a real symmetric matrix A ∈ Sn is the smallest
integer k such that there exists a real matrix V ∈ Rn×m where A = V V T and each column of V contains
at most k nonzero elements.
For k ∈ {1, 2, . . . , n}, we can also defineFW(k) := {X ∈ Sn | X has a factor width of at most k}.
It is obvious that the factor width is only defined for semidefinite matrices, because for every matrix A inn
. Therefore, for every k ∈ {1, 2, . . . , n},Definition 2.1, the decomposition A = V V T implies that A ∈ S+
the set of matrices with a factor width of at most k gives an inner approximation of Sn+ : FW(k) ⊆ Sn+ .

2.2

Diagonal dominance approximationnwith the set of diagonally dominant matrices andIn [1] and [2], the authors approximated the cone S+
the set of scaled diagonally dominant matrices.

Definition 2.2. The set of diagonally dominant matrices DDn and the set of scaled diagonally dominant
matrices SDDn are defined as follows:X
DDn := {A ∈ Sn | Ai,i ≥|Ai,j | (i = 1, 2, . . . , n)},j6=i

SDDn := {A ∈ Sn | DAD ∈ DDn for some positive diagonal matrix D}.
It is easy to see that DDn is a convex cone and SDDn is a cone in Sn . As a consequence of the Gershgorinn. Ahmadi et al. [1] defined Un,k as the set
circle theorem [18], we have the relation DDn ⊆ SDDn ⊆ S+nof vectors in R with at most k nonzeros, each equal to 1 or −1. They also defined a set of matrices
Un,k := {uuT | u ∈ Un,k }. Barker and Carlson [6] proved the following theorem.
Theorem 2.3. (Barker and Carlson [6]) DDn = cone(Un,2 ).
Pk
The conical hull of a given set K ⊆ Sn is defined as cone(K) := { i=1 αi Xi | Xi ∈ K, αi ≥ 0, k ∈ Z≥0 },where Z≥0 is the set of nonnegative integers. A cone generated in this way by a finite number of elements
is called finitely generated. Theorem 2.3 implies that DDn has n2 extreme rays; thus, it is a finitely
generated cone.
A cone K ∈ Sn is polyhedral if K = {X ∈ Sn | hAi , Xi ≤ 0} for some Ai ∈ Sn . The following theorem
follows from the results of Minkowski [34] and Weyl [45].
Theorem 2.4. (Minkowski-Weyl theorem, see Corollary 7.1a in [39]) A convex cone is polyhedral if andonly if it is finitely generated.

4

The above theorem ensures that DDn is a polyhedral cone. Using the expression in Theorem 2.3,
Ahmadi et al. proved that optimization problems over DDn can be solved as LPs. They also provedthat optimization problems over SDDn can be solved as SOCPs. They designed a column generation
method using DDn and SDDn to obtain a series of inner approximations of Sn+ . As for the relation
between the factor width and diagonal dominance, useful results were presented in [10] and in [2], which
gives a relation between SDDn and the set of matrices with a factor width of at most 2.
Lemma 2.5. (See [10] and Theorem 8 in [2]) FW(2) = SDDn
Note that Definition 2.1 implies that the set FW(k) is convex for any k ∈ {1, 2, . . . , n}, and we obtainthe following corollary as Lemma 2.5:
Corollary 2.6. The set SDDn is a convex cone.

2.3

SD basis approximation

Tanaka and Yoshise defined semidefinite (SD) bases [41].
Definition 2.7. (Definitions 1 and 2 in [41]) Let ei ∈ Rn denotes the vector with a 1 at the ith coordinate
and 0 elsewhere, and let I = (e1 , . . . , en ) ∈ Sn be the identity matrix. Then
B+ := {(ei + ej )(ei + ej )T | 1 ≤ i ≤ j ≤ n}
is called an SD basis of Type I, andB− := {(ei + ei )(ei + ei )T | 1 ≤ i ≤ n} ∪ {(ei − ej )(ei − ej )T | 1 ≤ i < j ≤ n}
is called an SD basis of Type II. Matrices in SD bases Type I and II are defined as
+
−
Bi,j:
= (ei + ej )(ei + ej )T , Bi,j:= (ei − ej )(ei − ej )T .

n
As shown in [41], B+ and B− are subsets of S+
and bases of Sn . Given a set K ⊆ Sn , we define the dual∗ncone of K as (K) := {A ∈ S | hA, Bi ≥ 0 for any B ∈ K}. The conical hull of B+ ∪ B− and its dualn
, as follows.
give an inner and an outer polyhedral approximation of S+

Definition 2.8. Let I = (e1 , . . . , en ) ∈ Sn be the identity matrix. The inner and outer approximationsnby using SD bases are defined asof S+
Sin := cone(B+ ∪ B− ), Sout := (Sin )∗ .
nnnn
By Definition 2.7, we know that B+ , B− ⊆ S+
. Since S+
is a convex cone, we have Sin ⊆ cone(S+) = S+.
nnn ∗By Lemma 1.7.3 in [32], we know that S+
is self-dual; that is, S+= (S+) . Accordingly, we can concludenthat Sin ⊆ S+
⊆ Sout .

Remark 2.9. In [41], B+ and B− are defined as B+ (P ) and B− (P ) using an orthogonal matrix P
instead of the identity matrix I. In fact, for any orthogonal matrix P ,
+
+
− T
−
P B+ P T := {P Bi,j
P T | Bi,j
∈ B+ } and P B− P T := {P Bi,j
P | Bi,j∈ B− }

also give other bases and generalizations of B+ and B− . However, as we will see in section 4, we use
the matrices in the bases as in optimization problems of the form
min hC, Xi s.t. hA, Xi = b, hY, Xi ≥ 0 (Y ∈ B+ ),5

which is equivalent tomin hP CP T , X̄i s.t. hP AP T , X̄i = b, hY, X̄i ≥ 0 (Y ∈ P B+ P T ).

(2)

Therefore, we consider that the generalizations P B+ P T and P B− P T are not essential throughout thispaper and omit those descriptions from subsequent sections to simplify the presentation.

3

Expansion of SD basesnWhen we use the SD bases for approximating S+, the sparsity of the matrices in those bases is quite
important in terms of computational efficiency. As we mentioned in Remark 2.9, for any orthogonal
matrix P , P B+ P T and P B− P T give generalizations of the SD bases. However, it is hard to choose anappropriate orthogonal matrix P (except for the identity matrix I) to keep the sparsity of the matrices
P CP T and P AP T in (2). In this section, we try to extend the definition of the SD bases in order tonobtain various sparse SD bases which will lead us to sparse polyhedral approximations of S+.

3.1

SD bases and their relations with S+n and DDnnby using SD bases. The lemma is a direct
First, we give a lemma that provides an expression of S+ncorollary of the fact that any X ∈ S+ has nonnegative eigenvalues and a corresponding orthogonal basisof eigenvectors.

Lemma 3.1.
!
nS+
= cone[T{P XP | X ∈ B+ }!
[= coneP ∈O nT{P XP | X ∈ B− } ,P ∈O nwhere On is the set of orthogonal matrices in Rn×n .
nby changing the matrix P = (p1 , .., pn ) ∈ On when creating
Lemma 3.1 gives a way to approximate S+n
SD bases. However, a dense matrix P ∈ O may lead to a dense formulation of the approximation using
SD basis, which is unattractive from the standpoint of computational efficiency.

Note that we can easily see that the set cone(B+ ∪ B− ), the conical hull of the sparse SD bases B+ and
B− , is equivalent to cone(Un,2 ). Thus, we obtain the following proposition as a corollary of Theorem
2.3.
Proposition 3.2.
cone(B+ ∪ B− ) = DDn .

3.2

Expansion of SD bases without losing sparsityn
The previous section shows that we can obtain a sparse polyhedral approximation of S+
by using the
SD bases. In this section, we try to extend the definition of the SD bases in order to obtain variousnsparse polyhedral approximations of S+.

6

Definition 3.3. Let I = (e1 , . . . , en ) ∈ Sn be the identity matrix. Define the expansion of the SD basiswith one parameter α ∈ R as
B̄i,j (α) := (ei + αej )(ei + αej )T ,B̄(α) := {B̄i,j (α) | 1 ≤ i ≤ j ≤ n}.
The proposition below ensures that the expansion of the SD bases also gives bases of Sn .
Proposition 3.4. Let I = (e1 , . . . , en ) ∈ Sn be the identity matrix. For any α ∈ R \ {0, −1}, B̄(α) is aset of n(n + 1)/2 independent matrices and thus a basis of Sn .
Proof. Let α ∈ R \ {0, −1}. Accordingly, for 1 ≤ i < j ≤ n, we haveB̄i,j (α) :=(ei + αej )(ei + αej )T=ei eTi + α(ei eTj + ej eTi ) + α2 ej eTj=α(ei eTi + ei eTj + ej eTi + ej eTj ) + (1 − α)ei eTi + (α2 − α)ej eTj+=αBi,j+α(α − 1) +1−α +Bi,i +
Bj,j ,
4
4(3)

and for every 1 ≤ i ≤ n, we also haveB̄i,i (α) :=(ei + αei )(ei + αei )T=(1 + α)2 ei eTi =(1 + α)2 +Bi,i .
4

Suppose that there exist γi,j ≥ 0 (1 ≤ i ≤ j ≤ n) such thatX
γi,j B̄i,j (α) = O.
1≤i≤j≤n7(4)

Then, by (3) and (4), we see thatO=nX
γi,i (1 + α)2
i=1

=

4

X

+
Bi,i
+

1≤i<j≤nn
X(1 + α)2+γi,i Bi,i
+
4
i=1

+

X



1−α +
α(α − 1) ++γi,j αBi,j+Bi,i +
Bj,j44+αγi,j Bi,j+1≤i<j≤n

n−1
X

n
1−α X
+
(
γi,j )Bi,i
4
i=1
j=i+1

j−1
X

n
X

α(α − 1)+(γi,j )Bj,j
4
i=1
j=2




n
X
γ1,1 (1 + α)
1−α
+
=
+
(
γ1,j ) B1,1
4
4 j=2


n
i−1
n−1
X
X
X (1 + α)2
1
−
α
α(α
−
1)
+

γi,i +((+
γi,j ) +γj,i ) Bi,i
4
4
4
j=i+1
j=1
i=2


n−1
α(α − 1) X
γn,n (1 + α)2+γj,n ) Bn,n
+
(
+
4
4
j=1
X
+
+
αγi,j Bi,j
.
2

(5)

1≤i<j≤n+Since {Bi,j} = B+ is a set of linearly independent matrices, all the coefficients for Bi,j in (5) should be
0. Thus, we havenγ1,1 (1 + α)2
1−α X
0=
+
(
γ1,j ),
4
4 j=2

(6)

n
i−1
1−α X
α(α − 1) X
(1 + α)2γi,i +(
γi,j ) +(γj,i ) (2 ≤ i ≤ n − 1),0=4
4 j=i+1
4
j=1

(7)

n−1
γn,n (1 + α)2α(α − 1) X
0=+(γj,n ),
4
4
j=1

(8)

0 = αγi,j (1 ≤ i < j ≤ n).

(9)

Since α 6= 0, by (9) we have
γi,j = 0 (1 ≤ i < j ≤ n).

(10)

γi,i = 0 (i = 1, 2, . . . , n).

(11)

Since α 6= −1, (6)-(10) imply that

The above leads us to conclude that {B̄i,j (α)} = B̄(α) is a set of n(n+1)/2 linearly independent matrices.

If we let α = 1, then it is straightforward that B̄(1) = B+ . If we let α be other real numbers, we
may obtain different SD bases. The following proposition gives the condition for generating different
expanded SD bases.
8

Proposition 3.5. Let I = (e1 , . . . , en ) ∈ Sn be the identity matrix. Suppose that α1 ∈ R \ {0, −1} andα2 ∈ R \ {0, α1 }. Then, for every 1 ≤ i < j ≤ n,
(ei + α2 ej )(ei + α2 ej )T ∈/ cone(B̄(α1 )).
Proof. For 1 ≤ i ≤ j ≤ n, let us define
1
2
B̄i,j
:= (ei + α1 ej )(ei + α1 ej )T , B̄i,j:= (ei + α2 ej )(ei + α2 ej )T .

Note that if i = j, then
1
2
B̄i,i
:= (1 + α1 )2 ei eTi , B̄i,i:= (1 + α2 )2 ei eTi .

(12)

2
1
For every i < j, we can write B̄i,j
as a linear combination of B̄i,j
:
2
B̄i,j
=ei eTi + α22 ej eTj + α2 (ei eTj + ej eTi )α2α1 (ei eTj + ej eTi ) (because α1 6= 0)=ei eTi + α22 ej eTj +α1
α2 T α2 α12=ei eTi + α22 ej eTj −ei e −
ej eTjα1 iα1
α2  Tei ei + α1 (ei eTj + ej eTi ) + α12 ej eTj
+
α1
α2 1
α1 − α2 T=ei ei + α2 (α2 − α1 )ej eTj +B̄
α1α1 i,jα1 − α2α2 (α2 − α1 )α2 1=
(1 + α1 )2 ei eTi +(1 + α1 )2 ej eTj +B̄α1 (1 + α1 )2(1 + α1 )2
α1 i,j(because α1 6= −1)=

α2 (α2 − α1 ) 1
α2 1
α1 − α21B̄i,i+B̄j,j +B̄ (by (12)).
22
α1 (1 + α1 )(1 + α1 )α1 i,j(13)

Since α1 6∈ {0, −1}, Proposition 3.4 ensures that B̄(α1 ) is linearly independent, and hence, the expression2(13) for B̄i,jis unique.
2
Suppose that B̄i,j∈ cone B̄(α1 ) . In this case, all the coefficients in (13) should be nonnegative, which
implies that
α1 − α2α2 (α2 − α1 )
α2
≥ 0,
≥ 0,
> 0.
α1 (1 + α1 )2(1 + α1 )2
α1

(14)

From the last inequality in (14), we have either(i) α1 , α2 > 0or(ii) α1 , α2 < 0.

For case (i), from the first and second inequalities of (14), we have α2 − α1 ≥ 0 and α1 − α2 ≥ 0, which
implies α2 = α1 and contradicts the assumption α2 6= α1 . A similar contradiction is obtained for case2(ii). Thus, we have B̄i,j∈/ cone(B̄(α1 )). 

9

3.3

Expression of SDDn with expanded SD bases

As we have seen in Corollary 2.6, the set SDDn = FW(2) is a convex cone. This fact ensures that as acorollary of Theorem 2.3, the conical hull of the union of the extended SD bases B̄(α) on α ∈ R coincides
with FW(2) and hence, the set of scaled diagonally dominant matrices SDDn :Corollary 3.6.
!
cone

[

B̄(α)

= SDDn .

α∈R

3.4

Notes on the parameter αHere, we discuss the choice for the parameter α to increase the “volume” of the polyhedral approximationncone(B̄(α)) of the semidefinite cone S+. For any α ∈ R and 1 ≤ i < j ≤ n, by Definition 3.3, we cancalculate the Frobenius norm of B̄i,j (α):
kB̄i,j (α)k =k(ei + αej )(ei + αej )T kq
= Trace ((ei + αej )(ei + αej )T (ei + αej )(ei + αej )T )=kei + αej k2=1 + α2 .

(15)According to Proposition 3.5, by changing α, one can obtain different polyhedral approximations. However, we can see thatlim

B̄i,j (α)|α|→∞ kB̄i,j (α)k

1

= lim

|α|→∞ 1 + α2

(ei + αej )(ei + αej )T (by (15)),

1
α
α2
T
T
T
= lim
e
e
+
(e
e
+
e
e
)
+
ej eTjii
ji
ji
1 + α2
1 + α2|α|→∞ 1 + α2
1 +,= ej eTj = Bj,j4

and by Definitions 2.7 and 3.3, we haveB̄i,j (0) =1 ++−B , B̄i,j (1) = Bi,j
, B̄i,j (−1) = Bi,j.
4 i,iThis shows that, if |α| → ∞ or α ∈ {0, 1, −1}, the new matrix B̄i,j (α) will become close to the existing+++−
matrices, e.g. Bi,i
, Bj,j, Bi,jand Bi,j, and the “volume” of the polyhedral approximation cone(B̄(α) ∪nB+ ∪B− ) of the semidefinite cone S+ will also be close to the “volume” of the existing inner approximationncone(B+ ∪ B− ) of S+.
To give an illustrative explanation of the above discussion, here we consider the specific case



a c
2
2
S+ =
| a, b, c ∈ R, a, b ≥ 0, ab − c ≥ 0
c b2
and draw some figures in R3 with coordinate a, b and c. Fig. 1 [a] shows the set of S+
in R3 . The redarrow in Fig. 1 [b] shows the extreme rays {γ B̄i,j (α) | γ ≥ 0} with |α| → ∞ and α ∈ {0, 1, −1}. The

10

conical hull of these extreme rays is cone(B+ ∪ B− ) and its cross section with {X ∈ S2 | hX, Ii = 1}
is illustrated as the blue area. To avoid generating a new matrix B̄i,j (α) that is close to the existing
matrices, we should choose an α such that the angle between B̄i,j (α) and existing matrices are equal, as
illustrated in Fig. 1 [c].

2[a] The set of S+.

[b] The set of {γ B̄i,j (α) | γ ≥ 0}[c] B̄i,j (α) that are not close to
the existing matrices

Figure 1: Choice of α to generate B̄i,j (α) ∈ S2 in R3
We expand this idea to the case of generating a matrix B̄i,j (α) ∈ Sn . Given an α ∈ R, we can define theangles between matrices in the expanded SD bases and SD bases Type I and II for every 1 ≤ i < j ≤ n,
as follows:θ1 (α) := arccos
θ3 (α) := arccos+
hB̄i,j (α), Bi,ii+kB̄i,j (α)kkBi,ik+hB̄i,j (α), Bi,ji+kB̄i,j (α)kkBi,jk, θ2 (α) := arccos, θ4 (α) := arccos+
hB̄i,j (α), Bj,ji+kB̄i,j (α)kkBj,jk−hB̄i,j (α), Bi,ji−kB̄i,j (α)kkBi,jk,.

Thus, we havecosθ1 (α) =+hB̄i,j (α), Bi,ii+kB̄i,j (α)kkBi,ikh(ei + αej )(ei + αej )T , (ei + ei )(ei + ei )T i
(by (15))(1 + α2 )k(ei + ei )(ei + ei )T k
4kei k4=(because eTi ej = 0)
(1 + α2 )4kei k2
1=(because kei k = 1).
1 + α2=

Similarly, we havecosθ2 (α) =(1 − α)2α2(1 + α)2
,
cosθ
(α)
=
.
,
cosθ
(α)
=
4
3
1 + α22(1 + α2 )2(1 + α2 )In general, to obtain a large enough inner approximation with limited parameters, we prefer an α that++makes θ1 (α) = θ3 (α), which means that the new matrix B̄i,j (α) will be in the middle of Bi,iand Bi,jn
on the boundary of S+ . Similarly, we can obtain α by calculating θ2 (α) = θ3 (α), θ1 (α) = θ4 (α) and11θ2 (α) = θ4 (α). By solving these equalities, we find that√α = ±1 ± 2.
The expansions with these parameters are expected to provide generally large inner approximations for
n
S+
.

4

Cutting plane methods for the maximum stable set problem

Conic optimization problems, including SDPs and copositive programs, have been shown to provide tightbounds for NP-hard combinatorial and noconvex optimization problems. Here, we consider applyingnapproximations of S+
to one of those NP-hard problems, the maximum stable set problem. A stable setof a graph G(V, E) is a set of vertices in V , such that there is no edge connecting any pair of vertices inthe set. The maximum stable set problem aims to find the stability number, i.e. the number of verticesof the largest stable set of G, namely α(G).
De Klerk and Pasechnik [15] proposed a copositive programming formulation to obtain the exact stability
number of a graph G with n vertices:α(G) = max heeT , Xi
s.t. hA + I, Xi = 1,

(16)

X ∈ Cn∗ ,where e is the all-ones vector, A is the adjacency matrix of graph G, and Cn∗ is the dual cone of thecopositive cone Cn := {X ∈ Sn | dT Xd ≥ 0 ∀d ∈ Rn , d ≥ 0}.
Although problem (16) is a conic optimization problem, it is still difficult since determining whether
X ∈ Cn∗ or not is NP-hard [16]. A natural approach is to relax this problem to a more tractable
optimization problem. From the definition of each cone, we can see the validity of the following inclusions:nnnCn∗ ⊆ S+
∩ N n ⊆ S+
⊆ S+
+ N n ⊆ Cn .
n
By replacing Cn∗ with S+∩ N n , one can obtain an SDP relaxation of (16):max heeT , Xi
s.t. hA + I, Xi = 1,

(17)n
X ∈ S+∩ N n.

Solving this SDP is not as easy as it seems to be; in fact, we could not obtain a useful result of (17) after 6hours of calculation using the state-of-the-art SDP solver Mosek for a random generalized problem whenn = 300. Combining the expanded SD bases with the cutting plane method, we apply the approximationsnof S+
to (17) and solve it by calculating a series of more tractable problems.
nn
Let P n satisfy S+⊆ P n ⊆ Sn and replace X ∈ S+
by X ∈ P n in (17). Then, we obtain a relaxation of(17):

max heeT , Xi
s.t. hA + I, Xi = 1,
X ∈ P n ∩ N n.
12

(18)

Usually, the relaxed problem (18) is expected to be easier to solve and to give us a better upper boundof problem (17) from its optimal solution X ∗ . To get a better upper bound, we select some eigenvectors
with negative eigenvalues of an optimal solution X ∗ of problem (18), say d1 , .., dk , by adding cutting
planeshdi dTi , Xi ≥ 0(i = 1, .., k)to (18), and obtain a new optimization problem
max heeT , Xi
s.t. hA + I, Xi = 1,

(19)

hdi dTi , Xi ≥ 0 (i = 1, .., k)nnX ∈P ∩N .

Notice that the optimal solution X ∗ of problem (18) is cut from the feasible region of problem (19) sincen
hdi dTi , X ∗ i < 0 (i = 1, .., k). On the other hand, since S+= {X ∈ Sn | ∀d ∈ Rn , hddT , Xi ≥ 0} ⊆ P n ,every feasible solution of (17) is feasible for (19), and hence problem (19) is a relaxation of problem(17). These facts ensure that problem (19) is a tighter relaxation of problem (17) than problem (18).
By repeating this procedure, we are able to obtain a series of nonincreasing upper bounds of (17). Since
the eigenvectors are usually dense, we only have to add eigenvectors corresponding to up to the second
smallest eigenvalues to {di } at every iteration, which increases computational efficiency.
nbased onAs for the selection of the initial relaxation P n , we are ready to use the approximations of S+√
the expanded SD bases. Let H := {±1, ±1 ± 2} be the set of parameters calculated in Section 3.4, and
let SDB n denote the conical hull of expanded SD bases using H:!
[
SDB n := coneB̄(α) .
α∈H

Then, as has been described in the previous sections, we haven
S+
⊆ SDD∗n ⊆ SDB∗n ⊆ DD∗n .

(20)

If SDB ∗n or DD∗n is selected to be Pn , the corresponding relaxed problem in the cutting plane procedure
becomes an LP, which allows us to use powerful state-of-the-art LP solvers, such as Gurobi [21]. Ahmadi
et. al. [1] showed that when SDD∗n is selected, the relaxations turn out to be SOCPs. Although SDD∗nprovides a tighter relaxation than either DDn or SDB n , the latter two relaxations are expected to havea lower computational cost. In addition, in [1], Ahmadi et al. also proposed an SOCP-based cutting
plane approach, named SDSOS, which adds SOCP cuts at every iteration. We conducted experiments
to compare the efficiencies of those cutting plane methods using different approximations and SDSOS.
The specifications of the experimental methods are summarized in Table 4.
We tested these methods on the Erdös-Rényi graphs ER(n, p), randomly generated by Ahmadi et al.
in [1], where n is the number of vertices and every pair of vertices has an edge with probability p. All
experiments were performed with MATLAB 2018b on a Windows PC with an Intel(R) Core(TM) i7-6700
CPU running at 3.4 GHz and 16 GB of RAM. The LPs were solved using Gurobi Optimizer 8.0.0 [21]and the SOCPs and SDPs are solved using Mosek Optimizer 9.0 [35].
Fig. 2 shows the result for an instance with n = 250 and p = 0.8. The x-axis is the number of iterations,and the y-axis is the gap between the upper bounds of each method and the SDP bound obtained by13

Table 1: Specifications of the experimental methods
Number of cuts added at each iteration
MethodPn
SolverLP cutSOCP cut
CPDD
DD∗n
2
0
GurobiCPSDB SDB ∗n20
GurobiCPSDD SDD∗n
2
0
Mosek
SDSOS SDD∗n
2
1
Mosek

(17); the gap is computed byf ∗ −fk
f∗× 100% for the obtained upper bound fk at k’s iteration and the∗

SDP bound f obtained by solving (17) directly.
As can be seen in this figure, the accuracy of CPDD is the worst among the four methods at each
iteration. CPSDB achieves almost the same upper bounds as CPSDD and SDSOS, which shows thatthe proposed polyhedral approximation SDB n is promising for obtaining a solution close to the nonnpolyhedral approximation SDDn of S+. Although SDSOS adds an extra SOCP cut at every iterationand takes longer to solve, the accuracy of SDSOS does not seem to be affected and is not so different
from the accuracy of CPSDD at each iteration.

Figure 2: Relation between the number of iterations and the gap

Fig. 3 shows the relation between the computation time and the gap of each method for the same
instance. Although its accuracy is not necessarily the best at every iteration, it seems that CPSDB is
the most efficient method. CPSDB attains an upper bound whose gap is 2 within 30 s, while CPSDDand SDSOS attain upper bounds whose gap is 4 after the same amount of time. The difference mightcome from that the subproblems of CPSDB are sparse LPs at earlier iterations and the computations
are relatively cheaper than those of CPSDD and SDSOS whose subproblems are SOCPs.
Table 2 and 3 give the bounds of iterative methods and the SDP bound for all the instances. In Table
14

Figure 3: Relation between the computational time (s) and the gap

2, the CPSDD0 /SDSOS0 column shows the first upper bound obtained by CPSDD and SDSOS, i.e., theupper bound obtained by solving the same SOCP before adding any cutting plane. The (5 min) and(10 min) columns of CPSDD (SDSOS) show the upper bounds obtained after 5 minutes and after 10
minutes of the CPSDD (SDSOS) computation, respectively. The SDP column shows the SDP boundobtained by solving (17).
Similarly, in Table 3, the CPDD0 and CPSDB0 columns show the first upper bounds obtained by CPDD
and CPSDB, respectively, before adding any cutting plane. The (5 min) and (10 min) columns of CPDD
(CPSDB) show the upper bounds obtained after 5 minutes and after 10 minutes of the CPDD (CPSDB)
computation, respectively.
Note that we failed to solve SDPs (17) for instances having n = 300 nodes within our time limit 20000s.
In Table 2, the Value and Time (s) columns of SDP with n = 300 show the results obtained in [1] forthese two instances, as a reference.
As can be seen in Table 2 and 3, for all instances, the values of CPSDD0 /SDSOS0 are better thanthe values of CPSDB0 and CPDD0 . These results correspond to the inclusion relationship of initialapproximations (20). We can also see that the values of CPSDB0 are almost the same as those of
CPSDD0 /SDSOS0 for all instances, while the values of CPDD0 are much worse than others. For all
instances, CPSDB seems to be significantly more efficient than all other methods. For example, forinstance with n = 250 and p = 0.3, after 10 min of calculation, CPSDB obtained an upper bound of
73.24, while CPSDD and SDSOS got upper bounds greater than 90 and CPDD got a bound of morethan 146.
At present, solving a large SDP, e.g., one with more than n = 300 nodes requires a significant amountof computational time. The cutting plane method CPSDB with our polyhedral approximation SDB n is
a promising way of obtaining efficient upper bounds of such large SDPs in a moderate time.

15

n
150
150
200
200
250
250
300
300

Table 2: Upper bounds obtained by SDP and SOCP methods on ER(n, p) graphs
CPSDD0 /SDSOS0
CPSDD
SDSOS
SDP
p
Value
Time (s) (5 min) (10 min) (5 min) (10 min)Value
Time (s)0.3 105.70
0.95
38.91
37.02
40.97
37.38
20.44
105.46
0.8
31.78
1.00
10.07
9.66
9.70
9.31
6.00
110.630.3 140.47
3.14
70.48
55.52
75.46
61.31
23.73
549.63
0.8
40.92
3.14
12.10
11.29
12.17
11.38
6.45
497.55
0.3 176.25
6.60
115.41
93.81
119.6799.99
26.78
1562.52
0.8
51.87
6.79
17.36
15.30
17.43
15.39
7.18
1553.63
0.3 210.32
13.05
160.42138.60162.77143.12 (29.13) (32300.60)
0.8
60.97
13.31
21.71
17.77
22.66
18.50
(7.65) (20586.02)

n

p

150
150
200
200
250
250
300
300

0.3
0.8
0.3
0.8
0.3
0.8
0.3
0.8

5

Table 3: Upper bounds obtained by LP methods on the same ER(n, p) graphs
CPDD0
CPDD
CPSDB0CPSDB
Value Time (s) (5 min) (10 min)Value Time (s) (5 min) (10 min)
117
0.06
76.76
67.51 107.29
0.24
36.80
35.12
46
0.05
13.70
12.71
32.76
0.28
9.51
9.06
157
0.1
113.28104.07 142.25
0.52
55.07
48.18
54
0.11
17.39
16.07
42.14
0.57
11.58
11.00
194
0.17
154.75146.20 178.30
0.84
91.88
73.24
68
0.17
28.02
22.26
53.22
1.00
14.76
13.57
230
0.26
183.89174.02 212.97
1.29
133.83110.95
78
0.24
47.87
32.28
62.47
1.36
18.11
16.05

Concluding remarks

We developed techniques to construct a series of sparse polyhedral approximations of the semidefinite
cone. We provided a way to approximate the semidefinite cone by using SD bases and proved thatthe set of diagonally dominant matrices can be expressed with sparse SD bases. We proposed a simple
expansion of SD bases that keeps the sparsity of the matrices that compose it. We gave the conditions
for generating linearly independent matrices in expanded SD bases as well as for generating an expansion
different from the existing one. We showed that the polyhedral approximation using our expanded SD
bases contains the set of diagonally dominant matrices and is contained in the set of scaled diagonallydominant matrices. We also proved that the set of scaled diagonally dominant matrices can be expressedusing an infinite number of expanded SD bases.
The polyhedral approximations were applied to the cutting plane method for solving a semidefinite
relaxation of the maximum stable set problem. The results of the numerical experiments showed thatthe method with our expanded SD bases is more efficient than other methods (see Fig. 3); improving
the efficiency of our method still remains an important study issue.
One future direction of study is to increase the number of vectors in the definition of the SD bases.
The current SD bases are defined as a set of matrices (ei + ej )(ei + ej )T . If we use three vectors, as in(ei + ej + ek )(ei + ej + ek )T , we might obtain another inner approximation that remains relatively sparsewhen the dimension n is large.
Another future direction is to focus on the factor width k of a matrix. The cone of matrices with factor
width at most k = 2 was introduced in order to give another expression of the set SDDn of scaled16

diagonally dominant matrices. By considering a larger width k > 2, we may obtain a larger innernapproximation of the semidefinite cone S+, although it would not be polyhedral, or even characterized
by using SOCP constraints. Finding efficient ways to solve approximation problems over such cones
might be an interesting challenge.
Also, our expanded SD bases can be applied to some other difficult problems. Mixed integer nonlinear
programming has recently become popular in many practical applications. In [33], Lubin et al. proposeda cutting plane framework for mixed integer convex optimization problems. In [26], Kobayashi and
Takano proposed a branch and bound cutting plane method for mixed integer SDPs. It would beninteresting to see whether the approximations of S+
proposed in this paper could be used to improvethe efficiency of those methods.

Acknowledgments
The authors would like to sincerely thank the anonymous reviewers for their thoughtful and valuablecomments which have significantly improved the paper. Among others, one of the reviewers pointed
out Remark 2.9 which helped the authors to simplify the presentation of the paper. This research was
supported by the Japan Society for the Promotion of Science through a Grant-in-Aid for Challenging
Exploratory Research (17K18946) and a Grant-in-Aid for Scientific Research ((B)19H02373) from the
Ministry of Education, Culture, Sports, Science and Technology of Japan.

References[1] A. A. Ahmadi, S. Dash, and G. Hall, Optimization over structured subsets of positive semidefinite matrices via column generation, Discrete Optimization, 24 (2017), pp. 129–151.
[2] A. A. Ahmadi and A. Majumdar, DSOS and SDSOS optimization: more tractable alternatives
to sum of squares and semidefinite optimization, SIAM Journal on Applied Algebra and Geometry,
3 (2019), pp. 193–230.
[3] N. Arima, S. Kim, and M. Kojima, A quadratically constrained quadratic optimization model forcompletely positive cone programming, SIAM Journal on Optimization, 23 (2013), pp. 2320–2340.
[4] N. Arima, S. Kim, M. Kojima, and K.-C. Toh, A robust Lagrangian-DNN method for a class ofquadratic optimization problems, Computational Optimization and Applications, 66 (2017), pp. 453–
479.
[5] N. Arima, S. Kim, M. Kojima, and K.-C. Toh, Lagrangian-conic relaxations, part i: A unified
framework and its applications to quadratic optimization problems, Pacific Journal of Optimization,
14 (2018), pp. 161–192.
[6] G. Barker and D. Carlson, Cones of diagonally dominant matrices, Pacific Journal of Mathematics, 57 (1975), pp. 15–32.
[7] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, vol. 9,Siam, 1994.
[8] L. Bishan, L. Lei, M. Harada, H. Niki, and M. J. Tsatsomeros, An iterative criterion for
H-matrices, Linear Algebra and Its Applications, 271 (1998), pp. 179–190.

17

[9] G. Blekherman, P. A. Parrilo, and R. R. Thomas, Semidefinite Optimization and Convex
Algebraic Geometry, SIAM, 2012.
[10] E. G. Boman, D. Chen, O. Parekh, and S. Toledo, On factor width and symmetric Hmatrices, Linear Algebra and Its Applications, 405 (2005), pp. 239–248.
[11] S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,
Mathematical Programming, 120 (2009), pp. 479–495.
[12] S. Burer and R. D. C. Monteiro, A projected gradient algorithm for solving the maxcut SDP
relaxation, Optimization Methods and Software, 15 (2001), pp. 175–200.
[13] G. Dantzig, R. Fulkerson, and S. Johnson, Solution of a large-scale traveling-salesman problem, Journal of the Operations Research Society of America, 2 (1954), pp. 393–410.
[14] G. B. Dantzig, D. R. Fulkerson, and S. M. Johnson, On a linear-programming, combinatorial
approach to the traveling-salesman problem, Operations Research, 7 (1959), pp. 58–66.
[15] E. De Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via
copositive programming, SIAM Journal on Optimization, 12 (2002), pp. 875–892.
[16] P. J. Dickinson and L. Gijben, On the computational complexity of membership problems forthe completely positive cone and its dual, Computational Optimization and Applications, 57 (2014),
pp. 403–415.
[17] M. Dür, Copositive programming–a survey, in Recent Advances in Optimization and Its Applications in Engineering, Springer, 2010, pp. 3–20.
[18] S. A. Geršgorin, Über die abgrenzung der eigenwerte einer matrix, Bulletin de l’Académie desSciences de l’URSS. Classe des Sciences Mathématiques et na, 6 (1931), pp. 749–754.
[19] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum
cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42 (1995),
pp. 1115–1145.
[20] R. E. Gomory, Outline of an algorithm for integer solutions to linear programs, Bulletin of theAmerican Mathematical Society, 64 (1958), pp. 275–278.
[21] L. Gurobi Optimization,
Gurobi optimizer reference
http://www.gurobi.com, 2018, [Accessed: 2018-11-20].

manual.

Available

at[22] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge university press, 1990.
[23] S. E. Karisch and F. Rendl, Semidefinite programming and graph equipartition, Topics in
Semidefinite and Interior-Point Methods, 18 (1998), pp. 77–95.
[24] S. Kim and M. Kojima, Exact solutions of some nonconvex quadratic optimization problems via
SDP and SOCP relaxations, Computational Optimization and Applications, 26 (2003), pp. 143–154.
[25] S. Kim, M. Kojima, and K.-C. Toh, A lagrangian–DNN relaxation: a fast method for computing
tight lower bounds for a class of quadratic optimization problems, Mathematical Programming, 156(2016), pp. 161–187.
[26] K. Kobayashi and Y. Takano, A branch-and-cut algorithm for solving mixed-integer semidefinite
optimization problems, Computational Optimization and Applications, 75 (2020), pp. 493–513.

18

[27] H. Konno, J.-y. Gotoh, T. Uno, and A. Yuki, A cutting plane algorithm for semi-definite
programming problems with applications to failure discriminant analysis, Journal of Computationaland Applied Mathematics, 146 (2002), pp. 141–154.
[28] K. Krishnan, Linear programming approach to semidefinite programming problems, PhD thesis,
Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, 2002.
[29] K. Krishnan and J. E. Mitchell, A semidefinite programming based polyhedral cut and priceapproach for the maxcut problem, Computational Optimization and Applications, 33 (2006), pp. 51–
71.
[30] K. Krishnan and J. E. Mitchell, A unifying framework for several cutting plane methods forsemidefinite programming, Optimization Methods and Software, 21 (2006), pp. 57–74.
[31] J. B. Lasserre, An explicit exact SDP relaxation for nonlinear 0-1 programs, in Integer Programming and Combinatorial Optimization, K. Aardal and B. Gerards, eds., Berlin, Heidelberg, 2001,
Springer Berlin Heidelberg, pp. 293–303.
[32] M. Laurent and F. Vallentin, Semidefinite optimization. Lecture Notes, available at
http://page. mi. fu-berlin.de/fmario/sdp/laurentv. pdf, 2012, [Accessed: 2018-11-20].
[33] M. Lubin, E. Yamangil, R. Bent and J. P.Vielma, Polyhedral approximation in mixed-integer
convex optimization, Mathematical Programming, 172.1-2 (2018), pp. 139–168.
[34] H. Minkowski, Geometrie der Zahlen, Leipzig : Teubner, 1896.
[35] MOSEK ApS, The MOSEK optimization toolbox for MATLAB manual. Version 8.1., available at
http://docs.mosek.com/8.1/toolbox/index.html,2017, [Accessed: 2019-10-1][36] K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39 (1987), pp. 117–129.
[37] F. Permenter and P. Parrilo, Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone, Mathematical Programming, (2014), pp. 1–54.
[38] F. Permenter and P. A. Parrilo, Basis selection for SOS programs via facial reduction andpolyhedral approximations, in 53rd IEEE Conference on Decision and Control, Dec 2014, pp. 6615–
6620.
[39] A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, 1998.
[40] J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,
Optimization Methods and Software, 11 (1999), pp. 625–653.
[41] A. Tanaka and A. Yoshise, LP-based tractable subcones of the semidefinite plus nonnegativecone, Annals of Operations Research, 265 (2018), pp. 155–182.
[42] M. J. Todd, Semidefinite optimization, Acta Numerica, 10 (2001), pp. 515–560.
[43] K.-C. Toh, M. J. Todd, and R. H. Tütüncü, SDPT3—a MATLAB software package forsemidefinite programming, version 1.3, Optimization Methods and Software, 11 (1999), pp. 545–
581.
[44] H. Waki and M. Muramatsu, Facial reduction algorithms for conic optimization problems, Journal of Optimization Theory and Applications, 158 (2013), pp. 188–215.
[45] H. Weyl, Elementare theorie der konvexen polyeder, Commentarii Mathematici Helvetici, 7 (1935),
pp. 290–306.
19[46] H. Wolkowicz, R. Saigal, and L. Vandenberghe, Handbook of Semidefinite Programming:
Theory, Algorithms, and Applications, vol. 27, Springer Science & Business Media, 2012.
[47] M. Yamashita, K. Fujisawa, and M. Kojima, Implementation and evaluation of SDPA
6.0 (Semidefinite Programming Algorithm 6.0), Optimization Methods and Software, 18 (2003),
pp. 491–505.

20