求解二次规划问题的拉格朗日及有效集方法

求解二次规划问题的拉格朗日及有效集方法

——最优化方法课程实验报告

学院：数学与统计学院

班级：硕2041班

姓名：王彭

学号：3112054028

指导教师：阮小娥

同组人：钱东东

求解二次规划问题的拉格朗日及有效集方法

求解二次规划问题的拉格朗日

及有效集方法

摘要

二次规划师非线性优化中的一种特殊情形，它的目标函数是二次实函数，约束函数都是线性函数。由于二次规划比较简单，便于求解（仅次于线性规划），并且一些非线性优化问题可以转化为求解一些列的二次规划问题，因此二次规划的求解方法较早引起人们的重视，称为求解非线性优化的一个重要途径。二次规划的算法较多，本文仅介绍求解等式约束凸二尺规划的拉格朗日方法以及求解一般约束凸二次规划的有效集方法。

关键字：二次规划，拉格朗日方法，有效集方法。

- 1 -

《最优化方法》课程实验报告

- 2 - 【目录】

摘要........................................................................................................................... - 1 -1 等式约束凸二次规划的解法............................................................................... - 3 -

1.1 问题描述.................................................................................................... - 3 -

1.2 拉格朗日方法求解等式约束二次规划问题............................................ - 3 -

1.2.1 拉格朗日方法的推导...................................................................... - 3 -

1.2.2 拉格朗日方法的应用...................................................................... - 4 -

2 一般凸二次规划问题的解法............................................................................... - 5 -

2.1 问题描述.................................................................................................... - 5 -

2.2 有效集法求解一般凸二次规划问题........................................................ - 6 -

2.2.1 有效集方法的理论推导.................................................................. - 6 -

2.2.2 有效集方法的算法步骤.................................................................. - 9 -

2.2.3 有效集方法的应用........................................................................ - 10 -

3 总结与体会......................................................................................................... - 11 -

4 附录..................................................................................................................... - 11 -

4.1 拉格朗日方法的matlab程序................................................................. - 11 -

4.2 有效集方法的Matlab程序 .................................................................... - 11 -

求解二次规划问题的拉格朗日及有效集方法

- 3 -

1 等式约束凸二次规划的解法

1.1 问题描述

我们考虑如下的二次规划问题

??

???

=+b Ax t s x c Hx x T T ..,

2

1min (1.1) 其中n n R H ?∈对称正定，n m R A ?∈行满秩，n R x c,∈，m R b ∈。

1.2 拉格朗日方法求解等式约束二次规划问题

1.2.1 拉格朗日方法的推导

首先写出拉格朗日函数： )(21

)L(x,b Ax x c Hx x T T T --+=λλ，(1.2)

令

0),(,

0),(=?=?λλλx L x L x ，

得到方程组

.

,A -Hx T b Ax c -=--=λ

将上述方程组写成分块矩阵形式：

.0H ??????--=????????????--b c x A

A T λ(1.3)

我们称伤处方程组的系数矩阵

??

????0A -A -H T 为拉格朗日矩阵。

下面的定理给出了线性方程组(1.1)有唯一解的充分条件。

定理1 设n m R H ?∈对称正定，n m R A ?∈行满秩。若在问题(1.1)的解*x 处满足二阶充分条件，即

,0,0,,0d T =≠∈?>Ad d R d Hd n

则线性方程组(1.4)的系数矩阵非奇异，即方程组（1.4）有唯一解。其中，方程组(1.4)为（1.1）对应的齐次方程组：

《最优化方法》课程实验报告

- 4 - 00A -H T =????????????-v d A

（1.4）.

下面，我们来推导方程(1.3)的求解公式。根据定理1，拉格朗日矩阵必然

是非奇异的，故可设其逆为

??????--=??????C B B G T 0A

-A -H T .

由恒等式

??

?

?

??=??????--????????m n m m n n

T I I C B B G 000A

-A -H T 可得

.

,

0,0,A HG T m T

n m m n T T n I AB AG C A HB I B ==-=--=+??

于是由上述四个等式得到矩阵C B,G,的表达式

)

7.1(.

)()6.1(,)()5.1(,)(H G 111111111-1----------==-=T T T T A AH C AH A AH B AH A AH A H 因此，由(1.3)可得解得表达式

)8.1(,

x ???

???-+-=??????--??????--=??????Cb Bc b B Gc b c C B

B G T T λ

其中，C B,G,分别由(1.5),(1.6),(1.7)给出。

下面给出x 和λ的另一种等价表达式。设k x 是问题(1.1)的任一可行点，即

k x 满足b =k Ax 。而在此点处目标函数的梯度为c Hx x f k k +=?=)(g k ，利用k x 和k g ，可将(1.8)改写为

)9.1(.x ?

?

?

???-=??????k k k Bg Gg x λ

1.2.2 拉格朗日方法的应用

（1）拉格朗日方法的Matlab 程序见附录。 （2）利用拉格朗日方法求解下列问题：

求解二次规划问题的拉格朗日及有效集方法

- 5 -

.

22,

4..,

22min 3213213212

32221=+-=+++-++x x x x x x t s x x x x x x

解 容易写出

.24,112111,100,200042022H ??????=??????-=??

??

?

?????=??????????--=b A c 利用Matlab 程序求解该问题可以结果如下：

2 一般凸二次规划问题的解法

2.1 问题描述

考虑一般二次规划

)1.2(,}

