北航最优化方法大作业Word格式.docx
《北航最优化方法大作业Word格式.docx》由会员分享，可在线阅读，更多相关《北航最优化方法大作业Word格式.docx（23页珍藏版）》请在冰点文库上搜索。
算例1中，由b1可知，节点2为需求节点，节点1为供给节点，由节点1将信息传输至节点2的最短路径为弧1。
图2算例1最优传输示意图
求得的最优解为x1*=[4000000000000]T，即只经过弧1运输4个单位流量，其余弧无流量。
又因为，每条弧的费用均为5，所以最小费用为20。
经分析，计算结果合理可信。
1.3.2算例2（b2=[4;
算例2中，由b2可知，节点3为需求节点，节点1为供给节点，由节点1将信息传输至节点2的最短路径为弧2。
图3算例2最优传输示意图
求得的最优解为x2*=[0400000000000]T，即只经过弧2运输4个单位流量，其余弧无流量。
1.3.3算例3（b3=[0;
算例3中，由b3可知，节点2为需求节点，节点3为供给节点，由节点3将信息传输至节点2的最短路径为弧5->
弧1。
图4算例3最优传输示意图
求得的最优解为x3*=[4000400000000]T，即经过弧5运输4个单位流量至节点1，再经弧1运输4个单位流量至节点2，其余弧无流量。
又因为，每条弧的费用均为5，所以最小费用为40。
1.3.4算例4（b4=[4;
算例4中，由b4可知，节点7为需求节点，节点1为供给节点，由节点1将信息传输至节点7的最短路径为弧1->
弧4->
弧10。
图5算例3最优传输示意图
求得的最优解为x4*=[4004000004000]T，即经过弧1运输4个单位流量至节点2，再经弧4运输4个单位流量至节点5，最后经弧5运输4个单位流量至节点7，其余弧无流量。
又因为，每条弧的费用均为5，所以最小费用为60。
2重要算法编写与观察
2.1习题5.6
（a）初值为（0,0）时
本算法令g的2范数在<
10-4时，停止迭代，经过86次迭代收敛。
收敛因子（f（k+1）-f*）/（f（k）-f*）=0.7623
图6收敛因子截图
（b）初值为（-0.4,0）时
10-4时，停止迭代，经过112次迭代收敛。
收敛因子（f（k+1）-f*）/（f（k）-f*）=0.81
图7收敛因子截图
（c）初值为（10,0）时
10-4时，停止迭代，经过5次迭代收敛。
收敛因子（f（k+1）-f*）/（f（k）-f*）=3.9022e-4
图8收敛因子截图
（d）初值为（11,0）时
10-4时，停止迭代，经过2次迭代收敛。
收敛因子（f（k+1）-f*）/（f（k）-f*）=0
图9收敛因子截图
图10自变量（x1,x2）截图
总结：
最速降线法的收敛因子随着初值的不同而变化，对于个别初值（如本习题初值取（11,0）时），算法可迅速收敛。
因此，初值的选取对于最速降线法的收敛速度有较大影响。
2.2习题5.7
（a）由
可得：
故，牛顿迭代法的确切公式为：
（b）从以下五个初值开始迭代
（1）x（0）=7.40
表1初值1牛顿法迭代结果表
迭代次数
x值
梯度值
1
7.4
-1
2
7.44
-0.09090909
3
7.4444
-0.00090009
4
7.4444444
-9.00E-08
5
（2）x（0）=7.20
表2初值2牛顿法迭代结果表
7.2
-11
7.31
-3.903225806
7.403775
-0.906507337
7.440723
-7.60E-02
7.444413
-0.000631068
（3）x（0）=7.01
表3初值3牛顿法迭代结果表
7.01
-391
7.019775
-193.2756005
7.03867
-94.43899464
7.073976
-4.51E+01
7.135638
-20.49016561
（4）x（0）=7.80
表4初值4牛顿法迭代结果表
7.8
7.16
-16
7.2624
-6.243902439
7.369879
-1.81E+00
7.431934
-0.260664533
（5）x（0）=7.88
表5初值5牛顿法迭代结果表
7.88
4.454545455
7.0176
-218.2727273
7.034503
-106.9318135
7.066328
-5.13E+01
7.122757
-23.58481436
（c）本问题的最优值为7.4444444。
由上述五个初值点的前五步迭代可以看出：
当初值点在区间（7.4444444，7.8888）内时，第二次迭代点将落在（7，7.4444444）之间，随后逐渐增加，直至逼近最优值。
当初值点在区间（7，7.4444444）内时，则迭代点逐渐增加，逼近最优值。
当取初值不在（7,7.8888）内时，牛顿法不收敛。
2.3习题5.8
（a）没有线搜索的牛顿法
μ=0.1时，
μ=1时，
（b）具有线搜索的牛顿法
（未完成）
2.4习题5.9
（a）初值选（1.2,1.2）时，
◆最速降线法：
10-2时，停止迭代，经过3262次迭代得到以下结果。
图11最速降线法初值为（1.2,1.2）的等值线图及迭代轨迹
◆牛顿法：
本算法令s的4范数在<
10-6时，停止迭代，经过4次迭代得到以下结果。
图12牛顿法初值为（1.2,1.2）的等值线图及迭代轨迹
（b）初值选（-1.2,1）时，
本算法令g的4范数在<
10-2时，停止迭代，经过6835次迭代得到以下结果。
图13最速降线法初值为（-1.2,1）的等值线图及迭代轨迹
10-6时，停止迭代，经过6次迭代得到以下结果。
图14牛顿法初值为（-1.2,1）的等值线图及迭代轨迹
2.5习题5.19
N=5
迭代6次后，满足收敛条件。
表6N=5时，各迭代点x值
迭代次数/分量
0.774441
-1.74458
1.044994
4.405481
4.894544
4.454954
4.740748
-14.4459
-4.78046
7.945445
17.41944
-4.80614
45.656
-86.4661
-46.194
99.4417
6
5.000468
-140
640.0001
-1140
7
640
N=8
迭代19次后，满足收敛条件。
表7N=8时，各迭代点x值
8
0.754494
-1.71448
0.486849
1.18697
1.744509
4.107568
4.484544
4.598854
4.770408
4.619757
-7.74774
-5.18495
-1.184
4.661465
6.074494
9.044461
11.64715
-4.56949
48.44644
-40.4749
-44.1741
-44.1857
-1.6446
45.14449
54.7498
4.577401
-74.4411
199.8408
-9.99548
-174.858
-171.851
-10.8654
469.4744
-4.15904
104.8461
-645.04
1081.886
446.6416
-1014.4
-914.459
1401.446
-5.65084
154.4884
-874.601
1478.11
445.7144
-1444.46
-1156.48
1454.944
9
-5.64898
154.4878
1478.108
445.7146
-1444.47
10
6.688844
-489.117
4810.06
-9974.65
14761.11
1879.748
-15549.9
8487.119
11
6.744416
-489.454
4810.494
-9974.11
14764.74
1880.191
-15541.7
8488.07
14
6.789876
-489.481
4811.108
-9976.46
14765.09
1880.84
-15544.4
8489.454
7.645489
-445.681
4087.908
-6008.64
4107.694
16980.64
-46494.6
11414.66
7.405147
-181.14
1454.897
-1497.76
-10051.4
44195.97
-48554.5
14876.44
15
5.044404
-90.4414
79.06581
4858.444
-47184.4
58454.08
-55845.6
19754.97
16
-7.98171
504.7645
-7559.41
46199.76
-148600
416414.8
-168167
51480.46
17
-7.99416
504.8604
-7559.64
46199.85
416415.4
-168168
51480.16
18
-7.99414
504.8646
51480.15
19
-8.00048
504.9999
-7560
46400
416416
51480
40
-8.00004
504.0004
N=14
迭代49次后，满足收敛条件。
（表略）
N=40
迭代74次后，满足收敛条件。
2.6习题5.27
调用MATLAB自带的lsqnonlin.m函数，计算可得对应的x
（1）、x
（2）和标准差如下表所示。
表8选取各初值的计算结果
初值
x1虚实部
x1虚部
x2实部
x2虚部
标准差
[11]
0.0007
-15.3303
0.2767i
0.0075
[0.10.1]
0.0006
-14.4171
0.0267
[0.010.01]
-12.9432
0.0026
由上可知，标准差值较为恒定，随初值变化不十分显著；
x1和x2值随初值选取的不同而不同。
2.7习题6.4
3附录
3.1对偶单纯形法函数MATLAB程序
function[sol,val,kk]=duioudanchun（A,N）
B=A;
[mA,nA]=size（A）;
kk=0;
flag=1;
whileflag
kk=kk+1;
ifA（:
nA）>
=0
flag=0;
sol=zeros（1,nA）;
fori=1:
mA-1
sol（N（i））=A（i,nA）;
end
val=sol*（B（mA,:
））'
;
else
ifA（i,nA）<
0&
A（i,1:
nA-1）>
disp（'
haveinfinitesolution!
'
）;
break;
ifflag
temp=0;
temp
temp=A（i,nA）;
outb=i;
sita=zeros（1,nA-1）;
nA-1
ifA（outb,i）<
sita（i）=A（mA,i）/A（outb,i）;
temp=-inf;
ifsita（i）<
sita（i）>
temp=sita（i）;
inb=i;
ifi==outb
N（i）=inb;
A（outb,:
）=A（outb,:
）/A（outb,inb）;
mA
ifi~=outb
A（i,:
）=A（i,:
）-A（outb,:
）*A（i,inb）;
A（mA,nA）=0;
end
3.2最速降线法求Rosenbrock函数最小值matlab程序如下：
functionrb=rbfun（x,y）
rb=100*（y-x^2）^2+（1-x）^2
clear
clc
symsxygG
g=gradient（rb（x,y）,[xy]）%定义梯度向量
G=hessian（rb（x,y）,[xy]）%定义海森阵
X（1,:
）=[-1.41];
%定义初始点
x=X（1,1）;
y=X（1,4）;
A（1,:
）=subs（g）%给梯度赋初值
i=1
while（norm（A（i,:
）,4）>
10^（-4））%收敛条件
f（i）=rb（x,y）%记录函数值
P（i,:
）=-A（i,:
）%得到迭代方向
fz（i）=-A（i,:
）*P（i,:
）'
%-gT*p%精确搜索法步长的分子
fm（i）=P（i,:
）*subs（G）*P（i,:
%精确搜索法步长的分母
a（i）=fz（i）/fm（i）%精确搜索法步长
X（i+1,:
）=X（i,:
）+a（i）*P（i,:
）%产生新的点
x=X（i+1,1）;
y=X（i+1,4）
A（i+1,:
）=subs（g）%产生新的梯度
i=i+1
3.3牛顿法求Rosenbrock函数最小值matlab程序如下：
%定义初值
H=subs（inv（G））%得到海森阵初值
S（1,:
）=-A（1,:
）*H%得到s初值
while（norm（S（i,:
10^（-6））%收敛条件
f（i）=rb（x,y）%定义函数值
）+S（i,:
）%得到下一迭代点
y=X（i+1,4）%给x,y分别赋值
）=subs（g）%得到新的梯度值
H=subs（inv（G））%得到新的海森阵
S（i+1,:
）=-A（i+1,:
）*H%得到新的增量s
3.4共轭梯度法求解习题5.19程序如下：
K=40
G=zeros（K,K）
form=1:
K
forn=1:
G（m,n）=1/（m+n-1）
end
）=zeros（1,K）
b=ones（1,K）
）=X（1,:
）*G-b
P（1,:
）
while（norm（A（i,:
10^（-6））%收敛条件
d=P（i,:
）*G
fz（i）=A（i,:
）*A（i,:
%精确搜索法步长的分子
）*d'
）+a（i）*d
beta（i+1）=（A（i+1,:
）*A（i+1,:
）/（A（i,:
）
P（i+1,:
）+beta（i+1）*P（i,:
升级会员 