目标函数的几种极值求解方法

目标函数极值求解的几种方法

1 题目：min?x一维搜索法：

?2??2?x2?1?22，取初始点x????1,3?1T，分别用最速下降法，

牛顿法，共轭梯度法编程实现。

迭代下降算法大都具有一个共同点，这就是得到点x?k?后需要按某种规则确定一个方向d?k?，再从x?k?出发，沿方向d?k?在直线（或射线）上求目标函数的极小点，从而得到x?k?的后继点x?k?1?，重复以上做法，直至求得问题的解，这里所谓求目标函数在直线上的极小点，称为一维搜索。

一维搜索的方法很多，归纳起来大体可以分为两类，一类是试探法：采用这类方法，需要按某种方式找试探点，通过一系列的试探点来确定极小点。另一类是函数逼近法或插值法：这类方法是用某种较简单的曲线逼近本来的函数曲线，通过求逼近函数的极小点来估计目标函数的极小点。本文采用的是第一类试探法中的黄金分割法。原理书上有详细叙述，在这里介绍一下实现过程：

⑴ 置初始区间[a1,b1]及精度要求L>0,计算试探点?1和?1，计算函数值

f??1?和f??1?，计算公式是：?1?a1?0.382?b1?a1?，?1?a1?0.618?b1?a1?。令

k=1。

⑵ 若bk?ak?L则停止计算。否则，当f??K?>f??k?时,转步骤⑶;当

f??K??f??k?时,转步骤⑷ 。

⑶ 置ak?1??k,bk?1?bk,?k?1??k,?k?1?ak?1?0.618?bk?1?ak?1?,计算函数值

f??k?1?,转⑸。

⑷ 置ak?1?ak,bk?1??k,?k?1??k,?k?1?ak?1?0.382?bk?1?ak?1?,计算函数值f??k?1?,转⑸。

⑸ 置k=k+1返回步骤 ⑵。

1. 最速下降法

实现原理描述：在求目标函数极小值问题时,总希望从一点出发,选择一个目

标函数值下降最快的方向,以利于尽快达到极小点,正是基于这样一种愿望提出的最速下降法,并且经过一系列理论推导研究可知,负梯度方向为最速下降方向。

最速下降法的迭代公式是x?k?1??x?k???kd?k?，其中d?k?是从x?k?出发的搜索方

?k是从x?k?出发沿方向d?k?向，这里取在点x?k?处最速下降方向，即d?k????f?xk?。进行的一维搜索步长，满足f?x?k???kd?k???minf?x?k???d?k??。

??0

实现步骤如下：

⑴ 给定初点x?1??Rn ，允许误差??0，置k=1。⑵ 计算搜索方向d?k????f?xk?。

⑶ 若d?k???，则停止计算；否则，从x?k?出发，沿方向d?k?进行的一维搜索，求?k，使f?x?k???kd?k???minf?x?k???d?k??。

??0

⑷ x?k?1??x?k???kd?k?，置k=k+1返回步骤 ⑵。

2. 拟牛顿法

基本思想是用不包括二阶导数的矩阵近似牛顿法中的Hesse矩阵的逆矩阵，

因构造近似矩阵的方法不同，因而出现了不同的拟牛顿法。

牛顿法迭代公式：x?k?1??x?k???kd?k?，d?k?是在点x?k?处的牛顿方向，

d?k????2fx?k????1?fx?k?，?k是从x?k?出发沿牛顿方向d?k?进行搜索的最优步长。

??用不包括二阶导数的矩阵Hk近似取代牛顿法中的Hesse矩阵的逆矩阵

?2fx?k????1，Hk?1需满足拟牛顿条件。

实现步骤：

⑴ 给定初点x?1? ，允许误差??0。

⑵ 置H1?In（单位矩阵），计算出在x?1?处的梯度g1??f?x?1??，置k=1。

⑶ 令d?k???Hkgk。

⑷ 从x?k?出发沿方向d?k?搜索，求步长?k，使它满足

fx?k???kd?k??mifnx?k???d?k?，令x?k?1??x?k???kd?k?。

??0???? ，

⑸ 检验是否满足收敛标准，若fy否则进行步骤⑹。

??k?1?则停止迭代，得到点x?x????，

?k?1?

⑹ 若k=n，令x?1??x?k?1?，返回⑵；否则进行步骤⑺。⑺

令

gk?1??fx?k?1?

??，

p?k??x?k?1??x?k?，

q?k??gk?1?gk，

p?k?p?k?THkq?k?q?k?THk，置k=k+1 。返回⑶。Hk?1?Hk??k?T?k???k?TpqqHkq?k?

3. 共轭梯度法

若d?1?,d?2?,?,d?k?是Rn中k个方向，它们两两关于A共轭，即满足

d?i?TAd?j??0,i?j;i,j?1,?,k，称这组方向为A的k个共轭方向。共轭梯度法的

基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点，根据共轭方向的基本性质这种方法具有二次终止性。

实现步骤如下：

⑴ 给定初点x?1? ，允许误差??0，置

y?1??x?1?，d?1????f?y?1??，k=j=1。

⑵ 若fy?j???，则停止计算；否则，作一维搜索，求?j，满足

??

f?y?j???jd?j???minf?y?j???d?j??，令y?j?1??y?j???jd?j?。

??0

⑶ 若j?n，则进行步骤⑷，否则进行步骤⑸

⑷ 令d?j?1????fy?j?1???jd?j?，其中?j?

???fy?j?1?j???f?y???22，置j=j+1，转⑵。

⑸ 令x?k?1??y?n?1?，y?1??x?k?1?，d?1????f?y?1??，置j=1，k=k+1，转⑵ 。

4. 实验结果

T 用以上三种方法通过Matlab编程得到实验数据。初始值x?1???1,3? 。迭

代精度sum(abs(x1-x).^2)<1e-4。 第一次迭代 结果x?2? 第二次迭代 结果x?3? 第三次迭代 结果x?4? 第四次迭代 结果x?5? 实验结果分析：

x?2??1? x?2??2? x?3??1?

共轭梯度法 最速下降法 拟牛顿法 1.5151631286 1.5151631286 1.5151631286 0.9393474854 0.939347485 0.9393474854 1.9730082275 2.0108108072 2.0000076259 1.0538992374 0.9861577108 1.0000419788 1.9869133934 2.005410162 2.0000038167 x?3??2? x?4??1? x?4??2? 0.9983654378 0.9896269240 0.9999998271 1.9992739761 1.0014531964

x?5??1? x?5??2? 由上表格可以看到最速下降法需要四次迭代实现所要求的精度，拟牛顿法和共轭梯度法需要三次。