有约束约束的二次最小化

此示例显示了一些选项设置对稀疏、有界约束、正定二次问题的影响。

创建二次矩阵 H，作为大小为 400×400 的三对角对称矩阵，其中主对角线上有 +4 个元素，非对角线上有 -2 个元素。

Bin = -2*ones(399,1);
H = spdiags(Bin,-1,400,400);
H = H + H';
H = H + 4*speye(400);

设置除第 400 个之外的每个分量的 [0,0.9] 的边界。允许第 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