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^Tbb^TAx都為1x1的純量且展開後是相等的,可以合併之

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

5 Replies to “Linear quadratic form in optimization problem Ax=b

    1. 因為不想算根號,所以一般多把norm取平方消根號。而根號基本上在正值時是為一個monotonic function,故對求最小解無影響。

    1. 抱歉應是筆誤,想表達是 Ax=b 的形式 應視為 A'x=b' 且 A 滿足 positive definite 條件時, x 的 eigen-vector 仍不變

Leave a Reply

Your email address will not be published. Required fields are marked *