3

Let C $\subseteq$ $\Re^n$ be the solution set of a quadrtatic inequality, C = $\{x \in \Re^n | x^TAx +b^Tx + c \leq 0\}$. $A \in \Re$, b $\in \Re^n$ and c $\in \Re$. We want to show:

  • That C is convex if A $\succeq$ 0.

For the first part we use the trick that the a set is convex if and only if its intersection with an arbitrary line $\{x+tv| t \in \Re\}$ is convex. If we substitude the line equation in the quandratic formula ($x^TAx +b^Tx + c$) we end up with:$\{x+tv| at^2 + bt +c \leq 0\}$ with $\alpha$ = $v^TAv$, $\beta$ = $b^tv+2x^tAv$ and $\gamma = c + b^Tx + x^TAx$.

I have readen that the later set is convex if $ a \geq 0$. Why is that true?

Thank you!!

Thoth
  • 863

1 Answers1

4

Consider the curve $v = v(u) = au^2 + bu + c$ where the $u$-axis is oriented to the right, and the $v$-axis is oriented upwards. Then, for $a > 0$ this curve is a parabola which is open towards $+\infty$. So the set $S = \{u | v(u) \leq 0\}$, that is the set of all values $u$ such that $(u,v(u))$ is below the $u$-axis, is a bounded interval. So $S$ is a convex set, as desired. In the case $a=0$, $S$ is of the form $[w,+\infty)$ or $(-\infty,w]$ for an appropriate value $w$, or $S = \mathbb R$. So $S$ is convex also in this case ($S=\emptyset$ is not interesting, because that means that the line doesn't intersect $C$. Finally, in the case $a<0$, the curve $v=v(u)$ is a parabola which is open towards $-\infty$. So $S$ (if not empty) consists of two disjoint intervals $(-\infty,r]$ and $[s,+\infty)$ for appropriate values $r$ and $s$. Thus, $S$ is not convex in this case.

jflipp
  • 4,786