I have read everywhere that the resolution of the linear system


where $A\in S_n(\mathbb R)$ and $b\in \mathbb R^n$ is equivalent to the resolution of the following optimization problem:

$$f(x)=\frac 12\langle Ax,x\rangle+\langle b,x\rangle.$$

Which means that if $x\in \mathbb R^n$ minimize the function $f(x)=\frac 12\langle Ax,x\rangle+\langle b,x\rangle$, then $x$ is solution of the linear sytem $Ax+b=0$ where $A\in S_n(\mathbb R)$.

I do not understand why this should be true... Can someone please explain it?

  • 1
    $\begingroup$ Did you try finding the gradient of $f$? $\endgroup$ – 5xum Feb 20 '17 at 14:05
  • $\begingroup$ @5xum The gradient of $f$ seems to be $\nabla f(x)=Ax+b$, but I think there is still some arguments missing here... $\endgroup$ – E. Joseph Feb 20 '17 at 14:08
  • $\begingroup$ It is not true. The sign is wrong. $\endgroup$ – Rodrigo de Azevedo Feb 20 '17 at 14:08
  • 1
    $\begingroup$ @E.Joseph Because there is only one zero for the gradient. The only other option would be for the function to go toward its minimum "at infinity", but that is also impossible. $\endgroup$ – 5xum Feb 20 '17 at 14:14
  • 1
    $\begingroup$ @E.Joseph I see that you have created (linear-system) tag. I just wanted to let you know that I have started a post on meta about this new tag: meta.math.stackexchange.com/questions/25694/tag-management-2017/… $\endgroup$ – Martin Sleziak Feb 25 '17 at 13:07

U cannot prove this by taking the gradient! This is not a function but a functional! You should variate it! U have the following functional $$F[x]=\langle{Ax}, x\rangle-\langle{b, x}\rangle$$ U variate the functional $$\delta{F[x]}=\langle{Ax}, \delta{x}\rangle-\langle{b, \delta{x}}\rangle=\langle{Ax-b}, \delta{x}\rangle$$ For the extremum, u require the functional to be stationary with respect to any variations, i.e. $$\delta{F[x]}=\langle{Ax-b}, \delta{x}\rangle=0$$ As the above equality holds for any $\delta{x}$, u better have $$x^{T}A^{T}-b^{T}=0$$ Taking the transpose of this equation, u arrive at $Ax=b$ !

| cite | improve this answer | |

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.