凸问题的算法

最速下降法

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

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

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

设 $\phi \left (\alpha ight )=f\left ( x_k +\alpha d_k ight )$

通过微分 $\phi$ 并将其等于零，我们可以得到 $\alpha$。

因此算法如下 −

• 初始化 $x_0$、$\varepsilon_1$、$\varepsilon_2$ 并设置 $k=0$。

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

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

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

• 如果 $\left \| x_{k+1-x_k} ight \| <\varepsilon_1$ 或 $\left \| \bigtriangledown f\left ( x_{k+1} ight ) ight \| \leq \varepsilon_2$，转至步骤 6，否则设 $k=k+1$，转至步骤 2。

• 最优解为 $\hat{x}=x_{k+1}$。

牛顿法

牛顿法的工作原理如下 −

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

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

在 $x_{k+1} 处，\bigtriangledown y\left ( x_{k+1} ight )=\bigtriangledown f\left ( x_k ight )+H\left ( x_k ight )\left ( x_{k+1}-x_k ight )$

要使 $x_{k+1}$ 成为最优解，$\bigtriangledown y\left ( x_k+1 ight )=0$

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

此处 $H\left ( x_k ight )$ 应为非奇异值。

因此算法如下 −

步骤 1 −初始化 $x_0,\varepsilon$ 并设置 $k=0$。

步骤 2 − 找到 $H\left ( x_k ight ) \bigtriangledown f\left ( x_k ight )$。

步骤 3 − 求解线性系统 $H\left ( x_k ight )h\left ( x_k ight )=\bigtriangledown f\left ( x_k ight )$ 并求出 $h\left ( x_k ight )$。

步骤 4 − 找到 $x_{k+1}=x_k-h\left ( x_k ight )$。

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

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

共轭梯度法

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

$min f\left ( x ight )=\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$。