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