coneprog АлгоритмыЭтот пример показывает время решения для coneprog с различными размерами задач и всеми алгоритмами LinearSolver опция. Задача состоит в том, чтобы найти расстояние точки до эллипсоида, где точка находится n размерности, и эллипсоид представлен ограничением конуса с m строки для матрицы ограничений. Выберите (n,m) = i*(100,20) для i от 1 до 10. The define_problem Функция helper в конце этого примера создает задачу для заданных значений m, n, и 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
Отображение результатов синхронизации. The 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, schur, и prodchol столбцы. The 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. Количество итераций почти одинаковое в каждой строке для всех алгоритмов. The 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