,,1{,0},,,1{,0..,21min ???

????+=∈≥-=∈=-+m l I i b x a l E i b x a t s x c Hx x i

T i i T

i T

T

其中H 是n 阶对称阵。记I}i 0,b -x a |{i )I(x i *T i *∈==，下面的定理给出了问题(2.1)的一个最优性充要条件。

定理2 *x 是二次规划问题(2.1)的局部极小点当且仅当

《最优化方法》课程实验报告

- 6 - （1）存在m R ∈*λ，使得

.)

(\,0;,0,,0,,0,

0****

*

*

*

*??

?????∈=∈≥∈≥-∈=-=--+∑∑∈∈x I I i I i I i b x a E i b x a a a c Hx i i

i T i i T i I

i i i E i i i λλλλ (2)记

0}.)I(x i 0,a d );I(x i 0,a d E;i 0,a d |{0}\R {d S **i T *i T i T n >∈=∈≥∈=∈=i λ且 则对于任意的S d ∈，均有0d T ≥Hd .

容易发现，问题(2.1)是凸二次规划的充要条件是H 半正定。此时，定理2

的第二部分自然满足。注意到凸优化问题的局部极小点也是全局极小点的性质，我们有下面的定理：

定理3 *x 是凸二次规划的全局极小点的充要条件是*x 满足KT 条件，即存在m R ∈*λ，使得

??

?????∈=∈≥∈≥-∈=-=--+∑∑∈∈).

(\,0;,0,,0,,0,

0Hx ****

*

*

*

*x I I i I i I i b x a E i b x a a a c i i

i T i i T i E i I

i i i i i λλλλ 2.2 有效集法求解一般凸二次规划问题

2.2.1 有效集方法的理论推导

首先引入下面的定理，它是有效集方法理论基础。

定理 4 设*

x 是一般凸二次规划问题的全局极小点，且在*

x 处的有效集为

)()(**x I E x S =，则*x 也是下列等式约束凸二次规划

)2.2().

(,0..,2

1min

*

?????

∈=-+x S i b x a t s x c Hx x i T i T T

的全局极小点。

从上述定理可以发现，有效集方法的最大难点是事先一般不知道有效集

)(*x S ，因此只有想办法构造一个集合序列去逼近它，即从初始点0x 出发，计算

求解二次规划问题的拉格朗日及有效集方法

- 7 -

有效集)(0x S ，解对应的等式约束子问题。重复这一做法，得到有效集序列

,,1,0)},({ =k x S k 使之)()(*x S x S k →，以获得原问题的最优解。

基于上述定理，我们分4步来介绍有效集方法的算法原理和实施步骤。 第一步，形成子问题并求出搜索方向k d .设k x 是问题(2.1)的一个可行点，据此确定相应的有效集)(k k x I E S =，其中}.,0|{)(I i b x a i x I i k T i k ∈=-=求解相应的子问题

)3.2(.

,0..,2

1min

?????

∈=-+k i T

i T T S i b x a t s x c Hx x

上述问题等价于

)

4.2(.,0..,2

1)(min ??

???∈=+=k T

i T

k

T k S i d a t s d g Hd d d q

其中.,c Gx g d x x k k k +=+=设求出问题(2.4)的全局极小点为k k d λ,是对应的拉格朗日乘子。

第二步，进行线性搜索确定步长因子k α.假设0≠k d ，分两种情形讨论。 (1) 若k k d x +是问题(2.1)的可行点，即

.,0)(,0)(I i b d x a E i b d x a i k k T i i k k T i ∈≥-+∈=-+及

则令.,11k k k k d x x +==+α

(2) 若k k d x +不是问题(2.1)的可行点，则通过线性搜索求出下降最好的可行点。注意到目标函数是凸二次函数，那么这一点应该在可行域的边界上达到。因此只要求出满足可行条件的最大步长k α即可。

当k S i ∈时，对于任意的0≥k α，都有0=k T i d a 和i k T i k k k T i b x a d x a ==+)(α，此时，0≥k α不受限制。当k S i ?时，即第i 个约束是严格的不等式约束，此时要求k α满足i k k k T i b d x a ≥+)(α，即

.,k k T i i k T i k S i x a b d a ∈-≥α

注意到上式右端非正，故当0≥k T i d a 时，上式恒成立。而当0

《最优化方法》课程实验报告

- 8 -

可解得

.k

T

i k

T i i k d a x a b -≤α 故有

.0|min ?

??

???<-==k T i k T i k T i i k k d a d a x a b αα

合并第(1)(2)可得

)5.2(}

,1min{k k αα=.

第三步，修正k S .当1=k α时，有效集不变，即k k S S =+:1.而当1

k

T

i k

T i i k

k d a x a b k

k k -=αα，

故k k

i k k k T i b d x a =+)(α，因此在!+k x 处增加了一个有效约束，即}{:1k k k i S S =+.

第四步，考虑0=k d 的情形。此时k x 是问题(2.3)的全局极小点。若这是对应的不等式约束的拉格朗日乘子均为非负，则k x 也是问题(2.1)的全局极小点，迭代终止。否则，如果对应的不等式约束的拉格朗日乘子有负的分量，那么需要重新寻找一个下降可行方向。

设)(,0k k j x I j k ∈<λ，现在要求一个下降可行方向k d ，满足0

k d g 且

)(,0;,0k k T

j k T j x I j d a E j d a ∈?≥∈?=，为简便计算，按下述方式选取k d ：

,

,,)(,

)(k k j k k T

j

j k k T j j j S j b d x a b d x a k k ≠∈?=+>+

即

)6.2(,

,,0,0?????≠∈?=>k k k T j k T j j j S j d a d a k

另一方面，注意到k x 是子问题(2.3)的全局极小点，故有

,0∑∈=-+k

S i i k i k a c Hx λ

即

,k k k A g λ=

求解二次规划问题的拉格朗日及有效集方法

- 9 -

其中

.)(,)(k k S i k i k S i i k a A ∈∈==λλ

从而，.k T

k T k k T k d A d g λ=由(2.6)知

,)()(k k k

j k T j S j j k T

j

k T

k e d a e d a

d A ==

∑∈

于是有

.0)()(<==k T

j k j j k T j T k k T k d a e d a d g k k k λλ

上式表明，由(2.6)确定的k d 是一个下降可行方向。因此，令}{\'k k k j S S =，则修正后的子问题

??

???∈=+=',0..,2

1)(min k T i T

k

T k S i d a t s d g Hd d d q 的全局极小点必然是原问题的一个下降可行方向。

2.2.2 有效集方法的算法步骤

经过上面的分析和推导，我们现在可写出有效集方法的算法步骤： （1）选取初值。给定初始可行点n R x ∈0，令0:=k .

（2）解子问题。确定相应的有效集)(k k x I E S =.求解子问题

??

???∈=+=,,0..,2

1)(min k T i T

k

T k S i d a t s d g Hd d d q 得极小点k d 和拉格朗日乘子向量k λ.若0≠k d 转步骤（4）；否则，转步骤（3）。

（3）检验终止准则。计算拉格朗日乘子

,k k k g B =λ

其中

.)(,

)(,

111k S i i k k T k k k k k a A H A A H A B c Hx g ∈---==+=

令

}.){(min )()

(i k x I i t k k λλ∈=

若0)(≥t k λ，则k x 是全局极小点，停算。否则，若0)(

《最优化方法》课程实验报告

- 10 -

（4）确定步长k α.令},1min{k k αα=，其中

.0|min ?

??

???<-=∈k T i k T i k T i i S i k d a d a x a b k

α

令.:1k k k k d x x α+=+

（5）若1=k α，则令k k S S =+:1；否则，若1

.k

T j k

T j j k d a x a b k k k -=

α

（6）令1:+=k k ，转步骤(1)。

2.2.3 有效集方法的应用

（1）有效集法的Matlab 程序见附录。

（2）用有效集方法求解下列二次规划问题：

??

?

?

?≥≥-≥----+-=.0,0623..,102)(min 2121212

22121x x x x t s x x x x x x x f 解 首先确定有关数据：

.006,100123[],[],,101,4112??

??

?

?????-=??????????--===??????--=??????--=bi Ai be Ae c H 利用Matlab 计算可得结果如下：

求解二次规划问题的拉格朗日及有效集方法

3 总结与体会

通过本次实验，笔者对求解等式约束凸二次规划问题的拉格朗日方法及一般约束条件下凸二次规划问题的有效集方法有了较深的认识和了解。

感谢阮老师的悉心教诲和指导，使得笔者对最优化课程中的理论推导、算法步骤及编程都比较熟悉，对以后的科研工作有很好的指导和借鉴意义。

4 附录

4.1 拉格朗日方法的matlab程序

(1) 拉格朗日算法函数

%本程序用拉格朗日方法求解灯饰约束条件的二次规划问题。

function [x,lam,fval]=qlag(H,A,b,c)

%功能：用拉格朗日方法求解等式约束二次规划：

% min f(x)=0.5*x'Hx+c'x，s.t. Ax=b

%输入：H,c分别是目标函数的矩阵和向量，A,b分别是约束条件中的矩阵和向量%输出：(x,lam)是KT点，fval是最优值

IH=inv(H);

AHA=A*IH*A';

IAHA=inv(AHA);

AIH=A*IH;

G=IH-AIH'*IAHA*AIH;

B=IAHA*AIH;

C=-IAHA;

x=B'*b-G*c;

lam=B*c-C*b;

fval=0.5*x'*H*x+c'*x;

(2)拉格朗日算法求解等式约束凸二次规划问题主程序：

H=[2 -2 0;-2 4 0;0 0 2];

c=[0 0 1]';

A=[1 1 1;2 -1 1];

b=[4 2]';

[x,lam,fval]=qlag(H,A,b,c)

4.2 有效集方法的Matlab程序

（1）有效集方法函数

- 11 -

《最优化方法》课程实验报告

- 12 - %本程序主要适用于求解一般约束条件下的凸二次规划问题function [x,lamk,exitflag,output]=qpact(H,c,Ae,be,Ai,bi,x0)

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

%min f(x)=0.5*x'*H*x+c'*x,

% s.t. 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

end

gk=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)));

