多数の線形制約がある場合の二次計画法

ライブスクリプトを開く

この例では、多数の線形制約が存在する問題において、quadprog 'active-set' アルゴリズムが、既定の 'interior-point-convex' アルゴリズムと比較して、いかに有効に機能するかを説明します。また、'active-set' アルゴリズムのラグランジュ乗数は、非アクティブな制約において厳密にゼロになります。このことは、アクティブな制約を求める場合に有用です。

問題の説明

N 個の変数と 10*N 個の線形不等式制約をもつ疑似乱数二次問題を作成します。N = 150 と指定します。

rng default % For reproducibility
N = 150;
rng default
A = randn([10*N,N]);
b = 10*ones(size(A,1),1);
f = sqrt(N)*rand(N,1);
H = 18*eye(N) + randn(N);
H = H + H';

得られた二次行列が凸であることを確認します。

ee = min(eig(H))

ee = 3.6976

すべての固有値が正であるため、二次形式 x'*H*x は凸になります。

線形等式制約または範囲は含みません。

Aeq = [];
beq = [];
lb = [];
ub = [];

2 つのアルゴリズムで問題を解く

quadprog 'active-set' アルゴリズムを使用するためのオプションを設定します。このアルゴリズムには、初期点が必要です。初期点 x0 を長さ N のゼロベクトルになるように設定します。

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

求解時間を測定します。

tic
[xa,fvala,eflaga,outputa,lambdaa] = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,opts);

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 0.042058 seconds.

この求解時間と既定の 'interior-point-convex' アルゴリズムを使用した場合の求解時間を比較します。

tic
[xi,fvali,eflagi,outputi,lambdai] = quadprog(H,f,A,b);

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>