最优化方法部分课后习题解答 1.一直优化问题的数学模型为:习题一12minf(x)=(x3)2+(x4)2⎧5g(x)=xx≥0⎜1122⎜s.t.⎨g2(x)=x1x2+5≥0 试用图解法求出:⎜0g(x)=x≥⎜31⎜⎩g4(x)=x2≥0(1)无约束最优点,并求出最优值。(2)约束最优点,并求出其最优值。(3)如果加一个等式约束h(x)=x1x2=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)=xx1125=0 ⎧15x1=⎜求解得到:⎨4其中:点为g1(x)和g2(x)的交点,令⎜⎨25 即最优点为x*=⎜⎩g2(x)=x1x2+5=0 (15,5):最优值为:f(x*)= 65⎜x=⎜⎩24448(3).若增加一个等式约束,则由图可知,可行域为空集,即此时最优解不存在。2.一个矩形无盖油箱的外部总面积限定为S,怎样
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
可使油箱的容量最大?试列出这个优化问题的数学模型,并回答这属于几维的优化问题.解:列出这个优化问题的数学模型为: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)=x22x23x24xx++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)=2x24xx+3x25x6解:∇2f(x)半正定,故f(x)为凸函数。(3)222f(x1,x2,x3)=x1+2x23x34x1x2解:∇2f(x)不是半正定,即f(x)非凸,然后判断‐ f(x),经验证:∇2(f(x))不是半正定,由此可知:f(x)非凸非凹。 7.设约束优化问题的数学模型为:1122minf(x)=x2+4x+x24x+10⎧s.t.⎨g1(x)=x1x2+2≥021212⎩g(x)=x2x22x+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)=(x2)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+x24x3+2x5=10(1)⎜s.t.⎨⎩⎜3x1x6=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))=10x15x2+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 1514314 -10x1 1 1 01727 17.5 0 05142514 此时,σ为正,目标函数已不能再减小,于是得到最优解为:x*=(1,3,0,0)均j2目标函数值为:f(x*)=17.5 3. 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题:minf(x)=5x12x2+3x36x4⎧7x+2x+3x+4x=1234(1)⎜⎜s.t.⎨2x1+x2+x3+2x4=3⎩x1,x2,x3,x4≥0解:(1)大M 法:把原问题化为标准形式,并加入人工变量如下: minf(x)=5x12x2+3x36x4+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.45y30.5z1+0.45z2+0.95z3⎧x+y1+z1≤20001⎜⎜x2+y2+z2≤2500⎜x+y3+z3≤12003⎜⎨123⎜0.4x10.6x20.6x3≤0s.t.⎜0.85y0.15y0.15y≥0⎜.2x0.2x0.8x00+≥⎜123⎜0.6y10.6y2+0.4y3≥0⎜⎜0.5z1+0.5z20.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+5x2x3≥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⎧y13y2+4y3=5⎜2y1+5y2+7y3≥6⎜s.t.⎨⎩123⎜2y1y2+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⎧x13x3+x4=3⎜⎨235s.t.⎜2x2x+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 x50x31101100x21.51101-0.5 20026*3T此时,所有σj≥0,故原问题的最优解为x=[0,,1]*,最优值为:f(x)=362其对偶问题得到最优解为:x*=[2,6]T,最优值为:f(x*)=36。 7.已知线性规划问题 minf(x)=2x1x2+x3⎧x1+x2+x3≤6⎜⎨12s.t.⎜x+2x≤4⎩x1,x2,x3≥0先用单纯形法求出最优解,再分别就下列情况进行
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
:(1)目标函数中变量x1,x2,x3的系数分别在什么范围内变化,问题的最优解不变; (2)两个约束条件的右端分别在什么范围内变化,问题的最优解不变。 解:将该规划问题化为标准型,引入松弛变量x4,x5minf(x)=2x1x2+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,当∆c3时,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的变化范围 B1b+B1⎡∆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,最优解保持不变。 B1b+B1⎡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)=t32t+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)=3t22,ϕ′′(t)=6,ϕ′(0)=2<0,ϕ′(3)=25>0取: ,t′′′=11=551≥0.01,继续迭代t=t5=1,ϕ(t)=1,ϕ(t)=6,所以t000=66606 , t=tϕ′(t0)=49,则tt00ϕ′′(t)60060060=11>0.01,令t=49,则t≈0.8165, tt0=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+50.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, t1t2>ε,继续迭代,因为ϕ(t1)>ϕ(t2),则新的搜索区间为[-3,0.056]: t1=1.832608,ϕ(t1)=0.306764,t2=1.111392,ϕ(t2)=0.987592, t1t2>ε,继续迭代,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.832608,0.056]: t1=1.111292,ϕ(t1)=0.987592,t2=0.665448,ϕ(t2)=0.888075,, t1t2>ε,继续,ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.832608,-0.665448]:t1=1.386753,ϕ(t1)=0.854402,t2=1.111392,ϕ(t2)=0.987592, t1t2>ε,继续,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.386753,-0.665448] t2=0.940987,ϕ(t2)=0.996518,t1=1.111392,ϕ(t1)=0.987592,, t1t2>ε,继续,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.111392,-0.665448]: t1=0.940987,ϕ(t1)=0.996518,t2=0.835799,ϕ(t2)=0.973038,, t1t2>ε,继续,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.111392,-0.835799]: t2=0.940987,ϕ(t2)=0.996518,t1=1.006115,ϕ(t1)=0.999962,, t1t2>ε,继续,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.111392,-0.940987]: t1=1.046295,ϕ(t1)=0.997857,t2=1.006115,ϕ(t2)=0.999962,, t1t2>ε,继续,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.046295,-0.940987]: t2=0.981215,ϕ(t2)=0.999647,t1=1.006115,ϕ(t1)=0.999962,, t1t2>ε,继续,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.046295,-0.981215]: t1=1.021434,ϕ(t1)=0.999540,t2=1.006115,ϕ(t2)=0.999962,, t1t2>ε,继续,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.021434,-0.981215]: t2=0.996579,ϕ(t2)=0.999987,t1=1.006115,ϕ(t1)=0.999962, t1t2>ε,继续,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.006115,-0.981215]: t1=0.996579,ϕ(t1)=0.999987,t2=0.990727,ϕ(t2)=0.999914,, t1t2>ε,继续,因为ϕ(t1)<ϕ(t2),所以新的搜索区间为[-1.006115,-0.990727]: t2=0.996579,ϕ(t2)=0.999987,t1=1.000237,ϕ(t2)=1.00000016,, t1t2>ε,继续,因为ϕ(t1)<ϕ(t2),所以新的搜索区间为[-1.006115,-0.996579]: t1=1.000237,ϕ(t1)=0.99999364,t2=1.000237,ϕ(t2)=1.00000016,, t1t2>ε,继续,因为ϕ(t1)>ϕ(t2),所以新的搜索区间为[-1.002472,-0.996579]:t2=0.998830,ϕ(t2)=0.999998505,t1=1.000237,ϕ(t1)=1.00000016, t1t2>ε,继续,因为ϕ(t1)<ϕ(t2),新的搜索区间为[-1.002472,-0.998830] t1=1.001081,ϕ(t1)=0.999999075,t2=1.000237,ϕ(t2)=1.00000016, 因为t1t2<ε,停止迭代。所以:t*=t1+t2=1.000659,ϕ*=ϕ(t*)=0.9999999565。2 5.用抛物线插值法求解 minf(x)=8x32x27x+3已知初始单谷区间[a,b]=[0,2],ε=0.001。解:t1=0,t2=2,取t0=1,t≈0.5227,t0t>ε,t<t0,ϕ(t)=0.063<ϕ(t0)=2 新搜索区间为[0,1],t1=0,t2=1,t0≈0.5227,t≈0.5704,t0t>ε,t>t0, ϕ(t)=0.1588<ϕ(t0)=0.063,所以,新的搜索区间为[0.5227,1], t1=0.5227,t2=1, t0≈0.5704,t≈0.6146,t0t>ε,t>t0,ϕ(t)=0.2004<ϕ(t0)=0.1588 所以,新的搜索区间为:[0.5704,1],t1=0.5704,t2=1,t0≈0.6146,t≈06232, t0t>ε,t>t0,ϕ(t)=0.2029<ϕ(t0)=0.2004,所以新的搜索区间为:[0.6146,1], t1=0.6146,t2=1,t0≈0.6232,t≈0.6260,t0t>ε,t>t0, ϕ(t)=0.2032<ϕ(t0)=0.2029,新的搜索区间为:[0.6232,1],t1=0.6232,t2=1, t0≈0.6260,t≈0.6284,t0t>ε,t>t0,ϕ(t)=0.2034<ϕ(t0)=0.2032 新的搜索区间为[0.6260,1],t1=0.6260,t2=1,t0≈0.6284,t≈0.6276, t0t<ε,∴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=x0011122133⎜T⎜g=0.02003⋅=⎜⎜⎜⎜⎜⎜21⎣⎦⎣⎦⎣⎦10gTg0A00000.003f(x1)=3.68655 Tg1=∇f(x1)=[3.839760.15],g1>εgTg⎡1.91988⎤⎡3.8976⎤⎡0.07348⎤x=x11g=⎜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)=6010x14x2+x1解:+x2 g(x)=∇f(x)=[10+2xx,4+2xx]T⎡21⎤⎡2G(x)=1⎤⎜⎜⇒G(x)1=⎜⎜⎜⎜⎣12⎦⎜=1=2⎜⎜⎣33⎜⎦⎡21⎤⇒x=xG(x)1g(x)=⎡0⎤⎜3⎜10⎤=[8,6]T1003⎜⎜⎡⎜⎜ 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)+(2x21)+x1+x2+10,初始点x0=[0,0],ε=0.01.t8⎡9⎤⎜0⎜T解:g(x)=∇f(x)=[8x1+9,4x23]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=99t299t+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⎜=[12t0,18t0]⎜⎜⎣1⎦⎣8⎦ 令min[(12t0)2+4(18t)2]=minϕ(t), 则d[ϕ(t)]=520t680t0.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.7380621.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)=[4x1x2,2x2x1]TT,取初始点x0=[0,1]00,p=∇f(x)=[1,2]T ⎡0⎡1⎤T⎤x1=x0+t0p0=⎜+t⎜=[t0,12t0]⎜0⎜⎣1⎦⎣2⎦ 00令min[2t2+(12t)2t0(12t0)]=minϕ(t) 则d[ϕ(t)]=16t50t0.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.31250.683594t,0.3750.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)=(4120x5)2+(x6)2,初始点x=[8,9]T,ε=0.01. 6、解:取H0=I,⎡80⎤TA=⎜,⎜⎣02⎦g(x)=[8x140,2x212] Tx0=[8,19]T,g0=[24,6] Tx1=[4.86154,8.21538]T,g1=[1.10768,4.43076]第一步迭代得: 010用DFP法第二次迭代:s=xx=[3.13846,0.78462]T 010y=gg=[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.126970.03149⎤∴H1=⎜1+.030770.00770.062260.00390=0.031491.00380⎜⎜0⎜⎜0⎜⎜⎜⎣⎦⎣⎦⎣⎦⎣⎦则搜索方向p1=H1g1=[0.28017,4.48248]从x1出发沿p1进行直线搜索,即: x1=x1+tp1=[4.861540.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)=1x1≤012kk⎜⎜∂x1解:构造增广目标函数: ⎧F(x,µ)=⎨x22x)2+x+µ(1121(x∉D)x2+x2⎩(x∈D) 对于x∉D的情况: 由∂F=0,∂F=0⎧x12µ(1x1)=02得:⎨∂x1∂x2⎩2x2=0 推出:x∗(µ)=⎛µ,0⎞⎜1⎜⎝⎠+µ 当µ→+∞时,x∗(µ)