end

if y>=0

exitflag=0;

求解二次规划问题的拉格朗日及有效集方法

else

exitflag=1;

for i=1:ni

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

index(i)=0;

break;

end

end

end

k=k+1;

else

exitflag=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 tm1

tm=tm1;

ti=i;

end

end

end

alpha=min(alpha,tm);

x=x+alpha*dk;

%修正有效集

if tm<1

index(ti)=1;

end

end

if exitflag==0

break;

end

k=k+1;

end

output.fval=0.5*x'*H*x+c'*x;

output.iter=k;

（2）求解子问题函数

%求解子问题

function [x,lambda]=qsubp(H,c,Ae,be)

ginvH=pinv(H);

- 13 -

《最优化方法》课程实验报告

- 14 - [m,n]=size(Ae);

if m>0

rb=Ae*ginvH*c+be;

lambda=pinv(Ae*ginvH*Ae')*rb;

x=ginvH*(Ae'*lambda-c);

else

x=-ginvH*c;

lambda=0;

end

（3）有效集方法求解一般约束凸二次规划问题主程序

clc;

clear;

H=[2 -1;-1 4];

c=[-1 -10]';

Ae=[];be=[];

Ai=[-3 -2;1 0;0 1];

bi=[-6 0 0]';

x0=[0 0]';

[x,lambda,exitflag,output]=qpact(H,c,Ae,be,Ai,bi,x0)

二次规划问题

序列二次规划法 求解一般线性优化问题: 12min (x) h (x)0,i E {1,...,m }s.t.(x)0,i {1,...,m } i i f g I =∈=?? ≥∈=? (1.1) 基本思想：在每次迭代中通过求解一个二次规划子问题来确定一个下降方向，通过减少价值函数来获取当前迭代点的移动步长，重复这些步骤直到得到原问题的解。 1.1等式约束优化问题的Lagrange-Newton 法 考虑等式约束优化问题 min (x) s.t.h (x)0,E {1,...,m} j f j =∈= (1.2) 其中:,n f R R →:()n i h R R i E →∈都为二阶连续可微的实函数. 记1()((),...,())T m h x h x h x =. 则(1.3)的Lagrange 函数为： 1(,)()*()()*()m T i i i L x u f x u h x f x u h x ==-=-∑ （1.3） 其中12(,,...,)T m u u u u =为拉格朗日乘子向量。 约束函数()h x 的Jacobi 矩阵为：1()()((),...,())T T m A x h x h x h x =?=??. 对（1.3）求导数，可以得到下列方程组： (,)()A()*(,)0(,)()T x u L x u f x x u L x u L x u h x ??? ???-?===?????-???? （1.4） 现在考虑用牛顿法求解非线性方程（1.4）. (,)L x u ?的Jacobi 矩阵为： (,)()(,)() 0T W x u A x N x u A x ?? -= ?-??

求解二次规划问题

实验2 求解二次规划问题 LINDO 可以求解二次规划（QP ）问题。例如： ?? ? ??<=+>++-+=7.011.19.02.1..4.03min 22y y x y x t s y xy y x f 由LAGRANGE 乘子法，得 ()()()7.011.19.02.14.0322-+-++-+-+-+y C y x B y x A y xy y x ， 分别对x 、y 求偏导，得到两个约束条件： 4 .09.020 2.16->++-->+--C B A x y B A y x 在LINDO 中输入下列命令： MIN X+Y+A+B+C ST 6X-Y-1.2A+B>0 2Y-X-0.9A+B+C>-0.4 1.2X+0.9Y>1.1 X+Y=1 Y<0.7 END QCP 4 注释：MIN X+Y+A+B+C 一句只代表变量的出场顺序； QCP 4 一句代表前4行不是原问题真正的约束，原问题真正的约束从第5行开始。 LINDO 运行后输出以下结果：STATUS OPTIMAL QP OPTIMUM FOUND AT STEP 7 OBJECTIVE FUNCTION V ALUE 1) 1.355556 V ARIABLE V ALUE REDUCED COST X 0.666667 0.000000 Y 0.333333 0.000000

A 10.888889 0.000000 B 9.400000 0.000000 C 0.000000 0.366667 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -0.666667 3) 0.000000 -0.333333 4) 0.000000 -10.888889 5) 0.000000 9.400000 6) 0.366667 0.000000 NO. ITERATIONS= 7 这个结果说明：LINDO求解此二次规划问题（QP）共用7步迭代得到最优解fmin = 1.355556，X = 0.666667，Y = 0.333333。第5个松弛变量取值0.366667，其它松弛变量都取0值，即，这个最优解使得前4个约束条件都取等号；其对偶问题的最优解（影子价格）DUAL PRICES为Y1 = -0.666667，Y2 = -0.333333，Y3 = -10.888889，Y4 = 9.4，Y5 = 0。 农户生产的优化模型 本文内容取自生产实践，豫东一个普通农户，该农户所在地区的农业生产条件、气候状况属于中等。下列各变量的假设均建立在农村一般农业生产条件、气候状况之上。 假设（面积单位：亩）： X1 = 用于完成上缴国家任务的小麦一年总种植面积 X2 = 用于生产、生活的小麦一年总种植面积 X3 =用于生产、生活的油菜一年总种植面积 X4 =用于生产、生活的红薯一年总种植面积 X5 =用于完成上缴国家任务的棉花一年总种植面积 X6 =用于生产、生活的棉花一年总种植面积 X7 =用于完成上缴国家任务的玉米一年总种植面积 X8 =用于生产、生活的玉米一年总种植面积 X9 =用于生产、生活的芝麻一年总种植面积 X10 =用于生产、生活的花生一年总种植面积 X11 =用于生产、生活的大豆一年总种植面积 X12 =用于生产、生活的西瓜一年总种植面积 X13 =用于生产、生活的番茄一年总种植面积 X14 =用于生产、生活的白菜一年总种植面积 X15 =用于生产、生活的辣椒一年总种植面积 X16 =用于生产、生活的茄子一年总种植面积

