1 優化談話

優化問題是對現實世界問題的數學抽象。通常，我們有很多想做的事情，比如發表很多論文，賺很多錢。明確地說，我們想要完成一些事情。我們與世界互動，不斷采取行動以盡可能接近我們的目標。但我們能采取的行動是有限的。例如，一天沒有 25 個小時，我們不可能在一秒鐘內輸入 10,000 個單詞。將要采取的動作抽象為決策變量 x ，將動作的約束條件抽象為約束 x\in X ，將要完成的目標抽象為目標函數 f ，得到優化問題：

\begin{align} \min&~~~f(x)\\ \text{st} &~~~x\in X \end{align}

我們如何獲得更好的 x，甚至是最好的 x？它取決于目標函數f的性質和可行集X的形狀。如果f的性質不好，我們在選擇x時只能使用f本身，此時的優化方法稱為零階優化方法。零階優化被廣泛使用，包括網格搜索、模擬退火算法、遺傳算法、粒子群優化等。如果我們可以很容易地解決 f \nabla f 的梯度，我們就可以繼續朝著負的方向前進梯度，從而不斷地找到一個更好的 x ，這稱為一階優化方法，如今熱門的神經網絡在訓練中經常使用這種方法。當然，如果我們能找到更多關于 f 的信息，例如 f \nabla ^2f 的矩陣（由二階偏導數組成的矩陣），可以更快地達到最優解。值得一提的是，如果我們知道 f 是二階可微的，即使我們找不到 \nabla ^2f ，仍然可以通過一階信息 \nabla f 估計出二階信息 \nabla ^2f ，然后更快地解決它。簡而言之，f的性質越好，我們可以獲得的關于f的信息就越多，我們就能更好地解決它。當然，可行集X的作用也不容忽視。如果x被限制為離散值（例如整數、0-1變量），此時的問題稱為組合優化問題。著名的組合優化問題，如旅行商問題、背包問題、并且路徑問題被證明是NP完全的并且很難解決。組合優化也是一個很廣闊的大陸，暫時不列出來。

在這篇筆記中，我們主要以具有“一些性質”的f和具有“更好的形狀”的X為研究對象直線搜索方法,無約束優化方法,約束優化方法，并參考著名學者的著作《 》記錄了一些優化方法及其性質。

2 無約束優化 2.1 最優解存在的充分條件

我們首先考慮沒有約束的情況，即\min~f(x)。但在此之前，有一個非常關鍵的問題，我們什么時候才能找到 f(x) 的最小值？該定理給出了最優解存在的充分條件。

定理：設X為\{R}^n的非空子集，令f:X\\{R}在X的所有點上下半連續（函數值不大于函數極限）。如果 X 是緊的，或者 X 是閉的并且 f 是矯頑的，那么 f 在 X 上的最小值的集合是非空且緊的。

請注意，該定理不需要假設函數是連續的，只需要下半連續。這是因為下半連續性已經可以保證我們在任何可能的極限點處都能達到最小值，并且在趨于極限點時不會出現趨于最小值的鄰域函數值，以及對應的函數限制點的值更大。案子。對X的要求保證了可以得到極限點，不會出現在設定的邊界上或趨于無窮大。

2.2 最優條件

明確解的存在性后，就可以判斷一個解是否為最優解，這是求解最優化問題的前提。如果 f 是可微的，則局部最優的一階必要條件是 \nabla f(x)=0 ，如果 f 是二階可微的，則局部最優的二階必要條件是 \nabla^2f(x) 正半定。請注意，這不是充分條件，當 f 為凸時，一階必要條件也是充分的。若f為凸函數但不可微，一階充要條件為0\in\f(x)，即在點x處，水平面為次梯度，其他處的函數值點在水平面之上。

當優化問題有約束時，最優性條件不僅非常有意義，而且非常有趣，看下面的表達式。

2.3 強凸函數的良好性質

如果函數的性質很好，我們可以從當前解中得到最優解的信息。例如，當 f 滿足 mI\le\nabla^2f\le MI 時，我們可以得到：

\frac{1}{2M}\|\nabla f(x)\|^2\le f(x)-f(x^*)\le\frac{1}{2m}\|\nabla f(x )\|^2

\frac{m}{2}\|xx^*\|^2\le f(x)-f(x^*)\le \frac{M}{2}\|xx^*\|^2

這意味著可以從當前梯度推斷出當前函數值與最優函數值之間的距離，進而可以推斷出當前解與最優解之間的距離。

證明：在點 x 處將 f 擴展為 x^*：

f(x^*)=f(x)+\nabla f(x)(x^*-x)+(x^*-x)\nabla^2f(\tilde x)(x^*-x)

根據 mI\le\nabla^2f\le MI ，所以：

