簡說最優化基本演算法

最優化演算法為大多數機器學習演算法所依賴的基礎，因此為了深入理解機器學習演算法，應首先了解最優化的基本演算法。

「最優化要指在一定條件限制下，選取某種研究方案使目標達到最優的一種方法。」

----百度百科

本文主要從以下幾個方面介紹最優化演算法：

優化基本知識
無約束優化

最速下降法
共軛方向法
牛頓法
擬牛頓法

有約束優化

線性規劃及對偶問題
非線性規劃

拉格朗日條件
KKT條件
凸優化

優化基本知識

凡是提及優化演算法，免不了離不開梯度，黑塞矩陣，方嚮導數這三個基本概念。

函數 $f: R^{n} ightarrow R$ ，則

梯度： $abla{f} = (frac{partial{f}}{partial{x_1}}, frac{partial{f}}{partial{x_2}}, dots, frac{partial{f}}{partial{x_n}})$
黑塞矩陣： $extbf{F(x)} = left[ egin{array}{ccc} frac{partial^{2}{f}}{partial^{2}{x_1}}{( extbf{x})} & dots &frac{partial^{2}{f}}{partial{x_n}partial{x_1}}{( extbf{x})} \ vdots & & vdots\ frac{partial^{2}{f}}{partial{x_n}partial{x_1}}{( extbf{x})} & dots &frac{partial^{2}{f}}{partial^{2}{x_n}}{( extbf{x})} end{array} ight]$
函數在沿方向的方嚮導數為 $frac{partial{f}}{partial{ extbf{d}}}( extbf{x}) = lim_{a o 0}{frac{f( extbf{x} + a extbf{d})}{a}} = frac{mathrm{d}}{ mathrm{d}a}{f( extbf{x}+a extbf{d})}|_{a = 0} = abla{f} cdot extbf{d}$

極小值點 $extbf{x}^{*}$ 的一階必要條件 (前提為函數為一階可微)：

$extbf{x}^{*}$ 為內點或邊界點，為 $extbf{x}^{*}$ 處的可行方向，則 $forall extbf{d} , extbf{d}^{mathrm{T}} abla{f}( extbf{x}^{*}) geq 0$ ；
$extbf{x}^{*}$ 為內點，則 $abla{f}( extbf{x}^{*}) = 0$ 。

極小值點 $extbf{x}^{*}$ 的二階必要條件 (前提為函數為二階可微)：

$extbf{x}^{*}$ 為內點或邊界點，為 $extbf{x}^{*}$ 處的可行方向，且 $extbf{d}^{mathrm{T}} abla{f}( extbf{x}^{*}) geq 0$ ，則 $extbf{d}^{mathrm{T}} extbf{F}( extbf{x}^{*}) extbf{d} geq 0$ ；
$extbf{x}^{*}$ 為內點， $abla{f}( extbf{x}^{*}) = 0$ ，則 $forall extbf{d}, extbf{d}^{mathrm{T}} extbf{F}( extbf{x}^{*}) extbf{d} geq 0$ ,即 $extbf{F}( extbf{x}^{*})$ 半正定。

極小值點的二階充分條件 (前提為函數為二階可微)：

$extbf{x}^{*}$ 為內點，若 $abla{f}( extbf{x}^{*}) = 0$ 且 $extbf{F}( extbf{x}^{*}) > 0$ (正定) ，則 $extbf{x}^{*}$ 為的嚴格局部極小點。

無約束優化

最速下降法（只涉及目標函數的一階導數）

負梯度方向為函數值下降最快的方向。最速下降法為每次迭代沿著負梯度方向，選取合適的步長，使得目標函數值能夠得到最大程度的減小。相鄰兩次迭代方向垂直，即 $abla{f}( extbf{x}_{k}) ot abla{f}( extbf{x}_{k+1})$

則最速下降法的迭代公式為：

$alpha_{k} = mathrm{arg}_{alpha_{k}geq0} ext{ }mathrm{min} f( extbf{x}_{k}-alpha_{k} abla{f}( extbf{x}_{k}))$
$extbf{x}_{k+1} = extbf{x}_{k} - alpha_{k} abla{f}( extbf{x}_{k})$

特殊情況：對於目標函數為二次型函數的情況，即 $f( extbf{x}) = frac{1}{2} extbf{x}^{T} extbf{Q} extbf{x}- extbf{b}^{T} extbf{x}$ ,則 $alpha_{k} = frac{ extbf{g}_{k}^{T} extbf{g}_{k}}{ extbf{g}_{k}^{T} extbf{Q} extbf{g}_{k}}$ ,其中 $extbf{g}_{k} = extbf{Q} extbf{x}_{k}- extbf{b}$ ，則迭代公式為 $extbf{x}_{k+1} = extbf{x}_{k} + frac{ extbf{g}_{k}^{T} extbf{g}_{k}}{ extbf{g}_{k}^{T} extbf{Q} extbf{g}_{k}} extbf{g}_{k}$ 。