二次规划问题

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。 [x,fval,exitflag] = quadprog(...)返回exitflag参数，描述计算的退出条件。 [x,fval,exitflag,output] = quadprog(...)返回包含优化信息的结构输出output。 [x,fval,exitflag,output,lambda] = quadprog(...)返回解x处包含拉格朗日乘子的 lambda参数。 变量： 各变量的意义同前。

求解二次规划问题的拉格朗日及有效集方法

求解二次规划问题的拉格朗日及有效集方法 ——最优化方法课程实验报告 学院：数学与统计学院 班级：硕2041班 姓名：王彭 学号：3112054028 指导教师：阮小娥 同组人：钱东东

求解二次规划问题的拉格朗日及有效集方法 求解二次规划问题的拉格朗日 及有效集方法 摘要 二次规划师非线性优化中的一种特殊情形，它的目标函数是二次实函数，约束函数都是线性函数。由于二次规划比较简单，便于求解（仅次于线性规划），并且一些非线性优化问题可以转化为求解一些列的二次规划问题，因此二次规划的求解方法较早引起人们的重视，称为求解非线性优化的一个重要途径。二次规划的算法较多，本文仅介绍求解等式约束凸二尺规划的拉格朗日方法以及求解一般约束凸二次规划的有效集方法。 关键字：二次规划，拉格朗日方法，有效集方法。 - 1 -

