0
$\begingroup$

So i'm trying to solve this problem and I don't have any idea how to proceed.

A is a Positive-definite matrix, $\alpha \in \Bbb R$,

Show that the set $$ S(A,a; \alpha) = \{x \in \Bbb R^n \mid \frac 12 \langle x,Ax \rangle + \langle a,x \rangle \leq \alpha \} $$ is convex.

How?

P.S. I know what convex means , I know what a Positive-definite matrix is , but they don't give me the form of the matrix, no nothing.

$\endgroup$
0
0
$\begingroup$

What you need to show is that for $x_1, x_2 \in S$ and $0 \leq t \leq 1$, the element $(1-t)x_1 + t x_2$ is also an element of $S$. The only piece of information about $A$ required to show this is that $A$ is positive definite. In particular, if $A$ is positive definite, then the function $f(x) = \sqrt{\langle x,Ax \rangle}$ is a norm over $\Bbb R^n$.

It is also helpful to observe that $$ \langle (x-x_0),A(x-x_0) \rangle = \langle x,Ax\rangle - \langle (A + A^T)x_0,x\rangle + \langle x_0,Ax_0\rangle $$ Now, if we take $x_0 = (A + A^T)^{-1}\alpha$, then we can rewrite the set $S$ as $$ S = \{x \in \Bbb R^n \mid \langle x-x_0, A(x-x_0) \rangle - \langle x_0,Ax_0 \rangle \leq \alpha \} \implies\\ S = \{x \in \Bbb R^n \mid \langle x-x_0, A(x-x_0) \rangle \leq \alpha + \langle x_0,Ax_0 \rangle\} \implies\\ S = \{x \in \Bbb R^n \mid [f(x-x_0)]^2 \leq \beta \} \implies\\ $$ where we have defined $\beta = \alpha + \langle x_0,Ax_0 \rangle$. If $\beta < 0$, $S$ must be empty. If $\beta \geq 0$, we have $$ S = \{x \in \Bbb R^n \mid f(x-x_0) \leq \sqrt{\beta}\} $$ It is now straightforward to show that $S$ is convex using the fact that $f$ is a norm.

$\endgroup$
2
  • $\begingroup$ Thank you, it's a bit complicated for me, I'm a bit Stuck at the end. What is the next step? $\endgroup$ – random_numbers Dec 31 '18 at 5:47
  • $\begingroup$ And English is Not my first language, you say that f is a norm, can you explain? I Google it and Found norm refering to vectors. $\endgroup$ – random_numbers Dec 31 '18 at 5:56
0
$\begingroup$

The set $S$ is convex as a lower-level set of a convex function $$ f:x\mapsto \frac{1}{2}\langle x,Ax\rangle + \langle\alpha,x\rangle. $$ (If $x,y$ is such that $f(x), f(y) \leq c$, then $f(tx+(1-t)y) \leq tf(x) +(1-t)f(y) \leq c$ for all $0<t<1$.)

To see that $f$ is convex, it suffices to show $$ g:t\in \mathbb{R}\mapsto f(x+ty) $$ is convex for all $x$ and $y\neq 0$. This follows from $$ g''(t) = \langle y, Ay\rangle>0. $$

$\endgroup$

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.