A Semidefinite Optimization and Conic Optimization
111
This SDO problem is particularly relevant in facility layout. Its feasible set is the set
of all symmetric matrices n × n that are PSD and have ones on the diagonal. Note
that Theorem A.1 implies that x 2
ij ≤ 1 holds for every off-diagonal element of X
feasible for (A.3). To see why this is true, consider the 2 × 2 principal submatrix
X({1, 2}) and apply (A.2):
x ii x ij
x ij x jj
0 ⇒ x ii x jj − x
2
ij ≥ 0 ⇔ x
2
ij ≤ 1
because x ii = 1 and x jj = 1.
A useful characterization of PSD matrices is the following:
Theorem A.2 An n × n symmetric matrix X is PSD if and only if y T X y ≥ 0 for
all vectors y ∈ ∈ n .
We can use this theorem to show that the matrices Γ = g g T defined by equation
(2.61) in Sect. 2.7 are PSD for any choice of g. This is because for any vector y:
y
T Γ y = y
T g g
T y = (g
T y)
2
≥ 0.
A.2 Second-Order Conic Optimization
The (n + 1)-dimensional second-order cone (SOC) is defined as
SOC
n+1
=
(x 0 , x 1 , . . . , x n ) ∈ R
n+1
| x 0 ≥
x 2
1 + . . . + x 2
n
.
An equivalent expression can be given in the form of a rotated quadratic cone:
SOC
n+1
=
(x 0 , x 1 , . . . , x n ) ∈ R
n+1
| 2x 0 x 1 ≥ x
2
2 + . . . + x
2
n , x 0 ≥ 0, x 1 ≥ 0
.
Mathematically, the latter is a rotation of the former through an angle of 45 degrees
in the (x 0 , x 1 )-plane, and for modelling purposes the rotated form is often more
convenient.
A non-negativity constraint x 0 ≥ 0 is just a SOC constraint in a space of
dimension 1 (n = 0); hence, LO is a special case of SOCO. For dimension 2, the
SOC can be expressed as
SOC
2
=
(x 0 , x 1 ) ∈ R
2
| x 0 ≥ |x 1 |
,
which is a rotated non-negative quadrant; hence, SOCO in dimension 2 is also a
LO problem. For dimensions 3 and greater, the SOC is not polyhedral, and hence in
111
This SDO problem is particularly relevant in facility layout. Its feasible set is the set
of all symmetric matrices n × n that are PSD and have ones on the diagonal. Note
that Theorem A.1 implies that x 2
ij ≤ 1 holds for every off-diagonal element of X
feasible for (A.3). To see why this is true, consider the 2 × 2 principal submatrix
X({1, 2}) and apply (A.2):
x ii x ij
x ij x jj
0 ⇒ x ii x jj − x
2
ij ≥ 0 ⇔ x
2
ij ≤ 1
because x ii = 1 and x jj = 1.
A useful characterization of PSD matrices is the following:
Theorem A.2 An n × n symmetric matrix X is PSD if and only if y T X y ≥ 0 for
all vectors y ∈ ∈ n .
We can use this theorem to show that the matrices Γ = g g T defined by equation
(2.61) in Sect. 2.7 are PSD for any choice of g. This is because for any vector y:
y
T Γ y = y
T g g
T y = (g
T y)
2
≥ 0.
A.2 Second-Order Conic Optimization
The (n + 1)-dimensional second-order cone (SOC) is defined as
SOC
n+1
=
(x 0 , x 1 , . . . , x n ) ∈ R
n+1
| x 0 ≥
x 2
1 + . . . + x 2
n
.
An equivalent expression can be given in the form of a rotated quadratic cone:
SOC
n+1
=
(x 0 , x 1 , . . . , x n ) ∈ R
n+1
| 2x 0 x 1 ≥ x
2
2 + . . . + x
2
n , x 0 ≥ 0, x 1 ≥ 0
.
Mathematically, the latter is a rotation of the former through an angle of 45 degrees
in the (x 0 , x 1 )-plane, and for modelling purposes the rotated form is often more
convenient.
A non-negativity constraint x 0 ≥ 0 is just a SOC constraint in a space of
dimension 1 (n = 0); hence, LO is a special case of SOCO. For dimension 2, the
SOC can be expressed as
SOC
2
=
(x 0 , x 1 ) ∈ R
2
| x 0 ≥ |x 1 |
,
which is a rotated non-negative quadrant; hence, SOCO in dimension 2 is also a
LO problem. For dimensions 3 and greater, the SOC is not polyhedral, and hence in