机械优化作业

机械优化设计报告。

二次规划法。

班级：信息计算111802班。

姓名：甘金宝。

学号：201118030202

一、绪论。二次规划是非线性规划中的一类特殊数学规划问题，在很多方面都有应用，如投资组合、约束最小二乘问题的求解、序列二次规划在非线性优化问题中应用等。在过去的几十年里，二次规划已经成为运筹学、经济数学、管理科学、系统分析和组合优化科学的基本方法。

二次规划的一般形式可以表示为，如下图，其中g是hessian矩阵，τ是有限指标集，c，x和，都是r中的向量。如果hessian矩阵是半正定的，则我们说（1.1）是一个凸二次规划，在这种情况下该问题的困难程度类似于线性规划（如果=0，二次规划问题就变成线性规划问题了）。

如果有至少一个向量满足约束并且在可行域有下界，则凸二次规划问题就有一个全局最小值。如果是正定的，则这类二次规划为严格的凸二次规划，那么全局最小值就是唯一的。如果是一个不定矩阵，则为非凸二次规划，这类二次规划更有挑战性，因为它们有多个平稳点和局部极小值点。

二、算法理论。

二次规划是非线性优化中的一种特殊情形，它的目标函数是二次实函数，约。

束函数都是线性函数。由于二次规划比较简单，便于求解(仅次于线性规划), 并且一些非线性优化问题可以转化为求解一系列的二次规划问题，因此二次规划的求解方法较早引起人们的重视，成为求解非线性优化的一个重要途径。二次规划的算法较多，本**仅介绍求解一般约束凸二次规划的有效集方法。

考虑一般二次规划。

有效集方法的最大难点是事先一般不知道有效集，因此只有想办法构造一个集合序列去逼近它。即从初始点出发，计算有效集，解对应的等式约束子问题。重复这一做法，得到有效集序列， ,使之，以获得原问题的最优解。

我们分六步来介绍有效集方法的算法原理和实施步骤。

第一步选定初始值。给定初始可行点，令。

第二步求解子问题。确定相应的有效集，求解子问题。

得到极小点和拉格朗日乘子向量。若转入步三；否则转步二。

第三步检验终止准则。计算拉格朗日乘子其中，令。若，则是全局极小点，停算。否则若，则令，转步一。

第四步确定步长。令，其中，其中。令。

第五步若，则令，否则，若，则令，其中满足。

第六步令，返回第一步。

三、算法框图。

四、算法程序。

function [x,lamk,exitflag,output]=qpact(h,c,ae,be,ai,bi,x0)

功能：用有效集方法解一般约束二次规划问题：

min f(x)=0.5*x’*h*x+c’*x, a’˙i*x-b˙i=0,(i=1,..l), a’˙i*x-b˙i?=0,(i=l+1,..m)

输入： x0是初始点， h, c分别是目标函数二次型矩阵和向量；

ae=(a˙1,..a˙l)’,be=(b˙1,..b˙l)’;

ai=(a˙–l+1?,.a˙m), bi=(b˙–l+1?,.b˙m)’.

输出： x是最优解， lambda是对应的乘子向量；output是结构变量，输出极小值f(x), 迭代次数k等信息， exitflag是算法终止类型。

主程序开始。

初始化。epsilon=1.0e-9; err=1.0e-6;

k=0; x=x0; n=length(x); kmax=1.0e3;

ne=length(be); ni=length(bi); lamk=zeros(ne+ni,1);

index=ones(ni,1);

for (i=1:ni)

if(ai(i,:)x>bi(i)+epsilon), index(i)=0; end

end算法主程序。

while (k<=kmax)

求解子问题。

aee=if(ne>0), aee=ae; end

for(j=1:ni)

if(index(j)>0), aee=[aee; ai(j,:)end

endgk=h*x+c;

m1,n1] =size(aee);

dk,lamk]=qsubp(h,gk,aee,zeros(m1,1));

if(norm(dk)<=err)

y=0.0;

if(length(lamk)>ne)

y,jk]=min(lamk(ne+1:length(lamk)))

endif(y>=0)

exitflag=0;

elseexitflag=1;

for(i=1:ni)

if(index(i)&(ne+sum(index(1:i)))jk)

index(i)=0; break;

endend

endk=k+1;

elseexitflag=1;

求步长。alpha=1.0; tm=1.0;

for(i=1:ni)

if((index(i)==0)&(ai(i,:)dk<0))

tm1=(bi(i)-ai(i,:)x)/(ai(i,:)dk);

if(tm1tm=tm1; ti=i;

endend

endalpha=min(alpha,tm);

x=x+alpha*dk;

修正有效集。

if(tm<1), index(ti)=1; end

endif(exitflag==0), break; end

k=k+1;

end*h*x+c'*x;

%%%求解子问题。

function [x,lambda]=qsubp(h,c,ae,be)

ginvh=pinv(h);

m,n]=size(ae);

if(m>0)

rb=ae*ginvh*c + be;

lambda=pinv(ae*ginvh*ae')*rb;

x=ginvh*(ae'*lambda-c);

elsex=-ginvh*c;

lambda=0;

end五、算法实现。

例1. 求解二次规划问题。

解：在matlab命令窗口输入下列命令：

h=[1 -1;-1 2];

c=[-6 -2]';

ae=[ be=[

ai=[-2 -1;1 -1;-1 -2; 1 0;0 1];

bi=[-3 -1 -2 0 0]';

x0=[0 0]';

x,lambda,exitflag,output]=qpact(h,c,ae,be,ai,bi,x0)

的计算结果为。x =

lambda =

exitflag =

output =

fval: -8.1111

iter: 7

该问题有精确解，最优值。

机械优化作业

机械优化设计优化作业习题

机械优化作业复合型法 1

最优化作业

其他用户还读了

机械优化作业

机械优化设计优化作业习题

机械优化作业 复合型法 1

最优化作业

其他用户还读了

机械优化作业复合型法 1