В этом примере показано влияние некоторых параметров на разреженную, ограниченную ограничениями, положительную определенную квадратичную задачу.
Создание квадратичной матрицы H как тридиагональная симметричная матрица размером 400-на-400 с записями + 4 на главной диагонали и -2 на внедиагональных.
Bin = -2*ones(399,1); H = spdiags(Bin,-1,400,400); H = H + H'; H = H + 4*speye(400);
Установить границы [0,0.9] в каждом компоненте, кроме 400-го. Разрешить неограниченное использование 400-го компонента.
lb = zeros(400,1); lb(400) = -inf; ub = 0.9*ones(400,1); ub(400) = inf;
Установка линейного вектора f до нулей, за исключением набора f(400) = –2.
f = zeros(400,1); f(400) = -2;
Решите квадратичную программу с помощью 'trust-region-reflective' алгоритм.
options = optimoptions('quadprog','Algorithm',"trust-region-reflective"); tic [x1,fval1,exitflag1,output1] = ... quadprog(H,f,[],[],[],[],lb,ub,[],options);
Local minimum possible. quadprog stopped because the relative change in function value is less than the function tolerance.
time1 = toc
time1 = 0.1044
Осмотрите решение.
fval1,exitflag1,output1.iterations,output1.cgiterations
fval1 = -0.9930
exitflag1 = 3
ans = 18
ans = 1682
Алгоритм сходится в относительно немногих итерациях, но принимает более 1000 CG (сопряженный градиент) итераций. Чтобы избежать итераций CG, задайте опции для использования прямого решателя.
options = optimoptions(options,'SubproblemAlgorithm','factorization'); tic [x2,fval2,exitflag2,output2] = ... quadprog(H,f,[],[],[],[],lb,ub,[],options);
Local minimum possible. quadprog stopped because the relative change in function value is less than the function tolerance.
time2 = toc
time2 = 0.0185
fval2,exitflag2,output2.iterations,output2.cgiterations
fval2 = -0.9930
exitflag2 = 3
ans = 10
ans = 0
На этот раз алгоритм принимает меньше итераций и не выполняет итераций CG. Время решения существенно уменьшается, несмотря на относительно трудоемкие шаги прямой факторизации, поскольку решатель избегает выполнения многих шагов CG.
Дефолт 'interior-point-convex' алгоритм может решить эту проблему.
tic [x3,fval3,exitflag3,output3] = ... quadprog(H,f,[],[],[],[],lb,ub); % No options means use the default algorithm
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>
time3 = toc
time3 = 0.0402
fval3,exitflag3,output3.iterations
fval3 = -0.9930
exitflag3 = 1
ans = 8
Все алгоритмы дают одинаковое значение целевой функции для отображения точности, -0.9930.
'interior-point-convex' алгоритм принимает наименьшее количество итераций. Тем не менее, 'trust-region-reflective' алгоритм с непосредственным решателем подпроблем быстрее всего достигает решения.
tt = table([time1;time2;time3],[output1.iterations;output2.iterations;output3.iterations],... 'VariableNames',["Time" "Iterations"],'RowNames',["TRR" "TRR Direct" "IP"])
tt=3×2 table
Time Iterations
________ __________
TRR 0.10443 18
TRR Direct 0.018544 10
IP 0.040204 8