Consider the problem $P$ of minimizing $\frac{1}{2}x^tBx + c^tx$
subject to $Ax=b$, where $\{x\in\mathbb{R}^{n}|Ax=b\}$ is non empty
and $B$ is symmetric.a) Prove that if $P$ has solution, then $z^tBz\ge 0$ for all $z\in
\ker A$b) Prove that $P$ has unique solution iff and only iff $z^tBz>0$ for
all $z\in \ker A, z\neq 0$c) Show with an example that $a$ is a necessary conidtion for
optimality but not sufficient
a) Note that $\nabla^2 f(x) = B$, and suppose that $Z$ is the matrix in which the columns for a basis for $\ker A$. Then solving the constrained problem $P$ is the same as solving the unconstrained problem $\min \phi(\gamma) = f(\overline{x}+Z\gamma)$ where $\overline{x}$ satisfies $A\overline{x}=b$. Saying that $P$ has a solution is the same as saying that the unconstrained problem has a solution, which is the same as saying there exists $\gamma^*$ such that $\nabla^2 (\gamma^*) \succeq 0$, which is the same as saying that $\nabla(\gamma^*)^2 = Z^t\nabla^2 f(\overline{x}+Z\gamma^*)Z=Z^tBZ \succeq 0$ which is the same as saying $z^tBz\ge 0$ for all $z\in \ker A$
b) Saying that $P$ has a unique solution is the same as saying that the unconstrained problem has a unique solution, I guess. Which is saying that $\phi(\gamma) = f(\overline{x}+Z\gamma)$ where $A\overline{x} = b$ has an unique solution. I need this to imply $z^tBz>0$ for $z\in \ker A$. How should I do it? Also, how to prove the converse?
c) How to find an example?
Best Answer
b) assume $P$ has a unique solution $\bar{\gamma}$, but $z^tBz < 0$ for some $z\in \ker A$. Consider $g(\alpha) = f(\bar{x}+Z(\bar{\gamma}+\alpha z))$. Note that $g$ is a quadratic function from $\mathbb{R}$ to $\mathbb{R}$, with $g'(0)=0$ and $g''(0)<0$. Therefore, $0$ is a maximum for $g$ (you can formally prove this with Taylor's theorem), which is a contradiction with $\bar{\gamma}$ being a minimum.
Now assume $z^tBz>0$ for all $z\in \ker A, z\neq 0$, and suppose there is more than solution. Let $\bar{\gamma}^1$ and $\bar{\gamma}^2$ ($\bar{\gamma}^1 \neq \bar{\gamma}^2$) be two solutions. Consider $h(\alpha) = f(\bar{x}+Z(\alpha\bar{\gamma}^1+(1-\alpha)\bar{\gamma}^2))$ for $\alpha \in [0,1])$. Since $h'(0)=h'(1)=0$, by the mean value theorem there must be a point in $(0,1)$ for which $h''(\alpha)=0$. This is in contradiction with the second derivative being strictly positive.
c) consider $A=B=0$.