************************************************************************

牛頓法（涉及目標函數的一階導數以及二階導數）

當初始點與極小值點足夠接近時，牛頓法的效率比最速下降法的要高。

牛頓法的主要思想為：

給定一個迭代點後，構造二次型函數，使得該二次型函數在該迭代點的一次導數和二次導數都與目標函數相同，將此二次型函數看為目標函數的近似函數；
求該二次型函數的極小點，作為下個迭代點。

通過對目標函數在 $extbf{x}_{k}$ 處進行泰勒展開得到二次型函數：

$f( extbf{x}) approx f( extbf{x}_{k}) + ( extbf{x} - extbf{x}_{k})^{T} extbf{g}_{k} + ( extbf{x} - extbf{x}_{k})^{T} extbf{F}( extbf{x}_{k})( extbf{x} - extbf{x}_{k})$

則此二次型函數的極小值點為其梯度為0，則 $extbf{F}( extbf{x}_{k})( extbf{x}- extbf{x}_{k}) - extbf{g}_{k} = 0$ ，因此牛頓法的迭代公式為 $extbf{x}_{k+1} = extbf{x}_{k} + extbf{F}( extbf{x}_{k})^{-1} extbf{g}_{k}$ .

由於 $extbf{F}( extbf{x}_{k})^{-1}$ 並不容易求，我們用解方程的方式來代替求逆，則牛頓法可以分為以下兩步：

求解 $extbf{F}( extbf{x}_k) extbf{d}_{k} = - extbf{g}_{k}$ ，得到 $extbf{d}_{k}$
下一個迭代點為 $extbf{x}_{k+1} = extbf{x}_{k} + extbf{d}_{k}$ .

************************************************************************

共軛方向法（共軛梯度法）

共軛方向法，在效率上講，處於最速下降法與牛頓法之間。

在描述共軛方向法之前，我們先定義共軛方向。給定 $extbf{Q} in R^{n imes n}$ ，對於一組方向 $extbf{d}_{0}, extbf{d}_{1}, extbf{d}_{1},dots, extbf{d}_{n}$ ，若對於任意，都有 $extbf{x}_{i}^{T} extbf{Q} extbf{x}_{j} = 0$ ，則我們說其關於共軛。

我們基於目標函數是二次型函數，即 $f( extbf{x}) = frac{1}{2} extbf{x}^{T} extbf{Q} extbf{x}- extbf{b}^{T} extbf{x}$ ，介紹基本共軛方向演算法，給定關於的共軛方向 $extbf{d}_{0}, extbf{d}_{1}, extbf{d}_{1}, dots, extbf{d}_{n-1}$ ，以及初始點 $extbf{x}_{0}$ ，具體迭代步驟如下：

$extbf{g}_{k} = extbf{Q} extbf{x}_{k} - extbf{b}$
$alpha_{k} = -frac{ extbf{g}_{k}^{T} extbf{d}_{k}}{ extbf{d}_{k}^{T} extbf{Q} extbf{d}_{k}}$
$extbf{x}_{k+1} = extbf{x}_{k} + alpha_{k} extbf{d}_{k}$

但是提前給出一組共軛方向並不容易，在這種情況下，共軛梯度法（對於二次型目標函數）被提出，其不需要提前給定共軛方向。共軛梯度法的步驟如下：

給定初始值 $extbf{x}_{0}$
計算 $extbf{g}_{0} = abla{f}( extbf{x}_{0})$ ，若 $extbf{g}_{0} = 0$ ，則停止迭代；否則， $extbf{d}_{0} = - extbf{g}_{0}$ .
計算步長 $alpha_{k} = -frac{ extbf{g}_{k}^{T} extbf{d}_{k}}{ extbf{d}_{k}^{T} extbf{Q} extbf{d}_{k}}$
計算 $extbf{x}_{k+1} = extbf{x}_{k} + alpha_{k} extbf{d}_{k}$
計算 $extbf{g}_{k+1} = abla{f}( extbf{x}_{k+1})$ 。若 $extbf{g}_{k+1} = 0$ ，則停止迭代。
計算 $eta_{k} = frac{ extbf{g}_{k+1}^{T} extbf{Q} extbf{d}_{k}}{ extbf{d}_{k}^{T} extbf{Q} extbf{d}_{k}}$
計算 $extbf{d}_{k+1} = - extbf{g}_{k} + eta_{k} extbf{d}_{k}$
令 ,回到第三步。

