Show that sublevel set $C$ is convex if $A \succcurlyeq 0$

Question

Let $C \subseteq \mathbb{R}^n$ be the solution set of a quadratic inequality,

$$ C = \{ x \in \mathbb{R}^n \mid x^TAx + b^Tx + c \le 0 \}$$

with $A \in \mathbb{R}^{n \times n}$ and $b \in \mathbb{R}^n$. Show that $C$ is convex if $A \succcurlyeq 0$

How does one prove it for the general case? I would think we would need to use the general definition of convexity somehow: if $\theta x_1 + (1-\theta)x_2 \in C$ where $\theta \in [0,1]$ and $x_1,x_2 \in C$ then $C$ is convex. But I don't know how to apply this.

Are you sure you did not mean $A \ge 0$? Take $n=1, A=-1, b=0, c=1$ to see that $C$ is not convex with $A \le 0$. — copper.hat, Sep 23 '19 at 15:13
The function $f(x) = x^TAx+b^Tx+c$ is convex, hence the level sets are convex. — copper.hat, Sep 23 '19 at 15:20
@copper.hat I agree that once we know it is convex, the level sets are convex. But I am not sure how to prove $x^TAx + b^Tx + c$ is convex. — CEP, Sep 23 '19 at 15:24
$x \mapsto b^Tx$ is linear, hence convex. The Hessian of $x \mapsto x^TAx$ is $A$ which is psd hence convex. The sum of convex functions is convex. — copper.hat, Sep 23 '19 at 15:38

Rodrigo de Azevedo · Answer 1 · 2020-07-11T18:12:14.573

If $\mathrm A \succeq \mathrm O_n$, then there exists an $n \times r$ matrix $\rm Q$ such that $\rm A = Q Q^\top$, where $r = \mbox{rank} (\rm A)$. Hence,

$$\mathrm x^\top \mathrm A \,\mathrm x + \mathrm b^\top \mathrm x + c = \mathrm x^\top \mathrm Q \mathrm Q^\top \mathrm x + \mathrm b^\top \mathrm x + c \leq 0$$

Using the Schur complement, the quadratic inequality above can be rewritten as the following linear matrix inequality (LMI)

$$\begin{bmatrix} \mathrm I_r & \mathrm Q^\top \mathrm x \\ \mathrm x^{\top} \mathrm Q & - c - \mathrm b^{\top} \mathrm x\end{bmatrix} \succeq \mathrm O_{r+1}$$

whose solution set is a spectrahedron and, thus, convex.

convex-analysis schur-complement linear-matrix-inequality spectrahedra

Show that sublevel set $C$ is convex if $A \succcurlyeq 0$

1 Answers1

Linked