引言

本文簡單地介紹一些凸優(yōu)化(Convex Optimization)的基礎(chǔ)知識(shí)，可能不會(huì)有很多證明推導(dǎo)，目的是能快速應(yīng)用到機(jī)器學(xué)習(xí)問題上。

凸集

直線與線段

設(shè)$x_1\ne x_2$為${\mathbb{R}}^n$空間中的兩個(gè)點(diǎn)，那么具有下列形式的點(diǎn)
$$y=\theta x_1+(1?\theta )x_2,\theta \in \mathbb{R}$$
組成一條穿越$x_1$和$x_2$的直線。

如果參數(shù)$\theta$的值在$0$到$1$之間變動(dòng)，就構(gòu)成了$x_1$和$x_2$之間的線段。

仿射集合

如果通過集合$C?{\mathbb{R}}^n$中任意兩個(gè)不同點(diǎn)的直線仍然在集合$C$中，那么稱集合$C$是仿射的。

可以擴(kuò)展到多個(gè)點(diǎn)的情況，如果${\theta }_1+?+{\theta }_k=1$，我們稱具有${\theta }_1{x}_1+?+{\theta }_k{x}_k$形式的點(diǎn)為$x_1,?,x_k$的仿射組合。

凸集

首先來了解下什么是凸集(Convex Set)。

集合$C$被稱為凸集，如果$C$中任意兩點(diǎn)間的線段仍然在$C$中，即對(duì)于任意$x_1,x_2\in C$和滿足$0\le \theta \le 1$的$\theta$都有
$$\theta x_1+(1?\theta )x_2\in C\text{\hspace{1em}(1)}$$

圖1. 凸集和非凸集 來自維基百科

直觀上來看，凸集的形狀是飽滿的，即沒有凹進(jìn)去的地方。

我們稱
$$\theta x_1+(1?\theta )x_2\text{\hspace{1em}(2)}$$
為點(diǎn)$x_1,x_2$的凸組合，類似地，可以推廣到多個(gè)點(diǎn)：
$${\theta }_1{x}_1+?+{\theta }_k{x}_k\text{\hspace{1em}(3)}$$
為點(diǎn)$x_1,?,x_k$的一個(gè)凸組合，其中${\theta }_1+?+{\theta }_k=1$且${\theta }_i\ge 0,i=1,?,k$。

一個(gè)集合是凸集也可以說集合包含其中所有點(diǎn)的凸組合。

我們稱集合$C$中所有點(diǎn)的凸組合的集合為其凸包，記作$\text{conv}C$。

多個(gè)凸集的交集也是凸集，這意味著如果每個(gè)不等式或等式約束條件定義的集合都是凸集，那么這些條件聯(lián)合起來定義的集合仍然是凸集。

基于凸集的概念可以定義凸函數(shù)。

凸函數(shù)

函數(shù)$f:{\mathbb{R}}^n\to \mathbb{R}$是凸的，如果函數(shù)的定義域($\text{dom}f$)是凸集，且對(duì)于任意$x_1,x_2\in \text{dom}f$和任意的$0\le \theta \le 1$，有
$$f(\theta x_1+(1?\theta )x_2)\le \theta f(x_1)+(1?\theta )f(x_2)\text{\hspace{1em}(4)}$$

圖2. 凸函數(shù)示意圖 來自維基百科

如圖2(取$\theta =\frac{1}{2}$)，從幾何意義上看，式$(4)$的不等式成立意味著點(diǎn)$(x_1,f(x_1))$和$(x_2,f(x_2))$之間的線段，即從$x_1$到$x_2$的弦，在函數(shù)$f$的圖像上方。

反之，如果式$(4)$中的函數(shù)為$\ge$，則稱為凹函數(shù)。如果$f$是凸函數(shù)，那么$?f$就是凹函數(shù)。注意，還有很多函數(shù)是非凸也非凹的。

凸函數(shù)的一個(gè)很好的性質(zhì)是，它只有一個(gè)局部極小值點(diǎn)，同時(shí)也是全局最小值點(diǎn)。

凸優(yōu)化問題

優(yōu)化問題

我們用
$$\begin{array}{rlrl}& \text{minimize}& & f_0(x)\\ & \text{s.t.}& & f_i(x)\le 0,i=1,\dots ,m\\ & & & h_i(x)=0,i=1,\dots ,p\end{array}\text{\hspace{1em}(5)}$$
描述在所有滿足$f_i(x)\le 0,i=1,?,m$及$h_i(x)=0,i=1,?,p$的$x$中尋找極小化$f_0(x)$的$x$的問題，即優(yōu)化問題。

