This question is closely related to my last question about extended quadratic forms.
I figured out a nice criterion, when
$$f : \mathbb R^n \rightarrow \mathbb R$$
$$f(x) = x^TAx + c^Tx$$
has a global minimum , where $A \in Mat(n,n,\mathbb R)$ is symmetric, $c \in Vec(n,\mathbb R )$
I want to know, when f(x) has a global minimum. It is clear, that A must be
positive semi-definite. In this case, I figured out that f(x) has a global
minimum, if and only if $c^T$ is orthogonal to the kernel of A. In other words,
for any $x$ with $Ax=0$ , the equation $c^Tx=0$ must hold.
- Is there an easy proof for this criterion ?
- Can this result be understood geometrically ?
Best Answer
The necessary part of the proof is really easy:
If $x^TAx$ can have negative values, then $f$ has no minimum on $\Bbb R^n$, because the term $ c^Tx$ is linear in $x$ and $x^TAx$ is bilinear.
Hence, we need $A$ to be positive semidefinite.
If $A$ is positive definite, then everything is ok, we can even find $x_\ast$ where minimum is attained: $x_\ast = -\frac 12 A^{-1}c$.
Suppose that $\ker A$ is non-zero, then take $x\ne 0$, $x\in \ker A$. $f(x)=c^Tx$. This is a linear function on $\ker L$, hence it can not have a minimum, unless it's constantly zero.
Therefore, we conclude the necessary conditions: $A$ is positive semidefinite and $\forall x\in \ker A$ we have $c^Tx=0$.
Let's now prove that these conditions are, in fact, sufficient. This part of the proof is slightly more difficult. Define $U=\ker A$ and $V=(\ker A)^\bot$. Clearly, $U\oplus V=\Bbb R^n$.
Let us also define $\lambda$ - smallest nonzero eigenvalue of $A$. Clearly, $\forall v\in V$ we have $v^TAv\ge \lambda |v|^2$ (ask if unclear why).
Furthermore, let $x=u+v$ such that $u\in U$ and $v\in V$ (this decomposition is unique). We can show that there exists $r>0$ such that $f(x)\ge 0$ for all $x=u+v$ such that $|v|> r$. Indeed, then $$f(x)=v^TAv + c^Tv\ge \lambda |v|^2+ c^Tv\ge |v|(\lambda|v|-|c|).$$ The last expression is non-negative when $|v|\ge \frac{|c|}{\lambda}$. We can now take $r =\frac{|c|}{\lambda} $.
The above result shows that on the set $E =\{(u+v):u\in \ker A,\;v\in (\ker A)^\bot, |v|\ge r\}$ our function $f$ is non-negative, hence $E$ in not interesting from minimization point of view (we know that $f(0)=0$). We now need to examine the complementary $E^c =\{(u+v):u\in \ker A,\;v\in (\ker A)^\bot, |v|\le r\} $.
We write $$0\ge \inf_{x\in \Bbb R^n} f(x)=\inf_{x\in E^c} f(x) = \inf_{v\in (\ker A)^\bot, |v|\le r}v^TAv + c^Tv $$ (we used that $c\in (\ker A)^\bot$). The last infimum exists and is finite because we minimize a continuous function on a compact set. Therefore, the sufficient part is also proven.
As for geometric understanding, I'd try to use convexity, but I'm not really apt to produce such proof.