有约束约束的二次最小化
此示例显示了一些选项设置对稀疏、有界约束、正定二次问题的影响。
创建二次矩阵 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.0539
检查解。
fval1,exitflag1,output1.iterations,output1.cgiterations
fval1 = -0.9930
exitflag1 = 3
ans = 18
ans = 1672
该算法在相对较少的迭代次数内收敛，但需要超过 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.0214
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.0229
fval3,exitflag3,output3.iterations
fval3 = -0.9930
exitflag3 = 1
ans = 8
比较结果
所有算法都给出相同的目标函数值来显示精度 – 0.9930。
"interior-point-convex" 算法需要的迭代次数最少。采用直接子问题求解器的 "trust-region-reflective" 算法，其解速度与 "interior-point-convex" 算法大致相当。
tt = table([time1;time2;time3],[output1.iterations;output2.iterations;output3.iterations],... VariableNames=["Time" "Iterations"],RowNames=["TRR" "TRR Direct" "IP"])
tt=3×2 table
0.0539 18
0.0214 10
0.0229 8