\nabla f(x)(x^*-x)+m\|xx^*\|^2\le f(x^*)-f(x)\le \nabla f(x)(x^*- x)+M\|xx^*\|^2

根據二次函數的性質，我們知道：

\min_y \{\nabla^\top (yx)+\frac{\alpha}{2}\|yx\|^2\}=-\frac{1}{2\alpha}\|\nabla\|^ 2

這樣就可以得到第一個公式。第二個公式在點 x^* 處將 f 擴展為 x：

f(x)=f(x^*)+(xx^*)\nabla^2f(\波浪號 x)(xx^*)

然后根據mI\le\nabla^2f\le MI得到。

2.3 最速下降法

很多情況下，我們無法直接求解\nabla f(x)=0，此時可以迭代求解。好消息是我們知道了梯度信息，當我們在負梯度方向走適當的距離時，函數的值會下降，我們可能會更接近最優解。梯度下降的最簡單形式是：

x_{k+1}=x_k-\ \nabla f(x_k)

其中\是步長，步長的選擇很有學問，可以選擇一個常數步長、一個衰減步長等。步長也可以通過搜索來確定，比如精確搜索，或者可以減少計算量，可以使用眾所周知的規則和規則搜索。一般來說，函數的性質越好，在相同的收斂和收斂速度下，需要的步長越小。

規則介紹到這里。搜索的目標是不斷增加非負整數 m直線搜索方法,無約束優化方法,約束優化方法，并找到第一個 m 使得以下公式成立：

f(x_k+\beta^ms d_k)\le f(x_k) +\sigma \beta^ms\nabla f(x_k)^\top d_k

其中 \sigma 和 \beta 是設置參數，d_k 是搜索方向。當步長很小的時候，基本按照梯度的斜率下降。但是這個公式的含義是不需要這么苛刻，我們設置了\sigma\in(0,1)的“容差因子”。犧牲下坡的坡度，換來更大的步幅。通常，需要對兩者進行權衡以實現更快的下降率。

2.4 牛頓法

在梯度下降法中，很難不問一個問題，沿著負梯度方向是不是下降最快的方向是真的嗎？如果我們知道二階信息 \nabla^2f ，我們可以更快地迭代嗎？牛頓法通過\nabla^2f對負梯度方向-\nabla f進行修正，從而達到更快的收斂速度。它的迭代方法是：

x_{k+1}=x_k-\ (\nabla^2 f(x_k))^{-1}\nabla f(x_k)

當函數是二次的時，這個公式的作用是將負梯度方向修正為指向最優解的方向。因此，如果一個函數比較接近二次形式，例如二階連續可微函數接近局部最優解時，收斂速度會大大加快。

牛頓法雖然收斂速度更快，但其計算成本卻不容忽視。當決策變量的維數較高時，矩陣的計算和求逆需要大量的計算，甚至計算起來過于復雜。此時可以使用牛頓法的變體，例如：

x_{k+1}=x_k-\ \begin{} * & 0 & \cdots & 0\\ 0 & * & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots &* \end{} ^{-1}\nabla f(x_k)

x_{k+1}=x_k-\ (\nabla^2 f(x_0))^{-1}\nabla f(x_k)

或通過其他方式估計：

x_{k+1}=x_k-\ [\text{ of }(\nabla^2 f(x_0))^{-1}]\nabla f(x_k)

2.4 共軛梯度法

與最速下降法不同的是，共軛梯度法的思想不是每次都往“最快”的方向走，而是找到一系列共軛方向，依次沿著這些方向移動。共軛方向是經過精心選擇的，因此對于二次函數，沿著這些方向依次精確搜索后可以獲得最優解。也就是說，每一次優化的方向都被“優化”過了，并且在這個方向上達到了最優解。共軛梯度法雖然是從二次形式推導出來的，但在非二次函數上也能有很好的收斂性能。

共軛方向 d_i 需要滿足以下“Q-共軛”性質：

d_i^\top Qd_j=0

從這個公式可以很容易地推導出共軛方向一定是線性無關的，所以\{R}^n有n個共軛方向。

如果對于二次形式 f(x)=x^\top Qx+b^\top x ，每一步搜索都是精確搜索：

\frac{\ (x_{k+1}+\alpha d_i)}{\ \alpha}=0

則有 x_{k+1}={\arg\min}_{x\in x_0 + \bm{\{span}}\{d_0,\cdots,d_k\}}f(x) ，即每一個都是沿著新的共軛方向優化的，不會影響已經優化的方向。

共軛方向 d_k 可以使用正交化從梯度 g_k 序列生成：

d_k=-g_k+\sum_{j=0}^{k-1}\frac{g_k^\top Q d_j}{d_j^\top Q d_j}d_j , d_0=-g_0

這個公式可以寫成迭代形式以便于求解：

