二次計画問題・整数二次計画問題の応用例 - 数学やプログラミングの備忘録

２次関数が現れる最適化問題って何があるんだろうか、、？

そう思っていろいろ調べてみました。

この記事では、二次計画問題だったり、整数二次計画問題だったり、とにかく二次関数が現れる最適化問題の代表的な応用例を紹介します。

この記事では、数式は書かずに簡単に紹介しますが、興味のある人はググってみてください。

応用例の一覧

例えば、 $n$ 個の工場を $n$ 箇所に配置する。各工場間で物資を輸送し、その総コストを最小化することを考える。工場A を 場所a 、 工場B を 場所b に配置するとき、

工場Aから工場Bまでの輸送コストは、

(工場Aから工場Bまでの輸送する物資量)×(場所aと場所bの距離)

で表される。配置場所を表す01変数を用意すると、目的関数は二次関数で表される。01整数二次計画問題 と呼ばれる問題に定式化される。

変数の数は、 [tex: n²] 個となる。QAPLIBというベンチマークサイトがある。

線形回帰モデルを最小二乗法で求めるとき、制約無し二次計画問題となる。サンプルデータと求める線形回帰モデルの誤差ベクトルのノルムの二乗を最小化する。以下の記事で、数学的に説明。

例えば、線形回帰モデルを求めるとき、パラメータの数が多いほど、手元のデータとの当てはまりは良いが、未知のデータの予測はうまくいかない。こんな現象を過適合という。

LASSOと呼ばれる手法は、手元のデータとの当てはまりの良さとパラメータの数を調整し、その結果、モデルに不要なパラメータは取り除かれ、予測精度が向上するとされている。

上記の最小二乗法の発展であり、二次関数が現れる最適化問題として定式化される。

ポートフォリオの平均・分散モデルでは、二次計画問題が利用される。二次関数で表される分散をコストと考え、例えば、ある一定以下のコストの条件で収益を最大化する。逆に、ある一定以上の収益の条件でコストを最小化する。入門書で見かけるものは、後者であり、二次計画問題として定式化される。

最適潮流計算(OPF: Optimal Power Flow)問題は、例えば次のように定式化される：　電力システムの回路方程式を制約条件とし、発電機燃料の総和を最小化。目的関数は一般に非線形関数であるが、二次関数に区分線形近似をする手法などが知られている。

最近ベクトル問題(CVP: Closest Vector Problem)は、暗号の分野に現れる問題である。最近ベクトル問題は、整数ベクトルが与えらたとき、それに最も近い整数ベクトルを求める問題。整数二次計画問題として定式化される。

サポートベクターマシンは、与えられたデータを２つのクラスに分類するために、各サンプルデータと距離が最大となるような超平面を求める。距離が二次関数で表されるため、二次計画問題となる。

ここまで見てきたように、距離が絡んでくると、二次関数が現れる。施設配置問題も様々なバリエーションがあるが(例えばQAP)、今回は以下のような問題を考える。

Aくんの学校では今日は席替えです。Aくんは、以下の特殊能力を使うことができます。

Aくんのクラスには、可愛い子が何人かいます。そこで、Aくんは思いつきました。「そうだ！可愛い子達みんなとできるだけ近い席にしよう！」これは例えば以下のように定式化されます: 実現可能な席の座標の制約の下、各可愛い子達との距離の2乗の総和を最小化(二次計画問題)。

私は、なんてくだらないことを書いているんだろう。。

Let's optimize!