範囲に制約のある二次の最小化
この例では、スパースで範囲制約付きの正定値 2 次問題に対する一部のオプション設定の効果を示します。
主対角線上のエントリが +4、非対角線上のエントリが -2、サイズが 400 x 400 の三重対角対称行列として、2 次行列 H を作成します。
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(400) = –2 を設定することを除いて、線形ベクトル f をゼロに設定します。
f = zeros(400,1); f(400) = -2;
Trust-Region-Reflective 法
"trust-region-reflective" アルゴリズムを使用して 2 次問題を解きます。
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
アルゴリズムは、比較的少ない反復回数で収束しますが、CG (共役勾配) 反復を 1,000 回以上実行します。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
