0
$\begingroup$

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

This is one of the problem of Convex Optimization. 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.

$\endgroup$
  • $\begingroup$ Which "Convex Optimization book" is it exactly ? There are plenty of such books. $\endgroup$ – Gabriel Romon May 4 '18 at 9:10
  • $\begingroup$ Its convex optimization book by Stephen Boyd. $\endgroup$ – Frank Moses May 4 '18 at 9:11
  • $\begingroup$ Group the terms related to the affine part and those related to the quadratic part. Then use the fact that $A \geq 0$. $\endgroup$ – LinAlg May 4 '18 at 11:32
2
$\begingroup$

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) $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ how can you not have a term with $\lambda_1^2$? $\endgroup$ – LinAlg May 4 '18 at 11:29
  • $\begingroup$ @LinAlg On the right-hand side $x_1^TAx_1$ appears with coefficient $\lambda_1-\lambda_1\lambda_2=\lambda_1^2$. And I implicitly assumed $A$ is symmetric. $\endgroup$ – Michal Adamaszek May 4 '18 at 11:38
  • $\begingroup$ Thank you for your answer. I think even if we do not assume $A$ to be symmetric the right side of your equation matches perfectly with my equation. But I do not know which steps you took to obtain the right side of your equation from my equation. $\endgroup$ – Frank Moses May 8 '18 at 2:38
  • $\begingroup$ @FrankMoses I just tied to group the terms the best I could. $\endgroup$ – Michal Adamaszek May 8 '18 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.