Квадратичная минимизация со связанными ограничениями

Этот пример показывает эффекты некоторых настроек опции на разреженную, ограниченную в связях, положительно определенную квадратичную задачу.

Создайте квадратичную матрицу 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- Области Отражающее Решение

Решите квадратичную программу, используя '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

Значение по умолчанию '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.

The '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    

Для просмотра документации необходимо авторизоваться на сайте