《最优化方法》课程实验报告 - 2 - 【目录】 摘要........................................................................................................................... - 1 -1 等式约束凸二次规划的解法............................................................................... - 3 - 1.1 问题描述.................................................................................................... - 3 - 1.2 拉格朗日方法求解等式约束二次规划问题............................................ - 3 - 1.2.1 拉格朗日方法的推导...................................................................... - 3 - 1.2.2 拉格朗日方法的应用...................................................................... - 4 - 2 一般凸二次规划问题的解法............................................................................... - 5 - 2.1 问题描述.................................................................................................... - 5 - 2.2 有效集法求解一般凸二次规划问题........................................................ - 6 - 2.2.1 有效集方法的理论推导.................................................................. - 6 - 2.2.2 有效集方法的算法步骤.................................................................. - 9 - 2.2.3 有效集方法的应用........................................................................ - 10 - 3 总结与体会......................................................................................................... - 11 - 4 附录..................................................................................................................... - 11 - 4.1 拉格朗日方法的matlab程序................................................................. - 11 - 4.2 有效集方法的Matlab程序 .................................................................... - 11 -

二次规划起作用集方法

《非线性规划》课程设计 题目：二次规划起作用集方法院系：数理学院应用数学系 专业：数学与应用数学 姓名学号：119084112 数112 指导教师： 日期：2014年6月19日

摘要 二次规划（QP）是指目标函数为决策变量x的二次函数，而约束函数是线性函数的非线性规划.二次规划规划问题是最简单的一类非线性约束优化问题，并且某些非线性规划可以转化为求解一系列二次规划问题，因此二次规划的求解方法也是求解非线性规划的基础之一. 关键词：二次规划；起作用集；乘子向量 Abstract Quadratic programming (QP) refers to the objective function for the quadratic function of the decision variables x, and the constraint function is a linear function of nonlinear programming, quadratic programming problem is the simplest nonlinear constraint optimization problems, and some nonlinear programming can be transformed into solving a series of quadratic programming problem, so the solving methods of quadratic programming is also one of the basis of solving nonlinear programming. Keywords: Quadratic programming; Work set; Multiplier vector

二次规划解法

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 X s i =∈=∑可以等价转换为下面的三个约束条件： i j ij s X ≤∑=151 i j ij Mn X ≤∑=151 i j ij n X *500151≥∑= 其中M 为一个很大数。 这样就可以得到下面的lingo 程序： sets : s/1..7/:sx; a/1..15/:z,y,n,t; links(s,a):c,x; endsets

二次规划实验举例

