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

ライブ スクリプトを開く

この例では、多数の線形制約が存在する問題において、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.069158 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>

toc
Elapsed time is 3.924934 seconds.

多数の線形制約をもつ問題に対しては、"active-set" アルゴリズムの方がはるかに高速です。

ラグランジュ乗数の検証

"active-set" アルゴリズムは、線形制約行列に関連するラグランジュ乗数構造体の少数の非ゼロ エントリのみを報告します。

nnz(lambdaa.ineqlin)
ans = 
14

対照的に、"interior-point-convex" アルゴリズムは、すべてが非ゼロ要素であるラグランジュ乗数構造体を返します。

nnz(lambdai.ineqlin)
ans = 
1500

これらのラグランジュ乗数はほぼすべてが N*eps よりも小さいサイズです。

nnz(abs(lambdai.ineqlin) > N*eps)
ans = 
23

言い換えれば、"active-set" アルゴリズムは、ラグランジュ乗数構造体に含まれるアクティブな制約を明確に示しますが、"interior-point-convex" アルゴリズムはそうではありません。

参考

|

トピック