二次规划的MATLAB解法：quadprog函数

声明

转载自新浪博客：漂流瓶jz的博客，版权归原作者。

综述

二次规划为非线性规划的一种，若某非线性规划的目标函数为自变量 $x$ 的二次函数，约束条件又全是线性的，就称这种规划为二次规划。

问题描述

Matlab中二次规划的数学模型可表述如下：

$$\min \frac{1}{2}x^{T}Hx + f^{T} x, \quad s.t. \begin{cases} Ax \leq B \\ A_{eq} \cdot x = B_{eq} \end{cases}$$

这里 $H$ 是实对称矩阵，$f, b$ 是列向量，$A$ 是相应维数的矩阵。

quadprog()用法

Matlab中求解二次规划的函数为quadprog，其的用法如下：

x = quadprog(H,f)
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(problem)
[x,fval] = quadprog(H,f,...)
[x,fval,exitflag] = quadprog(H,f,...)
[x,fval,exitflag,output] = quadprog(H,f,...)
[x,fval,exitflag,output,lambda] = quadprog(H,f,...)

$H, f$ 是把目标函数化成标准形式后得到的实对称矩阵和列向量。显然 $H$ 应当是原函数的海森矩阵。它的返回值是向量 $x$，$x_0$ 是 $x$ 的初始值；$A, B, A_{eq}, B_{eq}$ 定义了线性约束 $A \cdot x \leq B,\ A_{eq} \cdot x = B_{eq}$，如果没有线性约束，则 $A = [], B = [], A_{eq} = [], B_{eq} = []$；$LB$ 和 $UB$ 是变量 $x$ 的下界和上界。如果上界和下界没有约束，则 $LB = [], UB = []$。options 定义了优化参数，为简单起见，可以使用MATLAB的缺省参数设置。fval 是目标函数值。lambda 是Lagrange乘子，它体现哪一个约束有效。output 输出优化信息。

示例

问题

求解二次规划

$$\begin{cases} \min f(x) = 2x_1^2 - 4x_1 x_2 + 4x_2^2 - 6x_1 - 3x_2 \\ x_1 + x_2 \leq 3 \\ 4x_1 + x_2 \leq 9 \\ x_1, x_2 \geq 0 \end{cases}$$

求解

编写以下程序：

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))

求得 $x = \begin{bmatrix} 1.9500 \\ 1.0500 \end{bmatrix},\ \min f(x) = -11.0250$