最优化方法及其应用课后答案郭科陈聆魏友华

最优化方法部分课后习解答     1.一直优化问题的数学模型为：习题一12minf(x)=(x­3)2+(x­4)2⎧5g(x)=x­x­≥0⎜1122⎜s.t.⎨g2(x)=­x1­x2+5≥0     试用图解法求出：⎜0g(x)=x≥⎜31⎜⎩g4(x)=x2≥0（1）无约束最优点，并求出最优值。（2）约束最优点，并求出其最优值。（3）如果加一个等式约束h(x)=x1­x2=0，其约束最优解是什么？*解：（1）在无约束条件下，f(x)的可行域在整个x10x2平面上，不难看出，当x=（3，4）时，f(x)取最小值，即，最优点为x*=（3，4）：且最优值为：f(x*)=0 （2）在约束条件下，f(x)的可行域为图中阴影部分所示，此时，求该问题的最优点就是  在约束集合即可行域中找一点(x1,x2)，使其落在半径最小的同心圆上，显然，从图示中可 以看出，当x*= (15,5)时，f(x)所在的圆的半径最小。44 ⎧g(x)=x­x­1125=0 ⎧15x1=⎜求解得到：⎨4其中：点为g1(x)和g2(x)的交点，令⎜⎨25   即最优点为x*=⎜⎩g2(x)=­x1­x2+5=0 (15,5)：最优值为：f(x*)= 65⎜x=⎜⎩24448（3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。2.一个矩形无盖油箱的外部总面积限定为S，怎样可使油箱的容量最大？试列出这个优化问题的数学模型，并回答这属于几维的优化问题.解：列出这个优化问题的数学模型为：maxf(x)=x1x2x3⎧x2+2x2x3+2x1x3≤S⎨x1⎜s.t.⎜x1>0⎜x2>0⎜⎩x3>0该优化问题属于三维的优化问题。⎝⎠ijn×n1212nnn⎝⎠⎜1212121 x=s/3,y= s/3,z=  s/12 v=s33s==1⎛=s⎞2182⎜3⎜ 习题二  3.计算一般二次f(x)=1XTAX+bTX+c的梯度。2解：设：A=(a,b=(b)T,X=(x,x,.T：),b,...b..x)则 f(x)=1nnnaxx+bx+c，将它对变量x(i=1,2,...n)球偏导数得：∑∑ijij∑iii2i=1j=1i=1 ⎡11n⎜∑a1jxj+nai1xi+b1⎜⎤⎡nn⎜∑a1jxj⎜⎜∑ai1xi⎜⎤⎡⎤⎡∂f(x)⎤⎜⎜⎜2j=1∑2i=1⎜∂x1⎜⎜⎜j=1⎜⎜i=1⎜⎜∂f(x)⎜⎜11n⎜∑a2jxj+n∑ai2xi+b2⎜⎜⎜nn⎜⎜⎜⎡b⎤∑jxaj⎜⎜⎜+1+b∑ai2xi⎜⎜∇f(x)=⎜⎜= ⎜2j=1 2i=11⎜2⎜= ⎜j=1⎜⎜i=1⎜⎜2⎜⎜∂x2⎜⎜⋮⎜2⎜⋮⎜2⎜⋮⎜⎜b⎜⎜f(x)⎜⎜⎜∂⎜⎜⎜11⎜⎜⎜⎜⎜⎜⎜⎣3⎦⎣∂x3⎦n⎜anjxj+nainxi+bn⎜⎜⎜n∑anjxj⎜∑ainxi⎜∑⎣2j=1∑2i=1⎜⎦⎣j=1⎜⎦⎣i=1⎦1T= (AX+AX)+b2    5.求下列函数的梯度和Hesse矩阵  （1）f(x)=x22x23x2­4xx++12313  ⎛20-4⎞解：∇2f(x)=⎜40⎜0   ⎛x2ex1x2⎜⎜⎜­406⎜6xex1x2+xxex1x2⎞+2212（2）f(x)=3xx2+ex1x2解：∇2f(x)=⎜121212⎜126x+exx+xxexx6x+x2exx⎝21211⎠    6.判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：（1）f(x,x)=­x2+2x2+3xx解：∇2f(x)不是半正定，即f(x)非凸，然后判断‐ f(x)，经验证：∇2(­f(x))不是半正定，由此可知：f(x)非凸非凹。1211221（2）f(x,x)=2x2­4xx+3x2­5x­6解：∇2f(x)半正定，故f(x)为凸函数。（3）222f(x1,x2,x3)=x1+2x2­3x3­4x1x2解：∇2f(x)不是半正定，即f(x)非凸，然后判断‐ f(x)，经验证：∇2(­f(x))不是半正定，由此可知：f(x)非凸非凹。   7.设约束优化问题的数学模型为：1122minf(x)=x2+4x+x2­4x+10⎧s.t.⎨g1(x)=x1­x2+2≥021212⎩g(x)=­x2­x2­2x+2x≥0试用K-T条件判别点x=[­1,1]T是否为最优点。解：对于点x=[­1,1]T，g(足约束条件，故点X是可行解。x)=0，g(x)≥0，点满12⎛2⎞ ⎛1⎞且g1(x)是起作用约束，I={1}, ∇f(x)=⎜, ∇g1(x)=⎜，由∇gi(x)≥0条件下的⎜⎝­2⎠⎜⎝­1⎠  K-T条件得：∇f(x)­∑λi∇gi(x)=0,λi≥0，得到λ1=2，点x=[­1,1]Ti∈I满足K-T条 件。又因∇2f(x)正定，故f(x)为严格凸函数，该最优化问题是凸规划问题，由x*=[­1,1]T是K-T点，所以x*=[­1,1]T也是该问题的全局最优点。    8.设约束优化问题：  12minf(x)=(x­2)2+x2⎧g1(x)=­x1≤0⎨22s.t.⎜g(x)=­x≤0⎜g=­++≤⎩312(x)1x2x0 k它的当前迭代点为x=[1,0]T，试用K-T条件判定它是不是约束最优解。解：对于点x=[1,0]Tg(x)­1≤0,g(x)=,g(x)0]T是可行点，=k1k20=，点x=[1,0k3kk ⎛­2⎞⎛0⎞且起作用的约束条件是，g2(x),g3(x)，I={2,3}, ∇f(xk)=⎜⎜，∇g2(xk)=⎜⎝0⎠⎜⎝­1⎠ 1⎛2⎞∇g3(xk)=⎜⎜，由约束条件为gi(x)≤0时的K-T条件得，应有：⎝⎠ ⎧λ2=1T⎨，所以x=[1,0]∇f(x)+∑λi∇gi(x)=0,λi≥0解得：λi∈I⎩=1k3为K-T点。12现判断该问题是否为凸规划问题，因∇2f(x)正定，故f(x)为凸函数，g(x),g(x)为线性函数，亦为凸函数，∇2g(x)半正定，所以g(x)为凸函数，所以该优化问题为凸33k规划问题，即点x=[1,0]T是该问题的约束最优解。  习题三  1.   对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。maxf(x)=3x1+x2+2x3⎧2x1+3x2+6x3+x4=91⎜8x1+x2­4x3+2x5=10（1）⎜s.t.⎨⎩⎜3x1­x6=0⎜xj≥0,(j=1,2...6) ⎛1236300⎞⎜⎜⎝⎠解：令A=⎜81-4020⎜⎜30000-1⎜=(P1,P2,P3,P4,P5,P6) （1）基解x(0,16,­7,0,0,0)不是基可行解，=136（2）基解x2=(0,10,0,7,0,0)不是基可行解，（3）基解x3=(0,3,0,0,3.5,0)是基可行解，且f(x)=3，7（4）基解x4=(,­4,0,0,0,2145)不是基可行解，4（5）基解x5=(0,0,­,8,0,0)不是基可行解，2（6）基解x=(0,0,3,0,16,0)是基可行解，且f(x)=3，62（7）基解x=(1,0,­1,0,0,3)不是基可行解，72（8）基解x8=(0,0,0,3,5,0)是基可行解，且f(x)=0， （9）基解x=(5,0,0,­2,0,15)不是基可行解。944399（10）基解x10=(4,0,0,0,4,4)是基可行解，且f(x)=4。167（11）基解x11=(0,3,­6,0,0,0)不是基可行解。（12）基解x12=(0,10,0,­7,0,0)不是基可行解。 7（13）基解x13=(0,3,0,0,2,0)是基可行解，且f(x)=3。（14）基解x(0,0,­5,8,0,0)不是基可行解。=142（15）基解x(0,0,3,0,8,0)是基可行解，且f(x)=3。=152（16）基解x16=(0,0,0,3,5,0)是基可行解，且f(x)=3。2.   用单纯形法求解下列线性规划问题：maxf(x)=10x1+5x2 （1）⎜⎨512⎧3x1+4x2≤9s.t.⎜x+2x≤8⎩x1,x2≥0解：将现行规划问题化为形式如下：min(­f(x))=­10x1­5x2+0x3+0x4⎧3x1+4x2+x3=9⎜⎨5124s.t.⎜x+2x+x=8⎩x1,x2,x3,x4≥0作初始单纯形表，并按单纯形表步骤进行迭代，如下：  CBXBb-10 x1-5 x20 x30 x4θi0x39341030x48[5]2011.6  0-10-500 0x34.20[2.8]1-0.61.5-10x11.610.400.24  160-102  -5x2 1.5 0 1514­314  -10x1 1 1 0­1727    17.5 0 05142514 此时，σ为正，目标函数已不能再减小，于是得到最优解为：x*=(1,3,0,0)均j2目标函数值为：f(x*)=17.5   3.   分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题：minf(x)=5x1­2x2+3x3­6x4⎧7x+2x+3x+4x=1234（1）⎜⎜s.t.⎨2x1+x2+x3+2x4=3⎩x1,x2,x3,x4≥0解：（1）大M 法：把原问题化为标准形式，并加入人工变量如下：  minf(x)=5x1­2x2+3x3­6x4+Mx5+Mx6⎧x1+2x2+3x3+4x4+x5=7⎜⎨12346s.t.⎜2x+x+x+2x+x=3⎩x1,x2,x3,x4,x5,x6≥0作初始单纯形表，并按单纯形表步骤进行迭代，如下：   CBXBb5 x1-2 x23 x3-6 x4-6 x4-6 x4θi Mx 7 1 2 3 4 1 0 1.75 Mx 3 2 1 1 [2] 0 1 1.5  -10M5-3M-2-3M3-4M-6-6M00  Mx 1 -3 0 [1] 0 1 -2 1 -6x 1.5 1 0.5 0.5 1 0 0.5 3  9-M11+3M16-M003M+3  3x 1 -3 0 1 0 1 -2  -6x 1 2.5 0.5 0 1 -0.5 1.5   329100M-6M+15      5   6     5   4     3   4       因为M是一个很大的正数，此时σj均为正，所以，得到最优解：x*=(0,0,1,1,)T，最优值为f(x*)=­3   （2）两阶段法首先，构造一个仅含人工变量的新的线性规划如下：       ⎜⎨12346   按单纯形法迭代如下：ming(x)=0x1+0x2+0x3+0x4+x5+x6⎧x1+2x2+3x3+4x4+x5=7s.t.⎜2x+x+x+2x+x=3⎩x1,x2,x3,x4,x5,x6≥0  CBXBb0 x10 x20 x30 x41 x41 x4θi1x571234101.751x63211[2]011.5  -10-3-3-4-600 1x51-30[1]01-210x41.510.50.5100.53  -140-1003 0x31-30101-2 0x412.50.501-0.51.5   最优解为：x*=(0,0,1,1,0,0)，最优值：g(x)=0*x=(0,0,1,1,)T因人工变量x5=x6=0，则原问题的基可行解为: 如下表所示：,进入第二阶段计算  CBXBb5 x1-2 x23 x3-6 x43x31-3010-6x412.50.501  329100由上表可知，检验数均大于等于0，所以得到最优解：x*=(0,0,1,1,)T最优值为f(x*)=­3。   4.某糖果厂用原料A，B，C 加工成三中不同牌号的糖果，甲，乙，丙，已知各种牌号糖 果中A,B,C 含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及售价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立这个问题的线性规划数学模型。     甲 乙 丙原料成本（元/千克）每月限用量（千克） A≥60%≥15%  2.00 2000B   1.502500 C≤20%≤60%≤50% 1.00 1200加工费0.500.400.30  售价3.402.852.25  解：设xi,yi,zi≥0,i=1,2,3表示甲、乙、丙中分别含A、B、C 的含量，构造此问题的数学规划模型如下：maxf(x)=0.9x1+1.4x2+1.9x3+0.45y1+0.95y2+1.45y3­0.5z1+0.45z2+0.95z3⎧x+y1+z1≤20001⎜⎜x2+y2+z2≤2500⎜x+y3+z3≤12003⎜⎨123⎜0.4x1­0.6x2­0.6x3≤0s.t.⎜0.85y­0.15y­0.15y≥0⎜.2x0.2x0.8x00+­≥⎜123⎜0.6y1­0.6y2+0.4y3≥0⎜⎜0.5z1+0.5z2­0.5z3≥0⎜⎩xi,yi,zi≥0,i=1,2,3 5.求解下列线性规划问题的对偶问题  minf(x)=2x1+2x2+4x3⎧2x1+3x2+5x3≥2s.t.⎜3123（1）⎜x+x+7x≤3⎨⎜x1+4x2+6x3≤5⎜⎩x1,x2,x3≥0maxf(x)=5x1+6x2+3x3⎧+2x2+2x3=5x1⎜­x1+5x2­x3≥3（2）⎜s.t.⎨⎩123⎜4x1+7x2+3x3≤8⎜x无约束,x≥0,x≤0解：（1）由表3.7 可得该问题的对偶问题为：maxg(y)=2y1+3y2+5y3⎧2y1+3y2+y3≤2s.t.⎜3y123⎜+y+4y≤2⎨⎜5y1+7y2+6y3≤4⎜⎩y1≥0,y2,y3≤0（2）该问题的对偶问题为：ming(y)=5y1+3y2+8y3⎧y1­3y2+4y3=5⎜2y1+5y2+7y3≥6⎜s.t.⎨⎩123⎜2y1­y2+3y3≤3⎜y无约束,y≤0,y≥0  6．用对偶单纯形法求解下列线性规划问题：minf(x)=4x1+12x2+18x3⎧xx≥3+3（1）13⎜⎜s.t.⎨2x2+2x3≥5⎩x1,x2,x3≥0解：（1）首先，将“≥”约束条件两边反号，再加入松弛变量，得：   minf(x)=4x1+12x2+18x3+0x4+x5⎧­x1­3x3+x4=­3⎜⎨235s.t.⎜­2x­2x+x=­5⎩x1,x2,x3,x4,x5≥0建立初始单纯形表如下图所示，所有σj≥0。则对应对偶问题解是可行的，则继续迭代：  CBXBb4 x112 x218 x30 x40 x50x4-3-10-3100x5-50[-2]-201   4121800         计算min{­3,­5}=­5，所以x5为换出变量，θ=min{6,9}=6，确定x2为换入变量。继续迭代，得到如下单纯形表：  CBXBb4 x112 x218 x30 x40 x50x4-3-10[-3]100x2-2.50110-0.5   40600min{­3}=­3,x4换出，min{4，2}=2，x3换入。    CBXBb4 x112 x218 x30 x40 x50x311011­00x21.51­101-0.5   20026*3T此时，所有σj≥0，故原问题的最优解为x=[0,,1]*,最优值为：f(x)=362其对偶问题得到最优解为：x*=[2,6]T，最优值为：f(x*)=36。     7.已知线性规划问题  minf(x)=2x1­x2+x3⎧x1+x2+x3≤6⎜⎨12s.t.⎜­x+2x≤4⎩x1,x2,x3≥0先用单纯形法求出最优解，再分别就下列情况进行：（1）目标函数中变量x1,x2,x3的系数分别在什么范围内变化，问题的最优解不变；  （2）两个约束条件的右端分别在什么范围内变化，问题的最优解不变。 解：将该规划问题化为标准型，引入松弛变量x4,x5minf(x)=2x1­x2+x3+0x4+0x5,⎧x1+x2+x3+x4=6⎜s.t.x4⎜­+2x+x=⎨125⎩x1,x2,x3,x4,x5≥0用单纯形法求解，如下表： CBXBb2 x1-1 x21 x30 x40 x5  θi0x411111060x51.5-1[2]0012   2-1100 0x441.5011-0.5 -1x22-0.51000.5    1.50100.5     由上表可知，所有的检验数均大于等于零，得最优解: x*=(0,2,0,4,0)T,所以原问题的 最优解为：x*=(0,2,0,)T，最优值f(x*)=­2 （1）变量x1，x2，x3中，x1，x3为非基变量，x2为基变量。 ­由σ=3，当∆c­3时，cc+∆c≥1，所以，当c∈1,+∞),此时最优解不变。≥=[1212111212­由σ3=1，当∆c3≥­1时，c3=c3+∆c3≥0，所以，当c3∈[0,+∞),此时最优解不变。    ∆c2∈(­3,1)，最优解不变。 综上，当c∈[1,+∞)，c[­4,0]，c[0,+∞),此时最优解不变。∈∈1223（2）∆b1的变化范围 B­1b+B­1⎡∆b1⎤=4⎤+⎡1⎡0.5   ­0.5⎤⎡∆b1⎤⎡4⎤⎡1⎤b⎡0⎤=+∆≥1⎜0⎜⎜2⎜⎜0⎜⎜0⎜⎣⎦⎣⎦⎣⎦⎣⎦⎜2⎜⎜0⎜⎜0⎜⎣⎦⎣⎦⎣⎦ 得到：4+∆b1≥0⇒∆b1≥­4，则b1的变化范围是b1≥2，最优解保持不变。 B­1b+B­1⎡0⎤⎡4⎤⎡1=+­0.5⎤⎡0⎤⎡4⎤⎡­0.5⎤⎡0⎤=+∆b≥⎜⎜⎜⎜⎜⎜⎜⎜⎣2⎦⎣00.5⎦⎣∆b2⎦⎜⎜⎜⎜⎣2⎦⎣0.52⎜⎜⎦⎣0⎦⎣∆b2⎦ 得到：­4≤∆b2≤8，则b2的变化范围是[0,12]，最优解保持不变。    习题四   3.用Newton法求解 ϕ(t)=t3­2t+1用第1题求得的区间，按精度ε=0.01计算。解：ϕ(t0)=ϕ(0)=1,t1=t0+h0=1,ϕ(t1)=0,ϕ1=0,因为ϕ(t1)≤ϕ(t0)，则h1=h0=2 t2=t1+h1=1，ϕ(t2)=22,ϕ2=22,ϕ(t1)≤ϕ(t2)，反向，因为K=2≠0,所以α=0，b=3 则搜索区间为t∈[0,3]ϕ′(t)=3t2­2,ϕ′′(t)=6,ϕ′(0)=­2<0,ϕ′(3)=25>0取：  ，t′′′=1­1=55­1≥0.01，继续迭代t=t5=1,ϕ(t)=1,ϕ(t)=6,所以t000=66606 ， t=tϕ′(t0)=49,则t­t0­0ϕ′′(t)60060060=11>0.01,令t=49，则t≈0.8165， t­t0=0.0005<0.01,所以t*=0.817,ϕ*=ϕ(t*)≈­0.088。     4.用黄金分割法求解 minϕ(t)=t(t+2) 已知初始单谷区间[a，b]=[-3，5]，按精度ε=0.001计算。解：t1=­3+0.382×8=0.056,t2=­3+5­0.056=1.944， ϕ(t1)=0.115136,ϕ(t2)=7.667136，因为ϕ(t1)<ϕ(t2)，则新的搜索区间为[-3，1.944]： t2=t1=0.056,ϕ(t2)=0.115136,t1=­1.11392,ϕ(t1)=­0.987592， t1­t2>ε,继续迭代，因为ϕ(t1)>ϕ(t2)，则新的搜索区间为[-3，0.056]： t1=­1.832608,ϕ(t1)=­0.306764,t2=­1.111392,ϕ(t2)=­0.987592， t1­t2>ε,继续迭代，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.832608，0.056]： t1=­1.111292,ϕ(t1)=­0.987592,t2=­0.665448,ϕ(t2)=­0.888075，， t1­t2>ε,继续，ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.832608，-0.665448]：t1=­1.386753,ϕ(t1)=­0.854402,t2=­1.111392,ϕ(t2)=­0.987592， t1­t2>ε,继续，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.386753，-0.665448] t2=­0.940987,ϕ(t2)=­0.996518,t1=­1.111392,ϕ(t1)=­0.987592，， t1­t2>ε,继续，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.111392，-0.665448]： t1=­0.940987,ϕ(t1)=­0.996518,t2=­0.835799,ϕ(t2)=­0.973038，， t1­t2>ε,继续，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.111392，-0.835799]： t2=­0.940987,ϕ(t2)=­0.996518,t1=­1.006115,ϕ(t1)=­0.999962，， t1­t2>ε,继续，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.111392，-0.940987]： t1=­1.046295,ϕ(t1)=­0.997857,t2=­1.006115,ϕ(t2)=­0.999962，， t1­t2>ε,继续，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.046295，-0.940987]： t2=­­0.981215,ϕ(t2)=­0.999647,t1=­1.006115,ϕ(t1)=­0.999962，， t1­t2>ε,继续，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.046295，-0.981215]： t1=­1.021434,ϕ(t1)=­0.999540,t2=­1.006115,ϕ(t2)=­0.999962，， t1­t2>ε,继续，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.021434，-0.981215]： t2=­0.996579,ϕ(t2)=­0.999987,t1=­1.006115,ϕ(t1)=­0.999962， t1­t2>ε,继续，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.006115，-0.981215]： t1=­0.996579,ϕ(t1)=­0.999987,t2=­0.990727,ϕ(t2)=­0.999914，， t1­t2>ε,继续，因为ϕ(t1)<ϕ(t2)，所以新的搜索区间为[-1.006115，-0.990727]： t2=­0.996579,ϕ(t2)=­0.999987,t1=­1.000237,ϕ(t2)=­1.00000016，， t1­t2>ε,继续，因为ϕ(t1)<ϕ(t2)，所以新的搜索区间为[-1.006115，-0.996579]： t1=­1.000237,ϕ(t1)=­0.99999364,t2=­1.000237,ϕ(t2)=­1.00000016，， t1­t2>ε,继续，因为ϕ(t1)>ϕ(t2)，所以新的搜索区间为[-1.002472，-0.996579]：t2=­0.998830,ϕ(t2)=­0.999998505,t1=­1.000237,ϕ(t1)=­1.00000016， t1­t2>ε,继续，因为ϕ(t1)<ϕ(t2)，新的搜索区间为[-1.002472，-0.998830] t1=­1.001081,ϕ(t1)=­0.999999075,t2=­1.000237,ϕ(t2)=­1.00000016， 因为t1­t2<ε，停止迭代。所以：t*=t1+t2=­1.000659,ϕ*=ϕ(t*)=­0.9999999565。2    5.用抛物线插值法求解 minf(x)=8x3­2x2­7x+3已知初始单谷区间[a，b]=[0，2]，ε=­0.001。解：t1=0,t2=2,取t0=1，t≈0.5227，t0­t>ε,t<t0,ϕ(t)=­0.063<ϕ(t0)=2 新搜索区间为[0，1]，t1=0,t2=1,t0≈0.5227，t≈0.5704,t0­t>ε,t>t0, ϕ(t)=­0.1588<ϕ(t0)=­0.063，所以，新的搜索区间为[0.5227，1]， t1=0.5227,t2=1, t0≈0.5704，t≈0.6146,t0­t>ε,t>t0,ϕ(t)=­0.2004<ϕ(t0)=­0.1588 所以，新的搜索区间为：[0.5704，1]，t1=0.5704,t2=1,t0≈0.6146，t≈06232, t0­t>ε,t>t0,ϕ(t)=­0.2029<ϕ(t0)=­0.2004，所以新的搜索区间为：[0.6146，1]， t1=0.6146,t2=1,t0≈0.6232，t≈0.6260,t0­t>ε,t>t0, ϕ(t)=­0.2032<ϕ(t0)=­0.2029，新的搜索区间为：[0.6232，1]，t1=0.6232,t2=1,    t0≈0.6260，t≈0.6284,t0­t>ε,t>t0,ϕ(t)=­0.2034<ϕ(t0)=­0.2032 新的搜索区间为[0.6260，1]，t1=0.6260,t2=1,t0≈0.6284，t≈0.6276, t0­t<ε，∴t是ϕ(t)在区间上的近似最优解，t*=t=0.6276， ϕ*=ϕ(t*)=­0.2034。习题五    1.用最速下降法求解120minf(x)=x2+25x2，x=[2，2]T，ε=0.01.1、解：∇f(x)=[2x1,50x2]T⎡20⎤Hesse矩阵A=⎜T⎜⎣050⎦  g0=∇f(x0)=[4,100] ,g0  =100.07997gTg⎡2⎤4⎡⎤⎡1.91988⎤x=x00­11122133⎜T⎜g=­0.02003⋅=⎜⎜⎜⎜⎜⎜21­⎣⎦⎣⎦⎣⎦10gTg0A00000.003f(x1)=3.68655  Tg1=∇f(x1)=[3.83976­0.15],g1>εgTg⎡1.91988⎤⎡3.8976⎤⎡0.07348⎤x=x11­g=⎜­0.48089=⎜⎜⎜⎜⎜⎣­0.003⎦⎣0.15⎦⎣0.06913⎦21gTAg1f(x2)=0.124872g2>ε⎡0⎤⎡0⎤同理继续迭代，最后至x=，此时最优解x=⎜⎜⎜⎜⎣0⎦⎣0⎦，f(x)=0 2.用Newton法求解 22T-x1x2，初始点x0=[0，0]，ε=0.01.minf(x)=60­10x1­4x2+x1解：+x2 g(x)=∇f(x)=[­10+2x­x,­4+2x­x]T⎡21⎤⎡2G(x)=­1⎤⎜⎜⇒G(x)­1=⎜⎜⎜⎜⎣­12⎦⎜=1=2⎜⎜⎣33⎜⎦⎡21⎤⇒x=x­G(x)­1g(x)=⎡0⎤⎜3⎜­10⎤=[8,6]T100­3⎜⎜⎡⎜⎜ 012⎣⎦⎜4⎜⎣⎦⎜⎣33⎜⎦T∇f(x1)=[0,0],∇f(x1)=0≤0.01∴最优解为x*=[8,6]T,f(x*)=8  3.用修正Newton法求解 22Tminf(x)=（4x1+1）+（2x2­1）+x1+x2+10，初始点x0=[0，0]，ε=0.01.­t8⎡9⎤⎜0⎜T解：g(x)=∇f(x)=[8x1+9,4x2­3]x1=x0+t0p0=⎜⎜03⎜⎜t⎣⎜4⎜⎦  ⎡10⎤⎜G(x)=⎡80⎤G(x)­1=⎜，8，)⎜0g(x=[9，­3]T⎜⎜⎣04⎦⎜0⎜=⎜⎣81200112201⎜4⎜⎦  ⎡10⎤⎜⎡9⎤93⎡9t⎤­⎜80⎜⎜则p=­G(x)­1g(x)==[­,]T，令00⎜⎜0⎜⎣⎜⎜⎜1⎜⎣­3⎦844⎜⎦x1=x0+t0p0=⎜⎜⎜⎣⎜3⎜4t0⎜⎦  f(x=99t2­99t+16⇒t=1时，f(x)最小)1168  ∴x[­9,3]T，∇f(x)[0,0]T,==∇18411f(x)=0≤0.01∴x*=[­9,3]T,f(x*)=1578416  4.用共轭梯度法求解min（x2+4x2），取初始点x=[1，1]T，ε=0.01. 解：令f(x)=x22=[2x,8xT+4x,∇f(x)]，p=­∇)=­[111200f(x2,8]T  ⎡1⎡­2⎤⎤Tx1=x0+t0p0=⎜+t0⎜=[1­2t0,1­8t0]⎜⎜⎣1⎦⎣­8⎦  令min[(1­2t0)2+4(1­8t)2]=minϕ(t)，  则d[ϕ(t)]=520t­680t0.130969=⇒=dt00  x=[0.738062,­0.047752]T，∇f(x)=[1.476124,­0.382016]T   则λ=∇f(x1) =2.324878≈0.034189∇f(x0)68∴新搜索方向为p1=­∇f(x1)+λ0p0  ⎡­1.476124⎤⎡­2⎤⎡­1.544502⎤=+0.034189=⎜⎜⎜⎜⎜⎜⎣0.382016⎦⎣­8⎦⎣0.108504⎦  211111因此有x=x+tp=[0.738062­1.544502t,­0.047752+0.108504t]T  由df(x+tp0⇒t≈.477127)=0dt1111  ⎡0.738062⎤⎡­1.544502⎤ T0,0.007]⎣⎦⎣⎦ 因而得下一迭代点x2=x1+t1p1=⎜­0.047752⎜+0.477127⎜0.108504⎜=[0.0 *T*=[0,0],f(x)=0∇f(x2)=0≤0.01停止迭代，∴x  12125.用共轭梯度法求解minf(x)=2x2+x2-xx，自定初始点，ε=0.01. 解：∇f(x)=[4x1­x2,2x2­x1]TT，取初始点x0=[0,1]00，p=­∇f(x)=­[1,­2]T  ⎡0⎡1⎤T⎤x1=x0+t0p0=⎜+t⎜=[t0,1­2t0]⎜0⎜⎣1⎦⎣­2⎦  00令min[2t2+(1­2t)2­t0(1­2t0)]=minϕ(t)  则d[ϕ(t)]=16t­50t0.125=⇒=dt00  11∴x=[0.3125,­0.375]T，∇f(x)=[0.875,0.4375]T  220λ=∇f(x1) =0.95703125≈0.191406∇f(x0)5  ∴新搜索方向为p1=­∇f(x1)+λ0p0  ⎡­0.875⎤⎡1⎤⎡­0.683594⎤=+0.191406=⎜⎜⎜⎜⎜⎜⎣­0.4375⎦⎣­2⎦⎣­0.82012⎦211111因而得下一迭代点x=x+tp= [­0.3125­0.683594t,0.375­0.820312t]T  由df(xtp0⇒t=.456927，+)=0dt1111 22则x=[0.000,0.000]T，∇f(x)=[0,0]T,∇f(x2)=0≤0.01停止迭代  2则x*= x=[0,0]T，综上所述，原问题的最优解x*=[0,0]T，最优值为f(x*)=0     6.用DFP法求解minf(x)=（4120x­5）2+（x­6）2，初始点x=[8，9]T，ε=0.01. 6、解：取H0=I,⎡80⎤TA=⎜,⎜⎣02⎦g(x)=[8x1­40,2x2­12]  Tx0=[8,19]T,g0=[24,6]  Tx1=[4.86154,8.21538]T,g1=[­1.10768,4.43076]第一步迭代得：  010用DFP法第二次迭代：s=x­x=[­3.13846,­0.78462]T  010y=g­g=[­25.10768,­1.56924]T  syyHyssHyyH00TT则H=H+⎣⎦⎣⎦T0000­，10TT00000  TTTy0H0y0=y0因：s0y0=80.03071,y0=632.85811  sT=⎡9.849932.46250⎤s00⎜2.462500.61563⎜ss，00T=⎡9.849932.46250⎤⎜2.462500.61563⎜  ⎡10⎤⎡0.123080.03077⎤⎡0.996110.06226⎤⎡0.12697­0.03149⎤∴H1=⎜1+.030770.00770­.062260.00390=0.031491.00380⎜⎜0⎜⎜0⎜⎜­⎜⎣⎦⎣⎦⎣⎦⎣⎦则搜索方向p1=­H1g1=[­0.28017,4.48248]从x1出发沿p1进行直线搜索，即：  x1=x1+tp1=[4.86154­0.28017t,8.21538+4.48248t]T  由df(x0，得t=­0.48674+tp)=dt11  211所以x=x+tp≈[5.000,6.000]T2，由于g(x)=[0,0]T2，所以x=[5,6]T是极小 点。 习题六  1.用外点罚函数法求解：  minf(x)=x1+x2⎧s.t.⎨g(x)x2x0=­+≥112⎩g2(x)=x1≥0 解：利用外点罚函数法构造增广目标函数，如下：  ⎧x+x+µ+x+x12121[(­x2)22](x∉D)F(x,µ)=⎨⎩x1+x2(x∈D)  对于x∉D的情况：  由∂F=0,∂F=0⎜得：x∗(µ)=⎛­1,­11⎞24(1+µ)⎜2µ⎠∂x1∂x2⎝2+2µ  当µ→+∞时，x∗(µ)→(0,0)  即：x∗=(0,0)，且f(x∗)=0   2.用外点罚函数法求解：  2minf(x)=x12+x2  s.t.g(x)=1­x1≤012kk⎜⎜∂x1解：构造增广目标函数：  ⎧F(x,µ)=⎨x22­x)2+x+µ(1121(x∉D)x2+x2⎩(x∈D)  对于x∉D的情况：  由∂F=0,∂F=0⎧x1­2µ(1­x1)=02得：⎨∂x1∂x2⎩2x2=0  推出：x∗(µ)=⎛µ,0⎞⎜1⎜⎝⎠+µ 当µ→+∞时，x∗(µ)