比较的速度`coneprog`算法

打开生活的脚本

这个例子显示了解决时间coneprog具有不同的问题大小和所有的算法LinearSolver选择。问题是求点到椭球体的距离n尺寸和椭球面用圆锥约束表示米约束矩阵的行。选择(n, m) =我*(100年,20)为我从1到10。的define_problem的辅助函数这个例子到此结束的指定值产生问题米，n，以及随机数生成器的种子。该函数创建伪随机锥，每个矩阵行中有10个元素为1，每列中至少有2个元素为1，并确保矩阵的第一列是1的(密集)列。

准备问题数据

设置问题生成函数的参数。

n = 100;m = 20;种子= 0;

将实验设置为10个问题大小。

numExper = 10;

创建的完整列表LinearSolver选项值。

linearSolvers = {“汽车”，“增强”，“正常”，“舒尔”，“prodchol”}；

对于这些数据，“汽车”设置的原因coneprog使用“prodchol”线性解算器，所以这两个值的结果是一样的。

创建结构以保存产生的计时数据和每次运行所需要的迭代次数。

时间=结构();s =”“；时间。numExper probsize = repmat(年代,1);%初始化时间结构为零。为solver_i = linearSolvers time.(solver_i{1}) = 0 (numExper, 1);结束iter =结构();iter。numExper probsize = repmat(年代,1);为solver_i = linearSolvers iter.(solver_i{1}) = 0 (numExper, 1);结束

热身解算器

要获得有意义的时间比较，请运行解决(电话coneprog)几次而不定时的结果。这种“预热”使求解器能够有效地使用数据，并预先填充内部即时编译器。

[prob, x0] = define_problem(m, n, seed);选择= optimoptions (“coneprog”，“显示”，“关闭”）;为解(prob,x0, x0)“选项”、选择);结束

解算器运行

在所有问题上运行求解器，同时记录求解器的求解时间和迭代次数。

为我= 1:numExper%产生增大尺寸的问题。[prob, x0] = define_problem(m*i, n*i, seed);time.probsize (i) = num2str (m *我)+“x”+ num2str (n *我);iter.probsize (i) = num2str (m *我)+“x”+ num2str (n *我);解决每个算法产生的问题和测量时间。为solver_i = linearSolvers选项。LinearSolver = solver_i {1};Tic [~，~，~，output] =解(prob,x0，“选项”、选择);时间。(solver_i {1}) (i) = toc;iter (solver_i {1}) (i) = output.iterations;结束结束

显示结果

显示计时结果。的probsize列表示问题大小为“m x n”,在那里米是锥约束数和n为变量的个数。

时间表= struct2table(时间)

时间表=10×6表Probsize auto augmented normal schur prochol __________ ________ _________ ________ ________ ________ "20x100" 0.020335 0.214185 0.022258 0.018266 0.019167 "40x200" 0.028701 0.21417 0.063392 0.01956 0.030663 "60x300" 0.026849 0.38047 0.11627 0.02042 0.027778 "80x400" 0.032513 0.65735 0.23975 0.023377 0.034159 "100x500" 0.040358 1.2081 0.420950.026024 0.038788 "120x600" 0.089219 2.8035 0.92355 0.033922 0.0909 "140x700" 0.098881 7.4664 2.1049 0.046021 0.10043 "160 0x800" 0.11053 8.7302 2.908 0.054712 0.11306 "180x900" 0.11439 10.485 3.5668 0.056406 0.11708 "200x1000" 0.099195 6.7833 3.6698 0.053792 0.097791

最短的时间出现在汽车，舒尔,prodchol列。的汽车和prodchol算法是相同的问题，所以任何时间差异是由于随机效应。最长的时间出现在增强列,而正常的列时间是中间的。

时间结果的差异是由于每个迭代速度的差异还是由于每个求解器的迭代次数的差异?显示相应的迭代计数表。

itertable = struct2table (iter)

itertable =10×6表正常舒尔prodchol probsize自动扩充  __________ ____ _________ ______ _____ ________ " 20 x100“8 8 8 8 8”40 x200型“11 11 11 11 11”60×8 8 8 8 8“80 x400 8 8 8 8 8 100 x500“8 8 8 8 8”120 x600”19日11 11 11 19“140 x700 17 18 17 15 17 160 x800 16 16 16“180 x900分辨率下玩200 x1000“14十四14 13 14 10 10 10 10 10

对于该问题，迭代次数与问题大小不明确相关，这是内点算法的典型特征coneprog．对于所有算法，每行的迭代次数几乎相同。的舒尔和prodchol这个问题的迭代速度比其他算法快。

Helper函数

下面的代码创建define_problemhelper函数。

函数[prob, x0] = define_problem(m,n,seed)%%%生成以下优化问题％％％% % %分钟t% % %酸处理%%% || Ax - b || <= gamma%%% || x - xbar || <= t％％％%%，找到给定椭球最近的点(||Ax-b||<= gamma)%%%到给定的输入点xbar。％％％rng(种子);矩阵A中非零的目标总数为每行% 10个非零%在每列中加上2个非零%加上稠密的第一列。numNonZeros = 10*m + 2*n + m;一个= spalloc (m, n, numNonZeros);%每一行生成10个非零。为I = 1:m p = randperm(n,10);(我,p) = 1;结束%每列生成2个非零。为J = 2:n p = randperm(m,2);(p, j) = 1;结束第一列是密集的。(: 1) = 1;B = ones(m, 1);γ= 10;在椭球外找一个点。xbar =兰迪([10]-10年,n, 1);而范数(A*xbar - b) <= gamma xbar = xbar + randi([-10,10]，n,1)结束定义圆锥问题。概率= optimproblem (“描述”，“最小化到椭球体的距离”）;x = optimvar (“x”n);t = optimvar (“t”）;概率。目标= t;prob.Constraints。Soc1 = norm(x - xbar) <= t;prob.Constraints。so2 = norm(A*x - b) <= gamma;x0。x =稀疏(n, 1);x0。t = 0;结束