Appendix A
Semidefinite Optimization and Conic
Optimization
Semidefinite optimization (SDO) is the class of optimization problems in which
we seek to maximize or minimize a linear function of the elements of a matrix
variable subject to linear constraints on those elements, together with a constraint
that the entire matrix must be symmetric positive semidefinite (PSD). The PSD
condition is equivalent to requiring that all the eigenvalues of the matrix must be
greater than or equal to zero. LO is a special case of SDO that corresponds to the
matrix variable being a diagonal matrix, i.e., a matrix with all the elements off the
main diagonal equal to zero. Another special case of SDO is second-order conic
optimization (SOCO), which corresponds to optimizing over the second-order cone
(see Sect. A.2).
SDO problems are important because they are solvable in polynomial time (see
Sect. 2.1.1), so any problem that can be expressed using SDO is also solvable in
polynomial time. Moreover, SDO problems can be solved efficiently in practice, by
using an available software package or implementing a specialized algorithm.
SDO has a number of similarities with LO. Like LO problems, SDO problems
come in pairs. One of the problems is referred to as the primal, and the other is the
dual. Either problem can be chosen as the primal, since the two problems are dual
to each other. The most common standard formulation of SDO is as follows:
(P) min C, X
(D) max b T y
s.t. A i , X = b i , i = 1, . . . , m
s.t.
m
i=1
y i A i + S = C
X 0
S 0
(A.1)
where (P) denotes the primal and (D) the dual. The variables X and S are in S n , the
space of n×n real symmetric matrices; X 0 indicates that the matrix X is positive
semidefinite; the data matrices A i ∈ S n and C ∈ S n may be assumed without loss
© Springer Nature Switzerland AG 2021
M. F. Anjos, M. V. C. Vieira, Facility Layout, EURO Advanced Tutorials
on Operational Research, https://doi.org/10.1007/978-3-030-70990-7
109
Semidefinite Optimization and Conic
Optimization
Semidefinite optimization (SDO) is the class of optimization problems in which
we seek to maximize or minimize a linear function of the elements of a matrix
variable subject to linear constraints on those elements, together with a constraint
that the entire matrix must be symmetric positive semidefinite (PSD). The PSD
condition is equivalent to requiring that all the eigenvalues of the matrix must be
greater than or equal to zero. LO is a special case of SDO that corresponds to the
matrix variable being a diagonal matrix, i.e., a matrix with all the elements off the
main diagonal equal to zero. Another special case of SDO is second-order conic
optimization (SOCO), which corresponds to optimizing over the second-order cone
(see Sect. A.2).
SDO problems are important because they are solvable in polynomial time (see
Sect. 2.1.1), so any problem that can be expressed using SDO is also solvable in
polynomial time. Moreover, SDO problems can be solved efficiently in practice, by
using an available software package or implementing a specialized algorithm.
SDO has a number of similarities with LO. Like LO problems, SDO problems
come in pairs. One of the problems is referred to as the primal, and the other is the
dual. Either problem can be chosen as the primal, since the two problems are dual
to each other. The most common standard formulation of SDO is as follows:
(P) min C, X
(D) max b T y
s.t. A i , X = b i , i = 1, . . . , m
s.t.
m
i=1
y i A i + S = C
X 0
S 0
(A.1)
where (P) denotes the primal and (D) the dual. The variables X and S are in S n , the
space of n×n real symmetric matrices; X 0 indicates that the matrix X is positive
semidefinite; the data matrices A i ∈ S n and C ∈ S n may be assumed without loss
© Springer Nature Switzerland AG 2021
M. F. Anjos, M. V. C. Vieira, Facility Layout, EURO Advanced Tutorials
on Operational Research, https://doi.org/10.1007/978-3-030-70990-7
109