• $x\in {\mathbb{R}}^n$為優(yōu)化變量；

• 函數(shù)$f_0:{\mathbb{R}}^n\to \mathbb{R}$為目標(biāo)函數(shù)；

• 不等式$f_i(x)\le 0$稱為不等式約束，相應(yīng)的函數(shù)$f_i:{\mathbb{R}}^n\to \mathbb{R}$稱為不等式約束函數(shù)；

• 方程組$h_i(x)=0$稱為等式約束，相應(yīng)的函數(shù)$h_i:{\mathbb{R}}^n\to \mathbb{R}$稱為等式約束函數(shù)。

如果沒有約束，即$m=p=0$，我們稱問題$(5)$為無約束問題。

對(duì)目標(biāo)和所有約束函數(shù)有定義的點(diǎn)的集合
$$\mathcal{D}=\underset{i=0}{\overset{m}{?}}\text{dom}{f}_i\cap \underset{i=1}{\overset{p}{?}}\text{dom}{h}_i$$
稱為優(yōu)化問題$(5)$的定義域。當(dāng)點(diǎn)$x\in \mathcal{D}$滿足約束$f_i(x)\le 0,i=1,?,m$和$h_i(x)=0,i=1,?,p$時(shí)，$x$是可行的。當(dāng)問題$(5)$至少有一個(gè)可行點(diǎn)時(shí)，我們稱為可行的，否則稱為不可行。所有可行點(diǎn)的集合稱為可行集或約束集。

如果$x^{?}$是可行的并且$f_0(x^{?})=p^{?}$最優(yōu)值，我們稱$x^{?}$為最優(yōu)點(diǎn)。如果問題存在最優(yōu)解，我們稱最優(yōu)質(zhì)是課的或可達(dá)的，稱問題可解。

如果$x$可行且$f_i(x)=0$，我們稱約束$f_i(x)\le 0$的第$i$個(gè)不等式在$x$處起作用。如果$f_i(x)<0$，則約束$f_i(x)\le 0$不起作用。我們稱約束是冗余的，如果去掉它不改變可行集。

凸優(yōu)化

凸優(yōu)化問題是形如
$$\begin{array}{rlrl}& \text{minimize}& & f_0(x)\\ & \text{s.t.}& & f_i(x)\le 0,i=1,\dots ,m\\ & & & a_i^{T}x=b_i,i=1,?,p\end{array}\text{\hspace{1em}(6)}$$
的問題，其中$f_0,?,f_m$為凸函數(shù)，對(duì)比優(yōu)化問題$(5)$，凸優(yōu)化問題有三個(gè)附加的要求：

1. 目標(biāo)函數(shù)必須是凸的；
2. 不等式約束函數(shù)必須是凸的；
3. 等式約束函數(shù)$h_i(x)=a_i^T?b_i$必須是仿射的；

立即可以看到一個(gè)重要的性質(zhì)：凸優(yōu)化問題的可行集是凸的。

帶約束的優(yōu)化問題

拉格朗日乘子法

