Linear quadratic form in optimization problem \(Ax=b\)

談到最佳化(optimization)就不能逃避這個問題，為什麼大多的論文最佳化都喜歡來個

\[ \underset{x}{min}{\left \|Ax-b\right \|^2} \]

然後解

\[Ax=b\]

因為最好微分也最好解方程式! 但便宜的代價就是結果未必符合期望…解出來的\(x\)會有平均化residual的特性，在大多某些實際問題上不適用，以機率角度來說就是Gaussian prior，通常在實驗結果是個結果悽慘的對照組，但仍是一個非常適合入門的最佳化式子，因為我們需要一個夠爛的基準解，只要比它稍好就談得上學術貢獻拉!

本篇提供一個簡易的推導，故事是這樣來的，先從最簡單的二次式開始吧

\[f(x)=ax^2+bx+c\]

這是一個簡單的拋物線方程式，在大多數情況下我們希望\(a>0\)，也就是開口向上求最小值對應到的\(x\)，用上一點點偏微分對\(x\)求導數為0

\[\frac{\partial f(x)}{\partial x}=2ax+b=0\Rightarrow x=\frac{-b}{2a}\]

到此都是簡單的國中數學，我們先把流程記下來，待會兒在矩陣中也是如此。忘記的同學先複習一下norm-2怎算的，這邊就把開根號拿掉啦

\[f(x)=\left \|Ax-b\right \|^2\\=(Ax-b)^T(Ax-b)\\=(x^TA^T-b^T)(Ax-b)\\=x^TA^TAx-x^TA^Tb-b^TAx+b^Tb\]

這邊\(x^TA^Tb\)和\(b^TAx\)都為1×1的純量且展開後是相等的，可以合併之

\[f(x)=x^TA^TAx-2x^TA^Tb+b^Tb\]

對\(x^T\)偏微分求導數為0

\[\frac{\partial f(x)}{\partial x^T}=2A^TAx-2A^Tb=0\\\Rightarrow2A^TAx=2A^Tb\\\Rightarrow A’x=b’\]

就變成我們熟知的型態拉，乍看之下很蠢，似乎從第一行就可以直接觀察出\(Ax=b\)。要有效的解該式還需了解\(A\)的一些特性如symmetric, positive-definite等，不過那又是另外一個主題拉~

延伸到常用的L-2 norm regularization (Tikhonov regularization)仍會需要用這種方法，如下式

\[ \underset{x}{min}{\left \|Ax-b\right \| ^2+\lambda\left \| {\Gamma}x \right \|^2} \]

\[f(x)=x^TA^TAx-x^TA^Tb-b^TAx+b^Tb+{\lambda}x^T\Gamma^T{\Gamma}x\]

\[\frac{\partial f(x)}{\partial x^T}=2A^TAx-2A^Tb+2\lambda\Gamma^T{\Gamma}x=0\\\Rightarrow (A^TA+\lambda\Gamma^T{\Gamma})x=A^Tb\\\Rightarrow x=(A^TA+\lambda\Gamma^T{\Gamma})^{-1}A^Tb\]