# Proving a specific $min$ function is equivalent to solving $Ax-b$

The homework question asks to prove that

$$min_{x\in\mathbb{R}} {f(x) = 1/2-}$$

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.

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

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