拉格朗日乘子法(Lagrange Multiplier Method)用于求解帶等式約束條件的函數(shù)極值(優(yōu)化問題)。假設(shè)有如下極值問題
$$\begin{array}{rlrl}& \text{minimize}& & f(x)\\ & \text{s.t.}& & h_i(x)=0,i=1,\dots ,p\end{array}\text{\hspace{1em}(7)}$$
拉格朗日乘子法構(gòu)造如下拉格朗日乘子函數(shù)
$$L(x,\lambda )=f(x)+\sum _{i=1}^p{\lambda }_i{h}_i(x)\text{\hspace{1em}(8)}$$
其中$\lambda$為新引入的自變量，稱為拉格朗日乘子((Lagrange Multiplier)。構(gòu)造了該函數(shù)之后，去掉了對(duì)優(yōu)化變量的等式約束。對(duì)拉格朗日乘子函數(shù)的所有自變量求偏導(dǎo)，并令其為$0$。包括對(duì)$x$求導(dǎo)、對(duì)$\lambda$求導(dǎo)。得到下面的方程組：
$$\begin{array}{rl}{?}_{x}f(x)+\sum _{i=1}^p{\lambda }_i{?}_x{h}_i(x)& =0\\ h_i(x)& =0\end{array}\text{\hspace{1em}(9)}$$
求解該方程組即可得到函數(shù)的候選極值點(diǎn)。

拉格朗日對(duì)偶

對(duì)偶是求解最優(yōu)化問題的一種手段，它將一個(gè)最優(yōu)化問題轉(zhuǎn)換為另一個(gè)更容易求解的問題，這兩個(gè)問題是等價(jià)的。

對(duì)于如下帶等式約束和不等式約束的優(yōu)化問題：
$$\begin{array}{rlrl}& \text{minimize}& & f(x)\\ & \text{s.t.}& & g_i(x)\le 0,i=1,\dots ,m\\ & & & h_i(x)=0,i=1,\dots ,p\end{array}\text{\hspace{1em}(10)}$$
仿照拉格朗日乘子法構(gòu)造廣義拉格朗日乘子函數(shù)
$$L(x,\lambda ,\mu )=f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)+\sum _{i=1}^p{\mu }_i{h}_i(x)\text{\hspace{1em}(11)}$$
稱$\lambda$和$\mu$為拉格朗日乘子，特別要求${\lambda }_i\ge 0$。接下來將上面的問題轉(zhuǎn)化為所謂的原問題，其最優(yōu)化解為$p^{?}$。
$$p^{?}=\underset{x}{\min }\underset{\lambda ,\mu ,{\lambda }_i\ge 0}{\max }L(x,\lambda ,\mu )=\underset{x}{\min }{\theta }_P(x)\text{\hspace{1em}(12)}$$
上式第一個(gè)等號(hào)右邊的含義是先固定變量$x$，將其看成常數(shù)，讓拉格朗日函數(shù)對(duì)乘子變量$\lambda$和$\mu$求極大值；消掉(確定了)變量$\lambda$和$\mu$之后，再對(duì)變量$x$求極小值。

為了簡化表述，定義如下極大值問題
$${\theta }_P(x)=\underset{\lambda ,\mu ,{\lambda }_i\ge 0}{\max }L(x,\lambda ,\mu )\text{\hspace{1em}(13)}$$
這是一個(gè)對(duì)變量$\lambda$和$\mu$求函數(shù)$L$的極大值的問題，將$x$看成常數(shù)。這樣，原始問題被轉(zhuǎn)化為先對(duì)變量$\lambda$和$\mu$求極大值，再對(duì)$x$求極小值。

這個(gè)原問題和我們要求解的原始問題有同樣的解，下面給出證明。對(duì)于任意的$x$，分兩種情況討論。

(1)如果$x$是不可行解，對(duì)于某些$i$有$g_i(x)>0$，即$x$違反了不等式約束條件，我們讓拉格朗日乘子${\lambda }_i=+\infty$，最終使得目標(biāo)函數(shù)${\theta }_P(x)=+\infty$。如果對(duì)于某些$i$有$h_i(x)\ne 0$，即違反了等式約束，我們可以讓${\mu }_i=+\infty ?\text{sgn}(h_i(x))$，從而使得${\theta }_P(x)=+\infty$。

即對(duì)于任意不滿足等式或不等式約束條件的$x$，${\theta }_P(x)$的值是$+\infty$。

(2)如果$x$是可行解，這時(shí)${\theta }_P(x)=f(x)$。因?yàn)橛?span id="vxwlu0yf4" class="katex--inline">$h_i(x)=0$且$g_i(x)\le 0$，而我們要求${\lambda }_i\ge 0$，因?yàn)?span id="vxwlu0yf4" class="katex--inline">${\theta }_P(x)$的極大值就是$f(x)$。為了達(dá)到這個(gè)極大值，我們讓${\lambda }_i$和${\mu }_i$為$0$，函數(shù)$f(x)+{\sum }_{i=1}^p{\mu }_i{h}_i(x)$的極大值就是$f(x)$。

