Boyd & Vandenberghe, problem 2.10 — sublevel set of quadratic is convex

900 Views Asked by At

Problem 2.10 of Boyd & Vandenberghe's Convex Optimization:


Let $C \subseteq \Re^n$ be the solution set of a quadratic inequality, $$C = \left\{ x \in \Re^n \mid x^TAx +b^Tx + c \leq 0 \right\}$$ where $A \in \Re^{n \times n}$, b $\in \Re^n$ and c $\in \Re$. We want to show that $C$ is convex if $A \succeq 0$.


The solution is provided. But I want to prove it through another way in which we assume that if $x_1$ and $x_2$ are in the set then for $0\leq \lambda\leq1$ the point $\lambda x_1+(1-\lambda)x_2$ is also in the set.

I tried it and I end up with following equation $$\lambda^2x_1^TAx_1+\lambda x_1^TAx_2-\lambda^2 x_1^TAx_2+\lambda x_2^TAx_1-\lambda^2 x_2^TAx_1+(1-\lambda)^2x_2^TAx_2+b^T\lambda x_1+(1-\lambda)b^Tx_2+c$$ I do not know how to show that the above quantity is less than or equal to zero. Any help in this regard will be much appreciated. Thanks in advance.

1

There are 1 best solutions below

4
On BEST ANSWER

If $f(x)=x^TAx+b^Tx+c$ and $\lambda_1+\lambda_2=1$ then I think

$$ f(\lambda_1x_1+\lambda_2x_2) = \lambda_1f(x_1)+\lambda_2f(x_2)-\lambda_1\lambda_2(x_1-x_2)^TA(x_1-x_2) $$