第四章 二次规划

求解二次规划问题——外点罚函数法/内点罚函数法
外点罚函数法
做法就是在可行域之外设置障碍，可解决等式和不等式约束问题，但求出的最优解往往不在可行域内。

将约束条件转化成函数表达式的一部分，使新的函数式变为无约束的二次规划问题：
约束条件转换：
将等式和不等式转换后的式子融合：
算法步骤：
1 确定初始点x0，初始罚银子Mk（可取M1=1），设置精确度
2 用解析法或者其他方法求解驻点，得到x
3 当Mk*p（x）<精确度将此x作为最优解，若不满足将持续增大Mk
（很多算例上直接在算出驻点表达式后，将Mk趋近无穷来求解）
内点罚函数法
做法就是在可行域内部设限制，靠近边缘的域设置较大的障碍，边缘的障碍无穷大，用来解决不等式约束问题，算出的解必在可行域内部
同外点法一样将约束条件转化为函数的一部分，使之成为无约束二次规划问题：
约束条件转化：
倒数障碍函数和对数障碍函数（使用其中的一种就可以）
算法步骤：和外点法类似，但当前解不满足精度要求时，rk会缩小，甚多算例将rk趋近0来求解函数最小值。

2、对于二次规划模型求解：问题1：先求出ij c ，结果如下表：330.7 320.3 300.2 258.6 198 180.5 163.1 181.2 224.2 252 256 266 281.2 288 302 370.7 360.3 345.2 326.6 266 250.5 241 226.2 269.2 297 301 311 326.2 333 347 385.7 375.3 355.2 336.6 276 260.5 251 241.2 203.2 237 241 251 266.2 273 287 420.7 410.3 395.2 376.6 316 300.5 291 276.2 244.2 222 211 221 236.2 243 257 410.7 400.3 380.2 361.6 301 285.5 276 266.2 234.2 212 188 206 226.2 228 242 415.7 405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 195 176.2 161 178 435.7 425.3 405.2 386.6 326 310.5 301 291.2 259.2 237 226 216 198.2 185 162由于二次规划模型中约束条件151{0}[500,],1,2,7,ij i j X s i =∈=∑的存在，必须加以处理。

引进0-1变量15,...2,1,=i n i ，则151{0}[500,],1,2,7,ij i j Xs i =∈=∑可以等价转换为下面的三个约束条件：i j ij s X≤∑=151i j ij Mn X ≤∑=151i j ijn X*500151≥∑= 其中M 为一个很大数。

