[toc]

一、牛顿法

1.1 原理及公式

• 原理：对原始高维泰勒二阶展开用二阶近似，利用满足一阶必要条件解得一阶的极小点，类似于梯度法可得迭代公式。
• 

1.2 牛顿法的特点：

1.缺点 需要求Hesse矩阵的逆，也就是求解一个n维非齐次方程组，也可能黑塞矩阵不可逆；
当初始点原理目标函数的极小值时，即使0″ mathimg=”1″>也可能收敛的很慢。
如果黑塞矩阵非正定，牛顿法确定的方向也不必定是下降方向。

2. 优点 牛顿法可以求解多元方程组，这个时候F(x)表明的就是函数在x处的雅可比矩阵；
   牛顿法可以至少以阶数为二的收敛率收敛到
   对于正定二次型问题，牛顿法只需要一步就能走到最小点。

1.3牛顿修正法

• 加步长
• Levenberg-Marquardt修正，将Hesse矩阵变成，使其变成正定的。

二、共轭法

Prev

Gram-Schmid向量组共轭方法，从一组已知的线性无关向量组构造共轭向量。

2.1 共轭法的基本概念、原理和公式

2.1.1 定义

共轭定义：设Q是对称矩阵，对于所有方向，如果有，都有，则称他们是关于Q共轭的。
性质：如果Q是n阶对称正定矩阵，如果k个方向非零且关于Q共轭，那么它们是线性无关的。
定理：，该性质对最速下降法均成立。
原理：由于n个方向是提前给定的，每一步的公式中只需要求步长即可，那么步长的求法与最速下降一样，只需要求，解得

2.2 共轭法的特点

1. 收敛性质：对于n维二次型问题，能够在n步之内得到结果
2. 不需要计算Hesse矩阵也就不需要求逆了。

2.3 共轭梯度法

解二次型问题：

2.3.1 原理及公式

原理：每一次都利用上一次搜索方向和目标函数在当前迭代点的梯度向量之间的线性组合构造一个新方向，得到第k+1次方向：，使其与前面已经产生的搜索方向组成Q共轭方向。由定义可以求出：
性质：共轭梯度法的搜索方向是关于Q的共轭方向。

2.3.2解非二次型问题：

利用泰勒展开式的二阶近似，对应于共轭梯度法的Q矩阵，但是要求函数可微，且每次都需要计算黑塞矩阵，运算量可能很大。

2.3.3 实现注意事项

• n次迭代不必定到极小点，一般经过n次或n+1次迭代之后将搜索方向重新初始化为梯度方向
• 一维搜索精度：是影响共轭梯度法的关键因素

三、拟牛顿法

思想：构造一个正定矩来近似牛顿法中的，避免了求逆的计算量。
迭代公式：



正确性推导：
拟牛顿条件：由泰勒公式易得：
秩一修正公式：

正定的条件是构造出来的右边分母大于零。
性质：