最优化工程与应用基础_3,章

一维最优化2.黄金分割法3.进退法4.抛物线搜索法5.三次插值法1.一维最优化问题2一维最优化可以归结为单变量函数f(x)的极小化问题，是构成非线性最优化算法的基本算法，因为多元函数f(x1,…xn)都可以归结为在一系列逐步产生的下降方向上的一维搜索。一维最优化可以有试探法、精确搜索法和函数逼近法。下面我们讨论当搜索方向已经确定的情况下，如何选取步长？即，对于如下函数选取变量α，使得，并下降最多，该变量值为最优步长αk，这就是一维最优化问题。)(1kkkSXfXfkkXfXf11.一维最优化问题首先回顾一下古老的黄金分割问题:将线段L分成两段，较长段为x，较短段为L-x，要求xLxxL可以解出LLx618.02152.黄金分割法1.单峰函数定义：设)(xf是区间],[ba上的一元函数，x是)(xf在],[ba上的极小点，且对任意的,,],[,2121xxbaxx有（a）当xx2时，;)()(21xfxf（b）当时，xx1.)()(21xfxfa..b.x..1x2x则称是单峰函数。)(xf..2.黄金分割法性质：通过计算区间],[ba内两个不同点的函数值，就可以确定一个包含极小点的子区间。定理设是区间],[ba上的一元函数，x是)(xf在],[ba上的极小点。任取点)(xf,],[badc则有（1）如果)()(dfcf，则;],[bcx（2）如果,)()(dfcf则。],[daxa..b.x..cd6ab10.6180.382x2x10.382假设f(x1)f(x2)，x1为好点，将线段[x2,b]舍去，缩小后的新区间为[a，x1]，要求x1在新区间内仍然是具有对称关系的点，只需再产生一个新点，就可以缩小区间。因此，x1在新区间变为x2，并且符合黄金分割原理。已知初始区间[a,b]，目标函数f(x)在该区间内为单谷函数。提出两个试探点，按照黄金分割方法，两点对线段b-a满足黄金分割原理。下面对黄金分割法做进一步讨论。0.618x2x11aabax382.01abax618.02黄金分割法迭代公式：分别计算f1和f2，如果f1f2，说明x2是好点，新的区间为[x1,b]，x1点变为新区间的a点，x2点变为新区间的x1点，函数值f2等于新区间x1点的函数值f1，只需计算新的试探点x2。如果f1f2，说明x1是好点，新的区间为[a,x2]，x2点变为新区间的b点，x1点变为新区间的x2点，函数值f1等于新区间x2点的函数值f2，只需计算新的试探点x1。7abaxabax618.0382.0212.黄金分割法2.黄金分割法思想通过选取试探点使包含极小点的区间不断缩短，直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。下面推导黄金分割法的计算公式。上单峰，在设],[)(11baxf].,[11bax极小点假设进行次迭代前第k],,[kkbax],,[,kkkkba取规定.kk,)()(kkff和计算分两种情况：,)()(.1kkff若,1kka则令;1kkbb,)()(.2kkff若,1kkaa则令.1kkb？与如何确定kkkkkkab.1比率相同，即每次迭代区间长度缩短.2)0()(11kkkkabab)1()2(）可得：）与（由式（21)())(1(kkkkkkkkabaaba)3()4(件：要求其满足以下两个条kakbkku？取值的确定通过确定的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。,)()()1(kkuffk次迭代时有设在第则有。],[],[11kkkkuaba,,111kkuk次迭代时选取在第）有则由（4)(1111kkkkabau)(2kkkaba。不必重新计算因此则，如果令112,1kkkuu618.021512。次迭代时有若在第)()()2(kkuffk同理可得。算法步骤：0.],,[.111精度要求给定初始区间ba.1:k令),(382.01111aba令),(618.01111aba).()(11ff与并计算,.2kkab若停止，.2kkabx且否则，；时，转当3)()(kkff.4)()(时，转当kkff,.31kka令,1kkbb,1kk),(618.01111kkkkaba),(1kf计算。转2,.41kkaa令,1kkb,1kk),(382.01111kkkkaba),(1kf计算,1:kk令。转2,1:kk令黄金分割法的迭代效果：第k次后迭代后所得区间长度为初始区间长度的。倍k)215(黄金分割法适用于单谷区间上的任何函数，甚至是不连续函数，适用非常广泛。例.用黄金分割法求解如下一维非线性最优化问题：12min2xxxf初始区间为[a,b]=[-1,1],ε=0.16.解：236.0618.0236.0382.021abaxabax125.12,653.01ff528.0236.01618.0236.0618.02236.021,1,236.01abaxxxbbxa970.02,125.11ff因为f1f2,取：基本思想：对f(x)任选一个初始点a1及初始步长h，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高—低—高”形态。（1）选定初始点a,初始步长h＝h0，计算y1＝f(a1)，y2＝f(a1＋h)。（2）比较y1和y2。（a）如y1y2,向右前进；加大步长h＝2h，转（3）向前。（b）如y1y2,向左后退；h＝－h0，转（3）向后探测。（c）如y1＝y2，极小点在a1和a1＋h之间。步骤：3．进退法（3）产生新的探测点a3＝a1＋h，y3＝f(a3);（4）比较函数值y2与y3：（a）如y2y3,则初始区间得到；h0时，[a,b]=[a1,a3];h0时，[a,b]=[a3,a1];（b）如y2y3,加大步长h＝2h，a1=a2,a2=a3,转（3）继续探测。3．进退法确定初始单谷区间进退法示意图3．进退法抛物线插值法又叫二次插值法，以目标函数的抛物线插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索算法。插值法指的是已知几个点，用特定曲线将这些点连接起来，该曲线称为插值曲线，该曲线对应的函数称为插值函数。常用的插值方法有多项式插值和样条插值。其中，抛物线插值和线性插值是最为常用的两种多项式插值方法。4.抛物线插值考虑一维搜索问题：xfbxaminf(x)在[a,b]初始区间内为单谷函数。首先用试探法找到一点c，满足f(c)f(b)，f(c)f(b)，一般选取c为中间点。记为x1=a,x2=b,x3=c,f1=f(a),f2=f(c),f3=f(b)。4.抛物线插值思想在极小点附近，用二次三项式),()(xfx逼近目标函数处有相同的函数值，在三点与令)3()2()1()()(xxxxfx并假设).()(),()()3()2()2()1(xfxfxfxf)1(x)2(x)3(x)(xf)(xx*x,)(2cxbxax设)()()1(2)1()1()1(xfcxbxax)()()2(2)2()2()2(xfcxbxax)()()3(2)3()3()3(xfcxbxax.)(cbx和的系数近函数解上述方程组，可得逼的极小点，再求函数)(x令cxbx2)(,0解得cbx2如何计算函数?)(x。的极小点的估计值作为以)(xfx])()()()()()([2)()()()()()()3()2()1()2()1()3()1()3()2()3()2()1()2()1()3()1()3()2(222222xfxxxfxxxfxxxfxxxfxxxfxx令抛物线插值算法步骤：,],[)1()3()1(xx给定初始区间).()(),()()3()2()2()1(xfxfxfxf设。给定精度。。令)1()0(1:xxk。令。设3,2,1,)()()()2()()(2ixfxcxbxaxii解出。的极小点解出。系数cbxxcbak2)(,,)(及其的函数值最小的三个点中选择和从)(,,)3()()3()2()1(xfxxxxk。）转（。令。重新标记为左、右两点，21:,,)3()2()1(kkxxx）。否则转（，则算法停止若3,|)()(|)1()(kkxfxf5.三次插值法思路：,0)()()()1()2()1()2()1(xfxxxxxf且有，的函数值、在点已知利用这两点的函数值的极小点。内存在（则区间)(),.0)()2()1()2(xfxxxf在这两点有相同的函使它与项式和导数构造一个三次多)(,)(xfx的极小点。的极小点近似并用逼近用数值和导数，)()(,)()(xfxxfx)1(x)2(x)(xf)(x*xx设)1()()()()()1(2)1(3)1(dxxcxxbxxax令)()()()()()()()()2()2()1()1()2()2()1()1(xfxxfxxfxxfx则有)()(2)(3)()()()()()()2()1()2(2)1()2()1()2()1()2(2)1()2(3)1()2()1(xfcxxbxxaxfcxfdxxcxxbxxaxfd)2(。从而确定函数，的值求解方程组得出系数)(,,,xdcba的方法：确定函数)(x求解满足0)(0)(xx的极小点令0)(2)(3)()1(2)1(cxxbxxax)3(。bxxax2)(6)()1(而解方程（3），有两种情况：解得时，当0.1a)4(2)1(bcxx由（2）可知。)1()2()2()1(,0)(,0)(xxxfxfc。所以0b的极小点。是即因此)(,02)(xxbx。x解得时，当0.2aaacbbxx332)1()5(acbbaacbbax322336)(22此时有式中应取则在为使)5(,0)(xaacbbxx332)1(acbbc32)6(式可知由时，而当)6(0a式所以，)6(2)1(bcxx一表达式。两种情况下极小点的统、是21极小点的计算公式：令)7()]()([3)1()2()1()2(xxxfxfs)8()()()2()1(xfxfst)9()()()2()1(22xfxftw)10()2)()()(1)(()1()2()2()1()2()1(wxfxfwtxfxxxx则有算法步骤：要求计算给定初始点,)(,)(,)(,)(,,.1)2()1()2()1()2()1(xfxfxfxfxx。满足条件：0)(,0)(,)2()1()1()2(xfxfxx。给定允许误差0,0。和、、计算、、、按照公式xwts)10()9()8()7(.2。否则，转；则停止计算，得到点，若4||.3)1()2(xxx。停止计算，得到点，若。计算xxfxfxf|)(|)(,)(.4。转。则令，若2)()(,)()(,0)()1()1()1(xfxfxfxfxxxf。转。则令，若2)(