Proof Request - Optimization - $f : \mathbb R^n \to \mathbb R, \; f(x) = \frac{1}{2}x^TAx - b^Tx$

69 Views Asked by At

I am kindly requesting a proof to the following theorem-lemma found in my Optimization notes without proof :

Consider the quadratic function $f:\mathbb R^n \to \mathbb R, \; f(x) = \frac{1}{2}x^TAx -b^Tx.$ If the matrix $A$ is symmetrical and positive definite, the function $f$ is strictly convex and also if $\|x_n\| \to \infty$ then $f(\| x_n \|) \to \infty$.

2

There are 2 best solutions below

0
On BEST ANSWER

If we let $\phi(t) = f(x_0+t(x_1-x_0)) $, then $\phi''(t) = \langle x_1-x_0, A(x_1-x_0) \rangle > 0$, hence $f$ is strictly convex.

If $A>0$ then there is some $c>0$ such that $\langle x , Ax \rangle \ge c \|x\|^2$ for all $x$. Then $f(x) \ge { 1\over 2} c \|x\|^2 - \|b\| \|x\|$. If we choose $\|x\| \ge 2 { ( 1+\|b\| ) \over c}$ then $f(x) \ge \|x\|$ from which it follows that $\lim_{\|x\| \to \infty} f(x) = \infty$.

0
On

A theorem states that a twice differentiable multivariate function is strictly convex providing the bilinear form $f^{\prime \prime}(x)$ is positive definite at all $x$.

This is the case here as $f^{\prime \prime}(x)$ is constant and equal to $A$.

Regarding the second point, $A$ is diagonalizable in an orthonormal basis $\mathcal B$ with all eigenvalues strictly positive as $A$ is supposed symmetric positive definite. In that basis you have

$f(x) = \sum \lambda_i x^2_i - \sum b_i x_i$. If $\Vert x_i \Vert \to \infty$, then one of the coordinate of the sequence is unbounded. It is easy to prove that $\Vert f(x) \Vert \to \infty$ using that coordinate.