凸最適化 — 概念・手法・応用

凸最適化とは、凸な実行可能集合の上で凸関数を最小化することです。これが重要である主な理由は単純です。こうした凸性の条件が成り立てば、どの局所最小値も大域最小値になるからです。

この保証があるため、凸最適化の問題は一般の最適化問題よりもはるかに信頼しやすくなります。もちろん問題を正しく定式化する必要はありますが、いったんモデルが凸であれば、狭い近傍でだけ最良に見える解を追いかけることはありません。

よくある形は次のとおりです。

$$\text{minimize } f(x)$$

subject to

$$g_i(x) \le 0 \quad \text{for } i=1,\dots,m, \qquad Ax=b,$$

ここで、$f$ と各 $g_i$ は凸であり、等式制約はアフィンです。これらの条件のもとでは、実行可能集合は凸になり、最適化問題全体も凸になります。

凸最適化の定義

関数 $f$ が凸であるとは、その定義域内の任意の 2 点 $x$ と $y$、および任意の $0 \le t \le 1$ に対して、

$$f(tx + (1-t)y) \le t f(x) + (1-t) f(y).$$

が成り立つことをいいます。

平たく言えば、グラフ上の 2 点を結ぶ線分は、グラフの上側に位置します。1 変数では、多くの凸関数はすり鉢状に見えますが、実際の判定基準はこの不等式です。

集合が凸であるとは、その集合が 2 点を含むなら、それらを結ぶ直線上のすべての点も含むことをいいます。

必要なのは次の 2 つです。

• 凸な目的関数
• 凸な実行可能集合

どちらか一方でも欠けると、その問題は凸でなくなる可能性があります。

なぜ凸最適化は解析しやすいのか

最適化が難しいことが多いのは、谷がたくさん存在しうるからです。アルゴリズムは目的関数を改善し続けていても、局所的にしか最良でない点で止まってしまうことがあります。

凸最適化では、その特有の失敗が起こりません。目的関数が凸で、実行可能領域も凸であれば、局所的にこれ以上改善できない点は、すでに大域的に最適です。だからこそ、凸問題は統計、機械学習、制御、オペレーションズ・リサーチで重要なのです。

これは、すべての凸問題が簡単だという意味ではありません。規模が大きかったり、計算コストが高かったりするものもあります。意味するのは、構造が十分に整っているため、優れたアルゴリズムが誤解を招く局所的な挙動に惑わされず、本当の最適解を狙えるということです。

凸最適化の例

次の制約なし問題を考えます。

$$\text{minimize } f(x) = (x-3)^2 + 2.$$

これは凸最適化問題です。$f(x)$ は二次関数で、最高次の係数が正なので、すべての実数上で凸だからです。

最小化する点を求めるために、微分します。

$$f'(x) = 2(x-3).$$

導関数を 0 に等しく置くと、

$$2(x-3)=0 \quad \Rightarrow \quad x=3.$$

次に、目的関数の値を計算します。

$$f(3) = (3-3)^2 + 2 = 2.$$

したがって、最小値は $2$ であり、$x=3$ で達成されます。

この例は単純ですが、中心となる考え方をよく示しています。いったん $x=3$ に到達すれば、どこか別の場所に隠れたもっと低い谷があるわけではありません。

凸最適化の代表的な手法

どの手法を使うかは、問題の構造によって決まります。

滑らかな無制約問題や単純な制約付き問題では、勾配に逆らう方向へ進むことで目的関数を下げられるため、勾配ベースの手法がよく使われます。

多くの制約付き凸問題では、制約を直接扱え、実務でも良い性能を示すことが多いため、内点法が広く用いられます。

非平滑な凸問題では、劣勾配法や近接法のほうが適していることがあります。重要なのはアルゴリズムの一覧そのものではありません。凸という構造があることで、これらのアルゴリズムが安定して働ける土台が得られる、という点です。

凸最適化でよくある間違い

グラフを見ただけで凸だと判断する

あるグラフが 1 つの図ではすり鉢状に見えても、定義域全体や高次元では凸性を満たさないことがあります。簡単なスケッチよりも、定義や標準的な凸性の判定規則のほうが重要です。

制約の重要性を忘れる

目的関数が凸であるだけでは十分ではありません。実行可能集合が非凸なら、問題全体は凸最適化問題ではありません。

すべての臨界点を最小値だとみなす

微分可能な凸関数では、勾配が 0 の点は大域的最小化点です。しかし凸性がなければ、その結論は一般には成り立ちません。

凸と狭義凸を混同する

狭義凸はより強い条件です。狭義凸であれば最小化点が一意になることが多い一方、単なる凸性だけでは一意性は必ずしも保証されません。

凸最適化はどこで使われるか

凸最適化は、現実の問題を凸なコストと凸な制約でモデル化できる場面で現れます。

代表例としては、最小二乗フィッティング、サポートベクターマシン、凸なリスクモデルのもとでのポートフォリオ選択、多くの資源配分問題などがあります。ただし重要なのは具体的なモデルです。選んだ目的関数と制約が本当に凸の仮定を満たすときに限って、その応用は凸になります。

実務で凸性が役立つ場面

凸最適化は、単に数値を 1 つ得たいだけでないときに特に有用です。多くの場合、得られた答えが、自分で書いたモデルに対して本当に最適であるという保証が欲しいからです。

この保証は、工学やデータ分析で重要です。なぜなら、次の 2 つの問いを切り分けられるからです。

1. 数学的な問題を正しく解けたか。
2. その数学的な問題は現実をうまく表すモデルだったか。

凸性は 1 つ目の問いには大いに役立ちます。しかし 2 つ目を自動的に解決してくれるわけではありません。

似た問題を試してみよう

$f(x) = (x+1)^2 + 5$ の最小値を求めてみましょう。次に、凸ではなく凹である $f(x) = -(x+1)^2 + 5$ と比べてみてください。こうして並べて確認すると、凸性の役割がずっと見えやすくなります。

別の例も試したいなら、小さな最小二乗問題を自分で立ててみましょう。凸な誤差関数を最小化することで、安定した最良近似が得られることがわかります。