綜上兩種情況，問題${\theta }_P(x)$和我們要優(yōu)化的原始問題的關(guān)系可以表述為
$${\theta }_P(x)=\{\begin{array}{ll}f(x)& g_i(x)\le 0,h_i(x)=0\\ +\infty & \text{else}\end{array}$$
即${\theta }_P(x)$是原始優(yōu)化問題的無約束版本。對(duì)于任何不可行的$x$，有${\theta }_P(x)=+\infty$，從而使得原始問題的目標(biāo)函數(shù)趨向于無窮大，排除掉$x$的不可行區(qū)域，只剩下可行的$x$組成的區(qū)域。

這樣我們要求解的帶約束優(yōu)化問題被轉(zhuǎn)化成了對(duì)$x$不帶約束的優(yōu)化問題，并且二者等價(jià)。

下面定義對(duì)偶問題與其最優(yōu)解$d^{?}$。
$$d^{?}=\underset{\lambda ,\mu ,{\lambda }_i\ge 0}{\max }\underset{x}{\min }L(x,\lambda ,\mu )=\underset{\lambda ,\mu ,{\lambda }_i\ge 0}{\max }{\theta }_D(\lambda ,\mu )\text{\hspace{1em}(14)}$$
這里先固定拉格朗日乘子$\lambda$和$\mu$，調(diào)整$x$讓拉格朗日函數(shù)對(duì)$x$求極小值；然后調(diào)整$\lambda$和$\mu$對(duì)函數(shù)求極大值。

原問題和對(duì)偶問題只是改變了求極大值和極小值的順序，每次操控的變量是一樣的。如果原問題和對(duì)偶問題都存在最優(yōu)解，則對(duì)偶問題的最優(yōu)值不大于原問題的最優(yōu)值，即
$$d^{?}=\underset{\lambda ,\mu ,{\lambda }_i\ge 0}{\max }\underset{x}{\min }L(x,\lambda ,\mu )\le \underset{x}{\min }\underset{\lambda ,\mu ,{\lambda }_i\ge 0}{\max }L(x,\lambda ,\mu )=p^{?}\text{\hspace{1em}(15)}$$
證明，假設(shè)原問題的最優(yōu)解為$x_1,{\lambda }_1,{\mu }_1$，對(duì)偶問題的最優(yōu)解為$x_2,{\lambda }_2,{\mu }_2$，由于原問題是先對(duì)$(\lambda ,\mu )$取極大值，有
$$L(x_1,{\lambda }_1,{\mu }_1)\ge L(x_1,{\lambda }_2,{\mu }_2)$$
這里固定$x_1$。

而對(duì)偶問題先對(duì)$x$取極小值，有
$$L(x_2,{\lambda }_2,{\mu }_2)\le L(x_1,{\lambda }_2,{\mu }_2)$$
這類變化的只是$x$。上面兩個(gè)式子中右邊都是一樣的，從而有
$$L(x_1,{\lambda }_1,{\mu }_1)\ge L(x_2,{\lambda }_2,{\mu }_2)$$
這一結(jié)論稱為弱對(duì)偶定理(Weak Duality)。

原問題最優(yōu)值和對(duì)偶問題最優(yōu)值的差$p^{?}?d^{?}$稱為對(duì)偶間隙。如果原問題和對(duì)偶問題有相同的最優(yōu)解，那么我們就可以把求解原問題轉(zhuǎn)化為求解對(duì)偶問題，此時(shí)對(duì)偶間隙為0，這種情況稱為強(qiáng)對(duì)偶。

但要滿足怎樣的條件才能使得$d^{?}=p^{?}$呢，就是下面闡述的KKT條件。

KKT條件

KKT(Karush-Kuhn-Tucker)條件用于求解帶有等式和不等式約束的優(yōu)化問題，是拉格朗日乘子法的推廣。

對(duì)于如下帶等式約束和不等式約束的優(yōu)化問題：
$$\begin{array}{rlrl}& \text{minimize}& & f(x)\\ & \text{s.t.}& & g_i(x)\le 0,i=1,\dots ,m\\ & & & h_i(x)=0,i=1,\dots ,n\end{array}\text{\hspace{1em}(16)}$$
與拉格朗日對(duì)偶的做法類似，為其構(gòu)造拉格朗日乘子函數(shù)消掉等式和不等式約束：
$$L(x,\lambda ,\mu )=f(x)+\sum _{i=1}^m{\mu }_i{g}_i(x)+\sum _{i=1}^n{\lambda }_i{h}_i(x)\text{\hspace{1em}(17)}$$
$\lambda$和$\mu$稱為KKT乘子。

KKT條件包括：

1. ${?}_{x}L(x,\lambda ,\mu )=0$
2. $g_i(x)\le 0$
3. $h_i(x)=0$
4. ${\mu }_i\ge 0$
5. ${\mu }_i{g}_i(x)=0$

其中第三個(gè)條件$h_i(x)=0$等式約束和第二個(gè)條件$g_i(x)\le 0$不等式約束是本身應(yīng)該滿足的約束；第一個(gè)條件${?}_{x}L(x,\lambda ,\mu )=0$和拉格朗日乘子法相同。

第四個(gè)條件稱為對(duì)偶可行性條件；

第五個(gè)條件稱為互補(bǔ)松弛條件，而且當(dāng)一個(gè)變量取非零值時(shí)，另一個(gè)變量必須取零。

KKT條件是取得極值的必要條件，但如果一個(gè)優(yōu)化問題是凸優(yōu)化問題，則KKT條件是取得極小值的充分條件。

Slater條件

Slater條件：一個(gè)凸優(yōu)化問題如果存在一個(gè)候選$x$使得所有不等式約束都是嚴(yán)格滿足的，即對(duì)于所有的$i$都有$g_i(x)<0$，也就是說，在不等式約束區(qū)域內(nèi)部至少有一個(gè)可行點(diǎn)，則存在$(x^{?},{\lambda }^{?},{\mu }^{?})$使得它們同時(shí)為原問題和對(duì)偶問題的最優(yōu)解，即
$$p^{?}=d^{?}=L(x^{?},{\lambda }^{?},{\mu }^{?})$$
Slater條件是強(qiáng)對(duì)偶成立的充分條件而不是必要條件。

小結(jié)

Slater條件和KKT條件都是用來判斷最優(yōu)化問題是否有解的條件。它們之間的關(guān)系可以總結(jié)如下：

• Slater條件是一種充分條件，當(dāng)最優(yōu)化問題滿足Slater條件時(shí)，會(huì)保證強(qiáng)對(duì)偶性成立，并且原始問題和對(duì)偶問題都存在最優(yōu)解。具體來說，Slater條件要求不等式約束條件 $g_i(x)\le 0$ 和等式約束條件 $h_i(x)=0$ 滿足嚴(yán)格可行性，即存在一個(gè)$x$使得所有的不等式約束條件 $g_i(x)<0$ 均嚴(yán)格成立。
• KKT條件是一組必要條件，可以用于判斷某個(gè)點(diǎn)是否為最優(yōu)解。對(duì)于有約束的最優(yōu)化問題，其KKT條件包括互補(bǔ)松弛條件、不等式約束條件的拉格朗日乘子大于等于零以及梯度為零。若最優(yōu)化問題的解滿足KKT條件，則該解是最優(yōu)解的必要條件。

需要注意的是，Slater條件只是強(qiáng)對(duì)偶性的一種充分條件，而不是必要條件。也就是說，如果一個(gè)問題不滿足Slater條件，仍然有可能存在最優(yōu)解以及強(qiáng)對(duì)偶性。而KKT條件則是最優(yōu)解的必要條件，但不一定是充分條件，也就是說，一個(gè)滿足KKT條件的點(diǎn)并不一定是最優(yōu)解。

因此，在實(shí)際求解問題時(shí)，我們通常需要結(jié)合Slater條件和KKT條件來進(jìn)行判斷，以保證得到的解是可行的、正確的，并且滿足約束條件。

最優(yōu)化方法

梯度下降法

梯度下降法(gradient descent)或最速下降法是求解無約束最優(yōu)化問題的一種最常用的方法，它的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單。梯度下降法是一種迭代算法，每一步需要求解目標(biāo)函數(shù)的梯度向量。

假設(shè)$f(x)$是${\mathbb{R}}^n$是具有一階連續(xù)偏導(dǎo)數(shù)的函數(shù)。要求解的無約束最優(yōu)化問題是
$$\underset{x\in {\mathbb{R}}^n}{\min }f(x)\text{\hspace{1em}(18)}$$
$x^{?}$表示目標(biāo)函數(shù)$f(x)$的極小值點(diǎn)。

梯度下降法通過選擇適當(dāng)?shù)某踔?span id="vxwlu0yf4" class="katex--inline">$x^{(0)}$，不斷迭代，更新$x$的值，進(jìn)行目標(biāo)函數(shù)的極小化，直到收斂。由于負(fù)梯度方向是使函數(shù)值下降最快的方向，在迭代的每一步，以負(fù)梯度方向更新$x$的值，從而達(dá)到減少函數(shù)值的目的。