这样就可以得到下面的lingo 程序：sets :s/1..7/:sx;a/1..15/:z,y,n,t;links(s,a):c,x;endsetsdata:sx=800 800 1000 2000 2000 2000 3000;t=104 301 750 606 194 205 201 680 480 300 220 210 420 500 0;c=330.7 320.3 300.2 258.6 198 180.5 163.1 181.2 224.2 252 256 266 281.2 288 302370.7 360.3 345.2 326.6 266 250.5 241 226.2 269.2 297 301 311 326.2 333 347385.7 375.3 355.2 336.6 276 260.5 251 241.2 203.2 237 241 251 266.2 273 287420.7 410.3 395.2 376.6 316 300.5 291 276.2 244.2 222 211 221 236.2 243 257410.7 400.3 380.2 361.6 301 285.5 276 266.2 234.2 212 188 206 226.2 228 242415.7 405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 195 176.2 161 178435.7 425.3 405.2 386.6 326 310.5 301 291.2 259.2 237 226 216 198.2 185 162;enddata!目标函数;min=@sum(links:c*x)+0.05*@sum(a(j):z(j)*(z(j)+1)+y(j)*(y(j)+1));!每个工厂产量的限制;@for(s(i):@sum(a(j):x(i,j))<=sx);@for(s(i):@sum(a(j):x(i,j))<=90000000*n(i));@for(s(i):@sum(a(j):x(i,j))>=500*n(i));!每个结点运量的限制;@for(a(j):@sum(s(i):x(i,j))=z(j)+y(j));!区间长度的限制;@for(a(j)|j#le#14:z(j+1)+y(j)=t(j));!初始条件;z(1)=0;y(15)=0;!设置0-1变量;@for(a(j):@bin(n(j)));Local optimal solution found at iteration: 5800Objective value: 1278632.问题3：sets:s/1..7/:sx;a/1..21/:z,y,n,t;links(s,a):c,x;endsetsdata:sx=800 800 1000 2000 2000 2000 3000;t=104 301 750 606 194 205 201 680 480 300 220 210 420 500 0 0 0 0 0 0 0;c=330.7 320.3 300.2 258.6 198 180.5 163.1 181.2 224.2 252 256 266 281.2 288 302220 255 260 265 275 285370.7 360.3 345.2 326.6 266 250.5 241 226.2 269.2 297 301 311 326.2 333 347265 300 305 310 320 330385.7 375.3 355.2 336.6 276 260.5 251 241.2 203.2 237 241 251 266.2 273 287199 240 245 250 260 270420.7 410.3 395.2 376.6 316 300.5 291 276.2 244.2 222 211 221 236.2 243 257240 210 215 220 230 240410.7 400.3 380.2 361.6 301 285.5 276 266.2 234.2 212 188 206 226.2 228 242230 187 205 205 220 230415.7 405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 195 176.2 161 178230 200 183 186 160 150435.7 425.3 405.2 386.6 326 310.5 301 291.2 259.2 237 226 216 198.2 185 162245 225 210 215 192 189;enddata!目标函数;min=@sum(links:c*x)+0.05*@sum(a(j):z(j)*(z(j)+1)+ y(j)*(y(j)+1))+0.05*yd1*(yd1+1)+0.05*yd2*(yd2+1)+0.05*yd3*(yd3+1);!每个工厂产量的限制;@for(s(i):@sum(a(j):x(i,j))<=sx);@for(s(i):@sum(a(j):x(i,j))<=9000000*n(i));@for(s(i):@sum(a(j):x(i,j))>=500*n(i));!每个结点运量的限制;@for(a(j)|j#ne#9 #and# j#ne#11 #and#j#ne#17:@sum(s(i):x(i,j))=z(j)+y(j));@sum(s(i):x(i,9))=z(9)+y(9)+yd1;@sum(s(i):x(i,11))=z(11)+y(11)+yd2;@sum(s(i):x(i,17))=z(17)+y(17)+yd3;!区间长度的限制;@for(a(j)|j#le#14:z(j+1)+y(j)=t(j));y(16)+yd1=42;y(17)+yd2=10;z(17)+y(18)=130;yd3+y(19)=190;z(19)+y(20)=260;z(20)+y(21)=100;!初始条件;z(1)=0;y(15)=0;z(16)=0;z(18)=0;z(21)=0;!设置0-1变量;@for(a(j):@bin(n(j)));Local optimal solution found at iteration: 9263 Objective value: 1411287.。

9.2.4 二次规划问题9.2.4.1 基本数学原理如果某非线性规划的目标函数为自变量的二次函数，约束条件全是线性函数，就称这种规划为二次规划。

其数学模型为：其中，H, A,和Aeq为矩阵,f, b, beq, lb, ub,和x为向量。

9.2.4.2 相关函数介绍quadprog函数功能：求解二次规划问题。

语法：x = quadprog(H,f,A,b)x = quadprog(H,f,A,b,Aeq,beq,lb,ub)x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval] = quadprog(...)[x,fval,exitflag] = quadprog(...)[x,fval,exitflag,output] = quadprog(...)[x,fval,exitflag,output,lambda] = quadprog(...)描述：x = quadprog(H,f,A,b) 返回向量x，最小化函数1/2*x'*H*x + f'*x ，其约束条件为A*x <= b。

x = quadprog(H,f,A,b,Aeq,beq)仍然求解上面的问题，但添加了等式约束条件Aeq*x = beq。

x = quadprog(H,f,A,b,lb,ub)定义设计变量的下界lb和上界ub，使得lb <= x <= ub。

x = quadprog(H,f,A,b,lb,ub,x0)同上，并设置初值x0。

x = quadprog(H,f,A,b,lb,ub,x0,options)根据options参数指定的优化参数进行最小化。

[x,fval] = quadprog(...)返回解x处的目标函数值fval = 0.5*x'*H*x + f'*x。

二次规划问题的一个解法及几点注记二次规划问题是指在线性规划模型中，目标函数和约束条件均为二次函数的问题。

常见的解法有坐标下降法和半正定性法。

下面是关于二次规划问题的一个解法（坐标下降法）及几点注记。

解法：坐标下降法是一种求解二次规划问题的迭代算法。

基本思路是不断地求解当前点的搜索方向，然后在这个方向上移动，直到找到最优解为止。

具体步骤如下：1.设定初始点 x0，并求出当前点的目标函数值 f(x0)。

2.求解当前点 x0 的搜索方向 d0。

3.设定步长 t，求出下一个点 x1 = x0 + t * d0。

4.求出下一个点 x1 的目标函数值 f(x1)，并与当前点 x0的目标函数值 f(x0) 进行比较。

5.若 f(x1) < f(x0)，则接下来以 x1 为当前点，重复步骤 2-5；若 f(x1) ≥ f(x0)，则退出迭代。

注记：1.坐标下降法的关键在于如何求解当前点的搜索方向d0。

