Main Content

quadprog のウォーム スタート

ライブ スクリプトを開く

この例では、大規模で密な二次問題の求解をウォーム スタート オブジェクトで高速化する方法を示します。N 個の変数と 10N 個の線形不等式制約をもつ、スケール化した問題を作成します。N を 1000 に設定します。

rng default % For reproducibility
N = 1000;
rng default
A = randn([10*N,N]);
b = 5*ones(size(A,1),1);
f = sqrt(N)*rand(N,1);
H = (4+N/10)*eye(N) + randn(N);
H = H + H';
Aeq = [];
beq = [];
lb = -ones(N,1);
ub = -lb;

quadprog のために、ゼロから開始するウォーム スタート オブジェクトを作成します。

opts = optimoptions('quadprog','Algorithm','active-set');
x0 = zeros(N,1);
ws = optimwarmstart(x0,opts);

問題を解き、かかった時間を計測します。

tic
[ws1,fval1,eflag1,output1,lambda1] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws);
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>

toc
Elapsed time is 9.221035 seconds.

解には、複数のアクティブな線形不等式制約が含まれていますが、アクティブな範囲は含まれていません。

nnz(lambda1.ineqlin)
ans = 211

nnz(lambda1.lower)
ans = 0

nnz(lambda1.upper)
ans = 0

収束するまでに、ソルバーでは数百回の反復が必要です。

output1.iterations
ans = 216

任意の 1 つの目的を元の値の 2 倍に変更します。

idx = randi(N);
f(idx) = 2*f(idx);

前回のウォーム スタートの解から開始して、新しい目的の問題を解きます。

tic
[ws2,fval2,eflag2,output2,lambda2] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws1);
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>

toc
Elapsed time is 1.490214 seconds.

ソルバーが新しい問題を解く時間が大幅に短縮されています。

新しい解には、アクティブな制約がほぼ同数あります。

nnz(lambda2.ineqlin)
ans = 214

nnz(lambda2.lower)
ans = 0

nnz(lambda2.upper)
ans = 0

新しい解は、前回と近い解です。

norm(ws2.X - ws1.X)
ans = 0.0987

norm(ws2.X)
ans = 2.4229

この速度差は、ソルバーで必要となる反復回数が大きく減少したことに大きく起因しています。

output2.iterations
ans = 29

参考

|

関連するトピック