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

脚本——一维非线性规划(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)，（rho<1/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，要求rho<1/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步压缩之后，极小点所在区间长度将压缩到初始区间长度的(1-rho)^N约等于(0.61803)^N，称为总压缩比。（动画5）重复以上过程，如此往复，通过多次计算，即可获得精度水平足够的区间。(ppt13)黄金分割法算法步骤：（动画1）1、给定初始区间[𝑎_0，b_0]，给定精度要求epsina>0。令𝑎_1=𝑎_0+rho(b_0-𝑎_0)，b_1=𝑎_0+(1-rho)(b_0-𝑎_0)，并计算f(𝑎_1)与f(b_1)。（动画2）2、若b_1-𝑎_1<epsina，算法停止；否则，当f(𝑎_1)≥f(b_1)时，转3；当f(𝑎_1)<f(b_1)时，转4。（动画3）3、当f(𝑎_1)≥f(b_1)时,则𝒙*属于[𝑎_1，b_0]，令𝑎_2=b_1，b_2=𝑎_1+(1-rho)(b_0-𝑎_1)，计算f(b_2)。（动画4）4、当f(𝑎_1)<f(b_1)时，则𝒙*属于[𝑎_0，b_1]，令b_2=𝑎_1，𝑎_2=𝑎_0+rho(b_1-𝑎_0)，计算f(𝑎_2)。（动画5）5、重复上述计算过程，直到精度达到要求。(ppt14)（动画1）接下来介绍斐波那契法，它也是一种区间收缩算法，它与黄金分割法的区别：在区间压缩过程中，允许压缩比参数不断调整。其次，该方法与黄金分割法的理念类似，需要确定一个参数序列，即使得每次迭代中只需要计算一次目标函数值即可。两次迭代的中间点选择方式如下图所示。（动画2）从图可以看出来，我们还是把区间分3部分，两端区间长度相同。与黄金分割法的区别是压缩比每一笔都变了，比如由第K次压缩后，到第K+1次压缩，压缩比为rho_k+1(ppt15)（动画1）接着，两次迭代中的参数满足rho_(k+1)(1-rho_k)=1-2rou_k，整理后可得rho(k+1)=1-rho_k/(1-rou_k)，rho_k属于[0，1/2]，N次迭代后的总压缩比：(1-rho_1)(1-rho_2)...(1-rho_N)很多序列都能满足上式，我们最终的目标就是要收敛快，即要使得多次迭代后的总压缩比达到最小，因此我们可建立一个有约束优化问题:（动画2）（见背板）minmize(1-rho_1)(1-rho_2)...(1-rho_N),subjecttorho_(k+1)=1-rho_k/(1-rho_k)，k=1，...N-1，rho_k属于[0，1/2]，k=1，...N。(ppt16)（动画1）下面要求这个优化问题的最优解，我们引入斐波那契数列F_1，F_2，F_3，...，令F_(0)=0，F_(1)=1；对于k大于等于1，有（动画2）F_(k+1)=F_(k)+F_(k-1)，（动画3）比如F3=3,F4=5,F5=8,也称这个序列为兔子序列。（动画4）（见背板）可以证明上述优化问题的最优解采用斐波那契数列表示，即：rho_1=1-F_(N)/F_(N+1)，rho_2=1-F_(N-1)/F_(N)，...，rho_k=1-F_(N-k+1)/F_(N-k+2)，...，rho_N=1-F_(1)/F_(2)。（动画5）斐波那契数列法的总压缩比为：(1-rho_1)(1-rho_2)...(1-rho_N)=[F_(N)/F_(N+1)][F_(N-1)/F_(N)]...[F_(1)/F_(2)]=1/F_(N+1)。(ppt17)（动画1）（见背板）斐波那契法算法步骤如下：①给定初始区间[𝑎_0，b_1]和精度要求，求迭代次数N,确定压缩比1-rho_1=1-F_(N)/F_(N+1)，计算中间点𝑎_1和b_1，并计算f(𝑎_1)与f(b_1)，其中，𝑎_1=𝑎_0+rho*(b_0-𝑎_0)，b_1=𝑎_0+(1-rho)(b_0-𝑎_0)。（动画2）②当f(𝑎_1)>f(b_1)时，转3；当f(𝑎_1)<f(b_1)时，转④。（动画3）③则𝒙*属于[𝑎_1，b_0]，令𝑎_2=b_1，b_2=𝑎_1+(1-rho)*(b_0-𝑎_1)，计算f(b_2)。（动画4）④则𝒙*属于[𝑎_0，b_1]，令b_2=𝑎_1，𝑎_2=𝑎_0+rho*(b_1-𝑎_0)，计算f(𝑎_2)。(ppt18)下面来看二分法：（动画1）设f(𝒙)是定义在区间[𝑎_0，b_0]上的连续可微函数，求解函数f(𝒙)在区间的极小点，该方法的思路是以0.5的比率逐步缩小搜索区间，并在区间压缩过程中利用函数的一阶导数。（动画2）算法步骤如下：（动画3）1、区间[𝑎_0，b_0]上，验证f(𝑎_0)*f(b_0)<0，给定精度epsina。（动画4）2、求解区间[𝑎_0，b_0]的中点𝒙(0)=(𝑎_0+b_0)/2，计算𝒙(0)处的一阶导数。（动画5）3、若𝒙(0)处的一阶导数>0，则极小值点𝒙*属于[𝑎_0，𝒙(0)]。（动画6）4、若𝒙(0)处的一阶导数>0，则极小值点𝒙*属于[𝒙(0)，b_0]。（动画7）5、若𝒙(0)处的一阶导数=0，则𝒙(0)为函数的极小值点。（动画8）6、判断是否达到精度epsina，否则，在区间[𝑎_0，𝒙_1]或[𝒙_1，b_0]重复步骤2-5。(ppt19)下面我们总结本节课所学习的内容(ppt20)三种方法比较：（动画1）1、黄金分割法的压缩比rho约等于0.618固定；斐波那契法压缩比每步可变,总的压缩比1/F_(N+1)；二分法的压缩比rho等于二分之一。后面的方法比前面方法收敛快。（动画2）2、黄金分割法和斐波那契法只用到用到了f(𝒙)的值，但二分法用到了f(𝒙)的导数值，对函数的条件要求更强。（动画3）给大家留