一般来说，当前点的搜索方向 d0应该是当前点的二次梯二次规划问题的一个解法及几点注记：继续上文：注记：1.坐标下降法的关键在于如何求解当前点的搜索方向d0。

一般来说，当前点的搜索方向 d0应该是当前点的二次梯度的负方向，即 d0 = -∇2f(x0)。

2.坐标下降法的收敛速度取决于步长 t的取值。

常用的方法有常数步长法和自适应步长法。

常数步长法是指固定步长t，而自适应步长法是指根据当前点的目标函数值变化情况来调整步长 t。

3.坐标下降法的收敛性是指随着迭代次数的增加，目标函数的值会逐渐降低。

但是，坐标下降法并不能保证收敛到全局最优解，只能保证收敛到局部最优解。

4.坐标下降法的迭代次数一般较多，但是每次迭代的计算量较小，因此坐标下降法适用于线性规划问题规模较大的情况。

希望这些内容能为你的学习提供帮助！。

二次规划求解方法探讨李骥昭1 刘义山2(1.平顶山工业职业技术学院文化教育部1 河南 平顶山 467001; 2.平顶山工业职业技术学院文化教育部2 河南 平顶山 467001)摘要：文章推广与应用了二次非线性规划模型的基础理论及算法。

在线性规划模型中，活动对目标函数的贡献与活动水平成比例关系，因而目标函数是决策变量的线性函数，而在实际问题中，往往遇到活动对目标函数的贡献与活动水平不成比例关系的情形，即目标函数不是决策变量的线性函数，而是二次非线性函数，我们可以利用K-T 条件并转化为等价求解相应的线性规划问题。

经过分析可以得到结论，目标函数变成了线性函数，但约束函数中有一个非线性函数，这时问题仍然是非线性的。

应用Excel 规划求解工具解这个模型后我们知道如果投资者愿意承担多一点的风险，就可以获得更大的收益。

关键词：非线性规划，线性规划，目标函数，决策变量，模型 中图分类：O226 文献标识：A 0 引言非线性规划是运筹学的一个重要分支，它在管理科学、系统控制等诸多领域有广泛应用。

非线性规划的任一算法都不能仅仅考察可行域极点的目标函数值来寻优。

非线性规划的最优点可能在其可行域的任一点达到，即最优解可能在极点，或边介点或内点达到。

在非线性规划问题中，其变量取值受到多个约束条件的限制，对其求解，一方面要使目标函数每次选代要逐次下降，且还要保持解的可行性。

这就给寻找最优解带来更大的困难。

为使求解能较顺利进行，一般采用将约束条件转化为无约束条件，化为较简单问题来处理[1]。

1 预备知识1.1 相关概念,相关定理 若0x 使得()00>xg j 则称此约束条件是0x的不起作用约束；起作用约束：若0x 使得()00=xg j ，则称此约束条件是0x 的起作用约束[2]。

可行方向：若(){}0,,,,2,10|00>∈∃=≥=∈λnj E P L j x g x R x 的实数，使得[]0,0λλ∈，均有R P x ∈+λ0，则称方向P 是0x 的一个可行方向；当()P J j P xg Tj ,00∈>∇必为0x 的一个可行方向；下降方向：若0,00>∈∃∈λn E P R x 使得[]0,0λλ∈均有()()00x f P x f <+λ，则称P 为0x 的一个下降方向。

二次规划问题二次规划问题（quadratic programming）的标准形式为：sub.to其中，H、A、Aeq为矩阵，f、b、beq、lb、ub、x为向量其它形式的二次规划问题都可转化为标准形式。

MATLAB5.x版中的qp函数已被6.0版中的函数quadprog取代。

函数 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,exitfla g] = quadprog(…) % exitflag与线性规划中参数意义相同[x,fval,exitflag,output] = quadprog(…) % output与线性规划中参数意义相同[x,fval,exitflag,output,lambda] = quadprog(…) % lambda与线性规划中参数意义相同例5-8 求解下面二次规划问题sub.to解：则，，在MA TLAB中实现如下：>>H = [1 -1; -1 2] ;>>f = [-2; -6];>>A = [1 1; -1 2; 2 1];>>b = [2; 2; 3];>>lb = zeros(2,1);>>[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[ ],[ ],lb)结果为：x = %最优解0.66671.3333fval = %最优值-8.2222exitflag = %收敛1output =iterations: 3algorithm: 'medium-scale: active-set'firstorderopt: [ ]cgiterations: [ ]lambda =lower: [2x1 double]upper: [2x1 double]eqlin: [0x1 double]ineqlin: [3x1 double]>> lambda.ineqlinans =3.11110.4444>> lambda.lowerans =说明第1、2个约束条件有效，其余无效。