凸问题的算法

---

最速下降法

该方法也称为梯度法或柯西法。该方法涉及以下术语 -

$$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 ) \右\|}$。

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

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

• 如果$\左\| 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 )^TH\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 \右)$

令 $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 )h\left ( x_k \right )=\bigtriangledown f\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$。