(5.3.8)--2.4 一维非线性规划.doc

脚本——一维非线性规划

(ppt1,ppt2)同学，你好，这节课我们来学习一维非线性规划。

(ppt3)对于今天我们要讲的内容，先来了解这些问题实际背景。

(ppt4)（动画1,2）首先，我们观看下面两幅图，左边是汽车的流线图，我们设计的原则需要汽车受空气阻力尽量小，同时人坐车里需要舒适，外观需要漂亮等，设计出来的汽车流线就是一典型的一维非线性规划。（动画3）右边是平常所见到的桥梁道路曲线。这些都与一维非线性规划有着密切的联系，随着社会的发展，一维非线性规划也受到普遍的关注，广泛应用于科学工程等领域。

(ppt5)今天我们讲一维非线性规划的求解。在此之前，我们先看一维极值问题具体模型。

(ppt6)（动画1）无约束一维极值问题的一般表达式为：（动画2）??????f(??)，??属于R，或者??????f(??)，??属于[??_1，??_2]，（动画3）其中，??为一维变量，f(??)为一维变量??的函数。（动画4）针对一维极值问题的求解方法非常多，下面将主要介绍几类经典的有哪些信誉好的足球投注网站方法，如：黄金分割法、斐波那契法以及二分法。

(ppt7)（动画1）先来看黄金分割法，黄金分割法是用于求解一元单值函数f:R映到R，在闭区间[??_0，b_0]上是单峰的，即存在局部极小值点，且唯一。（动画2）对于极小值问题，单峰函数的图形如图所示。

(ppt8)黄金分割法的主要思想是：（动画1）首先，在区间[??_0，b_0]中挑选两点，由此把区间分为三段，然后再通过比较这两点的函数值大小，就可以确定是删去最左端还是最右端。如此进行下去不断缩短极小点所在的区间，直到达到足够的精度水平。（动画2）特别地，可以按照对称压缩方式来缩小极小点所在区间，即

（动画3）??_1-??_2=b_1-b_2=rho(b_0-??_0)，（rho1/2），（动画4）（见背板）具体的分段如下图所示，区间分3段，两边的长度相等，最好保证中间的长度小于两边的长度。

(ppt9)（动画1）在上述基础上，再计算目标函数值在中间点处的值，如果f(??_1)f(b_1)，那么极小点应该位于区间[??_0，b_1]中，若f(??_1)≥f(b_1)，极小点应该位于区间[??_1，b_0]中。（动画2）我们看示意图，为什么如果f(??_1)f(b_1)，那么极小点应该位于区间[??_0，b_1]中呢？因为在区间[??_0，b_1]中，至少有a1比区间的端点值小，说明在这个区间内，函数图形有下降的过程，极小值落在这个区间。

(ppt10)（动画1）通过上面分析，目标函数的极小点已经被压缩到[??_0，b_1]中。由于??_1已经位于区间[??_0，b_1]中，且f(??_1)已知，因此为了减少计算工作量，可令??_1作为b_2。这样我们还需要找一点??_2，找的原则是保证这一步的压缩比与前面的压缩比相同，并计算出函数在??_2的值。（动画2）具体的过程如图所示。第二次还是把区间分三部分，两边区间长度相等。剖分的原则是压缩比与第一次相同。

(ppt11)下面确定压缩比，即参数rho的确定：（动画1）不失一般性，假定初始区间[??_0，b_0]的长度为1，下一次压缩比仍是rho，（动画2）如图所示，经过一次压缩后区间长度变为[??_0，b_1]，把区间分三部分，[b_2，b_1]已经确定了。（动画3）左边区别取多长呢，即??_2位置如何选取，需要保证[??_0，a_2]等于[b_2，b_1]，且压缩比还是rho。因此我们可以得到

（动画4）rho（b_1-??_0）=b_1-b_2。（动画5）整个区间的长度假设为1后，b_1-??_0就等于1-rho，同时，由于第一次压缩两边的长度都是rho，因此夹在中间的部分为b_1-b_2=1-2rho，把他们代入上面方程中，（见背板）得到rho（1-rho）=1-2rho（动画6）整理后可得一元二次方程：rho^2-3rho+1=0，（动画7）解之可得rho_1=(3+5^(1/2))/2，rho_2=(3-5^(1/2))/2，要求rho1/2，从而可知rho=(3-5^(1/2))/2约等于0.382。

(ppt12)结合以上，我们对黄金分割法做一下总结：（动画1）由1-rho=(5^(1/2)-1)/2，故有rho/(1-rho)=(3-5^(1/2))/(5^(1/2)-1)=(1-rho)/1，即以rho/(1-rho)的比例划分区间，能够使的短区间与长区间长度之间的比值等于长区间与整个区间长度的比值。（动画2）如右上角图所示，第一次的压缩比为(1-rho)/1，（动画3）第二次的压缩比为rho/(1-rho)，这两个压缩比是相等的。（动画4）因此，按照1-rho的比例逐步压缩经过N步压缩之后，极小点所在区间长度将压缩到