最优化方法大作业

资料单位代码03学号《最优化方法》课程实践资料完成时间：2015年5月30日星期六选择题目：题目一使用优化软件，编写重要算法的程序1.第一大题：（1）学习最优流量工程问题，nonsmooth_MCFP.pdf（2）问题重述：Figure1一个简单的网络拓扑和流量需求如Figure1所示，网络有7个节点，13条弧，每条弧的容量是5个单位.此外有四个需求量均为4个单位的源－目的对（M=4)，具体的源节点、目的节点信息如图所示.这里为了简单，省去了未用到的弧，此外弧上的数字表示弧的编号。（3）极小化MAU设定变量x，为531的向量，其中(53)x即为变量z。使用linprog函数求解极小化问题得到x。之前确定三个约束条件。1、Axb，其中A为1353的矩阵，b为131的向量。资料2、eqeqxbA，其中eqA为2853的矩阵，eqb为281的向量。3、xlb，其中lb为153的向量编程计算后得到结果如下：（4）极小化FT成本函数设定变量x，为651的向量，其中(53:65)x即为变量lz。使用linprog函数求解极小化问题得到x。之前确定三个约束条件。1、Axb，其中A为7865的矩阵，b为781的向量。2、eqeqxbA，其中eqA为2865的矩阵，eqb为281的向量。3、xlb，其中lb为165的向量编程计算后得到结果如下：资料2.第二大题：2.1.习题5.62.1.1.问题分析问题2112212()(101810)/241513qxxxxxxx通过matlab画出其等高线为：2.1.2.最速下降法最速下降法中，取值：kkpg==()()kkkkkTkkTkgpggpGpgGgx1x2等高线-2024681012-2024681012资料(1)()kxkxkp2.1.3.算法流程图如下图所示：||g(x(k+1))||e选取初始点x0、e开始结束计算f(x0)、g(x0)、G(x0)设定p=-g、alpha=-g'*p/(p'*G*p)更新x(k+1)=x(k)+alpha*p计算f(x(k+1))、g(x(k+1))计算r(k+1)=(f(x(k+1))-f*)/(f(x(k))–f*)取r=max(r(k))输出最优解x*是否2.1.4.初始值（0,0）编程运行结构为：资料收敛过程曲线为：2.1.5.初始值（-0.4,0）编程运行结构为：收敛过程曲线为：x1x2等高线-2024681012-2024681012等高线收敛路径初始点收敛终点资料2.1.6.初始值（10,0）编程运行结构为：收敛过程曲线为：x1x2等高线-2024681012-2024681012等高线收敛路径初始点收敛终点资料2.1.7.初始值（11,0）编程运行结构为：收敛过程曲线为：x1x2等高线-2024681012-2024681012等高线收敛路径初始点收敛终点资料2.2.习题5.72.2.1.问题分析问题()94ln(7)fxxx497gx24(7)GxMatlab画出在区间(710)的函数、一阶导数、二阶导数的变化曲线为x1x2等高线-2024681012-2024681012等高线收敛路径初始点收敛终点资料77.588.599.510707274767880828486xf函数变化曲线77.588.599.510-35-30-25-20-15-10-50510xg一阶导数g变化曲线资料2.2.2.牛顿法牛顿法中，取值：kkkGsg1kkksxx其中，如果G不是半正定，则采用修正牛顿法(+)kkkGIsg77.588.599.510050100150200250300350400xg二阶导数G变化曲线资料2.2.3.算法流程图如下图所示：开始结束设定初始点x(0)计算f(x)、g(x)、G(x)计算迭代步长s=-g/G更新x(k+1)=x(k)+s迭代次数k=5输出最终的x是否2.2.4.初始值7.40编程运行结构为：收敛过程曲线为：资料2.2.5.初始值7.20编程运行结构为：收敛过程曲线为：7.397.47.417.427.437.447.457.4670.24570.2570.25570.2670.265xf函数变化曲线函数曲线收敛路径初始点收敛终点资料2.2.6.初始值7.01编程运行结构为：收敛过程曲线为：7.17.27.37.47.57.67.770.270.470.670.87171.271.471.6xf函数变化曲线函数曲线收敛路径初始点收敛终点资料2.2.7.初始值7.80编程运行结构为：收敛过程曲线为：6.856.96.9577.057.17.157.27.257.37.35727476788082xf函数变化曲线函数曲线收敛路径初始点收敛终点资料2.2.8.初始值7.88编程运行结构为：收敛过程曲线为：7.17.27.37.47.57.67.77.87.97070.57171.572xf函数变化曲线函数曲线收敛路径初始点收敛终点资料2.2.9.分析函数在区间（7，7.8888）内是凸函数，G恒大于零，所以单纯牛顿法保证收敛。2.3.习题5.82.3.1.问题分析问题12121212()910[ln(100)lnlnln(500)]fxxxuxxxxxxMatlab画出函数在区间1u,1[0,100]x和2[0,100]x的等高线如Figure2所示，发现最优值在（0.5，98）附近，对这个区域集中等高线，如Figure3所示。6.877.27.47.67.88717273747576777879xf函数变化曲线函数曲线收敛路径初始点收敛终点资料Figure2函数等高线x1x2等高线102030405060708090100102030405060708090100资料Figure3区域放大等高线2.3.2.牛顿法单纯牛顿法中，有kkkGsg1kkksxx其中，如果G不是半正定，则采用修正牛顿法(+)kkkGIsg带线搜索的牛顿法，有kkkGpg1kkkpxx其中，((1))(())kkfxkfxkgpx1x2等高线0.511.522.533.549595.59696.59797.59898.59999.5100资料2.3.3.算法流程图无线搜索的算法流程图如下：开始结束设定初始点x(0)计算f(x)、g(x)、G(x)计算迭代步长s=-g/G更新x(k+1)=x(k)+s||g(x)||10^-8输出最终的x是否具有线搜索的牛顿法的算法流程图如下：资料开始结束设定初始点x(0)、gama、rho、alpha计算f(x(k))、g(x(k))、G(x(k))计算p=-g/G更新x(k+1)=x(k)+alpha*p||g(x)||10^-8输出最终的x是否计算f(x(k+1))f(x(k+1))f(x(0))+rho*f`(x(0))*alpha或x在定义域内计算g(x(k+1))更新alpha=gama*alpha是否2.3.4.无线搜索（1u）：资料2.3.5.无线搜索（0.1u）：资料2.3.6.线搜索：1u资料x1x2等高线024681012889092949698100102等高线收敛路径初始点收敛终点资料x1x2等高线-10-50510405060708090100等高线收敛路径初始点收敛终点资料x1x2等高线051015202565707580859095100等高线收敛路径初始点收敛终点资料2.3.7.线搜索：0.1ux1x2等高线-10-505101520252030405060708090100等高线收敛路径初始点收敛终点资料x1x2等高线102030405060708090100102030405060708090100等高线收敛路径初始点收敛终点资料x1x2等高线-4-20246405060708090100等高线收敛路径初始点收敛终点资料x1x2等高线0510152065707580859095100等高线收敛路径初始点收敛终点资料2.3.8.分析：线搜索能够保证搜索在有效范围之内，具有更加可实现性。2.4.习题5.92.4.1.问题分析问题22211()100()2(1)fxxxxMatlab画出函数等高曲线为：x1x2等高线-505101520252030405060708090100等高线收敛路径初始点收敛终点资料Figure4Rosenbrock函数登高曲线Figure5Rosenbrock函数登高曲线x1x2等高线-1.5-1-0.500.511.5-1.5-1-0.500.511.5x1x2等高线-1.5-1-0.500.511.5-1.5-1-0.500.511.5资料2.4.2.回溯最速下降法：（1）算法kkpg==()()kkkkkTkkTkgpggpGpgGg((1))(())kkfxkfxkgp(1)()kxkxkp（2）流程（3）计算结果初始值为（1.2,1.2）x1x2等高线-1-0.500.51-0.6-0.4-0.200.20.40.60.811.21.4等高线收敛路径初始点收敛终点资料初始值为（-1.2,1）x1x2等高线0.9511.051.11.151.21.2511.051.11.151.21.251.3等高线收敛路径初始点收敛终点x1x2等高线-1-0.500.51-0.200.20.40.60.811.2等高线收敛路径初始点收敛终点资料2.4.3.回溯牛顿法中（1）算法kkkGpg如果G不是半正定，则采用修正牛顿法(+)kkkGIsg1kkkpxx其中，((1))(())kkfxkfxkgp（2）流程开始结束设定初始点x(0)、gama、rho、alpha计算f(x(k))、g(x(k))、G(x(k))计算p=-g/G更新x(k+1)=x(k)+alpha*p||g(x)||10^-8输出最终的x是否计算f(x(k+1))f(x(k+1))f(x(k))+rho*f`(x(k))*alpha更新alpha=gama*alpha是否（3）计算结果资料x1x2等高线-0.6-0.4-0.200.20.40.60.811.21.4-1.5-1-0.500.511.5等高线收敛路径初始点收敛终点资料2.5.习题5.192.5.1.算法流程根据题意算法流程图如下：x1x2等高线-1-0.500.5100.20.40.60.811.21.4等高线收敛路径初始点收敛终点资料开始结束确定维数N确定初始矩阵G、右端向量b、初始点x(0)计算g(0)=Gx-b,令p(0)=-g(0)计算d=G*p(k)、a=(g(k)`*g(k))/(p(k)`*d)||g(x)||10^-6输出最终的x是计算x(k+1)=x(k)+a*p(k)否计算g(k+1)=g(k)+a*d计算beta=(g(k+1)`*g(k+1))/(g(k)`*g(k))更新p(k+1)=-g(k+1)+beta*p(k)2.5.2.N=5运行结果资料2.5.3.N=8运行结果2.5.4.N=12运行结果2.5.5.N=20运行结果2.6.习题5.272.6.1.问题分析问题资料1(1/()1)12,)(1/)xctxxtx（1(1/()1)i12r,)(1/)xciiitxxtxd（ir,)(,)ijtxAijx（()()TgxArx()TGxAA2.6.2.修正的高斯牛顿法+)STTkAAIAr（(1)()xkxks(())(()0.1Tiffxksfxkgsssend22(())(())()1(())2fxkfxkskfxkrAs11()0.252()0.75/2kkkkifkelseifkend()0(1)()()0.75(1)()ifkxkxkelseifkxkx