最优化算法实验指导书 2.二次规划求解 例1 求解下面二次规划问题 21212221x 6x 2x x x x 2 1)x (f min ---+= sub.to 2x x 21≤+ 2x 2x 21≤+- 3x x 221≤+ 21x 0,x 0≤≤ 解：x f x H x 2 1)x (f '+'= 则??????--=2111H ，?? ????--=62f ，??????=21x x x 在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) Warning: Large-scale method does not currently solve this problem formulation, switching to medium-scale method. > In C:\MATLAB6p5\toolbox\optim\quadprog.m at line 213 Optimization terminated successfully. x = 0.6667 1.3333 fval = -8.2222 exitflag = 1

output = iterations: 3 algorithm: 'medium-scale: active-set' firstorderopt: [] cgiterations: [] lambda = lower: [2x1 double] upper: [2x1 double] eqlin: [0x1 double] ineqlin: [3x1 double] 例 1123 2212123min 246y x x x x x =+--- ..s t 1232131232 3 4 ,,0x x x x x x x x x +≤+≤+≤≥ （1）标准形式： 由 2212123246y x x x x x =+--- 22121231(22)2462 x x x x x =+--- 知 200020000H ?? ?= ? ??? 为半正定矩阵，约束不必改动。 （2）在编辑窗口建立一个存放各种信息的M 文件， 在MA TLAB 中实现如下： >> H = [2 0 0;0 2 0;0 0 0]; >> f = [-2 -4 -6]; >> A = [1 1 0; 0 1 1; 1 0 1]; >> b = [2; 3; 4]; >> C =[]; >> d=[]; >> xm=[0; 0; 0];

改进求解凸二次规划中的Lemke算法.

