トップ > 最適化とは > 二次計画法

整数計画法

ここでは数理計画法の中の二次計画法についてご紹介します。 二次計画法とは二次問題を解く解法・アルゴリズムを総称したものです。 なお Numerical Optimizer の「フルセット」「NLP(V17 まで)」のモジュールが 二次計画法のアルゴリズムに対応しています。

二次計画問題とは

目的関数が 2 次式で制約条件が線形で表現できる問題を二次計画問題と呼びます。 目的関数が凸の場合にはさらに有効なアルゴリズムを適用することが可能なります。 ここではそういった問題を前提として説明を致します。右のイメージ図は 2 変数の 2 次で凸な関数の例です。

二次計画問題イメージ

アルゴリズムイメージ

数理計画法を解く上で最も扱いに注意を要するのは不等式。いくつかの不等式は、 等式として満たされていて、最適解を形成するのに貢献していますが、 いくつかの不等式は最適解の存在する領域を定義しているだけの働きしかしていません。 もちろん、どの不等式が最適解を形成するのに直接貢献しているか (「アクティブ」になっているか)は問題を見ただけではわかりません。 あれかこれかと推定しながら計算を進めます。特に線形計画・二次計画の場合には、 このアクティブな不等式群の決定が最適解の探索とほぼ同じであることが知られており、 Numerical Optimizer に組み込まれている単体法・有効制約法はこの性質を活用した手法です。

二次計画法で取り扱うことのできる応用問題

Numerical Optimizer におけるアルゴリズムの工夫

アクティブになった不等式は以降の計算では等式として扱います。例えば x >= 0 という式がアクティブになったら x を 0 に固定してよく、変数を実質 減らして効率良く計算を行うことができます。例えばポートフォリオ最適化問 題などは、x >= 0 という不等式が数多くアクティブになる (0 に固定される変 数が多い)ので、有効制約法に向いた問題であることが知られています。

また、有効制約法はその性質上、アクティブになる不等式制約がおおまかにでも見積もれていれば 高速に解を求めることができます。 そのため、似通った QP を繰り返し解く場合には、アクティブになる不等式制約の 情報を引き継ぐことで高速化が図れます。 Numerical Optimizer の有効制約法には、この機能が実装されており、連続して QP を解く局面や 逐次二次計画法において活用されています。