1
$\begingroup$

I want to prove the following:

Given $A \in \mathbf{R}^{n \times n}$ is symmetric positive definite. Prove that $\hat{x}$ solves $Ax = b$ if and only if $\hat{x}$ minimizes the quadratic function $f: \mathbf{R}^n \to \mathbf{R}$ given by:

$$f(x) = \frac{1}{2}x^TAx - x^Tb$$

Attempt:

Since $A$ is positive definite, it is invertible since its eigenvalues are all strictly positive. Let $x = A^{-1}b$ and determine $f(y) - f(x)$ for any $y \in \mathbf{R}^n$. Since $Ax = b$:

$$\begin{align} f(y) - f(x) &= \frac{1}{2}y^TAy - y^Tb - \frac{1}{2}x^TAx + x^Tb \\ &= \frac{1}{2}y^TAy - y^TAx + \frac{1}{2}x^TAx \\ &= \frac{1}{2}(y - x)^TA(y-x)\end{align}$$ Since $A$ is positive definite, the last expression is nonnegative and therefore $f(y) \geq f(x)$ for all $y \in \mathbf{R}^n$, which gives x = $A^{-1}b$ as the global minimum of $f(x)$ and $$f(A^{-1}b) = -\frac{1}{2}b^TA^{-1}b$$

Concerns:

I'm concerned that this proof is determining what the global minimum of the equivalent system is not necessarily that $\hat{x}$ solves $Ax = b$ if and only if $\hat{x}$ minimizes the quadratic function. Any hints in the right direction would be greatly appreciated!

$\endgroup$
2
  • $\begingroup$ You could also try to calculate $\nabla f$. $\endgroup$ – Meowdog Oct 26 '20 at 18:49
  • 1
    $\begingroup$ Note the $A \succ 0$ implies that $A$ is invertible and that $f(x)$ is a strictly convex function, so its minimizer is unique. Also note that the minimizer $\hat{x}$ of $f$ satisfies $\nabla f(\hat{x}) = A\hat{x} - b = 0$. $\endgroup$ – V.S.e.H. Oct 26 '20 at 19:01
1
$\begingroup$

Because $A$ is invertible, "$\hat{x}$ solves $Ax=b$" is just "$\hat{x} = A^{-1} b$."

So to show the "if and only if" claim, you need to show that $A^{-1}b$ is the unique minimizer of $f$.

So far you have shown that $A^{-1}b$ is a minimizer (since $f(y) \ge f(A^{-1} b)$ for all $y$), but you still need to show it is the only one. To do this, it suffices to adjust your argument to show the stronger inequality $f(y) > f(A^{-1} b)$ for all $y \ne A^{-1} b$. Can you see how to do this? (Hint: $A$ is positive definite.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.