代表的な最適化問題

本記事では、代表的な最適化問題について紹介します。

解こうとしている問題が、どの最適化問題に所属する問題なのかを知ることにより、その難しさや適切なアルゴリズムを知ることができます。

 

一般的な最適化問題は、前記事でも述べた通り以下のようにあらわされます。

{min:f(x)}

{s.t.:g_i(x) \leq 0 (i=1,...,m),h_j(x) = 0 (j=1,...,l)} 

ここで、連続最適化における重要な概念として、凸集合と凸関数の定義を以下で与えます。

{Definition\ 1.} 集合{S \subseteq R^n}において、

{ x\in S, y\in S, \alpha \in [0,1] \Rightarrow (1-\alpha) x + \alpha y \in S}

が成り立つとき、{S}を凸集合といいます。これはすなわち、集合{S}内の任意の2点を結ぶ線分が{S}に含まれることを指します。

{Definition\ 2.} 関数{f:R^n \rightarrow (-\infty, +\infty ] }が任意の { x, y\in R^n}{\alpha \in [0,1] }に対して、

{ f((1-\alpha)x+\alpha y ) \leq (1-\alpha) f(x) +\alpha f(y) }

を満たすとき、{f}を凸関数といいます。

例として、{f(x)=x^2}などが凸関数にあたります。実際、

{ (1-\alpha) x^2 +\alpha y^2 - ((1-\alpha)x+\alpha y )^2 = \alpha (1- \alpha) (x-y)^2 \geq 0}

より、凸関数であることがわかります。

 

目的関数が凸関数であり、制約条件が凸集合であらわされるとき、その問題を凸計画問題といいます。凸計画問題は、局所的な解(local optimal solution)と大域的な解(global optimal solution)が一致するという良い性質を持っています。また、さらに厳しい制約のもと、その解の一意性が保証される場合もあります。このような解析の容易さから、凸計画問題に対する多くの研究が行われてきました。

これに対し、非凸な問題は、一般に局所的最適解と大域的最適解が一致せず、解析は困難なものとなります。

関数が凸であるかどうかを判定するためには、その二回微分のヘッセ行列が半正定値であるかどうかを調べることで求めることができます。(詳細は別記事で...)

以下では、 さらによく知られている問題について紹介します。

{min:c^T x}

{s.t.:Ax = b, x \geq 0} 

ここで{A}{m \times n}次元行列、{b}{n}次元ベクトル、{c}{n}次元ベクトルであり、{x}{n}次元の決定変数です。

この問題は最もよく研究され、利用されてきた問題の一つであり、これを用いて最適性条件や双対定理などの説明を後日行います。

  • 半正定値計画問題(Semidefinite Programming; SDP)

{min:C\bullet X}

{s.t.:A_i \bullet X = b_i \ (i=1,...,m), X \succeq 0} 

ここで、演算子{\bullet}{n}次対称行列{U, V}に対して、{U\bullet V = trace(UV)}で定義され、{A \succeq 0}は行列{A}が半正定値であることをあらわします。{C, A_i}は、それぞれ{n}次対称行列、{X}は、{n\times n}次決定変数となります。形をみて、察する方もいるかもしれませんが、これは線形計画問題の拡張となっています。最小固有値問題などもこれに属します。

 

本記事では、いくつかの特別な最適化問題の例を見てきました。
解こうとしている問題が、どれに属するのかを知ることでその問題の性質を知ることができます。
次回は、気になる方が多いであろう代表的なアルゴリズムについて紹介していきます。 

 

不定期更新ですがよろしくお願いします。
何かあればコメントやツイッターで気軽にお声がけください。