В этом примере показано, как хорошо quadprog
'active-set'
алгоритм выполняет в присутствии многих линейных ограничений, по сравнению с 'interior-point-convex'
по умолчанию алгоритм. Кроме того, множители Лагранжа от
'active-set'
алгоритм ниже нуля при неактивных ограничениях, которые могут быть полезными, когда вы ищете активные ограничения.
Создайте псевдослучайную квадратичную проблему с 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'
алгоритм не делает.