110
A Semidefinite Optimization and Conic Optimization
of generality to be symmetric; and b ∈ R m and y ∈ R m are column vectors. We use
the inner product between two matrices in S n defined as
R, S := trace(RS) =
n
i=1
n
j =1
R ij S ij
where trace (M) denotes the trace of the square matrix M, which is the sum of its
diagonal elements. It is usually assumed, without loss of generality, that the matrices
A i , i = 1, . . . , m, are linearly independent.
The dual SDO problem in (A.1) can equivalently be written without using the
dual variable S:
max b T y
s.t. C −
m
i=1
y i A i 0,
where the inequality constraint is interpreted as follows:
A − B 0 ⇔ A B.
A.1 Positive Semidefinite Matrices
Positive semidefinite matrices have numerous properties. For a 2 × 2 symmetric
matrix, the necessary and sufficient conditions for positive semidefiniteness are
x 11 x 12
x 12 x 22
0 ⇔ x 11 ≥ 0, x 22 ≥ 0, and x 11 x 22 − x
2
12 ≥ 0.
(A.2)
This is a special case of Theorem A.1 below. To state the theorem, we need the
following definition.
Definition A.1 If X ∈ S n , then for every nonempty subset I ⊆ {1, 2, . . . , n},
the principal submatrix of X corresponding to I , denoted by X(I ), is the square
submatrix with rows and columns indexed by I . The determinant of X(I ) is called
the principal minor of X corresponding to I .
Theorem A.1 For X ∈ S n , X is PSD if and only if all the principal minors of X
are non-negative.
Example A.1 An important example of an SDO problem is
min C, X
s.t. x ii = 1, i = 1, . . . , n
X 0.
(A.3)
A Semidefinite Optimization and Conic Optimization
of generality to be symmetric; and b ∈ R m and y ∈ R m are column vectors. We use
the inner product between two matrices in S n defined as
R, S := trace(RS) =
n
i=1
n
j =1
R ij S ij
where trace (M) denotes the trace of the square matrix M, which is the sum of its
diagonal elements. It is usually assumed, without loss of generality, that the matrices
A i , i = 1, . . . , m, are linearly independent.
The dual SDO problem in (A.1) can equivalently be written without using the
dual variable S:
max b T y
s.t. C −
m
i=1
y i A i 0,
where the inequality constraint is interpreted as follows:
A − B 0 ⇔ A B.
A.1 Positive Semidefinite Matrices
Positive semidefinite matrices have numerous properties. For a 2 × 2 symmetric
matrix, the necessary and sufficient conditions for positive semidefiniteness are
x 11 x 12
x 12 x 22
0 ⇔ x 11 ≥ 0, x 22 ≥ 0, and x 11 x 22 − x
2
12 ≥ 0.
(A.2)
This is a special case of Theorem A.1 below. To state the theorem, we need the
following definition.
Definition A.1 If X ∈ S n , then for every nonempty subset I ⊆ {1, 2, . . . , n},
the principal submatrix of X corresponding to I , denoted by X(I ), is the square
submatrix with rows and columns indexed by I . The determinant of X(I ) is called
the principal minor of X corresponding to I .
Theorem A.1 For X ∈ S n , X is PSD if and only if all the principal minors of X
are non-negative.
Example A.1 An important example of an SDO problem is
min C, X
s.t. x ii = 1, i = 1, . . . , n
X 0.
(A.3)