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

打开实时脚本

这个例子展示了quadprog“激活集”算法在存在许多线性约束时执行，与默认相比“interior-point-convex”算法。此外，拉格朗日乘子来自“激活集”算法在非活动约束下完全为零，这在寻找活动约束时很有帮助。

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

rng默认的%用于重现性N = 150;rng默认的A = randn([10*N,N]);b = 10*ones(size(A,1)，1);f =√(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“激活集”算法。该算法需要一个初始点。设定起始点x0长度为零的向量N．

Opts = optimoptions(“quadprog”，“算法”，“激活集”）;x0 = 0 (N,1);

计算解决方案的时间。

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

找到满足约束条件的最小值。由于目标函数在可行方向上不减少，优化完成，在最优性公差的值内，约束满足在约束公差的值内。<停止条件详细信息>

toc

运行时间为0.042058秒。

将解决方案的时间与默认的时间进行比较“interior-point-convex”算法。

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

找到满足约束条件的最小值。由于目标函数在可行方向上不减少，优化完成，在最优性公差的值内，约束满足在约束公差的值内。<停止条件详细信息>

toc

运行时间为2.305694秒。

“有效集的算法在有很多线性约束的问题上速度更快。

的“激活集”算法只报告与线性约束矩阵相关的拉格朗日乘子结构中的少数非零项。

nnz (lambdaa.ineqlin)

Ans = 14

相比之下，“interior-point-convex”算法返回一个包含所有非零元素的拉格朗日乘子结构。

nnz (lambdai.ineqlin)

Ans = 1500

几乎所有的拉格朗日乘子都小于N *每股收益大小。

nnz(abs(lambda .ineqlin) > N*eps)

Ans = 20

换句话说“激活集”算法在拉格朗日乘子结构中给出了明确的主动约束指示，而“interior-point-convex”算法没有。

另请参阅