Convex Optimization · Problem 4.39

Duality — Boyd & Vandenberghe

Mathematics — Optimization · sdps-congruence-transformations

Problem

SDPs and congruence transformations. Consider the SDP

\begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & x_1 F_1 + x_2 F_2 + \cdots + x_n F_n + G \preceq 0, \end{array}

with

F_i, G \in \mathbf{S}^k

c \in \mathbf{R}^n

. (a) Suppose

R \in \mathbf{R}^{k \times k}

is nonsingular. Show that the SDP is equivalent to the SDP

\begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & x_1 \tilde{F}_1 + x_2 \tilde{F}_2 + \cdots + x_n \tilde{F}_n + \tilde{G} \preceq 0, \end{array}

where

\tilde{F}_i = R^T F_i R

\tilde{G} = R^T G R

. (b) Suppose there exists a nonsingular

R

such that

\tilde{F}_i

and

\tilde{G}

are diagonal. Show that the SDP is equivalent to an LP. (c) Suppose there exists a nonsingular

R

such that

\tilde{F}_i

and

\tilde{G}

have the form

\tilde{F}_i = \left[ \begin{array}{cc} \alpha_i I & a_i \\ a_i^T & \alpha_i \end{array} \right], \quad i = 1, \ldots, n, \qquad \tilde{G} = \left[ \begin{array}{cc} \beta I & b \\ b^T & \beta \end{array} \right],

where

\alpha_i, \beta \in \mathbf{R}

a_i, b \in \mathbf{R}^{k-1}

. Show that the SDP is equivalent to an SOCP with a single second-order cone constraint.