下降方向取方向导数小于零的方向：$p_k^T\nabla f(x_k)<0$

$$ x^{(k+1)}=x^{(k)}+\alpha_k p_k $$

1. 单调下降算法
2. 全局收敛，对初始点选取没有额外要求。 | 精确步长： $\alpha_k=\argmin_{\alpha\ge0}f(x^{(k)}-\alpha\nabla f(x^{(k)}))=\phi(\alpha)$ 锯齿证明 $0=[\nabla f(x_l)]^T\nabla f(x-\alpha x)=-[\nabla f(x_l)]^T[\nabla f(x_{l+1})]$,两相邻迭代步垂直，锯齿 二次函数： $\alpha_k=\frac{-p_k\nabla f(x_k)}{p_k}^T[\nabla^2 f(x_k)]p_k,p_k=-\nabla f$ | 一阶必要：$|\nabla f(x)|<\epsilon$ 函数值变换：(绝对误差，相对误差)$|f(x)-f(x)|<\epsilon$ 迭代点变化：$|x-x|<\epsilon$ | 以二次型函数为例：‣ | | 共轭梯度方向 | $p_l=-\nabla f(x_k)+\beta_kp_{k-1}$ | | | | | | 牛顿方向 | $p_k=-(\nabla^2 f(x_k))^{-1}\cdot\nabla f(x_k)$ | | | | | | 拟牛顿方向 | $p_k=-(B_k)^{-1}\cdot\nabla f(x_k),\\B_k\approx\nabla^2f(x_k)$ | | | | |

二次函数：$f(x)=\frac 12x^TQx-b^Tx,0=\nabla f =Qx^-b,x^=Q^{-1}b$

1. 函数单调下降
2. 全局收敛性

梯度方法收敛性和收敛率