1.一些概念
$$ x_{k+1}=x_k + \alpha_k p_k $$
通过 $ || \nabla{f_k}|| < \epsilon $ 判断迭代是否停止
1.1 算法收敛性（是否收敛）
收敛条件（强）：（满足这个条件，算法一定会终止）
$$ \lim_{k\to\infty}||\nabla{f(x_i)}|| = 0 $$
收敛条件（弱）【下界限】：
$$ \lim_{k \to \infty} inf ||\nabla f(x_k)|| = 0 $$
对下界限条件的反正法：
当$ k \to \infty $, $||\nabla f(x_k) || \ge \epsilon > 0 $
1.2 收敛速度
（1）线性： $ || X_{k+1} - X^* || \le \Gamma || X_k - X^* || , 0<\Gamma<1 $
当 $\Gamma 接近0的时候，收敛很快，\Gamma接近1，收敛就很慢$
（2）二次：$ || X_{k+1} - X^*|| \le L || X_k - X^* ||^2, L>0 $
需要注意的是，这里的参数L是允许大于1的，因为主要依靠 $|| X_k - X^* ||^2 $这一部分进行收敛，所以当$ L>1 $和 $|| X_k - X^* ||^2 >1$, 那么这个二次收敛就没有意义了。所以只有当$|| X_k - X^* ||^2 $很小很小的时候才有意义。
（3） 超线性： $ || X_{k+1} - X^* || = o (|| X_k - X^* || ) $
1.3 所需条件
1.3.1 关于f(x)
水平界 L = { x | f(x) $\le$ f($x_0$)}，$ x_0 $ 是连续的
因为 L 不连续，有洞，所以需要有一个区域$ D \supseteq L$, D是L把洞口补起来得到的，我们更多也是在D上讨论。
f(x)下面有界限（必须的），上面有界
f(x)连续
f(x) 满足Lipscity连续， $ |f(x)-f(y)| \le L||x-y|| $, 当 $ |x-y| \to 0,| f(x)-f(y)| 也\to 0$
1.3.2 关于 $ \nabla f(x)$和 $\nabla^2f(x)$, 同上
1.3.3 关于方向 下降
下降方向 意味着：$\nabla f_k^T p_k < 0 $
最速下降：$ p_k = \nabla f_k $
牛顿法：$ p_k^N = - \nabla^2 f_k^{-1}\nabla f_k $
拟牛顿法： $ p_k^N = - B_k^{-1}\nabla f_k $
1.3.4 对于步长怎么选择：$\alpha_k $
目标函数： $ \alpha_k = \operatorname{argmin}{f(x_k + \alpha p_k)} , \alpha_k>0$
wolfe条件-1: $ \alpha $要充分下降（充分下降条件） $ f_{k+1} \le f_k + c_1 \alpha_k \nabla f_k^T p_k $
1.3.5 如果 $ x_k \to x^*,那么 x^*$满足二阶充分条件
二阶充分条件如下：
$ \nabla f(x^*) = 0 $
$ \nabla^2 f(x^*) $ 是正定
2 收敛性
2.1 定理（课本定理3.2）
首先假设： $ \nabla f(x) 满足 Lipschily 连续$
p_k 下降
$ \alpha_k 满足wolfe条件 $
在这三个假设下，则：$ \sum_k^N || \nabla f_k||^2 cos^2 \theta_k < \infty $
其中，$ cos \theta_k = \frac{ - \nabla f_k^T p_k}{|| \nabla f_k || || p_k ||}$
记(wolfer第一条件的解释）： $ f_{k+1} \le f_k + c_1 \alpha_k \nabla f_k^T p_k $
$ \Leftarrow \frac{f_k - f_{k+1}}{\alpha_k || p_k ||} \ge c_1 || \nabla f_k || cos\theta_k $
$ {f_k - f_{k+1}}{\alpha_k || p_k ||} $表示平均收敛速度
$ c_1 || \nabla f_k || cos\theta_k $表示初始斜率
wolfer第二条件的解释:
记：$ \nabla f_{k+1}^T p_k \ge c_2 \nabla f_k^T p_k , c_2<1$