一阶算法

• 梯度法
• 梯度投影法
• 共轭梯度法
• Nesterov最优梯度法
• 信頼域法

符号：

梯度：$\displaystyle g(x)=\bigtriangledown f(x)$

$Hesse$ 矩阵：$G(x)=\bigtriangledown^2f(x)$

* 无约束优化的求解步骤

$x_{k+1}=x_k+\alpha_k d_k$

$d_k：x_k点使得f(x)下降的方向$

$\alpha_k：步长$

* 迭代算法的求解

• 线性搜索：先确定下降方向$d_k$，再确定步长$\alpha_k$
• 信頼域算法：先确定方向$\alpha_k$ ,再确定$d_k$
• 停止准则：$f(x_{k+1})-f(x_k)$足够小

* 收敛速度

• 算法收敛：$\displaystyle\lim\limits_{k->\infty}||x_k-x^*||=0$
• 线性收敛：$\displaystyle \lim\limits_{k->\infty}\frac{||x_{k+1}-x^*||}{||x_k-x^*||}=a$ 当0<a<1时，是线性收敛
• 超线性搜索：$a=0$ 时，是超线性收敛
• 二次收敛：$\displaystyle \lim\limits_{k->\infty}\frac{||x_{k+1}-x^*||}{||x_k-x^*||^2}=a \ \ \ $ $a$是任意常数，称为二阶收敛

无约束优化算法

* 两个任务

• 一阶迭代算法的设计
• 优化算法

* 梯度法

• 使用优化序列：

$x_{k+1}=x_k+\mu_k \bigtriangleup x_k \ \ \ \ \ x=1,2,...$

寻找最优值$x_{opt}$

• $\mu_k$是第$k$次迭代的步长
• $\bigtriangleup x_k$ 是搜索方向

对于所有的$k$,每次计算后的结果: $f(x_{k+1})< f(x_k)$

* 梯度法的推导

* 一阶展开

• 目标函数在$x_k$的一阶展开

$f(x_{k+1})\approx f(x_k)+(\bigtriangledown f(x_k)^T) \bigtriangleup x_k$

若： $(\bigtriangledown f(x_k)^T) \bigtriangleup x_k < 0$

则： $f(x_{k+1})< f(x_k)$ 成立

• 所以, 为了满足$(\bigtriangledown f(x_k)^T) \bigtriangleup x_k < 0$：

$\bigtriangleup x_k=-\bigtriangledown f(x_k) cos\theta$

$0 \leq \theta < \pi/2$是下降方向和负梯度方向$-\bigtriangledown f(x_k)$的夹角

• 若：$\theta=0$, 则：

$\bigtriangleup x_k=-\bigtriangledown f(x_k)$,搜索方向直接取得负梯度方向，此时具有最大的下降步伐

* 称为最速下降法

$x_{k+1} = x_k - \mu_k \bigtriangledown f(x_k) \ \ \ \ \ \ k=1,2,...$

* 二阶展开

$\min \limits_{\triangle x}f(x+\triangle x)=f(x)+(\bigtriangledown f(x))^T \bigtriangleup x+\frac{1}{2}(\bigtriangleup x)^T \bigtriangledown^2 f(x) \bigtriangleup x$

• 对于最优点，$\bigtriangleup x$的梯度必须等于0

$\displaystyle\frac{\partial f(x+\bigtriangleup x)}{\partial \bigtriangleup x} = \bigtriangledown f(x)+\bigtriangledown^2 f(x)\bigtriangleup x=0$

$\iff \bigtriangleup x_{nt}=-(\bigtriangledown^2 f(x))^{-1} \bigtriangledown f(x_k)$

• $\bigtriangleup x_{nt}$是$Netton$的下降方向

梯度下降算法的总结

* 步骤1

• 选择起始点$x_1\in dom f$和允许的精度$\epsilon > 0, 令k =1$

• 计算目标函数在点$x_k$的梯度$\bigtriangledown f(x_k)$（或者是Hessian矩阵 $\bigtriangledown^2 f(x_k)$）

• 选择下降方向

  • 最速度下降法：$\bigtriangleup x_k = -\bigtriangledown f(x_k)$
  • 牛顿法：$\bigtriangleup x_k =-(\bigtriangledown^2 f(x))^{-1} \bigtriangledown f(x_k)$

* 步骤2

• 选择步长$\ \mu_k > 0$

* 更新优化序列

$x_{k+1}=x_k+\mu_k \bigtriangleup x_k$

* 步骤3

• 判断是否满足停止准则：

$|f(x_{k+1})- f(x_k)|\leq \epsilon$

则：计算停止输出$x_k$

* 否则

$k \leftarrow k+1$, 返回，进行下一轮计算