二次规划问题MATLAB求解

二次规划问题MATLAB求解

标准的二次规划问题形式要求目标函数是关于优化变量的二次函数，而约束条件只包含线性等式不等式约束和优化变量自身的上下限约束。对于二次规划问题，如果将目标函数看着非线性函数，那么二次规划问题则可以使用fmincon函数来进行求解。在Matlab优化工具箱中，提供了quadprog函数，求解具有标准二次规划问题。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,fval] = quadprog(...) 
[x,fval,exitflag] = quadprog(...) 
[x,fval,exitflag,output] = quadprog(...) 
[x,fval,exitflag,output,lambda] = quadprog(...)

在quadprog函数输入变量中，H和f分别为二次项系数矩阵和一次项系数向量。在对二次规划问题求解时，首先需要将目标函数转化为二次规划问题标准形式，得到系数矩阵H和系数向量f。
【演示实例】求解二次规划问题

在Matlab命令窗口中输入以下程序段：

H=[2 -1;-1 2];  %标准变换后的H矩阵
f=[-10;4];   %标准变换后的f向量
lb=zeros(2,1);  %下限约束
A=[-1 -1];  %线性不等式系数矩阵
b=-8;   %线性不等式右侧常数向量
[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[ ],[ ],lb)  %二次规划求解

返回结果如下：

x =
    6.3333
    1.6667
fval =
  -24.3333
exitflag =
     1

退出标志exitflag表明函数收敛与极值点。同样，将目标函数看着是非线性函数时，可以使用fmincon函数对二次规划问题进行求解，程序代码如下：

A=[-1 -1];
b=[-8];
lb=[0 0];
x0=[0;0];
fun=@(x)(x(1)^2-10*x(1)-x(1)*x(2)+x(2)^2-4*x(2));  %@函数句柄
options=optimset('Display','iter','MaxFunEvals',1e5);
[x,fval,exitflag,output,lambda,grad,hessian]=fmincon(fun,x0,A,b,[],[],lb,[],[],options)

返回结果，显示的迭代过程如下：

                                 max     Line search  Directional      First-order 
 Iter  F-count        f(x)         constraint   steplength   derivative   optimality Procedure 
    0      3            0          8                                         Infeasible 
    1      6          -40         -4            1        36            6      start point
    2     10     -50.7721         -6.9          0.5        0.864        1.57   
    3     13     -51.9816       -5.743            1        0.337        0.204   
    4     16          -52           -6            1    4.26e-008    4.45e-006

经过4代迭代后，方向导数为4.26e-8，因此搜索方向导数过小导致搜索过程结束，退出标志exitflag=5。输出结果如下：

x =
    8.0000
    6.0000
fval =
  -52.0000
exitflag =
     5

由于fmincon函数退出标志exitflag=5，因此无法判断此求解结果是否为全局极值点，但是比较fmincon函数和quadprog函数二者求解结果可以看出，fmincon函数的求解结果比quadprog函数要好。


More details could be found in my published book:
MATLAB编程基础与典型应用
北京：人民邮电出版社,2008
ISBN:978-7-115-17932-6/TP
Pls contact me with Email:lhd06@mails.tsinghua.edu.cn