d_k=-g_k+\ d_{k-1} , \=\frac{g_k^\top g_k}{g_{k-1}^\top g_{k-1}}

3 約束優化

通常我們遇到的優化問題都是有約束的，那么接下來，我們將在無約束優化的基礎上，討論如何在約束下進行優化。

3.1 梯度投影法

最簡單的想法是仍然按照無約束優化的算法進行優化，一旦當前解決了可行集，就將其取回來。這種方法稱為梯度投影法，即以下兩步交替進行：

\波浪號 x_{k+1}=x_k-\d_k

x_{k+1}=\arg\min_{y\in C}\|xy\|

這要求 C 是一個凸集，在這種情況下，投影是存在的（根據定理）并且是唯一的（根據矛盾和凸集的定義）。

3.2 條件梯度法

與先考慮最優性迭代的梯度投影法不同，條件梯度法的思想首先考慮約束。條件梯度法的思想是找到可行方向，然后在可行方向上進行優化，在可行集中找到沿可行方向最遠的點。以負梯度方向為可行方向（如果負梯度方向不可行，則已經是局部最優解），構造如下線性目標函數的子優化問題：

\begin{align} \min_x&~~~\nabla f(x_k)^\top(x-x_k)\\ \text{st} &~~~x\in C \end{align}

如果約束比較簡單（比如線性約束），那么次優化問題就會很容易解決（線性規劃），這也是條件梯度法的好處之一。

3.3 拉格朗日橙色定理

對于函數 f,h 連續可微且優化問題具有等式約束 h(x)=0 的情況，拉格朗日乘子定理給出了最優解的必要條件。

拉格朗日乘子定理：若x^*是h(x)=0條件下可微函數f的局部極小點，假設約束梯度\nabla h_1(x^*),\cdots,\nabla h_m( x^*) 是線性獨立的（正則性），則有一個唯一的拉格朗日乘數 \^* 使得：

\nabla f(x^*)+\sum_{i=1}^m\^* \nabla h_i(x^*)=0

如果函數是二次可微的，在 \{y|\nabla h_i(x^*)^\top y=0,i=1,\cdots,m\} 上，我們有：

\nabla^2 f(x^*)+\sum_{i=1}^m\^* \nabla^2 h_i(x^*)\ge0

該定理可以用懲罰法證明，證明過程中可以得到\^*的顯式表達式：

\^*=-\left(\nabla h(x^*)^\top \nabla h(x^*)\right)^{-1}\nabla h(x^*)^\top\nabla f( x^*)

反演部分解釋了為什么需要規律性才能獲得唯一的拉格朗日乘數。

3.4 KKT最優條件

KKT條件推廣了拉格朗日方法，對于函數f、h、g連續可微且優化問題有等式約束h(x)=0和不等式約束g(x)\le0的情況，最優解為給定的。解的必要條件。

-Kuhn- 最優性的必要條件：如果x^*是函數f在h(x)=0,g(x)\le0條件下的局部極小點，假設約束的梯度\nabla h_1( x^* ),\cdots,\nabla h_m(x^*),\nabla g_i(x^*), i\in\{i|g_i(x^*)=0\} 線性獨立（正則性），則有一個獨特的拉格朗日乘數 \^*,\mu^* 使得：

\nabla f(x^*) +\sum_{i=1}^m\^* \nabla h_i(x^*) +\sum_{i=1}^r\mu_i^* \nabla g_i(x^* ) =0

其中\mu_i^*\ge0。對于 g_i(x^*) ，\mu_i^*=0 。

3.5 FJ最優條件

FJ條件推廣了KKT條件，對于非常規情況，給出了最優解的必要條件。

Fritz John最優性的必要條件：如果x^*是函數f在h(x)=0,g(x)\le0條件下的局部極小點，則有標量\mu_0^*和乘數\^ *,\mu^* 使得：

\mu_0^*\nabla f(x^*) +\sum_{i=1}^m\^* \nabla h_i(x^*) +\sum_{i=1}^r\mu_i^* \nabla g_i (x^*) =0

其中\mu_i^*\ge0。對于 g_i(x^*) ，\mu_i^*=0 。\mu_0^*,\^*,\mu^* 并非全為零。

FJ條件更一般，我們可以通過函數的性質從FJ條件中推導出KKT條件，從而得到更強的必要條件。

3.6 從 FJ 條件到 KKT 條件

以下情況可以使FJ條件強化為KKT條件：

h是線性函數，g是凹函數。-條件：\nabla h_i(x^*)是線性無關的，存在一個向量d使得d^\top\nabla h_i(x^*)=0，對于g_i(x^*)=0有d ^\top\ nabla g_i(x^*) 。條件：h是線性函數，g是凸函數，存在x，g_i(x)，g_i(x^*)=0。