二次规划与非线性规划讲解

1、二次规划与非线性规划一、二次规划(Quadratic Program)概念二次规划:带有二次目标函数和线性约束的最优化问题.它是最简单的约束非线性规划问题.1.标准形式min q(x) = xT Gx + g T x,s.t. =i e E,(1)ax>bi9 i e 1.其中G是”"的对称矩阵.E,/分别对应等式约束和不等式约束指标集合.jeEU/都是”维向;=i2.二次规划研究的意义(1)二次规划问题简单，便于求解某些较复杂的非线性 规划问题可以转化为求解一系列二次规问题.(2)实际应用广泛：工作计划，时间调度，规模经济学，工程设计以及控制领 域，设施分配问题，选址问题，二

2、次分配问题，微观经济学 的很多问题.化学工程建模.二、Matlab中求解二次规划类型模型基本函数名一元函数极小min F (x) s.t. Xi<x<x2x=fminbnd(z xlf x2)无约束极小min F(X)X=fminunc (、F JXO) X=fminsearch(、FJ XO)线性规划min cT Xs.t. AXbX=linprog(crAzb)二次规划min 丄x Hx+g x 2s.t. AxbX=quadprog(H,gz Ar b)约束极小 (非线性规划)min F(X)s.t. G(X)WOX=fmincon ( 'FGJXO)达到H标问题mi

3、n rs.t. Fix) -wrgoalX=fgoalattain('F，x, goalz w)极小极大问题min max Fi (x) x F(x)is.t. G(x)W0X=fminimax(、FG z xO)X,FVAL=QUADPROG(H,g,A,b,Aeq,beq,LB,UB,XO,OPTIONS)X的返回值是向量 FVAL的返回值是目标函数在X处的值。(具体细节可以参看在Matlab指令中运行help quadprog后的帮 助)。例求解二次规划min /(x) = 2xi2-4x1x2 +4A22-6xr3x2X)+ x2 < 34兀+ x2 <9xx2 &

4、gt; 0转化为mat lab求解格式:21吃八Y( 1)Z、<V、厂0、</ 、4 L9丿1。丿min f(x) = 2x)2 - 4xx2 + 4x22 - 6召-3x2 = 1解编写如下程序：h=4,-4;-4,8；g=-6;-3；A=lzl;4,l；b=3;9；xr value =qriadprog (h,g,Azb z , , zeros (2 , D)求得ri-9500"G。Min W1.025C定义 如果目标函数或约束条件中至少有一个是非线性函数, 则最优化问题就叫做非线性规划问题.一般形式:佃(x)no K(x)=o(1)其中x =6*2,，心）4时是定义

5、在R上的实值函数定义把满足问题（1）中条件的解X（eR"）称为可行解（或可行点）.所有可行点的集合称为可行集（或可行域）.记为D即D= *lg/（x）o,竹（X）=O, X e R,z 问题可简记为 min/（x）.五、非线性规划的基本解法> SUTM外点法1.罚函数法一'SUTM内点法（障碍罚函数法）2.近似线性规划法1、罚函数法罚函数法基本思想是通过构造罚函数把约束问 题转化为一系列无约束最优化问题，进而用无约束最 优化方法夫求解.这类方法称为序列无约束最小化方 法.简称为SUMT法.其一为SUMT外点法，其二为SUMT内点法.2、近似规划法近似规划法的基本思想：将

6、问题屮的目标西数/(X) 和约束条件 &(x)no =乞(X) = o (/ = 1,J)近似为线性函数，并对变量的取值范围加以限制，从 而得到一个近似线性规划问题，再用单纯形法求解之, 把其符合原始条件的最优解作为解的近似.每得到一个近似解，都从这点出发，重复以上步骤.这样，通过求解一系列线性规划问题，产生一个 由线性规划最优解组成的序列，经验表明，这样的序 列往往收敛于非线性规划问题的解.13实现方法是:在点0处，将/(X), g,(x)也(X)按泰勒级数展开并取 一阶近似，得到近似线性规划问题：min/(X)a/(XA) + W(0)(X-0)£(X)讪 XJ + %(

7、XV(X X,O 心 1,，加£(X)U巧(x") +巧(xj (X-X“)= O j=l,/.13六、Matlab求解非线性规划问题标准型为：min F (X)s.t. AX<bAeq- X beqG(X)<0Ceq (X) =0VLB<X<VUB其中X为维变元向量，G(X)与Ceq (X)均为非线性函数组成 的向量。#MATLAB求解上述问题，基本步骤分三步1.首先建立M文件fun.m,用来定义目标函数F (X): func七ion f=fun(X);f=F(X)；2 若约束条件中有非线性约束:G(X) ()或 Ceq(X) =0,则建立M文件n

8、onIcon.m定义函数 GQQ 与Ceq(X):func七ion GzCeq=nonlcon(X)G=.3.建立主程序.求解非线性规划的函数是f mi neon,命令的基本 格式如下：(1) x=fmincon(, XO , A,b)(2) x=fmincon( xfunf ,X0 ,A,b , Aeq, beq)(3) x=fmincon( xfunz ,XO,Azb, Aeq,beqzVLB,VUB)(4) x=fmincon ( xfunr ,XO ,A,b,Ae*be* VLB, VUB,9 nonlconz )(6) x, fval = fmincon (.)(7) x, fval

9、, ex it f lag= fmincon (.)(8) xz fval z ex it f 1 ag f o trtpLrt= fmincon ()fmincon函数可能会给出局部最优解，这与初值X0的选取有关.i.min f = _兀_ 2x2s.t.写成标准形式：2xx3x2 - 6兀1+么2 - 5兀2 二。min f _Xj _ 2%2 1兀H2西 + 3勺6、"1 +4勺一5 >2先建立M-文件 fun3m: function f=fun3(x);f=-x(l) -2*x(2) + (1/2) *x(l) 24- (1/2) *x(2)八23.再建立主程序丫ouh

10、2m：xO=l;l；A=2 3 ;1 4; b=6;5；Aeq=;beq=；VLB=0;0; VUB=;xr fval =fmineon (1 fun3 1 zx0 ,Azb ,Aeq,beqVLBVUB)4.运算结果为：x = 0. 76471. 0588fval= -2. 0294MATLAB(vouh2)f(x) = eA| (4x： + 4 兀宀 + 2x9 +1)Xj+x2<0s.t. 1.5+x1x2-xi -x2 <0X兀210 <01-先建立M文件fun4e m定义目标函数:func七ion f=fun4(x); f=exp(x(1)* (4*x(l) A2+

11、2*x(2) A2+4*x(l) *x(2) +2*x(2) +1);2.再建立M文件mycon. m定义非线性约束：funuti on g,ceq=mycon(x)g=x(1)+x(2); 1 5+x (1) *x (2) -x (1) -x (2)；-x(l)*x(2)-10；ceq= ；193主程序youh 3m为:x0=-l;l；A= ;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmineon('fun41,x0,A,b,Aeq,beq,vlb,MATLAB(vouh3)4-运算结果为:1. 2250x = -1. 2250 fval = 1. 8951例min/(X) =2X s.t. g (X ) = 25 %2 0g2(X)= 7-X： 4-2 >00< x <5, 0<x2 <101.先建立“文件fun. m定义目标函数： function f=fun(x); f=-2*x(1)-x(2);2.再建立M文件myuon2m定义非线性约束： funct