3
$\begingroup$

Solving an inequality of the form $x^TAx\geq0$ or $x^TAx\leq0$ is straightforward. I mean we have to check if A is positive semidefinite or negative semidefinite. But what would be the solution to the inequality $x^TAx+b^Tx+c\leq0$ and $x^TAx+b^Tx+c\geq0$ ? Specifically I need to know when either of the inequality would be convex. If someone can share a good resource that talks about quadratic equation(not quadratic form) with matrices as coefficients besides Wikipedia, it would be great. Thank you.

$\endgroup$
4
$\begingroup$

Given an arbitrary line $L = \{ x_0 + tv \in R^n \ | \ t \in R \}$, we know that the set $C = \{ x \in R^n \ | \ x^TAx + b^Tx + c \le 0 \}$ is convex if and only if the intersection with this line is convex. For convexity, we want to prove that $L$ intersects $C$ as a continuous line segment where $t$ is continuous in a bounded range (e.g, stretching $v$ in a bounded range).

Substituting $L$ into $C$ we get the intersection $f(t) = (v^TAv)t^2 + (2x_0^TAv + b^Tv)t + (x_0^TAx_0 + b^Tx_0 + c) \le 0$, which is a concave upward function of $t$ if $A \ge 0 => v^TAv \ge 0$ (i.e., $ \ f''= v^TAv \ge 0$ ). $f(t)$ is bounded above by zero and bounded between a fixed range of $t$ (i.e., the two roots of f(t)=0). Therefore, $t$ is continuous in a bounded range implies that the intersection is a convex line segment.

In conclusion, $C$ is convex when $A \ge 0$.

$\endgroup$
0
$\begingroup$

If we substitute $x = y + v$ in the inequality $x^T A x + b^T x + c \le 0$ we get $y^T A y + (b^T + 2 v^T A) y + v^T A v + b^T v + c \le 0$. Assuming $A$ is invertible, we can choose $v$ so that $b^T + 2 v^T A = 0$, so the inequality becomes $y^T A y \le k$. If, for example, $A$ is positive definite and $k > 0$, this defines an ellipsoid.

$\endgroup$
4
  • $\begingroup$ Thanks for replying.....I have 2 doubts though. Firstly what was the need for the substitution? Can't we derive the same conclusion from the equation $x^TAx+b^Tx+c\leq0$? Secondly from your explanation can I conclude that the linear term i.e. $b^Tx+c$ has no role in changing the shape of the graph, although it might shift the graph up or down? $\endgroup$ – Shirin Mar 18 '13 at 4:09
  • $\begingroup$ Could you please explain we $v^TAy$ equals to $(v^TAy)^T$ in order to have: $v^TAy + (v^TAy)^T = 2v^TAy$ in the equation? Sorry for the bad time but I am interested to figure it out. Thanks. $\endgroup$ – Thoth Nov 16 '14 at 18:15
  • $\begingroup$ $v^T A y$ is a number, so it is its own transpose. $\endgroup$ – Robert Israel Nov 16 '14 at 20:45
  • $\begingroup$ :) Right. Thanks for the response! $\endgroup$ – Thoth Nov 17 '14 at 10:50

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.