Описание проблемы

Создание псевдослучайной квадратичной задачи с помощью N переменные и 10*N линейные ограничения неравенства. Определить N = 150.

rng default % For reproducibility
N = 150;
rng default
A = randn([10*N,N]);
b = 10*ones(size(A,1),1);
f = sqrt(N)*rand(N,1);
H = 18*eye(N) + randn(N);
H = H + H';

Проверьте, что полученная квадратичная матрица является выпуклой.

ee = min(eig(H))

ee = 3.6976

Все собственные значения являются положительными, поэтому квадратичная форма x'*H*x выпуклый.

Отсутствие ограничений линейного равенства или границ.

Aeq = [];
beq = [];
lb = [];
ub = [];

Решение проблемы с помощью двух алгоритмов

Задайте параметры для использования quadprog 'active-set' алгоритм. Этот алгоритм требует начальной точки. Установка начальной точки x0 быть нулевым вектором длины N.

opts = optimoptions('quadprog','Algorithm','active-set');
x0 = zeros(N,1);

Время решения.

tic
[xa,fvala,eflaga,outputa,lambdaa] = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,opts);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

<stopping criteria details>

toc

Elapsed time is 0.042058 seconds.

Сравнение времени решения со временем по умолчанию 'interior-point-convex' алгоритм.

tic
[xi,fvali,eflagi,outputi,lambdai] = quadprog(H,f,A,b);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

<stopping criteria details>

toc

Elapsed time is 2.305694 seconds.

'active-set' алгоритм намного быстрее при проблемах со многими линейными ограничениями.

Изучение множителей лагранжа

'active-set' алгоритм сообщает только несколько ненулевых записей в структуре множителя Лагранжа, связанных с матрицей линейных ограничений.

nnz(lambdaa.ineqlin)

ans = 14

Напротив, 'interior-point-convex' алгоритм возвращает структуру множителя Лагранжа со всеми ненулевыми элементами.

nnz(lambdai.ineqlin)

ans = 1500

Почти все эти множители Лагранжа меньше, чем N*eps по размеру.

nnz(abs(lambdai.ineqlin) > N*eps)

ans = 20

Другими словами, 'active-set' алгоритм дает четкие указания на активные ограничения в структуре множителя Лагранжа, тогда как 'interior-point-convex' алгоритм не используется.