Теплый старт quadprog

В этом примере показано, как теплый стартовый объект увеличивает скорость решения большой, плотной квадратичной задачи. Создание масштабированной проблемы с помощью N переменные и 10N линейные ограничения неравенства. Набор N до 1000.

rng default % For reproducibility
N = 1000;
rng default
A = randn([10*N,N]);
b = 5*ones(size(A,1),1);
f = sqrt(N)*rand(N,1);
H = (4+N/10)*eye(N) + randn(N);
H = H + H';
Aeq = [];
beq = [];
lb = -ones(N,1);
ub = -lb;

Создание теплого стартового объекта для quadprog, начиная с нуля.

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

Решить проблему, и время результат.

tic
[ws1,fval1,eflag1,output1,lambda1] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws);

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 9.221035 seconds.

Решение имеет несколько активных линейных ограничений неравенства и не имеет активных границ.

nnz(lambda1.ineqlin)

ans = 211

nnz(lambda1.lower)

ans = 0

nnz(lambda1.upper)

ans = 0

Решателю требуется несколько сотен итераций, чтобы сойтись.

output1.iterations

ans = 216

Измените одно случайное задание на удвоенное исходное значение.

idx = randi(N);
f(idx) = 2*f(idx);

Решите проблему с новой целью, начиная с предыдущего теплого стартового решения.

tic
[ws2,fval2,eflag2,output2,lambda2] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws1);

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 1.490214 seconds.

Решателю требуется гораздо меньше времени для решения новой задачи.

Новое решение имеет примерно такое же количество активных ограничений.

nnz(lambda2.ineqlin)

ans = 214

nnz(lambda2.lower)

ans = 0

nnz(lambda2.upper)

ans = 0

Новое решение близко к предыдущему решению.

norm(ws2.X - ws1.X)

ans = 0.0987

norm(ws2.X)

ans = 2.4229

Разница в скорости во многом обусловлена тем, что решатель принимает гораздо меньше итераций.

output2.iterations

ans = 29

См. также

optimwarmstart | quadprog

Связанные темы

• Передовые практики теплого старта