最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

範囲に制約のある二次の最小化

'trust-region-reflective' アルゴリズムをもつ関数 quadprog を使用して、上下限のある大規模な二次問題を最小化することができます。

MAT ファイル qpbox1.mat に保存されている問題は、正定の二次でヘッセ行列 H は上限 (ub) および下限 (lb) の制約を満たす三角対角です。

手順 1: ヘッシアンを読み込み、f、lb、ub を定義する

load qpbox1   % Get H
lb = zeros(400,1); lb(400) = -inf;
ub = 0.9*ones(400,1); ub(400) = inf;
f = zeros(400,1); f([1 400]) = -2;

手順 2: 開始点 xstart をもつ二次の最小化ルーチンを呼び出す

xstart = 0.5*ones(400,1);
options = optimoptions('quadprog','Algorithm','trust-region-reflective');
[x,fval,exitflag,output] = ... 
        quadprog(H,f,[],[],[],[],lb,ub,xstart,options);

exitflagoutput.iterations および output.cgiterations の結果の値を見ると、次のようになります。

exitflag,output.iterations,output.cgiterations

exitflag =

     3


ans =

    19


ans =

        1637

収束は 19 回の反復の間で生じ、CG 反復の高い数字は、線形システムを解くために必要なコストが高いことを示します。コストの観点から、SubproblemAlgorithm オプションを 'factorization' に設定することにより、各反復において直接的なソルバーを使用してみます。

options = optimoptions(options,'SubproblemAlgorithm','factorization');
[x,fval,exitflag,output] = ... 
        quadprog(H,f,[],[],[],[],lb,ub,xstart,options);

これにより、反復数は 10 に減りました。

exitflag,output.iterations,output.cgiterations

exitflag =

     3


ans =

    10


ans =

     0

各反復数において直接的なソルバーを使用すると、通常反復数が減ります。しかし、反復ごとの必要な時間は多くなります。この問題に関しては、quadprog を使って問題を解く時間は 10 倍短縮されるのでトレードオフを考えることは有意義なことです。

既定の 'interior-point-convex' アルゴリズムを使用してこの凸問題を解くこともできます。

options = optimoptions('quadprog','Algorithm','interior-point-convex');
[x,fval,exitflag,output] = ... 
        quadprog(H,f,[],[],[],[],lb,ub,[],options);

終了フラグと反復を確認します (内点法アルゴリズムは CG 反復を使用しません)。

exitflag,output.iterations

exitflag =

     1


ans =

     8