0

I have the following problem: Consider the quadratic function $f(x) = \frac{1}{2}x^{T}Ax + b^{T}x$ with $A \in \mathbb{R}^{n×n}$ symmetrical and $b\in \mathbb{R}^{n}$. Show that if $f$ is limited iinferiorly, then $A$ is semi-defined positive and $f$ has global minimizer. What I've done so far: indeed if $A$ is not positive semidefinite then there exists some $u\in\Bbb{R}^{n\times n}$ such that $u^{\top}Au<0$. Let $C_0:=u^{\top}Au$ and $C_1:=b^{\top}u$ so that $f(u)=C_0+C_1$, and for every scalar $k\in\Bbb{R}$ you have $$f(ku)=(ku)^{\top}A(ku)+b^{\top}(ku)=k^2(u^{\top}Au)+k(b^{\top}u)=C_0k^2+C_1k.$$ Because $C_0<0$ it follows that $\lim_{k\to\infty}f(ku)=-\infty$, contradicting the assumption that $f$ is bounded below.

My question is, how do I prove that $f$ has a global minimizer? Would I have to do the function gradient?

Sebastiano
  • 7,649
Amissadai ferreira
  • 34

3 Answers3

1

Why dont' you taylor expand around $x^*$ and prove by contradiction that if the hessian is not SPD or if the slope is not 0 then there exists some point $f(x^* + p) $ s.t. $f(x^* + p) < f(x^*)$ which is a contradiction

mathcomp guy
  • 478
1
  1. Here is a known theorem: let $f: \mathbb{R}^n\rightarrow \mathbb{R}$ be differentiable. Then it is convex $\iff \nabla f(y)(x-y) \leq f(x)-f(y)$
  2. Our $f$ is differentiable, and $\nabla f(y)=0$ has a solution. To see this: for a fixed $x$, using point 1 we can write $f(y) \leq f(x)-\nabla f(y)(x-y)$. Suppose $\nabla f(y)\neq 0$ for every $y$. Choose $y$ such that $x-y=\nabla f(y)^t/|\nabla f(y)|$, so that $\nabla f(y)(x-y)=1$. So, no matter what $x$ we choose we can always find $y$ such that $f(y)\leq f(x)-1$, hence $f$ is not bounded from below, which is absurd.
  3. Let $y$ be one solution. Then, for all $x \in \mathbb{R}^n$ we have $f(x)-f(y)\leq 0$ by the first point

($\nabla f$ is a row)

Lilla
  • 2,099
1

Let $k$ be the rank of $A$. The spectral theorem says that we can write $A=P^* D P$ where $D$ is diagonal and $P$ is unitary. We have that $$ f(x) = \langle Dy,y \rangle + \langle b',y \rangle$$ where we set $y=Px$ and $b'=Pb$. Notice that since $f$ is bounded below we must have $b'_j \ge 0$ for $j>k$. If you expand the scalar products in $f$ you see that $$f = \lambda_1 y_1 ^2 + b'_1 y_1 + \dots + \lambda_k y_k ^2 + b'_k y_k + \text{something positive}.$$where $\lambda_j$ are the strictly positive eigenvalues of $A$. Now you can minimize in each component. The global minimum is attained at $\bar{y} = (\bar{y}_1,\dots , \bar{y}_k,0,\dots,0)$ with $$\bar{y}_j = \begin{cases} 0 & \text{if } b'_j \ge 0 \\ -b'/\lambda_j & \text{else}. \end{cases} $$

gangrene
  • 1,517