由于$f(x)$具有一階連續(xù)偏導(dǎo)數(shù)，若第$k$次迭代值為$x^{(k)}$，則可將$f(x)$在$x^{(k)}$附近進(jìn)行一階泰勒展開：
$$f(x)=f(x^{(k)})+g_k^T(x?x^{(k)})\text{\hspace{1em}(19)}$$
在人工智能高等數(shù)學(xué)中我們知道在$x=a$點(diǎn)的泰勒展開式為：
$$g(x)=f(a)+\frac{f^{\prime }(a)}{1!}(x?a)+\frac{f^{\prime \prime }(a)}{2!}(x?a{)}^2+\frac{f^3(a)}{3!}(x?a{)}^3+...+\frac{f^n(a)}{n!}(x?a{)}^n\text{\hspace{1em}(20)}$$
這里去掉了高階項(xiàng)就得到了公式$(19)$，$g_k=g(x^{(k)})=?f(x^{(k)})$為$f(x)$在$x^{(k)}$的梯度，即一階偏導(dǎo)。

求出第$k+1$次迭代值$x^{(k+1)}$：
$$x^{(k+1)}\leftarrow x^{(k)}+{\lambda }_k{p}_k\text{\hspace{1em}(21)}$$
其中，$p_k$是搜索方向，取負(fù)梯度方向$p_k=??f(x^{(k)})$，${\lambda }_k$是步長，這里由一維搜索確定，即找到${\lambda }_k$使得
$$f(x^{(k)}+{\lambda }_k{p}_k)=\underset{\lambda \ge 0}{\min }f(x^{(k)}+\lambda p_k)\text{\hspace{1em}(22)}$$

