最適化
概要
最適化（mathematical optimization）とは、許される点の集合 $X$（実行可能集合）の中で目的関数 $f$ の値を最小または最大にする点（最適解）を求める問題と、その性質・解き方を調べる分野の総称である。目的関数と実行可能集合の形により、線形計画・凸最適化・組合せ最適化・変分問題などに分かれる。下半連続な目的関数は、ある水準集合が空でなくコンパクトなら最適解をもつ。微分可能な目的関数の局所最適解では、実行可能集合の接錐に属するすべての方向と勾配との内積が $0$ 以上になり、この条件から、内部の点での勾配 $0$、凸集合の上の変分不等式、非負の条件のもとでの相補性が導かれる。
材料の量の制約のもとで利益を最大にする生産計画、観測データに直線を当てはめて誤差の 2 乗の和を最小にすること、いくつかの都市を巡る経路の長さを最小にすること。これらはどれも「許される選択肢の集合 $X$ の中で、関数 $f$ の値を最小（または最大）にする点を探す」問題である。この形の問題を 最適化問題 といい、その性質と解き方を調べる分野を 最適化（数理最適化）という。最小二乗法・線形計画法・凸最適化・組合せ最適化・Lagrangeの未定乗数法・変分法 は、目的の関数と許される集合の形によって分かれた、最適化の各論である。
この記事では、どの種類にも共通する枠組み（最適値・最適解・局所最適解・問題の書き換え）を定め、各論との関係を表にまとめる。そのうえで、最適解が存在するための条件（thm-opt-existence）と、許される集合の「接錐」を使った 1 次の必要条件（thm-opt-tangent）を証明する。後者は、集合の内部での $\nabla f=0$、凸集合の上での変分不等式、非負の条件のもとでの相補性を一つの形にまとめたものである。
定義
集合 $X$ と関数 $f\colon X\to\mathbb{R}$ の組を 最適化問題（最小化問題）といい、
$$
\text{(P)}\qquad\text{最小化 } f(x)\quad\text{条件 } x\in X
$$
と書く。$f$ を 目的関数、$X$ の元を 実行可能解、$X$ を 実行可能集合 という。
- $p^*:=\inf_{x\in X}f(x)\in[-\infty,\infty]$ を (P) の 最適値 という（$X=\emptyset$ のとき $p^*=\infty$ とする）。$X=\emptyset$ のとき (P) は 実行不可能、$p^*=-\infty$ のとき 非有界 であるという。
- $x^*\in X$ が $f(x^*)=p^*$ を満たすとき、$x^*$ を 最適解 という。最適解があるとき、最適値は 達成される という。
- $X$ が距離空間の部分集合のとき、$x^*\in X$ が 局所最適解 であるとは、ある $r>0$ があって、$d(x,x^*)< r$ を満たすすべての $x\in X$ で $f(x^*)\le f(x)$ となることをいう。
最大化問題「最大化 $f(x)$ 条件 $x\in X$」は、最小化問題「最小化 $-f(x)$ 条件 $x\in X$」と同じ最適解をもち、最適値は符号が反対になる。
実際の問題では、$X$ は $\mathbb{R}^n$ の部分集合で、条件の式で与えられることが多い。
$$
X=\{x\in\mathbb{R}^n\mid g_i(x)\le0\ (i=1,\dots,m),\ h_j(x)=0\ (j=1,\dots,p)\}
$$
の形を最適化問題の 標準形 という（BV04 §4.1.1、p. 127・§4.1.2、p. 129）。条件のない問題（$X=\mathbb{R}^n$）を 制約なし最適化 という。
最適値があっても最適解があるとは限らない。$X=\mathbb{R}$、$f(x)=e^x$ では $p^*=0$ だが、$e^x=0$ となる $x$ はない。$f(x)=x$ では $p^*=-\infty$ で非有界である。
(P) を最適化問題とする。
- $\phi\colon\mathbb{R}\to\mathbb{R}$ が狭義単調増加なら、「最小化 $\phi(f(x))$ 条件 $x\in X$」の最適解と局所最適解は、(P) のものとそれぞれ一致する。
- （エピグラフ形）変数を 1 つ増やした問題
$$ \text{(P}'\text{)}\qquad\text{最小化 } t\quad\text{条件 } x\in X,\ f(x)\le t $$
の最適値は (P) の最適値に等しい。さらに、$(x^*,t^*)$ が (P$'$) の最適解であることと、$x^*$ が (P) の最適解で $t^*=f(x^*)$ であることは同値である。
1：$\phi$ は狭義単調増加なので、$f(x^*)\le f(x)$ と $\phi(f(x^*))\le\phi(f(x))$ は同値である。最適解であることは「すべての $x\in X$ で $f(x^*)\le f(x)$」と同値であり、局所最適解の定義もこの形の不等式だけで書かれている。
2：(P$'$) の実行可能解 $(x,t)$ では $t\ge f(x)\ge p^*$ なので、(P$'$) の最適値は $p^*$ 以上である。逆に $x\in X$ なら $(x,f(x))$ は実行可能で値は $f(x)$ なので、(P$'$) の最適値は $p^*$ 以下である。$x^*$ が (P) の最適解なら $(x^*,f(x^*))$ の値は $p^*$ で最適である。$(x^*,t^*)$ が (P$'$) の最適解なら $p^*=t^*\ge f(x^*)\ge p^*$ なので、$t^*=f(x^*)=p^*$ で $x^*$ は (P) の最適解である。$\square$
エピグラフ形は、目的関数を条件の側に移して、目的関数が 1 次式の問題に直す書き換えである（BV04 §4.1.3、p. 134）。たとえば $f(x)=\max_i(a_i\cdot x+b_i)$ の最小化は、条件 $a_i\cdot x+b_i\le t$（$i=1,\dots,k$）のもとで $t$ を最小にする線形計画問題になる。
最適化の主な種類
目的関数と実行可能集合の形によって、使える定理と解き方が変わる。
| 種類 | 実行可能集合 | 目的関数 | 中心になる定理 | 記事 |
|---|---|---|---|---|
| 制約なし最適化 | $\mathbb{R}^n$ の開集合 | 微分可能 | 臨界点の条件 $\nabla f=0$、Hesse 行列による 2 階の判定 | 極値 |
| 等式制約 | $\{x\mid g(x)=0\}$ | 微分可能 | 正則な点での Lagrange の未定乗数法 | Lagrangeの未定乗数法 |
| 線形計画 | 1 次不等式で決まる集合（多面体） | 1 次式 | 最適解は頂点でとれる、双対定理 | 線形計画法 |
| 凸最適化 | 凸関数の不等式で決まる凸集合 | 凸関数 | 局所最適解は最適解、強双対性、KKT 条件 | 凸最適化 |
| 最小二乗 | $\mathbb{R}^n$ | $\lvert Ax-b\rvert^2$ | 正規方程式 | 最小二乗法 |
| 組合せ最適化 | 有限集合 | 任意 | 最大流最小カット定理、貪欲法とマトロイド | 組合せ最適化 |
| 変分問題 | 関数の集合 | 積分で表された汎関数 | Euler–Lagrange 方程式、直接法 | 変分法 |
連続な変数の問題では、最適解の 存在 と、最適解が満たす 必要条件 の二つが理論の出発点になる。次の節以降でこの二つを、実行可能集合の形を問わない一般的な形で述べる。
最適解の存在
連続関数はコンパクト集合の上で最小値をとる。最適化では、目的関数が連続とは限らず、実行可能集合も有界とは限らないので、次の形が使いやすい。関数 $f\colon X\to\mathbb{R}$ と $\alpha\in\mathbb{R}$ について、$\{x\in X\mid f(x)\le\alpha\}$ を $f$ の 水準集合 という。
$X$ を位相空間、$f\colon X\to\mathbb{R}$ を下半連続な関数とする（半連続性）。ある $\alpha\in\mathbb{R}$ について水準集合 $L_\alpha:=\{x\in X\mid f(x)\le\alpha\}$ が空でなくコンパクトなら、(P) は最適解をもち、最適解の全体は空でないコンパクト集合である。
$f$ の $L_\alpha$ への制限も下半連続なので、空でないコンパクト空間 $L_\alpha$ の上で最小値をとる（半連続性 の定理「コンパクト空間上の極値」）。最小点を $x^*$ とすると $f(x^*)\le\alpha$ であり、$x\notin L_\alpha$ なら $f(x)>\alpha\ge f(x^*)$ なので、$x^*$ は $X$ 全体での最小点、つまり (P) の最適解である。最適解の全体は $\{x\in X\mid f(x)\le f(x^*)\}$ であり、下半連続性から $X$ の閉集合である（半連続性 の命題「開集合・閉集合による特徴づけ」）。これはコンパクト集合 $L_\alpha$ の閉部分集合なので、コンパクトである。$\square$
$X\subset\mathbb{R}^n$ を空でない閉集合、$f\colon X\to\mathbb{R}$ を下半連続な関数とし、$x\in X$ で $\lvert x\rvert\to\infty$ のとき $f(x)\to\infty$ とする（任意の $M$ に対し、$\rho$ があって、$x\in X$、$\lvert x\rvert>\rho$ なら $f(x)>M$）。このとき (P) は最適解をもつ。
$x_0\in X$ をとり $\alpha:=f(x_0)$ とおく。$L_\alpha$ は $x_0$ を含み、$X$ の閉集合（下半連続性）なので $\mathbb{R}^n$ の閉集合である。$M=\alpha$ に対する $\rho$ をとると $L_\alpha\subset\{\lvert x\rvert\le\rho\}$ なので有界である。有界閉集合はコンパクトなので（Heine–Borel の定理）、thm-opt-existence が使える。$\square$
$f$ が連続な場合は 最大値・最小値の定理 の定理「遠くで大きくなる関数の最小値」にあたる。連続性を下半連続性に弱めた分だけ、跳びのある目的関数も扱える。たとえば開集合 $A$ の上で $1$、外で $0$ の関数 $\chi_A$ は下半連続であり（半連続性 の命題「有限値指示関数と集合の開閉性」）、下半連続関数の和は下半連続なので（同じ記事の命題「上限・下限と安全な加法」）、連続な目的関数に「$A$ に入ると $1$ だけ費用がかかる」項 $\chi_A$ を足しても thm-opt-existence が使える。仮定は十分条件であって必要条件ではない。最小二乗問題の目的関数 $\lvert Ax-b\rvert^2$ は、$A$ の核が $0$ でなければ核の方向に動かしても値が変わらないので遠くで大きくならないが、最適解をもつ（最小二乗法 の定理「最小二乗解と正規方程式」）。
1 次の必要条件
最適解の近くでは、実行可能集合の中に向かう方向に動いても $f$ は減らないはずである。「実行可能集合の中に向かう方向」を極限で捉えたものが接錐である。以下 $\mathbb{R}^n$ の内積を $a\cdot b$、長さを $\lvert a\rvert$ と書く。
$X\subset\mathbb{R}^n$、$x^*\in X$ とする。$d\in\mathbb{R}^n$ が $x^*$ での $X$ の 接ベクトル であるとは、$X$ の点列 $x_k$ と正の数列 $t_k\to0$ で
$$
\frac{x_k-x^*}{t_k}\to d\qquad(k\to\infty)
$$
となるものがあることをいう。接ベクトルの全体を $T_X(x^*)$ と書き、$X$ の $x^*$ での 接錐 という。
$x_k=x^*$ とすれば $0\in T_X(x^*)$ であり、$t_k$ を $t_k/\lambda$ に替えれば $d\in T_X(x^*)$、$\lambda>0$ から $\lambda d\in T_X(x^*)$ が分かる。$x^*$ が $X$ の内部の点なら、十分大きな $k$ では $x^*+d/k\in X$ なので、そのような $k$ で $x_k=x^*+d/k$、ほかの $k$ で $x_k=x^*$ とし、$t_k=1/k$ とおけば $d\in T_X(x^*)$ となり、$T_X(x^*)=\mathbb{R}^n$ である。$X$ が凸集合なら、$x\in X$ について $x_k=x^*+(x-x^*)/k\in X$、$t_k=1/k$ により $x-x^*\in T_X(x^*)$ である。
$U\subset\mathbb{R}^n$ を開集合、$X\subset U$、$f\colon U\to\mathbb{R}$ とし、$x^*\in X$ は「最小化 $f(x)$ 条件 $x\in X$」の局所最適解で、$f$ は $x^*$ で（全）微分可能とする。このとき
$$
\nabla f(x^*)\cdot d\ge0\qquad(d\in T_X(x^*))
$$
が成り立つ。
$d\in T_X(x^*)$ とし、$x_k\in X$、$t_k\to0$ を定義のとおりにとる。$x_k\to x^*$ である（$x_k-x^*=t_k\cdot\frac{x_k-x^*}{t_k}$ で、第 2 因子は収束するので有界）。全微分可能性から
$$
f(x_k)=f(x^*)+\nabla f(x^*)\cdot(x_k-x^*)+\varepsilon_k\lvert x_k-x^*\rvert,\qquad\varepsilon_k\to0
$$
と書ける（$x_k=x^*$ のときは $\varepsilon_k=0$ とする）。局所最適性から、十分大きな $k$ で $f(x_k)\ge f(x^*)$ なので、両辺を $t_k>0$ で割って
$$
0\le\nabla f(x^*)\cdot\frac{x_k-x^*}{t_k}+\varepsilon_k\frac{\lvert x_k-x^*\rvert}{t_k}
$$
である。$k\to\infty$ とすると、第 1 項は $\nabla f(x^*)\cdot d$ に、第 2 項は $0\cdot\lvert d\rvert=0$ に収束する。よって $\nabla f(x^*)\cdot d\ge0$ である。$\square$
実行可能集合の形に応じて、この条件は次のよく知られた形になる。
thm-opt-tangent の仮定のもとで、次が成り立つ。
- （内部の点）$x^*$ が $X$ の内部の点なら $\nabla f(x^*)=0$ である。
- （凸集合）$X$ が凸集合なら、すべての $x\in X$ で $\nabla f(x^*)\cdot(x-x^*)\ge0$ である（変分不等式）。逆に、$f\colon\mathbb{R}^n\to\mathbb{R}$ が凸関数で、$X$ が凸集合、$x^*\in X$ で $f$ が微分可能かつ変分不等式が成り立てば、$x^*$ は最適解である。
- （非負の条件）$X=\{x\in\mathbb{R}^n\mid x_i\ge0\ (i=1,\dots,n)\}$ なら、各 $i$ で
$$ \frac{\partial f}{\partial x_i}(x^*)\ge0,\qquad x^*_i\,\frac{\partial f}{\partial x_i}(x^*)=0 $$
である。つまり $x^*_i>0$ の座標では偏微分係数は $0$ である（相補性）。
1：$T_X(x^*)=\mathbb{R}^n$ なので $d$ と $-d$ の両方で $\nabla f(x^*)\cdot d\ge0$、よって $\nabla f(x^*)\cdot d=0$ がすべての $d$ で成り立ち、$\nabla f(x^*)=0$ である（極値 の定理「極値点での勾配（Fermat の定理）」と同じ結論）。
2：前半は $x-x^*\in T_X(x^*)$ による。後半：凸関数は微分可能な点での接平面より上にあるので（凸最適化 の補題「凸関数は接平面より上にある」）、$x\in X$ について $f(x)\ge f(x^*)+\nabla f(x^*)\cdot(x-x^*)\ge f(x^*)$ である。
3：$X$ は凸集合なので 2 が使える。$e_i$ を第 $i$ 基本ベクトルとし、$x=x^*+e_i\in X$ とおくと $\frac{\partial f}{\partial x_i}(x^*)\ge0$ である。$x^*_i>0$ なら $x=x^*-x^*_ie_i\in X$ とおいて $-x^*_i\frac{\partial f}{\partial x_i}(x^*)\ge0$、つまり $\frac{\partial f}{\partial x_i}(x^*)\le0$ なので $\frac{\partial f}{\partial x_i}(x^*)=0$ である。$\square$
$x,y\ge0$ のもとで $f(x,y)=(x-1)^2+(y+2)^2$ を最小化する。制約がなければ最小点は $(1,-2)$ だが、これは実行可能でない。cor-opt-first-order の 3 の条件は
$$
2(x-1)\ge0,\quad 2(y+2)\ge0,\quad x\cdot2(x-1)=0,\quad y\cdot2(y+2)=0
$$
であり、$x,y\ge0$ と合わせると $x=1$、$y=0$ だけが満たす。$f$ は凸で実行可能集合は凸なので、2 の後半により $(1,0)$ が最適解で、最適値は $4$ である。$y$ 座標では偏微分係数 $4$ が正で、条件 $y\ge0$ がちょうど等号で効いている。
等式の条件 $g(x)=0$（$g\colon\mathbb{R}^n\to\mathbb{R}^k$ は $C^1$ 級）で決まる集合 $M$ の正則な点 $a$ では、$\operatorname{Ker}Dg(a)$ のどのベクトルも $M$ の中の曲線の速度として実現できる（Lagrangeの未定乗数法 の補題「接ベクトルを速度にもつ曲線」）。曲線 $\gamma$ に沿って $x_k=\gamma(1/k)$、$t_k=1/k$ とおけば $\operatorname{Ker}Dg(a)\subset T_M(a)$ が分かる。$\operatorname{Ker}Dg(a)$ は $-1$ 倍で閉じているので、thm-opt-tangent から局所最適解 $a$ では $\nabla f(a)\cdot v=0$（$v\in\operatorname{Ker}Dg(a)$）となり、$\nabla f(a)$ は $Dg(a)$ の行ベクトルの 1 次結合になる。これが Lagrange の未定乗数法の結論である（Lagrangeの未定乗数法 の定理「Lagrange の未定乗数法」）。不等式の条件では、微分可能な凸関数で書かれた凸な問題について、Karush–Kuhn–Tucker 条件は最適性の十分条件であり、Slater 条件のもとでは必要条件にもなる（凸最適化 の定理「Karush–Kuhn–Tucker の定理」）。
1 次の条件は必要条件であり、満たしても最適解とは限らない（ex-opt-table の 3 行目）。2 階の条件は 極値 と Hesse行列 で扱う。
降下方向と反復法
1 次の条件を満たさない点からは、値を下げる方向がある。
$U\subset\mathbb{R}^n$ を開集合、$f\colon U\to\mathbb{R}$ を点 $x\in U$ で微分可能とし、$d\in\mathbb{R}^n$ が $\nabla f(x)\cdot d<0$ を満たすとする。このとき、ある $\tau>0$ があって、$0< t<\tau$ なら $f(x+td)< f(x)$ である。とくに $\nabla f(x)\ne0$ なら $d=-\nabla f(x)$ がこの条件を満たす。
全微分可能性から $\frac{f(x+td)-f(x)}t\to\nabla f(x)\cdot d<0$（$t\to+0$）なので、$t>0$ が小さければ左辺は負である。$d=-\nabla f(x)$ なら $\nabla f(x)\cdot d=-\lvert\nabla f(x)\rvert^2<0$ である。$\square$
この命題が、点 $x_k$ から降下方向 $d_k$ に少し進む $x_{k+1}=x_k+s_kd_k$ を繰り返す 反復法 の出発点である。$d_k=-\nabla f(x_k)$ とするのが 勾配降下法、Hesse 行列で 2 次近似を作り $d_k=-\nabla^2f(x_k)^{-1}\nabla f(x_k)$ とするのが Newton 法 である（BV04 §9.3、p. 466・§9.5、p. 484）。線形計画では頂点を渡り歩く単体法（線形計画法 の節「単体法の仕組み」）、条件付きの凸最適化では実行可能集合の内部を進む内点法（BV04 第 11 章、p. 561）が使われる。
反例：条件を外すと崩れること
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-opt-existence の下半連続性 | $X=[0,1]$、$f(0)=1$、$0< x\le1$ で $f(x)=x$ | 最適解が存在する |
| thm-opt-existence の水準集合のコンパクト性 | $X=\mathbb{R}$、$f(x)=e^x$ | 最適解が存在する |
| cor-opt-first-order の 2 の後半の、$f$ の凸性 | $X=[-1,1]$、$f(x)=-x^2$、$x^*=0$ | 変分不等式を満たす点は最適解である |
| cor-opt-first-order の 2 の前半の、$X$ の凸性 | $X=\{x\in\mathbb{R}\mid\lvert x\rvert\ge1\}$、$f(x)=x^2$、$x^*=1$ | 最適解で変分不等式が成り立つ |
| 凸最適化 の定理「局所最適解は大域最適解」の凸性 | $X=[-3,3]$、$f(x)=x^3-3x$ | 局所最適解は最適解である |
1 行目：$\inf f=0$ だが $f(x)=0$ となる $x$ はない。$f(0)=1>0=\liminf_{x\to0}f(x)$ なので $0$ で下半連続でない。水準集合 $L_1=[0,1]$ はコンパクトなので、外れているのは下半連続性だけである。
2 行目：$f$ は連続で $\inf f=0$ だが達成されない。水準集合 $L_\alpha=(-\infty,\log\alpha]$（$\alpha>0$）は有界でなく、$\alpha\le0$ では空である。
3 行目：$f'(0)=0$ なので $f'(0)(x-0)\ge0$ がすべての $x$ で成り立つが、$f(1)=-1<0=f(0)$ である。$f$ は凹で凸でない。0 は最小点ではなく最大点である。
4 行目：$x^*=1$ は最適解（最適値 $1$）であり、thm-opt-tangent の条件 $f'(1)d=2d\ge0$（$d\in T_X(1)=[0,\infty)$）は成り立つ。しかし $x=-1\in X$ では $f'(1)(x-1)=2\cdot(-2)<0$ である。$X$ は凸でないので、$x-x^*$ が接錐に入らない。
5 行目：$f'(x)=3(x^2-1)$、$f''(1)=6>0$ なので $x=1$ は局所最適解で $f(1)=-2$ だが、$f(-3)=-18<-2$ である。$f$ は $[-3,0]$ で凸でない（$f''(x)=6x<0$）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
