第16讲 二次规划

第六章二次规划quadraticprogram一．二次规划简介二．等式约束二次规划方法1直接变量消去法方法2Lagrange乘子法一．二次规划简介.二次规划是最简单的约束非线性规划问题.二次规划:带有二次目标函数和线性约束的最优化问题.1.标准形式1min(),2..,,,.TTTiiTiiqxxGxgxstaxbiEaxbiI(1)其中G是nn的对称矩阵.,EI分别对应等式约束和不等式约束指标集合.,,,igxandaiEI都是n维向量.2．求解说明：如果Hessian矩阵正半定,则QP问题存在全局最优解;如果Hessian矩阵正定,则QP问题存在唯一的全局最优解.原因：？原因：此时目标函数为凸函数，任何K-T点都是二次规划问题的极小点.如果Hessian矩阵不定时,可能存在非全局的最优解.3．二次规划研究的意义(1)二次规划问题简单，便于求解.某些较复杂的非线性规划问题可以转化为求解一系列二次规问题.(2)实际应用广泛：工作计划，时间调度，规模经济学，工程设计以及控制领域，设施分配问题，选址问题，二次分配问题，微观经济学的很多问题.化学工程建模.4．应用实例-组合投资的马库维茨模型1952年Markowitz发表了《资产选择:投资的有效分散化》一文，奠定了资产组合的理论基础，从而推动了基金业的发展.Markowitz最早采用风险资产的期望收益率和用方差代表的风险来研究资产的选择和组合问题.Markowitz的证券组合投资模型是现代证券投资理论的基石.它解决了持有一定数量资本的投资者，怎样在选定的多种风险证券投资上分配投资量，从而达到分散风险，取得尽可能大的收益这样的投资问题.1990年获得诺贝尔经济学奖！模型的建立设投资的期限是一年，可供选择的金融资产数为n。设此n中金融资产的年收益为随机变量。由于我们主要关心投资的分配比例，不妨设投资总数为1个单位，用于第j中投资的资金比例为，令称为投资组合向量，显然应有：12(,,,)'n(1,2,,)jwjn12(,,,)'n11njjw投资一年的收益也是一个随机变量，期望收益为马库维茨建议用随机变量（组合投资收益）的方差作为投资风险的度量，即设随机向量的数学期望为，自协方差矩阵为'w1122(')()(),,()nnEwEwEwEw'w22(')(('(')))DwEwEwE()()'()ijnnDEEE那么投资者一般希望收益越大越好，风险越小越好。但收益大和风险小往往是两个有矛盾的目标，因此马库维茨将问题归结为：将风险控制在一定水平之下，选择投资组合使期望收益最大；或者在收益不低于某个水平前提下使投资的风险最小。这样就有以下两个马库维茨组合投资优化模型。2'.wDw1max(')..(')(0)1,0(1,2,,)njjjIEwstDwrwwjn其中r是预定的风险水平.第一个模型是控制风险,优化收益模型第二个模型是控制收益，极小化风险的模型21min(')..(')(0)1,0(1,2,,)njjjDwstEwaawwjn还可将收益和风险指标进行加权平均，得到如下模型其中，是一个适当选取的常数.由于在中包含了各分量的二次项，这三个模型均为二次规划模型.1min(')(1)(')..1,0(1,2,,)njjjcDwEwstwwjn01(')Dw模型的求解和应用上述三个模型中均需要用到随机变量的数学期望和协方差矩阵，这可以通过对前若干年的各资产收益的统计分析获得.而这些二次规划问题在系数确定后可用软件（如LINDO/LINGO）求解.Matlab中求解二次规划的命令是[X,FVAL]=QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)X的返回值是向量x，FVAL的返回值是目标函数在X处的值。（具体细节可以参看在Matlab指令中运行helpquadprog后的帮助）。例求解二次规划0,94336442)(min21212121222121xxxxxxx-x-xxx-xxf解编写如下程序：h=[4,-4;-4,8];f=[-6;-3];a=[1,1;4,1];b=[3;9];[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))求得1.02501)(Min,0500.19500.1xfx二．等式约束二次规划问题1．标准形式1min(),2..,TTTqxxGxgxstAxb(2)其中,,,,nmnmnnnxRbRARgRGR且G是对称的，设()rankAm.方法1直接变量消去法假定已经找到变量x的一分解：BNxxx，其中,mnmBNxRxR.对应A的分解为BNAAA使得BA可逆，则等式约束可写成：TTBBNNAxAxb，(3)由于1BA的存在，故知1()TBBNNxAbAx.(4)将(4)式带入(2)式，可得其等价形式：1ˆˆˆmin2nmTTNNNxRxGxgxc.(5)1ˆˆˆmin2nmTTNNNxRxGxgxc.(5)其中111ˆ()()TNNBBNBNBBBBggAAgGAAGAb，1111ˆ()()TTTTNNNBBNNBBNNBBBBNGGGAAAAGAAGAA，1111ˆ()()2TTTTBBBBBBcbAGAbgAb以及,,,,BBBNBBBNNNNBNNGGgxAgGxAgxAGG相应的分解.如果ˆG正定,则由(5)式,可得唯一解:1ˆˆNNxGg.代入(4)式可得对应的Bx.从而问题的最有解：11ˆˆˆˆBNTTTBBNxAbAAGgxxGg.(6)设在x处的Lagrange乘子为,则有AgGx(7)从而(考虑方程组前m行)1()BBBBBBNNAgGxGx.消去法优缺点：优点：思想简单明了.缺点：当BA接近于奇异阵的时候，求解x可能导致数值不稳定.例122212312323min..1,1.qxxxxstxxxxx.例122212312323min..1,1.qxxxxstxxxxx.解：由等式约束条件，可得23131,2xxxx.上式既是变量分解123,BNxxxxx.代入二次函数可得3222333min4(1)xRxxx，由此可解312x.然后代入Bx的表达式,得311,,22x.由AgGx，可知12210311111，从上式可求得Lagrange乘子122,1.方法2Lagrange乘子法定义1Lagrange函数1(,)()2TTTTLxxGxgxAxb,其中是Lagrange乘子.稳定点条件产生方程组:(,)0:0(,)0:0xTLxGxgALxAxb.经重新组织,可得线性方程组0TGAxgbA.(8)称其中的系数矩阵为Lagrange矩阵，(8)式成为KKT方程组.如果Lagrange矩阵的逆存在，且可表示为：10TTGAHTATU.则,x的表达式可写成：TxHgTbTgUb.(9)当1G存在时，,,HTU的直接表达式为：1111111111(),(),().TTTTHGGAAGAAGTGAAGAUAGA.110TTGAHTKATU.Lagrange逆矩阵中T和A的关系？0TGAKA(简化表示!)由1TTA，因而TT是A的左广义逆.当A正半定时，如果kx为任意可行点，则TkAxb.设梯度向量kkggGx,则最优解可重新表示为:kkTkxxHgTg.(10)(10)式表明:矩阵H对可行域包含了正确的曲率信息,因而可以看作是简约逆Hessian矩阵.为了避免矩阵求解带来的数值不稳定性，可用逐步分解的方法求解(KKT方程组)：0TGAxgbA.(8)方法:设G正定,先求出G的TLDL分解,再利用此分解因子消去(8)式中非对角线元素A,TA.此时右下角对角块从0变成负定矩阵1TAGA.然后再对其做ˆˆˆTLDL分解.得到:TKLDL,0,ˆˆTLDLDBLD,B由LDBA定义,并易于通过回代确定.补充内容：二次规划问题Matlab求解二次规划问题（quadraticprogramming）的标准形式为：sub.to其中，H、A、Aeq为矩阵，f、b、beq、lb、ub、x为向量其它形式的二次规划问题都可转化为标准形式.MATLAB5.x版中的qp函数已被6.0版中的函数quadprog取代。xfxHx21minbxAbeqxAeqbuxbl函数quadprog格式x=quadprog(H,f,A,b)%其中H,f,A,b为标准形中的参数，x为目标函数的最小值.x=quadprog(H,f,A,b,Aeq,beq)%Aeq,beq满足等约束条件.x=quadprog(H,f,A,b,Aeq,beq,lb,ub)%lb,ub分别为解x的下界与上界.x=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)%x0为设置的初值x=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)%options为指定的优化参数.[x,fval]=quadprog(…)%fval为目标函数最优值.[x,fval,exitflag]=quadprog(…)%exitflag与线性规划中参数意义相同.[x,fval,exitflag,output]=quadprog(…)%output与线性规划中参数意义相同.[x,fval,exitflag,output,lambda]=quadprog(…)%lambda与线性规划中参数意义相同.3xx)0,0(xx0110)xx(213xx)xx(fmin2121212121例求二次规划的最优解maxf(x1,x2)=x1x2+3sub.tox1+x2-2=0解：化成标准形式：sub.tox1+x2=2在Matlab中实现如下：H=[0,-1;-1,0];f=[0;0];Aeq=[11];b=2;[x,fval,exitflag,output,lambda]=quadprog(H,f,[],[],Aeq,b)结果为：x=1.00001.0000fval=-1.0000exitflag=4output=iterations:1algorithm:'large-scale:projectivepreconditionedconjugategradients'firstorderopt:0cgiterations:1message:'Optimizationterminated:localminimumfound;thesolutionissingular.'lambda=eqlin:1.0000ineqlin:[]lower:[]upper:[]