coneprog АлгоритмыЭтот пример показывает времена решения для coneprog с различными проблемными размерами и всеми алгоритмами LinearSolver опция. Проблема состоит в том, чтобы найти расстояние точки к эллипсоиду, где точка находится в n размерности и эллипсоид представлены коническим ограничением с m строки для матрицы ограничений. Выберите (n,m) = i*(100,20) для i от 1 до 10. define_problem функция помощника в конце этого примера создает проблему для заданных значений mN, и seed для генератора случайных чисел. Функция создает псевдослучайные конусы с 10 записями 1 в каждой строке матрицы и по крайней мере двух записях 1 в каждом столбце, и гарантирует, что первый столбец матрицы является (плотным) столбцом 1 с.
Установите параметры для проблемной функции генерации.
n = 100; m = 20; seed = 0;
Установите эксперимент запускаться для десяти проблемных размеров.
numExper = 10;
Создайте полный список LinearSolver значения опции.
linearSolvers = {'auto','augmented','normal','schur','prodchol'};Для этих данных, 'auto' установка причин coneprog использовать 'prodchol' линейный решатель, таким образом, вы получаете по существу те же результаты для тех двух значений.
Создайте структуры, чтобы содержать получившиеся данные о синхронизации и количество итераций, которые берет каждый запуск.
time = struct(); s = " "; time.probsize = repmat(s,numExper,1); % Initialize time struct to zeros. for solver_i = linearSolvers time.(solver_i{1}) = zeros(numExper, 1); end iter = struct(); iter.probsize = repmat(s,numExper,1); for solver_i = linearSolvers iter.(solver_i{1}) = zeros(numExper, 1); end
Чтобы получить значимые сравнения синхронизации, запустите solve (который вызывает coneprog) несколько раз не синхронизируя результаты. Этот "прогрев" готовит решатель, чтобы использовать данные эффективно и предварительно заполняет внутренний своевременный компилятор.
[prob, x0] = define_problem(m, n, seed); options = optimoptions('coneprog','Display','off'); for i = 1 : 4 sol = solve(prob,x0,'options',options); end
Запустите решатель на всех проблемах при записи времен решения и количества итераций, которые берет решатель.
for i = 1:numExper % Generate problems of increasing size. [prob, x0] = define_problem(m*i, n*i, seed); time.probsize(i) = num2str(m*i)+"x"+num2str(n*i); iter.probsize(i) = num2str(m*i)+"x"+num2str(n*i); % Solve the generated problem for each algorithm and measure time. for solver_i = linearSolvers options.LinearSolver = solver_i{1}; tic [~,~,~,output] = solve(prob,x0,'options',options); time.(solver_i{1})(i) = toc; iter.(solver_i{1})(i) = output.iterations; end end
Отобразите результаты синхронизации. probsize столбец указывает на проблемный размер как на "m x n", где m количество конических ограничений и n количество переменных.
timetable = struct2table(time)
timetable=10×6 table
probsize auto augmented normal schur prodchol
__________ ________ _________ ________ ________ ________
"20x100" 0.020335 0.042185 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.42095 0.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
"160x800" 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
Самые короткие времена появляются в autoШур, и prodchol столбцы. auto и prodchol алгоритмы идентичны для проблем, таким образом, любые различия в синхронизации происходят из-за случайных эффектов. Самые долгие времена появляются в augmented столбец, в то время как normal времена столбца являются промежуточными.
Должны различия в результатах синхронизации к различиям в скорости для каждой итерации или из-за количества итераций для каждого решателя? Отобразите соответствующую таблицу количеств итерации.
itertable = struct2table(iter)
itertable=10×6 table
probsize auto augmented normal schur prodchol
__________ ____ _________ ______ _____ ________
"20x100" 8 8 8 8 8
"40x200" 11 11 11 11 11
"60x300" 8 8 8 8 8
"80x400" 8 8 8 8 8
"100x500" 8 8 8 8 8
"120x600" 19 11 11 11 19
"140x700" 17 18 17 15 17
"160x800" 16 16 16 16 16
"180x900" 14 14 14 13 14
"200x1000" 10 10 10 10 10
Для этой проблемы количество итераций ясно не коррелируется к проблемному размеру, который является типичной характеристикой алгоритма внутренней точки, используемого coneprog. Количество итераций является почти тем же самым в каждой строке для всех алгоритмов. schur и prodchol итерации быстрее для этой проблемы, чем те из других алгоритмов.
Следующий код создает define_problem функция помощника.
function [prob, x0] = define_problem(m,n,seed) %%% Generate the following optimization problem %%% %%% min t %%% s.t. %%% || Ax - b || <= gamma %%% || x - xbar || <= t %%% %%% which finds the closest point of a given ellipsoid (||Ax-b||<= gamma) %%% to a given input point xbar. %%% rng(seed); % The targeted total number of nonzeros in matrix A is % 10 nonzeros in each row % plus 2 nonzeros in each column % plus a dense first column. numNonZeros = 10*m + 2*n + m; A = spalloc(m,n,numNonZeros); % For each row generate 10 nonzeros. for i = 1:m p = randperm(n,10); A(i,p) = 1; end % For each column generate 2 nonzeros. for j = 2:n p = randperm(m,2); A(p,j) = 1; end % The first column is dense. A(:,1) = 1; b = ones(m, 1); gamma = 10; % Find a point outside of the ellipsoid. xbar = randi([-10,10],n,1); while norm(A*xbar - b) <= gamma xbar = xbar + randi([-10,10],n,1); end % Define the cone problem. prob = optimproblem('Description', 'Minimize Distance to Ellipsoid'); x = optimvar('x',n); t = optimvar('t'); prob.Objective = t; prob.Constraints.soc1 = norm(x - xbar) <= t; prob.Constraints.soc2 = norm(A*x - b) <= gamma; x0.x = sparse(n,1); x0.t = 0; end