凸問題算法

---

---

最速下降法

此方法也稱為梯度法或高斯法。此方法包含了下列術語 -

$$x_{k+1}=x_k+\alpha_kd_k$$

$d_k= - \bigtriangledown f\left ( x_k \right )$ 或 $ d_k= -\frac{\bigtriangledown f\left ( x_k \right )}{\left \| \bigtriangledown f\left ( x_k \right ) \right \|}$

令 $\phi \left (\alpha \right )=f\left ( x_k +\alpha d_k\right )$

通過對 $\phi$ 求導並令其等於零，我們可以得到 $\alpha$。

因此，算法如下 -

• 初始化 $x_0$,$\varepsilon_1$,$\varepsilon_2$，並設置 $k=0$。

• 設置 $d_k=-\bigtriangledown f\left ( x_k \right )$ 或 $d_k=-\frac{\bigtriangledown f\left (x_k \right )}{\left \|\bigtriangledown f\left (x_k \right ) \right \|}$。

• 找到 $\alpha_k$，使得它最小化 $\phi\left ( \alpha \right )=f\left ( x_k+\alpha d_k \right )$。

• 設置 $x_{k+1}=x_k+\alpha_kd_k$。

• 如果 $\left \| x_{k+1-x_k} \right \| <\varepsilon_1$ 或 $\left \| \bigtriangledown f\left ( x_{k+1} \right ) \right \| \leq \varepsilon_2$，轉到步驟 6，否則設置 $k=k+1$ 並轉到步驟 2。

• 最優解為 $\hat{x}=x_{k+1}$。

牛頓法

牛頓法應用以下原理 -

$f\left ( x \right )=y\left ( x \right )=f\left ( x_k \right )+\left ( x-x_k \right )^T \bigtriangledown f\left ( x_k \right )+\frac{1}{2}\left ( x-x_k \right )^T H\left ( x_k \right )\left ( x-x_k \right )$

$\bigtriangledown y\left ( x \right )=\bigtriangledown f\left ( x_k \right )+H\left ( x_k \right )\left ( x-x_k \right )$

在 $x_{k+1}, \bigtriangledown y\left ( x_{k+1} \right )=\bigtriangledown f\left ( x_k \right )+H\left ( x_k \right )\left ( x_{k+1}-x_k \right )$

對於最優解 $x_{k+1}$，$\bigtriangledown y\left ( x_{k+1} \right )=0$

因此，$x_{k+1}=x_k-H\left ( x_k \right )^{-1} \bigtriangledown f\left ( x_k \right )$

此處 $H\left ( x_k \right )$ 應為非奇異矩陣。

因此，算法如下 -

步驟 1 - 初始化 $x_0,\varepsilon$，並設置 $k=0$。

步驟 2 - 找出 $H\left ( x_k \right ) \bigtriangledown f\left ( x_k \right )$。

步骤 3 − 求解线性系统 $H\left ( x_k \right )h\left ( x_k \right )=\bigtriangledown f\left ( x_k \right )$，其中未知数为 $h\left ( x_k \right )。

步骤 4 − 求解 $x_{k+1}=x_k-h\left ( x_k \right )。

步骤 5 − 如果 $\left \| x_{k+1}-x_k \right \|< \varepsilon$ 或 $\left \| \bigtriangledown f\left ( x_k \right ) \right \| \leq \varepsilon$，则转到步骤 6，否则将 $k$ 设为 $k+1$ 并转到步骤 2。

步骤 6 −最优解为 $\hat{x}=x_{k+1}$。

共轭梯度法

此方法用于解决以下类型的求解问题 −

$min f\left ( x \right )=\frac{1}{2}x^T Qx-bx$

其中 Q 是正定 nXn 矩阵，而 b 为常数。

给定 $x_0,\varepsilon,$ 计算 $g_0=Qx_0-b$

将 $d_0=-g_0$ 设为 $k=0,1,2,...,$

将 $\alpha_k=\frac{g_{k}^{T}g_k}{d_{k}^{T}Q d_k}$ 设为

计算 $x_{k+1}=x_k+\alpha_kd_k$

将 $g_{k+1}=g_k+\alpha_kd_k$ 设为

计算 $\beta_k=\frac{g_{k}^{T}g_k}{d_{k}^{T}Qd_k}$

计算 $x_{k+1}=x_k+\alpha_kd_k$

将 $g_{k+1}=x_k+\alpha_kQd_k$ 设为

计算 $\beta_k=\frac{g_{k+1}^{T}g_{k+1}}{g_{k}^{T}gk}$

将 $d_{k+1}=-g_{k+1}+\beta_kd_k$ 设为。