Let $f(x) = \frac{1}{2}x^tQx-b^tx, Q\in\mathbb{R}^{n\times n}$
symmetric definite positive and $b\in\mathbb{R}^n$. Let $x^0, x^1,
\cdots, x^n\in\mathbb{R}^n$ and define $\delta^j = x^j-x^0$, $\gamma^j
= \nabla f(x^j)-\nabla f(x^0)$, $j=0,1\cdots,n$. Prove that the vectors $\{\delta^j\}_{j=1}^n$ are linearly independent, then
$$\overline{x} = x^n-[\delta^1\cdots \delta^n]\cdot[\gamma^1\cdots
\gamma^n]^{-1}\cdot\nabla f(x^n)$$ is a global minimizer of $f$
So, that's what I did:
$$\nabla f(x) = Qx-b^t\implies \gamma^j = Qx^j-b^t-(Qx^0-b^t) = Q(x^j-x^0)\implies\\\gamma^j = Q\delta^j\implies\delta^j = Q^{-1}\gamma^j$$
So
$$\overline{x} = x^n-[Q^{-1}\gamma^1\cdots Q^{-1}\gamma^n]\cdot[\gamma^1\cdots
\gamma^n]^{-1}\cdot\nabla f(x^n) =\\ x^n -Q^{-1}[\gamma^1\cdots \gamma^n][\gamma^1\cdots \gamma^n]^{-1}\cdot\nabla f(x^n) = x^n-Q^{-1}\nabla f(x^n) \implies \\\overline{x} = x^n-Q^{-1}(Qx^n-b^t) = x^n-x^n+Q^{-1}b^t = Q^{-1}b^t$$
So I need to prove $\overline{x} = Q^{-1}b^t$ is a global minimizer? Also, I need to use linear independence of $\{\delta^j\}$ to something. I guess it is related with the inverse matrix. Maybe linear independence of $\{\delta\}^j$ implies that that matrix has an inverse, but I don't know why.
Also, as I recall, $f(x)$ is quadratic and therefore convex. So shouldn't it has only one minimum? (therefore, since it is convex, it's the global?) So I should need to prove only that $\overline{x}$ is a local minimum? In that case I should only have to calculate $\nabla f(\overline{x}) = Q(Q^{-1}b^t)-b^t = 0$. The second derivative is just $Q$ and is definite positive. So: first derivative zero, second derivatie def. positive. Therefore this point $\overline{x}$ should be a minimum.
Even though I think I solved the exercise I don't know what all this means. It could just have asked if $Q^{-1}b^t$ is a global minimum. I think it is trying to show me a process of finding a global minimum for a quadratic function but I don't see the motivation.
Best Answer
You found that $\overline x = Q^{-1}b$ and $\nabla f(x) = Qx-b$. The Hessian therefore is $H_f(x) = Q$, which is positive definite. Hence, any $x$ with $\nabla f(x) = 0$ is a local minimum of $f$. But $\nabla f(x) = 0$ is equivalent to $Qx = b$ and thus $x = Q^{-1}b = \overline x$. As you wrote, the function is strictly convex, so a local minimum is global. Done.