112
A Semidefinite Optimization and Conic Optimization
general, SOCO is not equivalent to LO. For instance, it is straightforward to verify
that a 2 × 2 PSD constraint is equivalent to a 3-dimensional SOC constraint:
x 11 x 12
x 12 x 22
0 ⇔ x 11 x 22 ≥ x
2
12 and x 11 , x 22 ≥ 0 ⇔
⎛
⎝
x 11 + x 22
x 11 − x 22
2x 12
⎞
⎠ ∈ SOC
3 .
(A.4)
This result can be proved using basic algebra, and it is left as an exercise for the
reader.
The SOCO primal–dual pair has the form:
(P SOC ) inf
j =1
c T
j x j
(D SOC ) sup b T y
s.t.
j =1
A j x j = b,
s.t. A T
j y + s j = c j , j = 1, . . . , ,
x j ∈ SOC
n j +1 , j = 1, . . . , ,
s j ∈ SOC
n j +1 , j = 1, . . . , ,
(A.5)
where is the number of SOCs.
SOCO is a special case of SDO in the sense that
(x 0 , x 1 , . . . , x n ) ∈ SOC
n+1
⇔
⎛
⎜
⎜
⎜
⎜
⎜
⎝
x 0 0 0 0 x 1
0 x 0 0 0 x 2
0 0
. . . 0
. . .
0 0 0 x 0 x n
x 1 x 2 · · · x n x 0
⎞
⎟
⎟
⎟
⎟
⎟
⎠
0.
(A.6)
While (A.4) can be checked easily, this more general statement about SOCs requires
more advanced matrix theory (see Sect. A.3).
The equivalence (A.6) makes it possible in principle to solve SOCO problems by
converting them to SDO problems. However, this is much less efficient than making
use of the SOC structure.
A.3 References and Further Reading
Conic optimization is a thriving research area, and this Appendix merely scratches
the surface of this large and growing field. A more detailed introduction to SDO,
including a discussion on the software available for SOCO and SDO problems, can
be found in Anjos (2017). A wealth of results about PSD matrices can be found
in Chapter 7 of Horn and Johnson (1990), including the statement and proof of
A Semidefinite Optimization and Conic Optimization
general, SOCO is not equivalent to LO. For instance, it is straightforward to verify
that a 2 × 2 PSD constraint is equivalent to a 3-dimensional SOC constraint:
x 11 x 12
x 12 x 22
0 ⇔ x 11 x 22 ≥ x
2
12 and x 11 , x 22 ≥ 0 ⇔
⎛
⎝
x 11 + x 22
x 11 − x 22
2x 12
⎞
⎠ ∈ SOC
3 .
(A.4)
This result can be proved using basic algebra, and it is left as an exercise for the
reader.
The SOCO primal–dual pair has the form:
(P SOC ) inf
j =1
c T
j x j
(D SOC ) sup b T y
s.t.
j =1
A j x j = b,
s.t. A T
j y + s j = c j , j = 1, . . . , ,
x j ∈ SOC
n j +1 , j = 1, . . . , ,
s j ∈ SOC
n j +1 , j = 1, . . . , ,
(A.5)
where is the number of SOCs.
SOCO is a special case of SDO in the sense that
(x 0 , x 1 , . . . , x n ) ∈ SOC
n+1
⇔
⎛
⎜
⎜
⎜
⎜
⎜
⎝
x 0 0 0 0 x 1
0 x 0 0 0 x 2
0 0
. . . 0
. . .
0 0 0 x 0 x n
x 1 x 2 · · · x n x 0
⎞
⎟
⎟
⎟
⎟
⎟
⎠
0.
(A.6)
While (A.4) can be checked easily, this more general statement about SOCs requires
more advanced matrix theory (see Sect. A.3).
The equivalence (A.6) makes it possible in principle to solve SOCO problems by
converting them to SDO problems. However, this is much less efficient than making
use of the SOC structure.
A.3 References and Further Reading
Conic optimization is a thriving research area, and this Appendix merely scratches
the surface of this large and growing field. A more detailed introduction to SDO,
including a discussion on the software available for SOCO and SDO problems, can
be found in Anjos (2017). A wealth of results about PSD matrices can be found
in Chapter 7 of Horn and Johnson (1990), including the statement and proof of