Brickman's Theorem and a Generalization

Kevin Shu

Quadratically Constrained Quadratic Programs

\max\quad x^{\intercal}Cx
\dots
x^{\intercal}A_1x = b_1
x^{\intercal}A_mx = b_m
\text{s.t.}

Quadratically Constrained Quadratic Programs

\max\quad x^{\intercal}Cx
\dots
x^{\intercal}A_1x = b_1
x^{\intercal}A_mx = b_m
\text{s.t.}
\max\quad \langle C, X \rangle
\dots
\langle A_1, X\rangle = b_1
\langle A_m, X\rangle = b_m
\text{s.t.}
X \succeq 0
\le

Quadratically Constrained Quadratic Programs

\max\quad x^{\intercal}Cx
\dots
x^{\intercal}A_1x = b_1
x^{\intercal}A_mx = b_m
\text{s.t.}
\max\quad \langle C, X \rangle
\dots
\langle A_1, X\rangle = b_1
\langle A_m, X\rangle = b_m
\text{s.t.}
X \succeq 0
\le

Shor Relaxation

S Lemma

\max\quad x^{\intercal}Cx
x^{\intercal}A_1x = b_1
\text{s.t.}
\max\quad \langle C, X \rangle
\langle A_1, X\rangle = b_1
\text{s.t.}
X \succeq 0
=

For one constraint, the Shor relaxation is tight.

2 Constraints

\max\quad x^{\intercal}Cx
x^{\intercal}A_1x = b_1
\text{s.t.}
\max\quad \langle C, X \rangle
\langle A_1, X\rangle = b_1
\text{s.t.}
X \succeq 0
=
\text{If }A_1 \text{ is positive definite, then}
x^{\intercal}A_2x = b_2
\langle A_2, X\rangle = b_2

Brickman's Theorem

\text{Let }S^n = \{x \in \R^{n+1} : \|x\|_2 = 1\}\text{ for }n > 2.
\text{Let }Q:\R^{n+1} \rightarrow \R^2 \text{ be a homogeneous}
\text{quadratic map.}
\text{Then }Q(S^n)\text{ is convex.}

The image of a circle under a homogeneous quadratic map is an ellipse.

We need to show that between any two points in          ,the line segment between them is contained in the image.

Q(S^n)

We need to show that between any two points in          ,the line segment between them is contained in the image.

Q(S^n)

Consider the great circle containing x and y.

Contract the great circle to a point and watch what happens to its image.

\text{Let }\text{SO}(n) = \{X \in \R^{n\times n} : X^{\intercal}X = I,\;\det(X) = 1\}.
\text{Let }T:\R^{n\times n} \rightarrow \R^2 \text{ be linear}.
\text{Then for }n > 2,T(\text{SO}(n))\text{ is convex.}