目的関数(objective function)とは、最適化問題「最小化 $f(x)$ 条件 $x\in X$」で値を最小(または最大)にしたい関数 $f$ のことである。制約は値 $\infty$ をとる項として目的関数に取り込め、連続な等式制約の問題に最適解があれば、2 次の罰金法の最小点の集積点は最適解である。$P$ を実対称行列とする 2 次式 $\frac12x^{\top}Px+q^{\top}x$ が下に有界であることは、$P$ が半正定値で $q$ が $P$ の像に入ることと同値で、そのとき最小点の全体は $Px=-q$ の解の全体である。目的関数が複数あるときは、正の重みの和の最小点は Pareto 最適解であり、凸集合の上の凸関数の場合は、弱 Pareto 最適解がどれも $0$ 以上の重み(すべてが $0$ ではない)の和の最小点になる。
目的関数(objective function)とは、最適化問題「最小化 $f(x)$ 条件 $x\in X$」で、値を最小(または最大)にしたい関数 $f$ のことである。許される点の集合 $X$(実行可能集合)が「何を選べるか」を表すのに対し、目的関数は「選んだものをどう評価するか」を表す。生産計画の利益、データへの当てはめの誤差、巡回路の長さ、統計モデルの負の対数尤度は、どれも目的関数の例である。
最適化問題の一般的な枠組み(最適値・最適解・局所最適解、最適解の存在、1 次の必要条件)は 数理最適化 で扱う。この記事では目的関数そのものに目を向け、次のことを述べる。制約は、値 $\infty$ をとる項や、条件がどれだけ満たされないかに応じた罰の項として目的関数に取り込むことができる(prop-obj-indicator、prop-obj-penalty)。2 次式の目的関数については、下に有界であるための条件と最適解の全体が 2 次の部分の行列の固有値・固有ベクトルと 1 次の部分の係数で完全に決まる(thm-obj-quadratic)。目的関数が複数あるときは「最適」の意味が Pareto 最適に変わり、重み付きの和をとるスカラー化で Pareto 最適解が得られ、凸の場合には逆も成り立つ(thm-obj-scalarization)。
集合 $X$ と関数 $f\colon X\to\mathbb{R}$ について、最適化問題
$$
\text{(P)}\qquad\text{最小化 } f(x)\quad\text{条件 } x\in X
$$
の $f$ を 目的関数 という。最大化問題「最大化 $f(x)$ 条件 $x\in X$」の $f$ も目的関数という。より一般に、集合 $E$ の上の $(-\infty,\infty]$ に値をとる関数 $g$ を目的関数とする問題「最小化 $g(x)$ 条件 $x\in E$」も考え、$\operatorname{dom}g:=\{x\in E\mid g(x)< \infty\}$ を $g$ の 実効定義域 という。
最大化問題は、目的関数を $-f$ に替えた最小化問題と同じ最適解をもつので(数理最適化 の定義「最適化問題・最適値・最適解」)、以下では最小化で述べる。
$X\subset\mathbb{R}^n$ が不等式 $f_i(x)\le0$ と等式 $h_j(x)=0$ で与えられる標準形では、$f_0$ を目的関数、$f_i$・$h_j$ を制約関数と呼び分ける。目的関数は コスト関数(cost function)とも呼ばれる(BV04 §4.1.1, p. 127)。分野によって、損失の平均である経験損失(機械学習)、効用関数・利得(経済学・ゲーム理論)、エネルギー(物理)などの名で現れるものも、それぞれの問題の目的関数である。
目的関数を狭義単調増加な関数 $\phi$ で $\phi\circ f$ に替えても最適解は変わらず、目的関数を変数 $t$ と条件 $f(x)\le t$ に置き換えるエピグラフ形の書き換えもできる(数理最適化 の命題「問題の書き換え」)。ただし、$\phi\circ f$ は凸性や微分可能性などの性質を保つとは限らない。たとえば $f(x)=x^2$ は凸だが、$\phi(u)=\sqrt u$($u\ge0$)を合成した $\lvert x\rvert$ は $0$ で微分できず、$\phi(u)=-e^{-u}$ を合成した $-e^{-x^2}$ は凸でない。最適解の集合は同じでも、解き方の選択は目的関数の形に左右される。
集合 $X\subset E$ について、$\iota_X(x):=0$($x\in X$)、$\iota_X(x):=\infty$($x\notin X$)とおく。これは凸解析で使う標示関数で、$0$ と $1$ をとる 指示関数 とは値が異なる。
$E$ を集合、$X\subset E$、$f\colon E\to\mathbb{R}$ とし、$g:=f+\iota_X\colon E\to(-\infty,\infty]$ とおく。
1:$x\notin X$ では $g(x)=\infty$、$x\in X$ では $g(x)=f(x)$ なので、下限は $X$ の上の $f$ の下限に等しい。$X\ne\emptyset$ なら $g$ の最小点は $g$ の値が有限な点、すなわち $X$ の点の中で $f$ を最小にする点であり、逆も同じである。
2:$t=0$ または $t=1$ なら両辺は等しい。$0< t< 1$ とする。$x,y$ の一方が $X$ にないなら右辺は $\infty$ で、不等式は成り立つ。$x,y\in X$ なら $X$ の凸性から $(1-t)x+ty\in X$ で、左辺は $f((1-t)x+ty)\le(1-t)f(x)+tf(y)$ である。$\square$
こうして制約付きの問題は、値 $\infty$ を許した目的関数の制約なしの問題として書ける。凸最適化の理論で目的関数を拡張実数値で扱うのはこのためである。ただし $g$ は $X$ の外で値 $\infty$ をとるので、$X$ の境界をまたぐと値が有限から $\infty$ へ跳び、微分を使う解き方はそのままでは使えない。そこで、条件がどれだけ満たされないかに応じて有限の大きさの罰を与える項を目的関数に足し、罰を次第に重くしていく方法がある。$\lvert h(x)\rvert^2$ を罰の項にするものを 2 次の罰金法(quadratic penalty method)という(BV04 Exercise 5.14, p. 277)。
$f\colon\mathbb{R}^n\to\mathbb{R}$ と $h\colon\mathbb{R}^n\to\mathbb{R}^m$ を連続とし、$X:=\{x\mid h(x)=0\}$ の上の $f$ の最小化問題 (P) が最適解 $\bar x$ をもつとする。$\mu>0$ について $Q_\mu(x):=f(x)+\mu\lvert h(x)\rvert^2$ とおく。$\mu_k\to\infty$ とし、各 $k$ で $x_k$ が $Q_{\mu_k}$ の $\mathbb{R}^n$ 全体での最小点であるとする。このとき、点列 $(x_k)$ の集積点はどれも (P) の最適解である。
$h(\bar x)=0$ なので、$x_k$ の最小性から
$$
f(x_k)\le f(x_k)+\mu_k\lvert h(x_k)\rvert^2=Q_{\mu_k}(x_k)\le Q_{\mu_k}(\bar x)=f(\bar x)
$$
である。よって $f(x_k)\le f(\bar x)$ かつ $\lvert h(x_k)\rvert^2\le(f(\bar x)-f(x_k))/\mu_k$ である。部分列 $x_{k_j}\to x^*$ をとる。$f$ の連続性から $f(x_{k_j})\to f(x^*)$ なので分子 $f(\bar x)-f(x_{k_j})$ は有界で、$\mu_{k_j}\to\infty$ より $\lvert h(x_{k_j})\rvert^2\to0$ である。$h$ の連続性から $h(x^*)=0$、すなわち $x^*\in X$ である。また $f(x^*)=\lim_jf(x_{k_j})\le f(\bar x)$ で、$\bar x$ は最適解なので $f(x^*)=f(\bar x)$ であり、$x^*$ は最適解である。$\square$
たとえば $f(x)=x_1^2+x_2^2$、$h(x)=x_1+x_2-2$ では、(P) の最適解は $(1,1)$ である。$Q_\mu$ は狭義凸で座標の入れ替えで変わらないので、ただ 1 つの最小点は $x_1=x_2=s$ の形であり、$2s^2+\mu(2s-2)^2$ を $s$ で微分して $0$ とおくと $s=2\mu/(1+2\mu)$ を得る。$\mu\to\infty$ で $(s,s)\to(1,1)$ となるが、各 $\mu$ では $h=-2/(1+2\mu)\ne0$ で、罰金法の最小点は実行可能集合の外から近づく。
2 次式は、1 次式の次に基本的な目的関数である。変数ごとの関数の和(分離可能)に直せるので、最小化の様子が完全に分かる。以下、$\operatorname{Im}P$、$\operatorname{Ker}P$ は行列 $P$ の像と核である。
$P$ を $n$ 次の実対称行列、$q\in\mathbb{R}^n$ とし、$f(x):=\frac12x^{\top}Px+q^{\top}x$($x\in\mathbb{R}^n$)とおく。
実対称行列 の定理「実対称行列のスペクトル定理」により、直交行列 $U$ と実数 $\lambda_1,\dots,\lambda_n$ で $P=U\operatorname{diag}(\lambda_1,\dots,\lambda_n)U^{\top}$ となるものがある。$U$ の第 $i$ 列を $u_i$ とし、$y:=U^{\top}x$、$c:=U^{\top}q$ とおくと $x^{\top}Px=\sum_i\lambda_iy_i^2$、$q^{\top}x=c^{\top}y$ なので
$$
f(x)=\sum_{i=1}^{n}\Bigl(\frac12\lambda_iy_i^2+c_iy_i\Bigr)
$$
である。$y\mapsto Uy$ は $\mathbb{R}^n$ の全単射なので、$f$ の性質はこの右辺を $y\in\mathbb{R}^n$ の関数として調べればよい。$\operatorname{Im}P=U\operatorname{Im}\operatorname{diag}(\lambda_i)$ なので、$q\in\operatorname{Im}P$ は「$\lambda_i=0$ となる $i$ では $c_i=0$」と同値である。また $P$ が半正定値であることはすべての $\lambda_i\ge0$ と同値である。
1:条件が成り立たないとする。ある $i$ で $\lambda_i< 0$ なら、$x=tu_i$($y=te_i$)とおくと $f=\frac12\lambda_it^2+c_it\to-\infty$($t\to\infty$)である。ある $i$ で $\lambda_i=0$、$c_i\ne0$ なら、$x=tu_i$ で $f=c_it$ は $t$ を $-c_i$ と同じ符号の方向に大きくすると $-\infty$ に発散する。どちらの場合も $f$ は下に有界でない。逆に条件が成り立てば、$\lambda_i>0$ の項は
$$
\frac12\lambda_iy_i^2+c_iy_i=\frac{\lambda_i}{2}\Bigl(y_i+\frac{c_i}{\lambda_i}\Bigr)^2-\frac{c_i^2}{2\lambda_i}\ge-\frac{c_i^2}{2\lambda_i}
$$
を満たし、$\lambda_i=0$ の項は $c_i=0$ なので $0$ である。よって $f\ge-\sum_{\lambda_i>0}c_i^2/(2\lambda_i)$ で、下に有界である。
2:1 の計算から、$f$ の値 $-\sum_{\lambda_i>0}c_i^2/(2\lambda_i)$ が達成されるのは、$\lambda_i>0$ のすべての $i$ で $y_i=-c_i/\lambda_i$ となるときであり、$\lambda_i=0$ の $y_i$ は任意である。これは「すべての $i$ で $\lambda_iy_i+c_i=0$」と同値であり($\lambda_i=0$ では $c_i=0$ なので自動的に成り立つ)、$\operatorname{diag}(\lambda_i)y+c=U^{\top}(Px+q)$ なので $Px=-q$ と同値である。この 1 次方程式の解の全体は $x_0+\operatorname{Ker}P$ である。最小値は $Px_0=-q$ を代入して $\frac12x_0^{\top}Px_0+q^{\top}x_0=\frac12x_0^{\top}Px_0-x_0^{\top}Px_0=-\frac12x_0^{\top}Px_0$ であり、$q^{\top}x_0=-x_0^{\top}Px_0$ なのでこれは $\frac12q^{\top}x_0$ に等しい。
3:最小点があれば $f$ は下に有界なので、1 により 1 の条件が成り立つ。最小点がただ 1 つなら、2 により $\operatorname{Ker}P=0$ で、半正定値と合わせてすべての $\lambda_i>0$、すなわち $P$ は正定値である。逆に $P$ が正定値なら $P$ は正則で $\operatorname{Im}P=\mathbb{R}^n\ni q$ なので 1 の条件が成り立ち、2 により最小点の全体は $-P^{-1}q+\{0\}$ である。$\square$
$P$ が半正定値の場合は BV04 Example 4.5(pp. 140–141)に同じ場合分けがある。$P$ が正定値の場合は 正定値行列 の注意「極値の判定と最適化」でも平方完成で示されている。上の定理は、$P$ が半正定値でない場合も含めて、下に有界であることの必要十分条件を与えている。
最小二乗の目的関数(ex-obj-types の 2)では $P=2A^{\top}A$ は半正定値で($x^{\top}A^{\top}Ax=\lvert Ax\rvert^2\ge0$)、$\operatorname{Ker}A^{\top}A=\operatorname{Ker}A$ と、対称行列の像は核の直交補空間であることから $\operatorname{Im}A^{\top}A=(\operatorname{Ker}A)^{\perp}=\operatorname{Im}A^{\top}$ なので $q=-2A^{\top}b\in\operatorname{Im}P$ である。したがって最小二乗問題はつねに最適解をもち、その全体は正規方程式 $A^{\top}Ax=A^{\top}b$ の解の全体である(最小二乗法 の定理「最小二乗解と正規方程式」と同じ結論)。
$P=\begin{pmatrix}1&1\\1&1\end{pmatrix}$ の固有値は $2$ と $0$ で、$\operatorname{Im}P$ は $(1,1)$ の張る直線、$\operatorname{Ker}P$ は $(1,-1)$ の張る直線である。
費用を下げたいが品質も上げたい、というように、評価の基準が複数あることが多い。そのときは目的関数がベクトル値になり、「最適」の意味を決め直す必要がある。
集合 $X$ と関数 $f_1,\dots,f_k\colon X\to\mathbb{R}$ について、$x,y\in X$ とする。すべての $i$ で $f_i(y)\le f_i(x)$ であり、ある $i$ で $f_i(y)< f_i(x)$ であるとき、$y$ は $x$ を 優越する という。$x\in X$ を優越する $y\in X$ がないとき、$x$ を Pareto 最適解 という。すべての $i$ で $f_i(y)< f_i(x)$ となる $y\in X$ がないとき、$x$ を 弱 Pareto 最適解 という。
Pareto 最適解は弱 Pareto 最適解である。どれか 1 つの $f_i$ を下げるには別の $f_j$ を上げなければならない点が Pareto 最適解で、その全体は一般に 1 点ではない(BV04 §4.7.3, pp. 177–178)。複数の目的関数を、重み $w_i\ge0$ をつけた和 $\sum_iw_if_i$ という 1 つの目的関数に置き換えることを スカラー化 という。
集合 $X$ と関数 $f_1,\dots,f_k\colon X\to\mathbb{R}$、$w=(w_1,\dots,w_k)\in\mathbb{R}^k$ について、$x^*\in X$ が $\sum_iw_if_i$ の $X$ の上での最小点であるとする。
1:$y\in X$ が $x^*$ を優越するなら、すべての $i$ で $w_i(f_i(y)-f_i(x^*))\le0$ で、ある $i$ では $< 0$ なので、$\sum_iw_if_i(y)< \sum_iw_if_i(x^*)$ となり、$x^*$ の最小性に反する。
2:すべての $i$ で $f_i(y)< f_i(x^*)$ となる $y\in X$ があれば、$w_i\ge0$ と $w\ne0$ から $\sum_iw_i(f_i(y)-f_i(x^*))< 0$ となり、同じく矛盾する。
3:$F(x):=(f_1(x),\dots,f_k(x))$ とし、
$$
\mathcal{A}:=\{t\in\mathbb{R}^k\mid\text{ある }x\in X\text{ ですべての }i\text{ について }f_i(x)\le t_i\},\qquad \mathcal{B}:=\{t\in\mathbb{R}^k\mid\text{すべての }i\text{ で }t_i< f_i(x^*)\}
$$
とおく。$\mathcal{A}$ は凸集合である:$t,t'\in\mathcal{A}$ をそれぞれ $x,x'\in X$ が満たし、$0\le s\le1$ なら、$X$ の凸性から $(1-s)x+sx'\in X$ で、$f_i$ の凸性から $f_i((1-s)x+sx')\le(1-s)f_i(x)+sf_i(x')\le(1-s)t_i+st'_i$ である。$\mathcal{B}$ は空でない開凸集合である。$x^*$ は弱 Pareto 最適解なので $\mathcal{A}\cap\mathcal{B}=\emptyset$ である。
Hahn–Banachの分離定理 の定理「Hahn–Banachの定理(第一幾何形)」を $\mathbb{R}^k$ の開凸集合 $\mathcal{B}$ と凸集合 $\mathcal{A}$ に使うと、$0$ でない線形汎関数、すなわち $0$ でない $w\in\mathbb{R}^k$ と実数 $\alpha$ で
$$
w^{\top}u< \alpha\le w^{\top}v\qquad(u\in\mathcal{B},\ v\in\mathcal{A})
$$
となるものがある。$w_j< 0$ となる $j$ があったとすると、$v:=F(x^*)\in\mathcal{A}$ と $r>0$ について $v+re_j\in\mathcal{A}$ であり、$w^{\top}(v+re_j)=w^{\top}v+rw_j\to-\infty$($r\to\infty$)となって $\alpha\le w^{\top}(v+re_j)$ に反する。よってすべての $w_i\ge0$ である。$\varepsilon>0$ について $F(x^*)-\varepsilon(1,\dots,1)\in\mathcal{B}$ なので $w^{\top}F(x^*)-\varepsilon\sum_iw_i< \alpha$ であり、$\varepsilon\to0$ として $w^{\top}F(x^*)\le\alpha$ である。一方、$x\in X$ なら $F(x)\in\mathcal{A}$ なので $\alpha\le w^{\top}F(x)$ である。したがって $\sum_iw_if_i(x^*)\le\sum_iw_if_i(x)$($x\in X$)であり、$x^*$ は $\sum_iw_if_i$ の最小点である。$\square$
1 と、凸の場合に Pareto 最適解について述べた 3 は BV04 §4.7.4(pp. 178–180)にあり、そこでは $w\ge0$ の重みで得られる最小点が Pareto 最適とは限らないことも注意されている(下の反例の表の 4 行目)。3 で重みの成分に $0$ を許す必要があることは ex-obj-pareto の端点が示し、凸性を外せないことは反例の表の 5・6 行目が示す。
$X=\mathbb{R}$、$f_1(x)=x^2$、$f_2(x)=(x-1)^2$ とする。Pareto 最適解の全体は区間 $[0,1]$ である。実際、$x< 0$ なら $y=0$ が、$x>1$ なら $y=1$ が $x$ を優越する。$x\in[0,1]$ について $f_1(y)\le f_1(x)$ かつ $f_2(y)\le f_2(x)$ なら $\lvert y\rvert\le x$ かつ $\lvert y-1\rvert\le1-x$ で、後者から $y\ge x$、前者と合わせて $y=x$ なので、$x$ を優越する点はない。
$w_1,w_2>0$ について $w_1x^2+w_2(x-1)^2$ を微分して $0$ とおくと、最小点は $x=w_2/(w_1+w_2)$ で、$(0,1)$ のすべての点がこの形で得られる(thm-obj-scalarization の 1)。端点 $0$、$1$ は $w=(1,0)$、$(0,1)$ で得られる。この例は凸なので、thm-obj-scalarization の 3 のとおり、すべての Pareto 最適解がスカラー化で得られている。
thm-obj-quadratic と thm-obj-scalarization の仮定を 1 つずつ外す。
| 外す仮定 | 例 | 成り立たなくなること |
|---|---|---|
| thm-obj-quadratic の 1 の「$P$ が半正定値」($q\in\operatorname{Im}P$ は保つ) | $P=\operatorname{diag}(1,-1)$、$q=0$ | $f$ が下に有界 |
| thm-obj-quadratic の 1 の「$q\in\operatorname{Im}P$」(半正定値は保つ) | $P=\operatorname{diag}(1,0)$、$q=(0,1)$ | $f$ が下に有界 |
| thm-obj-quadratic の 3 の「$P$ が正定値」(半正定値・$q\in\operatorname{Im}P$ は保つ) | $P=\operatorname{diag}(1,0)$、$q=0$ | 最小点がただ 1 つ |
| thm-obj-scalarization の 1 の「すべての $w_i>0$」 | $X=[0,1]^2$、$f_1=x_1$、$f_2=x_2$、$w=(1,0)$、$x^*=(0,1)$ | 最小点が Pareto 最適解 |
| thm-obj-scalarization の 3 の「$X$ が凸」 | $X=\{(0,1),(1,0),(\frac35,\frac35)\}$、$f_i=x_i$、$x^*=(\frac35,\frac35)$ | Pareto 最適解がスカラー化の最小点 |
| thm-obj-scalarization の 3 の「$f_i$ が凸」 | $X=[0,1]$、$f_1=x$、$f_2=1-x^2$、$x^*=\frac12$ | Pareto 最適解がスカラー化の最小点 |
1 行目:$q=0\in\operatorname{Im}P$ で、$f=\frac12(x_1^2-x_2^2)$ は $x=(0,t)$ で $-\frac12t^2\to-\infty$ である。$P$ は固有値 $-1$ をもち半正定値でない。
2 行目:$P$ は半正定値で、$\operatorname{Im}P$ は第 1 座標軸だから $q=(0,1)\notin\operatorname{Im}P$ である。$f=\frac12x_1^2+x_2$ は $x=(0,t)$、$t\to-\infty$ で $-\infty$ に発散する。
3 行目:$P$ は半正定値で $q=0\in\operatorname{Im}P$ だが正定値でない。$f=\frac12x_1^2$ の最小点は $x_1=0$ を満たすすべての点で、ただ 1 つではない。
4 行目:$f_1,f_2$ は 1 次式で凸、$X$ は凸、$w=(1,0)$ は $w\ge0$、$w\ne0$ を満たし、$x_1$ の最小点の全体は $\{0\}\times[0,1]$ なので $x^*=(0,1)$ は最小点である。しかし $(0,0)$ は $f_1$ で等しく $f_2$ で小さいので $x^*$ を優越し、$x^*$ は Pareto 最適解でない(2 のとおり弱 Pareto 最適解ではある)。
5 行目:$f_i$ は 1 次式で凸だが、$X$ は 3 点の集合で凸でない。$(0,1)$ は第 2 成分が、$(1,0)$ は第 1 成分が $\frac35$ より大きいので、どちらも $x^*$ を優越せず、$x^*$ は Pareto 最適解である。$w\ge0$、$w\ne0$ について 3 点での $w_1x_1+w_2x_2$ の値は $w_2$、$w_1$、$\frac35(w_1+w_2)$ で、$\min(w_1,w_2)\le\frac12(w_1+w_2)< \frac35(w_1+w_2)$ だから $x^*$ はどの重みでも最小点にならない。
6 行目:$X$ は凸、$f_1$ は 1 次式で凸だが、$f_2$ は凹で凸でない。$[0,1]$ で $f_1$ は狭義増加、$f_2$ は狭義減少なので、$f_1(y)\le f_1(\frac12)$ かつ $f_2(y)\le f_2(\frac12)$ なら $y\le\frac12\le y$ で $y=\frac12$ となり、$x^*$ は Pareto 最適解である。$w\ge0$、$w\ne0$ について、$x=0,\frac12,1$ での $w_1x+w_2(1-x^2)$ の値は $w_2$、$\frac12w_1+\frac34w_2$、$w_1$ である。$w_1\le w_2$ なら $\frac12w_1+\frac34w_2\le w_1$ から $w_2\le\frac23w_1\le\frac23w_2$ となって $w_2=0$、したがって $w_1=0$ となり $w\ne0$ に反する。$w_2< w_1$ なら $\frac12w_1+\frac34w_2\le w_2$ から $w_1\le\frac12w_2\le w_2$ となって $w_2< w_1$ に反する。よって $x^*$ はどの重みでも最小点にならない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する