大型稀疏二次规划的内点算法
这个例子展示了在遇到稀疏问题时使用稀疏算术的价值。矩阵有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)')