一維搜索是一種優(yōu)化算法，也被稱為線性搜索。在機(jī)器學(xué)習(xí)中，一維搜索通常是用來確定如何更新模型參數(shù)的步長或?qū)W習(xí)率，以最小化訓(xùn)練數(shù)據(jù)上的損失函數(shù)。

一維搜索可以簡單理解為在某個(gè)方向上尋找一個(gè)合適的步長，使得當(dāng)前位置向這個(gè)方向前進(jìn)這個(gè)步長之后，能夠使目標(biāo)函數(shù)（或者損失函數(shù)）達(dá)到最小值。其實(shí)現(xiàn)過程通常是沿著負(fù)梯度方向進(jìn)行搜索，并通過逐步縮小搜索范圍和增加精度等方法，找到一個(gè)近似的最優(yōu)解。

因?yàn)橐痪S搜索只在一個(gè)方向上進(jìn)行搜索，在復(fù)雜的高維問題中很少直接使用，通常會(huì)作為其他更復(fù)雜優(yōu)化算法的輔助手段。

梯度下降法算法如下：

輸入： 目標(biāo)函數(shù)$f(x)$，梯度函數(shù)$g(x)=?f(x)$，計(jì)算精度$?$；

輸出： $f(x)$的極小點(diǎn)$x^{?}$。

(1) 取初值$x^{(0)}\in {\mathbb{R}}^n$，令$k=0$。

(2) 計(jì)算$f(x^{(k)})$。

(3) 計(jì)算梯度$g_k=g(x^{(k)})$，當(dāng)$||g_k||<?$時(shí)，停止迭代，令$x^{?}=x^{(k)}$；否則，令$p_k=?g(x^{(k)})$，求${\lambda }_k$使
$$f(x^{(k)}+{\lambda }_k{p}_k)=\underset{\lambda \ge 0}{\min }f(x^{(k)}+\lambda p_k)$$
(4) 置$x^{(k+1)}=x^{(k)}+{\lambda }_k{p}_k$，計(jì)算$f(x^{(k+1)})$

當(dāng)$||f(x^{(k+1)})?f(x^{(k)})||<?$或$||x^{(k+1)}?x^{(k)}||<?$時(shí)，停止迭代，令$x^{?}=x^{(k+1)}$。

(5) 否則，置$k=k+1$，轉(zhuǎn)(3)。

當(dāng)目標(biāo)函數(shù)是凸函數(shù)時(shí)，梯度下降法的解釋全局最優(yōu)解。但一般情況下，其解不保證是全局最優(yōu)解。且收斂速度也未必是很快的。

如果是無約束優(yōu)化問題，想要收斂速度快的話，可以考慮牛頓法或擬牛頓法。

牛頓法和擬牛頓法都是求解無約束最優(yōu)化問題的常用方法，具有收斂速度快的優(yōu)點(diǎn)。牛頓法是迭代算法，每一步需要求解目標(biāo)函數(shù)的海森矩陣的逆矩陣，計(jì)算比較復(fù)雜，而且有時(shí)候海森矩陣不一定存在逆陣。擬牛頓法通過正定矩陣近似海森矩陣的逆矩陣或海森矩陣，簡化了這一計(jì)算過程。