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