大型稀疏二次规划的内点算法

打开实时脚本

这个例子展示了在遇到稀疏问题时使用稀疏算术的价值。矩阵有n行，你选择的地方n是一个大的值，和几个非零的对角线带。一个完整的矩阵大小n——- - - - - -n可以用完所有可用的内存，但一个稀疏矩阵没有问题。

问题是最小化x'*H*x/2 + f'*x受

X (1) + X(2) +…+ x(n) <= 0，

在哪里F =[-1;-2;-3;…;-n]．H是稀疏对称带状矩阵。

创建稀疏二次矩阵

创建一个基于矢量位移的对称循环矩阵(2 2 3, 6日,14日,6日3]， 14在主对角线上。让矩阵是n——- - - - - -n,在那里N = 30,000．

N = 3e4;H2 = speye(n);H = 3 * circshift (H2 3 2) + 6 * circshift (H2 2 2) + 2 * circshift (H2, 1、2).．.+ 14*H2 + 2*circshift(H2,1,2) + 6*circshift(H2,2,2) + 3*circshift(H2,3,2);

查看矩阵结构。

间谍(H)

创建线性约束和目标

线性约束是解元素的和是非正的。目标函数包含一个用向量表示的线性项f．

A = ones(1,n);B = 0;F = 1:n;F = -f;

解决问题

用函数求解二次规划问题interior-point-convex”算法。为防止求解器过早停止，请设置StepTolerance选项0．

选项= optimoptions(@quadprog，“算法”，“interior-point-convex”，“StepTolerance”, 0);[x, fval exitflag、输出λ)=.．.quadprog (H f A、b ,[],[],[],[],[], 选项);

最小值满足约束条件。优化完成是因为目标函数在可行方向上不递减，在最优性容差值范围内，约束条件满足在约束容差值范围内。<停止条件详细信息>

在许多计算机上，您不能创建一个完整的n——- - - - - -n矩阵时n= 30000。所以你只能用稀疏矩阵来解决这个问题。

检查解决方案

查看与线性不等式相关的目标函数值、迭代次数和拉格朗日乘子。

流(目标函数值为%d。迭代次数为%d。\n拉格朗日乘子是%d。\n'，.．.fval、output.iterations lambda.ineqlin)

目标函数值为-3.133073e+10。迭代次数是7。拉格朗日乘数为1.500050e+04。

因为没有下界、上界或线性等式约束，唯一有意义的拉格朗日乘子是lambda.ineqlin．因为lambda.ineqlin为非零时，可以看出不等式约束是活动的。计算约束以确定解在边界上。

流(线性不等式约束A*x的值为%d.\n'* x)

线性不等式约束A*x的值为9.150244e-08。

溶液组分的和为零，在公差范围内。

解决方案x有三个区域:初始部分，最终部分，以及在大部分解上近似线性的部分。画出这三个区域。

Subplot (3,1,1) plot(x(1:60))标题('x(1)到x(60)') subplot(3,1,2) plot(x(61:n-60))'x(61)到x(n-60)') subplot(3,1,3) plot(x(n-59:n))'x(n-59)到x(n)'）

另请参阅

quadprog|circshift