目的関数

同義語:objective functionコスト関数cost function

概要

目的関数(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$ ではない)の和の最小点になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 数理最適化, 凸関数, 実対称行列

目的関数(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}$ は凸でない。最適解の集合は同じでも、解き方の選択は目的関数の形に左右される。

目的関数の典型
  1. 1 次式 $f(x)=c^{\top}x$:実行可能集合が 1 次不等式で決まれば 線形計画法 の問題である。生産計画の利益 $c^{\top}x$($c_i$ は製品 $i$ の単価、$x_i$ は生産量)の最大化がその例である。
  2. 2 次式 $f(x)=\frac12x^{\top}Px+q^{\top}x$:$A$ を $m\times n$ 行列、$b\in\mathbb{R}^m$ とすると、最小二乗の目的関数は $\lvert Ax-b\rvert^2=x^{\top}A^{\top}Ax-2b^{\top}Ax+\lvert b\rvert^2$ であり、定数 $\lvert b\rvert^2$ を除けば $P=2A^{\top}A$、$q=-2A^{\top}b$ の場合である(最小二乗法)。
  3. 最大値型 $f(x)=\max_{1\le i\le k}(a_i^{\top}x+b_i)$:1 次式の最大値で、凸だが折れ目で微分できない。エピグラフ形で線形計画に直せる(数理最適化 の命題「問題の書き換え」の後の段落)。
  4. 分離可能 $f(x)=\sum_i\psi_i(x_i)$:変数ごとの関数の和で、実行可能集合も直積なら変数ごとに独立に最小化できる。下の thm-obj-quadratic の証明は、座標を取り替えて 2 次式をこの形にする。
  5. 有限集合の上の関数:都市を巡る順序の全体の上で巡回路の長さを最小化する 巡回セールスマン問題 のように、実行可能集合が空でない有限集合なら最適解はつねに存在するが、要素の個数は膨大になりうる(組合せ最適化)。
  6. 負の対数尤度 $f(\theta)=-\sum_k\log p_\theta(y_k)$:これを最小化する $\theta$ が 最尤推定 の推定量である。

制約と目的関数の受け渡し

集合 $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. $\inf_{x\in E}g(x)=\inf_{x\in X}f(x)$ であり($X=\emptyset$ のときは両辺 $\infty$ とする)、$x^*\in X$ が (P) の最適解であることと、$x^*$ が $g$ の $E$ 全体での最小点で $g(x^*)< \infty$ であることは同値である。
  2. $E=\mathbb{R}^n$ で $X$ が凸集合、$f$ が凸関数なら、$g$ は凸である。すなわち $x,y\in\mathbb{R}^n$、$0\le t\le1$ について $g((1-t)x+ty)\le(1-t)g(x)+tg(y)$ が成り立つ($0\cdot\infty=0$、$a+\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)。

2 次の罰金法の極限

$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) の最適解である。

罰の項は 0 に近づく

$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 次式の目的関数

2 次式は、1 次式の次に基本的な目的関数である。変数ごとの関数の和(分離可能)に直せるので、最小化の様子が完全に分かる。以下、$\operatorname{Im}P$、$\operatorname{Ker}P$ は行列 $P$ の像と核である。

2 次の目的関数の最小化

$P$ を $n$ 次の実対称行列、$q\in\mathbb{R}^n$ とし、$f(x):=\frac12x^{\top}Px+q^{\top}x$($x\in\mathbb{R}^n$)とおく。

  1. $f$ が $\mathbb{R}^n$ で下に有界であることと、$P$ が半正定値かつ $q\in\operatorname{Im}P$ であることは同値である。
  2. 1 の条件のもとで $f$ は最小値をとり、最小点の全体は
    $$ \{x\in\mathbb{R}^n\mid Px=-q\}=x_0+\operatorname{Ker}P $$
    ($x_0$ は $Px_0=-q$ の解の 1 つ)である。最小値は $-\frac12x_0^{\top}Px_0=\frac12q^{\top}x_0$ である。
  3. $f$ がただ 1 つの最小点をもつことと、$P$ が正定値であることは同値である。そのとき最小点は $-P^{-1}q$ である。
固有ベクトルの座標で変数を分ける

実対称行列 の定理「実対称行列のスペクトル定理」により、直交行列 $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)$ の張る直線である。

  1. $q=(-1,-1)$ は $\operatorname{Im}P$ に入る。$s:=x_1+x_2$ とおくと $f=\frac12s^2-s$ で、最小点の全体は直線 $x_1+x_2=1$、最小値は $-\frac12$ である。$x_0=(\frac12,\frac12)$ について $-\frac12x_0^{\top}Px_0=-\frac12$ で、thm-obj-quadratic の 2 と一致する。
  2. $q=(1,-1)$ は $\operatorname{Im}P$ に入らない。$x=t(1,-1)$ とおくと $Px=0$ なので $f=q^{\top}x=2t\to-\infty$($t\to-\infty$)で、下に有界でない。

複数の目的関数

費用を下げたいが品質も上げたい、というように、評価の基準が複数あることが多い。そのときは目的関数がベクトル値になり、「最適」の意味を決め直す必要がある。

Pareto 最適

集合 $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 つの目的関数に置き換えることを スカラー化 という。

スカラー化と Pareto 最適解

集合 $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. すべての $i$ で $w_i>0$ なら、$x^*$ は Pareto 最適解である。
  2. すべての $i$ で $w_i\ge0$ で、$w\ne0$ なら、$x^*$ は弱 Pareto 最適解である。
    逆向きについて、$X$ が $\mathbb{R}^n$ の空でない凸集合で、各 $f_i$ が $X$ の上の凸関数であるとする。
  3. $x^*\in X$(ここでは最小点とは仮定しない)が弱 Pareto 最適解(とくに Pareto 最適解)なら、すべての $i$ で $w_i\ge0$ かつ $w\ne0$ を満たす $w$ で、$x^*$ が $\sum_iw_if_i$ の $X$ の上での最小点となるものがある。
1・2 は直接に、3 は凸集合の分離による

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 行目が示す。

2 つの 2 次関数

$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^*$ はどの重みでも最小点にならない。

関連項目

参考文献

[1]
Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st ed., Cambridge University Press, 2004, §4.1.1(目的関数・コスト関数の語、p. 127)、Example 4.5(制約なしの 2 次の最適化、pp. 140–141)、§4.7.3(Pareto 最適、pp. 177–178)、§4.7.4(スカラー化と凸の場合の逆、pp. 178–180)、Exercise 5.14(2 次の罰金法、p. 277)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する