二次型最大值正定问题？

来源：蜘蛛抓取(WebSpider) 时间：2022-11-05 06:40 标签： 二次型最大值

在效率上，共轭方向法位于最速下降法和牛顿法之间。它具有特性：对于n维二次型问题，能够在n步之内得到结果；共轭梯度法不需要计算海森矩阵；不需要求逆；在二次型函数中，如果海森矩阵是正定的，可以收敛到全局最小点；非二次型问题，不保证收敛（除非离极值点较近），不保证收敛到极小值（除非使用修改的算法）。

定理：如果Q是n阶正定矩阵（自然是对称的），如果方向d(0), d(1),... , d(k)，k≤n-1非零，且是关于Q共轭的，那么它们线性无关；

构造n阶正定矩阵的n个共轭向量方法：利用Gram-Schmidt方法

1、n维二次型函数最小化问题

其中，Q是正定的，x是n维向量。

（1）基本的共轭方向算法

这种方法不需要预先给定Q共轭方向，而是随着迭代的进行不断产生Q共轭方向。在每次迭代中，利用上一个搜索方向和目标函数在当前迭代点的梯度向量之间的线性组合构造一个新的方向。

如果将上面的二次型函数视为某个目标函数泰勒展开式的二阶近似，就可以将共轭梯度法推广应用到一般的非线性函数。（当然应该要求展开点离函数极小点比较近，这样可以保证收敛）

 但是存在一个问题，在二次型函数中，海森矩阵Q是常数矩阵，而对于非线性函数则不一定，因此就需要在每次迭代过程中重新计算，尤其是逆矩阵，这将带来非常大的计算量。因此需要想办法避免Q的计算。从上面的算法中，可以看出f(x)的海森矩阵Q只出现在 αk 和 βk 的计算公式中，而 αk 的计算可以通过一维搜索方法代替，前面的文章介绍过。因此只需要考核 βk 的计算，

这样一方面通过搜索求解 αk ，另一方面通过上面三个公式求解 βk ，就避免了每次迭代中海森矩阵的计算， 只需要在每次迭代中计算目标函数值和梯度。对于二次型问题，三个公式是等价的。但是，对于目标函数为非线性函数时，三个公式并不一致。

3、停止条件： 使用前面文章中介绍的方法取代 梯度模为零， 见 

对于非二次型问题，共轭梯度法通常不会在n步之内收敛到极小点，随着迭代的进行，搜索方向将不再是Q共轭方向，因为海森矩阵不是常数矩阵，它依赖于以前的迭代，误差在不断累积。常用的解决办法是每经过几次迭代后，如n次或n+1次，重新将搜索方向初始化为目标函数梯度的负方向，然后继续搜索直至满足停止条件。另外，需要强调的是在非二次型函数最小化问题中，一维搜索中 αk 的精度对共轭梯度法的性能很关键，如果采用了不精确的一维搜索方法，建议使用H-S公式计算 βk 。

我要回帖

更多关于 二次型最大值 的文章

 

随机推荐