************************************************************************

擬牛頓法

擬牛頓法的思路為：

為牛頓法增添步長
為 $extbf{F}( extbf{x}_{k})^{-1}$ 尋找近似矩陣

因此擬牛頓法的的迭代公式為：

$extbf{d}_{k} = - extbf{H}_{k} extbf{g}_{k}$ ( $extbf{H}_{k}$ 為對稱矩陣)
$alpha_{k} = mathrm{arg}_{alpha geq 0} mathrm{min} f({ extbf{x}_{k} + alpha extbf{d}_k})$
$extbf{x}_{k+1} = extbf{x}_{k} + alpha_{k} extbf{d}_{k}$

有約束優化

線性規劃以及對偶問題

線性規劃的標準形式為：

minimize $extbf{c}^{T} extbf{x}$

subject to ;

其中 $extbf{c} in R^{n}, extbf{A} in R^{m imes n}, rank( extbf{A}) = m, extbf{b} in R^{m}, m < n, extbf{b} geq extbf{0}$

對於方程 ,選擇矩陣前的前m列為基，經過簡單行變換矩陣 $extbf{B} in R^{m imes m}$ 可以使得前m列變為單位矩陣，即 $extbf{B} extbf{A} = [ extbf{I}_{m}, extbf{Y}_{m, n-m}]$ , $extbf{B} extbf{b} = extbf{y}_{0}$ 增廣矩陣標準型： $[ extbf{I}_{m}, extbf{Y}_{m,n-m}, extbf{y}_{0}] = left[ egin{array}{cccccccc} 1 & 0 & cdots & 0 & y_{1,m+1} & cdots & y_{1,n} & y_{1,0} \ 0 & 1 & cdots &0 & y_{2, m+1} & cdots & y_{2,n} & y_{2, 0} \ vdots & vdots & ddots & vdots & vdots & & vdots & vdots \ 0 & 0 & cdots & 1 & y_{m, m+1} & cdots & y_{m, n} & y_{m,0} end{array} ight]$

檢驗數為 $r_{i} = c_{i} - z_{i} = c_{i} - (c_{1}y_{1,i} + cdots + c_{m}y_{m,i})$

利用單純性法來求解線性規劃，其步驟為：

根據初始基本可行解構造增廣矩陣規範型
計算非基變數的檢驗數
若所有的非基檢驗數都為非負，則停止運算，當前基本可行解為最優解，否則進入下一步。
從負檢驗數中選擇一個檢驗數 $r_{q}$ ，其對應的非基變數為進階變數。
若不存在 $y_{i,q} > 0$ ，則停止運算，則問題無解。否則，計算 $p = mathrm{arg} extbf{ } mathrm{min}_{i} {{frac{y_{i,0}}{y_{i,q}}: y_{i,q} >0}}$ , p對應的基變數為出階變數。若求解得多個下標滿足條件，則為最小的下標值
以元素 (p,q) 為樞紐元素作為樞紐元素作樞紐變換，更新增廣矩陣規範型
轉到步驟2.

可以利用單純形表來解決線性規劃問題，舉個??，如下：

線性規劃問題為：

maximize $7x_{1} + 6x_{2}$

s.t. $2x_{1} + x_{2} leq 3 ; x_{1} + 4x_{2} leq 4; x_{1}, x_{2} geq 0$

首先把該規劃問題轉化為標準形式，目標函數乘以-1，為約束1和約束2加入鬆弛變數，得到的單純形表如下：

$egin{array}{cccc} & x_{1} & x_{2} & x_{3} & x_{4} & b\ & 2 & 1 & 1 & 0 & 3\ & 1 & 4 & 0 & 1 & 4 \ extbf{c}^{T} extbf{x} & -7 & -6 & 0 & 0 & 0 end{array}$

最後一行包含了檢驗數，-7最小，則第一列為進階向量，利用 b 列除以 $x_{1}$ 列，得到 $frac{3}{2} < frac{4}{1}$ ，則基變數中的第一個為出階變數，則以第一行第一列為出的元素為樞紐元素得到第二個單純形表 $egin{array}{cccc} & x_{1} & x_{2} & x_{3} & x_{4} & b\ & 1 & frac{1}{2} & frac{1}{2} & 0 & frac{3}{2}\ & 0 & frac{7}{2} & -frac{1}{2} & 1 & frac{5}{2} \ extbf{c}^{T} extbf{x} & 0 & -frac{5}{2} &frac{7}{2} & 0 & frac{21}{2} end{array}$ , 利用b列除以 $x_{2}$ 列，得到 $3 > frac{5}{7}$ ，則第二行第二列的元素為樞紐元素，得到的單純形表為 $egin{array}{cccc} & x_{1} & x_{2} & x_{3} & x_{4} & b\ & 1 & 0 & frac{4}{7} & -frac{1}{7} & frac{8}{7}\ & 0 & 1 & -frac{1}{7} & frac{2}{7} & frac{5}{7} \ extbf{c}^{T} extbf{x} & 0 & 0 &frac{22}{7} & frac{5}{7} & frac{86}{7} end{array}$ ，則 $x_{1} = frac{8}{7}, x_{2} = frac{5}{7}, x_{3} = 0, x_{4} = 0$ 為線性規劃的最優解，相應的目標函數的值為 $-frac{87}{7}$ 。則原問題的最優解為 $x_{1} = frac{8}{7}, x_{2} = frac{5}{7}$ ,相應的目標函數值為 $frac{87}{7}$ .

