数学やプログラミングの備忘録

数理最適化, Python, C++をメインに紹介するブログ。

MENU

二次計画問題のクラスと解法

クラス

二次式が現れる最適化問題はいろいろあるから、クラス別に簡単にまとめてみます。なんともマニアックな記事です。

この記事に出てくるのは、以下のクラスです。

  1. 制約無し二次計画問題
  2. 線形制約付き二次計画問題
  3. 二次計画問題
  4. 0-1整数二次計画問題
  5. 整数二次計画問題
  6. 混合整数二次計画問題

ちなみに、下に書いてあるほどクラスは大きく、上のクラスを含みます。例えば、二次計画問題は、整数二次計画問題の特殊ケース(整数性が無いという意味で)です。一般に、下のクラスほど難しいです。

この記事で紹介する最適化問題の目的関数は全て、


f(x) =x^T Q x + p^T x + r

と表します。また、

  •  x :  n 次元ベクトル (変数)
  •  Q :  n\times n 対称行列
  •  p :  n 次元ベクトル
  •  r : 定数

とします。少しだけですが、各クラスにおける  f(x) が凸関数のときの解法の話をします。

制約無し二次計画問題


\begin{array}{ll}
\min_{x} & x^T Q x + p^T x + r\\
\text{s.t.} & x \in \mathbb{R}^n
\end{array}

名前の通り、制約無しの最適化問題 x は実数をとります。行列  Q が半正定値ならば、目的関数は凸関数です。この場合、制約無し凸二次計画問題 とか呼んだりする。ちなみに、正定値のときは、目的関数は狭義凸関数である。目的関数が凸関数ならば、いろんなソフトウェアやライブラリーで解くことができます。が、凸ならこの問題はソフトウェアやライブラリーを使うまでも無く簡単に解けるんです。凸関数は微分して0の点で最小値を取るので、勾配ベクトル  \nabla f(x) が0ベクトルとなる  x を求めればよいんです。つまり、線形方程式を解けばいいんです。(雑な説明)

線形等式制約付き二次計画問題


\begin{array}{ll}
\min_{x} & x^T Q x + p^T x + r\\
\text{s.t.} & A x = b\\
& x \in \mathbb{R}^n
\end{array}

名前の通り、線形の等式制約付きの最適化問題。制約無しのときと同様に、目的関数が凸関数ならば、線形等式制約付き凸二次計画問題 とか呼ばれ、線形方程式を解くこと で最適解を見つけることができます。そういう意味では、制約無しのときと、難しさはさほど変わりません。

二次計画問題


\begin{array}{ll}
\min_{x} & x^T Q x + p^T x + r\\
\text{s.t.} & A x \le b\\
& x \in \mathbb{R}^n
\end{array}

等式制約は2つの不等式制約で書けるから、この問題は線形等式制約付き二次計画問題を含みます。目的関数が凸関数ならば、凸二次計画問題と呼んだりします。二次計画問題という名前にしたけれど、もっと細かく言うなら、この問題は、線形制約付き二次計画問題 と呼ぶべきかもしれない。人によっては、二次計画問題というと、二次の制約付いている場合もあるからです。凸二次計画問題はいろんな解き方があります。内点法や有効制約法などなど。制約無しや線形等式制約付きの場合と比べて難しいんですが、現代のソフトウェアやライブラリーは優秀だから、凸二次計画問題はさほど難しくない問題と認識してもよいでしょう。最適化ソフトウェアのCPLEXやGurobiなら、ほとんど一瞬で解けるでしょう(もちろん変数の数による)。

0-1整数二次計画問題


\begin{array}{ll}
\min_{x} & x^T Q x + p^T x + r\\
\text{s.t.} & A x \le b\\
& x \in \{0,1\}^n
\end{array}

ここまで、変数  x_1,\dots,x_n は 実数を取ることが許されていました。この問題は、0か1しか選ぶことができません。組み合わせ最適化問題で現れる問題です。目的関数が凸関数であろうと、問題の難しさは、このクラスの問題から跳ね上がります。 最適解見つけるの大変だから、最適解である保証は無いけど良解を出すっていう手法(つまりヒューリスティクス)があるくらいです。この問題を真っ向勝負で最適解見つけたいなら、最適化ソフトウェアのCPLEXかGurobiの二択だと思います(個人的には)。ただこれらは、商用ソフトウェアなのでお金がかかります。かと言って、自分で高性能なアルゴリズムを実装するのはかなりハードルが高いです。最適解であるという保証付きのソフトウェアは、フリーでもいくつかありますが、CPLEXやGurobiと比べて、性能はイマイチという印象です(個人的には)。勉強用ならフリーソフトウェアで十分でしょう。ちなみに、CPLEXやGurobiは分枝限定法(branch-and-bound algorithm)ベースのアルゴリズムが実装されています。branch-and-cut algorithm とかですね。しかし、大規模な問題であれば、CPLEXやGurobiでも解くのは難しいでしょう。

整数二次計画問題


\begin{array}{ll}
\min_{x} & x^T Q x + p^T x + r\\
\text{s.t.} & A x \le b\\
& x \in \mathbb{Z}^n
\end{array}

0-1整数二次計画問題は0か1でしたが、整数二次計画問題では各変数は整数という制約が付きます。このクラスの問題も難しいです、、目的関数が凸関数では無かったら、絶望的に難しいです。目的関数が凸関数だったとして、CPLEXやGurobiで時間制限3日で解ける問題の大きさは、変数の数が2桁くらいと思います。 問題によりますが、50〜99くらいでしょうか。数理最適化の分野では、整数凸二次計画問題はCPLEXやGurobiで解くのが一般的で、それらで解けないならどうする?と研究が始まったりするらしいです。例えば、ヒューリスティクスを考えるとか。

混合整数二次計画問題


\begin{array}{ll}
\min_{x} & x^T Q x + p^T x + r\\
\text{s.t.} & A x \le b\\
& x_i \in \mathbb{Z}\ (i \in I)\\
& x_i \in \mathbb{R}\ (i \in\{1,\dots,n\} \setminus I)
\end{array}

最後は最も表現力が高いクラスの混合整数二次計画問題です。整数も実数もokということなので, これまでの説明してきた問題はこの混合整数二次計画問題の特殊ケースになります。目的関数が凸ならば, CPLEXやGurobiが上手くうごいてくれます。「集合  I={1,\dots,n} (つまり、整数二次計画問題)の場合と、そうでないときでどちらが難しいか」はどうなんでしょうか。場合によるんでしょうか。整数変数が少なければ、簡単に解けそうですが、、。半分のときと、All整数変数でどちらが難しいんだろう。。

おわりに

まとめてみると意外と大変でした。次は応用例をまとめようと思います。