改进求解凸二次规划中的Lemke 算法 张璐 辽宁工程技术大学理学院,辽宁阜新(123000 E-mail:zhanglu85517@https://www.sodocs.net/doc/774182198.html, 摘要:通过对经典的Lemke 互补转轴算法求解凸二次规划问题的分析,找到了Lemke 算法的局限性。本文在Lemke 算法求解线性互补问题的基础上修正了经典的Lemke 算法的迭代过程,提出了一种改进的Lemke 算法,通过算例证明了算法能有效克服解的局限性,减少了凸二次规划问题的迭代过程,提高了算法的效率。 关键词:非线性规划;凸二次规划;线性互补问题;Lemke 算法 1.引言 二次规划问题是最简单而又最基本的非线性规划问题,其目标函数是二次函数,约束是线性等式或不等式。对于二次规划问题,可行域是凸集,所以当目标函数是凸函数时,任何K-T 点都是二次规划问题的极小点。研究二次规划问题的算法不仅仅是为了解决二次规划问题本身,同时也是为了更好的求解其他非线性规划问题。因为大多数最优化方法是从二次函数模型导出的,这种类型的方法在实际中常常是有效的,其主要是因为一般函数的极小点附近常可用二次函数很好地进行近似。由于二次规划是特殊的非线性规划,因此求解非线性规划问题的方法均可用于二次规划问题的求解。同时,由于二次规划本身的特殊性,对它的求解可以采用一些更有效的方法[1]。因此,不论从数学角度还是应用角度来看,二次规划问题的研究都具有重要意义。到目前为止,已经出现了很多求解二次规划问题的算法,并且现在仍有很多学者在从事这方面的研究工作。所以,需要我们对现存的有效的求解二次规划问题的算法进行改进,得到新的求解算法来克服某些算法的缺点,并且给出具体的实例显示该算法的有效性。本文主要研究凸二次规划的求解算法,以及线性互补问题的性质等相关问题。对Lemke 算法进行进一步研究,对它可能出现退化的原因和迭代过程以及局限性进一步分析。本文通过分析经典的Lemke 互补转轴算法求解含有等式

求解二次规划问题的拉格朗日及有效集方法样本

求解二次规划问题的拉格朗 日及有效集方法——最优化方法课程实验报告 学院: 数学与统计学院 班级: 硕2041班 姓名: 王彭 学号: 指导教师: 阮小娥 同组人: 钱东东

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 求解二次规划问题的拉格朗日 及有效集方法 摘要 二次规划师非线性优化中的一种特殊情形, 它的目标函数是二次实函数, 约束函数都是线性函数。由于二次规划比较简单, 便于求解( 仅次于线性规划) , 而且一些非线性优化问题能够转化为求解一些列的二次规划问题, 因此二次规划的求解方法较早引起人们的重视, 称为求解非线性优化的一个重要途径。二次规划的算法较多, 本文仅介绍求解等式约束凸二尺规划的拉格朗日方法以及求解一般约束凸二次规划的有效集方法。 关键字: 二次规划, 拉格朗日方法, 有效集方法。

【目录】 摘要................................................ 错误!未定义书签。 1 等式约束凸二次规划的解法.......................... 错误!未定义书签。 1.1 问题描述.................................... 错误!未定义书签。 1.2 拉格朗日方法求解等式约束二次规划问题........ 错误!未定义书签。 1.2.1 拉格朗日方法的推导.................... 错误!未定义书签。 1.2.2 拉格朗日方法的应用.................... 错误!未定义书签。 2 一般凸二次规划问题的解法.......................... 错误!未定义书签。 2.1 问题描述.................................... 错误!未定义书签。 2.2 有效集法求解一般凸二次规划问题.............. 错误!未定义书签。 2.2.1 有效集方法的理论推导.................. 错误!未定义书签。 2.2.2 有效集方法的算法步骤.................. 错误!未定义书签。 2.2.3 有效集方法的应用...................... 错误!未定义书签。 3 总结与体会........................................ 错误!未定义书签。 4 附录.............................................. 错误!未定义书签。 4.1 拉格朗日方法的matlab程序................... 错误!未定义书签。 4.2 有效集方法的Matlab程序..................... 错误!未定义书签。

二次型及其矩阵表示

第六章 二次型 第一讲 二次型及其矩阵表示、标准形 教 学 目 的：通过本节的学习，使学生了解并掌握二次型的基本概念及其矩 阵表示方法. 教学重点与难点：二次型的矩阵表示 教学计划时数：2课时 教 学 过 程： 一、二次型的概念 定义1：含有n 个变量n x x x ,,,21 的二次齐次函数 22 2 121112221212112323221,1(,, ,)22222n nn n n n n n n n n n f x x x a x a x a x a x x a x x a x x a x x a x x --=+++++ ++++++ （1） 称为二次型. 附：1、当ij a 为复数时,f 称为复二次型；当ij a 为实数时,f 称为实二次型； 2、ij a 可以等于0，即（1）式中的各项都存在. 例1 ()2 2 2 12312313,,2454f x x x x x x x x =++-；()123121323,,f x x x x x x x x x =++ 都为实二次型； 二、二次线性与对称矩阵 在（1）式中,取ij ji a a =,则,2i j ji j i ij j i ij x x a x x a x x a +=令12(,,,)T n x x x x =，则（1） 式可化为 11121121 222212121 2 (,,,)(,, ,).n n T n n n n nn n a a a x a a a x f x x x x x x x Ax a a a x ???? ??? ??? == ??? ??????? 称12(,, ,)T n f x x x x Ax =为二次型的矩阵形式，记为()T f x x Ax =，其中实对称矩阵A 称 为该二次型的矩阵.二次型f 称为实对称矩阵A 的二次型.实对称矩阵A 的秩称为二次型f 的秩，即()()R A R f =.

《线性代数》教学大纲-哈尔滨理工大学

《线性代数》教学大纲 Lin ear Aigebra 课程编号：070A1060 适用专业：理工管各专业学时：40 学分：3 一、内容简介 内容包括：行列式，矩阵的运算，向量的线性相关性，线性方程组的基本理论及解法，特征值与特征向量的概念与计算，矩阵的相似对角阵及用正交变换化对称矩阵为对角阵的方法，化二次型为标准形，线性空间与线性变换。 二、本课程的目的和任务 线性代数是高等学校理工科和经济学科等有关专业的一门重要基础课。它不但是其它数学课程的基础，也是各类工程及经济管理课程的基础。另外，由于计算机科学的飞速发展和广泛应用，许多实际问题可以通过离散化的数值计算得到定量的解决，于是作为处理离散问题的线性代数，成为从事科学研究和工程设计的科技人员必备的数学基础。 三、本课程与其它课程的关系 本课程的先修课是高等数学中的“空间解析几何与向量代数”部分。作为基础课，它是许多后继课，如计算方法、数理统计、运筹学以及其他专业基础课和专业课的基础。 随着对教学内容的改革，本课程可以与高等数学中的某些部分结合起来讲授，如向量代数；又可在多元函数的微分学中介绍其部分应用，如二次型的正定性。 四、本课程的基本要求 通过本课程的学习，要求学生熟练掌握行列式的计算，矩阵的初等变换，矩阵秩的定义和计算，禾U用矩阵的初等变换求解方程组及逆阵，向量组的线性相关性，禾U用正交变换化对称矩阵为对角形矩阵等有关基础知识，并具有熟练的矩阵运算能力和利用矩阵方法解决一些实际问题的能力，从而为学习后继课及进一步扩大知识面奠定必要的数学基础。具体要求如下： n阶行列式的定义 第一讲二阶与三阶行列式、全排列及其逆序数、目的：理 解n阶行列式的定义。 要求：掌握二阶、三阶行列式的计算，会求全排列的逆序数，利用定义计算简单的行列式。 第二讲对换、行列式的性质目的：理解n阶行列式的性质。

Quadprog二次规划问题

Quadprog 什么是二次规划？ 如果某非线性规划的目标函数为自变量的二次函数，约束条件全是线性函数，就称这样规划为二次规划。其数学模型为： ?? ???≤≤=≤+ub x lb beq x Aeq b Ax t s x f Hx x T T x ·..21min ， 式中，Ｈ,Ａ，和Aeq 为矩阵 f,ｂ, beq, lb, ub , 和x 为向量。 利用quadprog 函数求解二次规划问题，其调用格式为： ● x=quadprog(H,f,A,b) 这个函数的功能是：用来解最简单，最常用的模型： x f Hx x T T +2 1 Subject to Ax ≤b ● x=quadprog(H,f,A,b,Aeq,beq) 仍然求解上面的问题，但添加了等式约束条件Aeq*x=beq 。 ● x=quadprog(H,f,A,b,lb,ub,) 定义设计变量的下届Ib 和上界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,fvaI]=quadprog(H,f,A,b) 这个函数的功能是，返回解x 处的目标函数值fval=x f Hx x T T +2 1 ● [x,fvaI,exitfIag]=quadprog(H,f,A,b) 返回exitfIag 参数，描述计算的退出条件。 ● [x,fvai,exitfIag,output]=quadprog(H,f,A,b) 返回包含优化信息的结构输出output,其中包括：迭代次数，使用的算法，共轭梯度迭代的使用次数等信息。 ● [x,fvaI,exitfIag,output,Iambda]=quadprog(H,f,A,b) 返回解x 处包含拉格朗日乘子的lambda 参数。其中，LAMBDA.ineqlin 对应于线性不等式，LAMBDA.eqlin 对应于线性等式约束。

