0
$\begingroup$

The homework question asks to prove that

$min_{x\in\mathbb{R}} {f(x) = 1/2<Ax,x>-<b,x>}$

is equivalent to solving a linear system $Ax-b$.

The hint the professor gave is to recite the proposition:

The gradient of the function $f(x)$ is $∇f(x) = Ax − b$.

Moreover,

(i) if A is positive definite, then $f$ admits a unique minimum at $x_{0}$ that is a solution of the linear system $Ax = b$;

(ii) if $A$ is positive indefinite and if $b$ belongs to the range of $A$, then $f$ attains its minimum at all vectors $x_{0}$ that solve the linear system $Ax = b$ and at these vectors only.

I don't understand how using that hint gets me anywhere near the original problem.

$\endgroup$
  • $\begingroup$ What must be true of the gradient at the minimum? $\endgroup$ – Alex R. May 19 at 6:34
  • $\begingroup$ that it must be unique? $\endgroup$ – Jess Savoie May 19 at 6:36
0
$\begingroup$

Suppose we are solving $Ax = b$ for $x$. This equation can be written, as you did, $$ Ax - b = 0. $$ Now, suppose we start out as a little less optimistic: a solution may not exist. So, we want an $x$ such that $Ax$ is as close as possible to $b$. In other words, we are now solving the minimization problem: $$ \min_{x} \rightarrow |Ax - b|^2. $$ In other words, we are minimizing the function $$ f(x) = {1 \over 2} |Ax - b|^2, $$ where the $1/2$ does not affect the solution space, but makes it more algebraically convenient to compute the gradient of $f$.

(In your problem, you have $x \in \mathbb{R}$, which I suspect is a typo. If $A$ is a matrix and $x$ and $b$ vectors of appropriate dimension, please interpret my $||$'s as the magnitude that we get from the dot product: $|w|^2 = w \cdot w$.)

Accordingly, we are minimizing $$ f(x) = {1 \over 2}|Ax - b|^2 = {1 \over 2}(Ax - b) \cdot (Ax - b) = {1 \over 2}|Ax|^2 - (Ax)\cdot b + {1 \over 2}|b|^2. $$ Since $b$ is a constant vector, however, the minima of $$ {1 \over 2}|Ax|^2 - (Ax)\cdot b + {1 \over 2 }|b|^2 $$ are the same as the minima of $$ {1 \over 2}|Ax|^2 - (Ax)\cdot b. $$

$\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.