************************************************************************

對偶問題：

把形如：

minimize $extbf{c}^{T} extbf{x}$

subject to ;

轉化為：

maximize $mathbf{lambda}^{T}mathbf{b}$

subject to $mathbf{lambda} extbf{A} leq extbf{c}^{T}$ ;

目標值相同

************************************************************************

非線性規劃

拉格朗日條件

拉格朗日條件是為瞭解決等式約束優化。

問題描述：

minimize

subject to

正則點：對於滿足約束 $h_{1}(mathbf{x}^{*}) = 0, cdots, h_{m}(mathbf{x^{*}})$ 的點 $x^{*}$ ，如果梯度向量 $abla{h}_{1}(mathbf{x}^{*}), cdots, abla{h}_{m}(mathbf{x}^{*})$ 線性無關，則稱點 $x^{*}$ 為該約束的一個正則點。

已知

$mathrm{D}mathbf{h}(mathbf{x}) = left[ egin{array}{c} mathrm{D}h_{1}(mathbf{x})\ vdots\ mathrm{D}h_{m}(mathbf{x}) end{array} ight] = left[ egin{array}{c} abla{h}_{1}(mathbf{x})^{T}\ vdots\ abla{h}_{m}(mathbf{x})^{T} end{array} ight]$

拉格朗日定理：

$mathbf{x}^{*}$ 為的極值點，且為正則點，則存在 $mathbf{lambda ^{*} }in R^{m}$ ,使得 $mathrm{D}{f}(mathbf{x}^{*}) + mathbf{lambda}^{T}mathrm{D}{mathbf{h}}(mathbf{x}^{*}) = mathbf{0}^{T}$

極小值點存在二階必要條件和充分條件。

************************************************************************

KKT條件

KKT條件為瞭解決不等式優化問題。

問題描述如下：

minimize

subject to

對於不等式優化問題，其約束的正則點 $mathbf{x}^{*}$ 為令等式以及在 $mathbf{x}^{*}$ 處起作用的不等式的梯度線性無關的點。在 $mathbf{x}^{*}$ 處起作用的不等式滿足 $g(mathbf{x^{*}}) = 0$ , 在 $mathbf{x}^{*}$ 處不起作用的不等式滿足 $g(mathbf{x^{*}}) < 0$ 。

KKT條件：設 $mathbf{x}^{*}$ 為正則點以及局部極小點，則存在 $mathbf{lambda}^{*}$ 和 $mathbf{mu}^{*}$ 使得

$mathbf{mu}^{*} geq mathbf{0}$
$mathrm{D}{f}(mathbf{x}^{*}) + {mathbf{lambda}^{*}}^{T}mathrm{D}{mathbf{h}}(mathbf{x}^{*}) + {mathbf{mu}^{*}}^{T}mathrm{D}mathbf{g}(mathbf{x}^{*})= mathbf{0}^{T}$
${mathbf{mu}^{*}}^{T}mathbf{g}(mathbf{x}^{*}) =0$

************************************************************************

凸優化

若在介紹KKT條件中描述的問題的目標函數為凸函數，且約束條件構成的可行域為凸集。若存在存在 $mathbf{x}^{*}$ , $mathbf{lambda}^{*}$ 和 $mathbf{mu}^{*}$ 使得：

$mathbf{mu}^{*} geq mathbf{0}$
$mathrm{D}{f}(mathbf{x}^{*}) + {mathbf{lambda}^{*}}^{T}mathrm{D}{mathbf{h}}(mathbf{x}^{*}) + {mathbf{mu}^{*}}^{T}mathrm{D}mathbf{g}(mathbf{x}^{*})= mathbf{0}^{T}$
${mathbf{mu}^{*}}^{T}mathbf{g}(mathbf{x}^{*}) =0$

則 $mathbf{x}^{*}$ 是在上的全局極小點。

以上即為最優化的基礎演算法，敬請批評指正。