matlab5二次规划问题

二次规划的标准形式为： min (1/2)X’HX+f’X 约束条件：Ax≤b Aeqx=beq，lb≤x≤ub，其中：f、b、beq、lb、ub、x是矢量，H、 A、Aeq为矩阵。 在MATLAB中可以使用quadprog函数来求最小值。 调用格式: x=quadprog (H,f,A,b) x=quadprog (H,f,A,b,Aeq,beq) 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=quadprog (H,f,A,b,Aeq,beq,lb,ub,x0,options,P1,P2,…) [x,fval]= quadprog (…) [x,fval,exitflag]= quadprog (…) [x,fval,exitflag,output]= quadprog (…) [x,fval,exitflag,output,lambda]= quadprog (…) fval为目标函数的最优值；其中：H,f,A,b为标准形中的参数，x为目标函数的最小值；x0为初值；Aeq,beq 满足等式约束Aeq.x=beq；lb,ub满足lb lambda是Lagrange乘数，它体现有效约束的个数；output输出优化信息；exitflag为终止迭代的条件：若

exitflag>0，表示函数收敛于解x；若exitflag=0,表示超过函数估值或迭代的最大次数；exitflag<0表示函数不收敛于解x；output为优化信息：若参数output=iterations表示迭代次数， output=funccount表示函数赋值次数， output=algorithm表示所使用的算法。 例0-6 计算下面二次规划问题 minf（x）= (1/2)x1^2+x2^2- x1x2-2x1-6x2 约束条件： x1+x2≤2 -x1+x2≤2， 2x1+x2≤3； x1≤0； x2≤0 解：把二次规划问题写成标准形式：(1/2)XTHX+fTX 这里： H= 1 -1 f= -2 X= x1 -1 2 -6 x2

02 第二节 化二次型为标准型

第二节 化二次型为标准形 若二次型),,,(21n x x x f 经可逆线性变换化为只含平方项的形式 ,2 222211n n y b y b y b +++ 则称之为二次型),,,(21n x x x f 的标准形. 由上节讨论知,二次型AX X x x x f T n =),,,(21 在线性变换CY X =下,可化为 .)(Y AC C Y T T 如果AC C T 为对角矩阵 ? ????? ????? ?=n b b b B 21 则),,,(21n x x x f 就可化为标准形,2 222211n n y b y b y b +++ 其标准形中的系数恰好为对角阵B 的对角线上的元素,因此上面的问题归结为A 能否合同于一个对角矩阵. 内容分布图示 ★ 二次型的标准性 ★ 用配方法化二次型为标准形 ★ 例1 ★ 例2 ★ 例3 ★ 例4 ★ 用初等变换化二次型为标准形 ★ 例5 ★ 例6 ★ 定理3 -4 ★ 用正交变换化二次型为标准形 ★ 例7 ★ 例8 ★ 二次型与对称矩阵的规范形 ★ 例9 ★ 例10 ★ 内容小结 ★ 课堂练习 ★ 习题5-2 ★ 返回 内容要点： 一、用配方法化二次型为标准形. 定理1 任一二次型都可以通过可逆线性变换化为标准形. 拉格朗日配方法的步骤: (1) 若二次型含有i x 的平方项,则先把含有i x 的乘积项集中,然后配方,再对其余的变量进行同样过程直到所有变量都配成平方项为止, 经过可逆线性变换, 就得到标准形; (2) 若二次型中不含有平方项, 但是)(0j i a ij ≠≠,则先作可逆变换 ),,,2,1(j i k n k y x y y x y y x k k j i j j i i ≠=? ?? ??=+=-=且 化二次型为含有平方项的二次型, 然后再按(ⅰ)中方法配方. 注：配方法是一种可逆线性变换, 但平方项的系数与A 的特征值无关. 因为二次型f 与它的对称矩阵A 有一一对应的关系，由定理1即得: 定理2 对任一实对称矩阵A ，存在非奇异矩阵C ，使=B AC C T 为对角矩阵. 即任一 实对称矩阵都与一个对角矩阵合同. 二、用初等变换化二次为标准型 设有可逆线性变换为CY X =，它把二次型AX X T 化为标准型BY Y T ，则 B AC C T =. 已