具有多个线性约束的二次规划

打开实时脚本

此示例显示了与默认的 'interior-point-convex' 算法相比，quadprog 'active-set' 算法在存在许多线性约束的情况下的表现如何。此外，'active-set' 算法中的拉格朗日乘数在非活动约束恰好为零，这在您寻找活动约束时非常有用。

问题描述

创建一个具有 N 变量和 10*N 线性不等式约束的伪随机随机二次问题。指定 N = 150。

rng default % For reproducibility
N = 150;
rng default
A = randn([10*N,N]);
b = 10*ones(size(A,1),1);
f = sqrt(N)*rand(N,1);
H = 18*eye(N) + randn(N);
H = H + H';

检查得到的二次矩阵是否是凸的。

ee = min(eig(H))

ee = 3.6976

所有特征值都是正的，所以二次型 x'*H*x 是凸的。

不包括线性等式约束或边界。

Aeq = [];
beq = [];
lb = [];
ub = [];

使用两种算法求解问题

设置选项以使用 quadprog 'active-set' 算法。该算法需要一个初始点。将初始点 x0 设置为长度为 N 的零向量。

opts = optimoptions('quadprog','Algorithm','active-set');
x0 = zeros(N,1);

对解进行计时。

tic
[xa,fvala,eflaga,outputa,lambdaa] = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,opts);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

<stopping criteria details>

toc

Elapsed time is 0.042058 seconds.

将解时间与默认 'interior-point-convex' 算法的时间进行比较。

tic
[xi,fvali,eflagi,outputi,lambdai] = quadprog(H,f,A,b);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

<stopping criteria details>