シンギュラリティは近い ～全人類がいますぐ注目すべき特異点論と多目的最適化の知られざる関係～

はじめに

Fujitsu Advent Calendar 2017 も25日目，とうとう最終日となりました．振り返れば今年1年，チェス・将棋・囲碁でトッププロを上回るAIが登場したり，日本のスパコンが環境性能世界ランキング上位を独占したり，ヒト型ロボットがバク宙したりと，シンギュラリティの到来を思わせるようなビッグニュースが度々報じられました．そんな1年の締めくくりとして，シンギュラリティについて解説しようと思います．

さて，これから解説するシンギュラリティは，2045年に人工知能がどうこうという話ではなく，数学における 可微分写像の特異点論 (singularity theory of differentiable mappings) です．写像の微分がフルランクでない点＝写像が特別な振る舞いをする点を調べる理論です．

……待って！ブラウザをそっ閉じないで！この可微分写像の特異点論こそが「技術的特異点」に出てくる特異点の語源にもなった理論なんです¹．しかも最近になって，多目的最適化と深い関係がある，ということが分かってきたため，一部で大変な盛り上がりを見せています²．そんなわけで，この記事では多目的最適化と特異点論の関係について解説します³．

この記事はまだ書きかけです．定理と書いてある内容が平気で間違ってたりしますのでご注意ください．正確なところが知りたい人は文末に挙げた参考文献をあたってください．来年のAdvent Calendarまでには書き上げたい…
$
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\intr}{int}
\DeclareMathOperator{\cl}{cl}
\DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\comp}{\circ}
\DeclareMathOperator{\minimize}{minimize}
\DeclareMathOperator{\subjto}{subject to}
\DeclareMathOperator{\st}{sush that}
\newcommand{\tforall}{\text{ for all }}
\newcommand{\texists}{\text{ for some }}
\newcommand{\A}{\mathcal{A}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Pos}{\mathrm{Pos}}
\newcommand{\pd}{\partial}
\newcommand{\bd}{\partial}
\newcommand{\homeo}{\simeq}
\newcommand{\dominates}{\prec}
\newcommand{\sdominates}{\prec_{\mathrm s}}
\newcommand{\faceof}{\triangleleft}
\newcommand{\set}[1]{\left \{\,#1\, \right \}}
\newcommand{\bra}[1]{\left [\,#1\,\right ]}
\newcommand{\par}[1]{\left (\,#1\,\right )}
\newcommand{\abs}[1]{\left |\,#1\,\right |}
$

この記事の流れ

さっそく本題に入りたいところですが，多目的最適化や特異点論を説明するにはそれなりに予備知識が必要なので，理系の学部教養レベル（多変数の微積分と線形代数）だけで取り掛かれるところから準備していきます．まずは最も基本的な単目的最適化を紹介し，モース理論との関係を示します．その議論を多目的最適化に拡張して，特異点論との関係を示します．その後，多目的最適化に特有のトピックとして，解集合の構造に関する研究を紹介します．最後に，本分野の発展に重要と思われる未解決問題を紹介して終わりたいと思います．

多目的最適化と特異点論はいずれも，広大な研究領域を指す言葉です．それらのサブトピックは多岐に渡り，細部にまで両者は関連し合っているため，1本の記事ですべてを紹介することはとてもできません．この記事では，両者の関係のなかでも最も根幹の部分を提示することに留めたいと思います．様々な話題を駆け足に巡っていきますが，本来，それぞれにつき1冊の本が書けるくらいの内容をもっています．いずれも代表的な文献を紹介しますので，各論に興味を持った方はそちらを当たってみてください．

単目的最適化

最適化とは，「与えられた条件下で最も良い答えを見つけよ」という問題です．例えば，以下のような問題はみな最適化問題として定式化され，今日の学術界や産業界で応用されています．

• 工業製品を設計する
  • 規格の範囲内で最も性能の高い製品を設計する
• 生産計画や運用計画を立てる
  • 限られた資源を最も利益が大きくなるように配分する
• 機械学習を訓練する
  • 学習器のパラメータを最も予測精度が高くなるようにチューニングする

これらの問題を統一的に表す方法を定式化しておきましょう．

(定義)
関数 $f,g_1,\dots,g_l:\R^n\to\R$ が与えられたとき，集合 $X:=\set{x\in\R^n\mid g_1(x)\le0,\dots,g_l(x)\le0}$ 上で $f$ を最適化する問題を 単目的最適化問題 (single-objective optimization problem) といい，以下のように書く：

\begin{align}
\minimize \ & f(x)\\
\subjto   \ & g_1(x)\le0,\dots,g_l(x)\le0.
\end{align}

ここで，関数 $f$ を 目的関数 (objective function) という．関数 $g_1,\dots,g_l$ を 制約関数 (constraint function) という．集合 $X$ を 実行可能領域 (feasible region) という．

「関数を最適化する」とは関数の最小点を求めることを意味します．

(定義)
点 $x\in X$ が関数 $f:X\to\R$ の 最小点 (minimum point) であるとは， $f(y)<f(x)$ をみたす $y\in X$ が存在しないことをいう．

とはいえ， $X$ 全体のなかから大域的な最小点を見つけ出すことは特別な場合を除いて難しいです．そこで，局所的な最小点を求めることを目標とする場合もあります．

(定義)
点 $x\in X$ が関数 $f:X\to\R$ の 局所最小点 (locally minimum point) であるとは， $x$ の近傍 $U$ が存在して， $f(y)<f(x)$ をみたす $y\in U$ が存在しないことをいう．

モース理論

モース理論はもともと，数学において 多様体 (manifold) とよばれる図形の繋がり方を調べるために開発された技術です．多様体を直接調べる代わりに，その多様体上にどんな関数が定義できるかを調べることで，多様体の繋がり方を探ることができます．しかし，今回は多様体の話は持ち出さず，多様体の繋がり方を調べる道具であるハンドル分解やモースホモロジーなどの話題も割愛します．ユークリッド空間上のモース理論を考え，最適化との関係を見いだせる部分をピックアップして紹介します⁴．

本節を通して $X=\R^n$ とします．つまり，最適化問題としては制約関数がない場合を考えることに相当します．また，関数は $C^\infty$ 級，すなわち何回でも微分できるものとします．なお，制約を考えた場合には， $X$ は 滑層分割集合 (stratified set) というものになります．本稿では説明しませんが，滑層分割集合上のモース理論もあり，本節とほぼ同様の議論が可能です．

多変数関数の1階微分と2階微分を考えます．

(定義)
関数 $f:\R^n\to\R$ に対して，1階導関数のベクトル$$D f(y):=\par{\frac{\pd f}{\pd x_1}(y),\dots,\frac{\pd f}{\pd x_n}(y)}^t$$を 勾配 (gradient) といい，2階導関数の行列

D^2f(y):=
\begin{pmatrix}
\dfrac{\pd^2 f}{\pd x_1 \pd x_1}(x) & \cdots & \dfrac{\pd^2 f}{\pd x_1 \pd x_n}(x)\\
\vdots & \ddots & \vdots\\
\dfrac{\pd^2 f}{\pd x_n \pd x_1}(x) & \cdots & \dfrac{\pd^2 f}{\pd x_n \pd x_n}(x)
\end{pmatrix}

を へッセ行列 (Hessian matrix) という．

1変数関数の増減表を思い出してください．一般的な点の近傍では関数値は単調増加または単調減少し，1階微分が消える特別な点の近傍では増減が変わるのでした．増減がどう変化するかは，2回微分を見ればわかるのでした．これを多変数に拡張します．

(定義)
関数 $f:\R^n\to\R$ に対して，点 $x\in\R^n$ が $Df(x)=0$ をみたすとき， $x$ を 臨界点 (critical point) といい， さもなければ 正則点 (regular point) という．点 $v\in\R$ の逆像 $f^{-1}(v):=\set{x\in\R^n\mid f(x)=v}$ が臨界点を含むとき， $v$ を 臨界値 (critical value) といい，さもなければ 正則値 (regular value) という．臨界点 $x$ が 非退化 (nondegenerate) とは， ヘッセ行列 $D^2f(x)$ が正則すなわち $\rank D^2f(x)=n$ であることをいう．

モース理論では，2階微分で増減の変化が記述できるような関数を扱います．

(定義)
関数 $f:\R^n\to\R$ が モース関数 (Morse function) とは， $f$ のすべての臨界点が非退化であることをいう．

いま興味があるのは関数の臨界点の近傍での振る舞い（関数値の増減の変化）です．大域的には異なる関数であっても，1点の近傍だけに限ればまったく同じ振る舞いをする関数はたくさんあります．それらは臨界点の近傍を調べるうえでは同じと思って差し支えないので，まとめて1つと考えます．

(定義)
点 $p\in\R^n$ について $C^\infty$ 写像全体の集合 $C^\infty(\R^n,\R^m)$ に同値関係 $f \sim g$ を以下で定義する：$$f \sim g:\Leftrightarrow\mbox{ある $p$ の近傍 $U$ が存在して $f|_U=g|_U$}$$この同値類 $\bra{f}$ を $f$ の 写像芽 (map germ) と呼び，写像芽をその代表元（写像）と同一視して， $f:(\R^n,p)\to\R^m$ と表す．

この概念は本節以降も使うので写像で定義しておきました．今考えているのは $m=1$ のケースで，この場合は関数芽とよびます．以下でも，本節以降も使う概念は写像で定義するので，同様に読み替えてください．

さて，多変数関数の臨界点の関数芽としてどんなものが現れるでしょうか．1変数関数では，臨界点は極大点・極小点・変曲点に分類できるのでした．いずれの臨界点も，関数のソース（変数）に座標変換を行っても，ターゲット（値）に定数を加えても，別のタイプの臨界点には変化しません．多変数関数でも，これらの変換で不変な分類を考えます．

(定義)
2つの写像芽 $f:(\R^n,p)\to(\R^m,q)$ と $g:(\R^n,p')\to(\R^m,q')$ が $\mathcal R$ 同値 ($\mathcal R$-equivalent) とは，ある $C^\infty$ 同相写像芽 $\phi:(\R^n,p)\to(\R^n,p')$ が存在して $f(x)-q+q'=g\comp\phi(x)$ と表せることをいう．

\begin{CD}
(\R^n,p)@>f>>(\R,q)\\
@V{\phi}VV @VV{-q+q'}V \\
(\R^n,p')@>>g>(\R,q')\\
\end{CD}

ここで， $C^\infty$ 同相写像 とは，全単射な $C^\infty$ 写像で，逆写像も $C^\infty$ 級であることをいう．

写像芽 $f$ と $g$ のソースを揃える座標変換が $\phi$ で， ターゲットを揃える定数加算が $-q+q'$ だと解釈できます．

次のモースの補題が，モース関数の臨界点の分類を与えます．

(定理)
モース関数 $f:\R^n\to\R$ の臨界点 $p$ での関数芽 $f:(\R^n,p)\to(\R,q)$ は，ある $0\le\lambda\le n$ について以下の関数芽 $\phi_\lambda:(\R^n,0)\to(\R,0)$ と $\mathcal R$ 同値である：
$$
\phi_\lambda(x) = - x_1^2 - x_2^2 - \dots - x_{\lambda}^2 + x_{\lambda+1}^2 + \dots + x_n^2
$$
この $\lambda$ は $\mathcal R$ 同値を与える $C^\infty$ 同相写像芽の取り方によらない．これを臨界点 $p$ の 指数 (index) という．

以上のことから，モース関数の臨界点の $\mathcal R$ 型は $n+1$ 種類に分類できることがわかりました．しかも，以下のように臨界点のタイプは簡単な計算で判定できるのです．

(定理)
モース関数 $f$ の臨界点 $p$ の指数は，へッセ行列 $D^2f(p)$ の（重複度も込めた）負の固有値の数に等しい．

このように，考察の対象をモース関数に限ることで状況がとても簡単になります．嬉しい反面，あまりに都合がよすぎてむしろ心配にもなってきます．モース理論は十分に一般性のある理論なのでしょうか．関数のなかにはヘシアンが退化したものもありますから，モース理論は「すべての関数」を扱うことはできません．しかしせめて「ほとんどの関数」に通用するものであってほしいものです．微分を用いた議論をするうえでは，以下の条件をみたせば「ほとんど」といってもよいでしょう．

• すべての関数を近似できるほど豊富にある＝どの関数のどの近傍にもモース関数がある
• 関数そのものを近似できるだけでなく，その導関数までをも近似できる＝上記の近傍は，関数値だけでなく導関数の値も加味して近さを判断している

まず，関数の導関数まで込めた近傍を扱う方法を定義します⁵．

(定義)
写像 $f:\R^n\to\R^m$ の $r$次ジェット ($r$-jet) を $$j^rf(x):=\par{x,f(x),\frac{\pd f_i}{\pd x_j}(x),\frac{\pd^2 f_i}{\pd x_{j_1}\pd x_{j_2}}(x),\dots,\frac{\pd^r f_i}{\pd x_{j_1}\dots\pd x_{j_r}}(x)}$$ で定義する． $r$次ジェット空間 ($r$-jet space) を $$J^r(\R^n,\R^m):=\set{j^rf(x)\mid x\in\R^n,f\in C^\infty(\R^n,\R^m)} \par{=\R^l,\ l=n+\binom{n+r}{r}m}$$ と定義する．非負整数 $r$ と 開集合 $U\subseteq J^r(\R^n,\R^m)$ について $$W^r(U):=\set{f\in C^\infty(\R^n,\R^m)\mid j^rf(\R^n)\subseteq U}$$ とおいて，$$\set{W^r(U)\mid r\in\Z_{\ge0},U\subseteq J^r(\R^n,\R^m)\mbox{ open}}$$ を開集合の基として生成される位相を ホイットニー $C^\infty$ 位相 (Whitney $C^\infty$ topology) という．

上記の意味での「ほとんど」を表す概念がジェネリシティです．

(定義)
写像の性質 $P$ が ジェネリック (generic) であるとは，ホイットニー $C^\infty$ 位相を入れた $C^\infty(\R^n,\R^m)$ において， 集合 $\set{f\in C^\infty(\R^n,\R^m)\mid\mbox{$f$ は $P$ をみたす}}$ が残留集合を含むことをいう．ここで，位相空間 $X$ の部分集合 $A$ が 残留集合 (residual set) とは，加算個の稠密開集合たちの共通部分として表せることをいう．位相空間 $X$ の 部分集合 $A$ が 稠密 (dense) とは，閉包が全体と一致する $(\cl A=X),$ すなわち， $X$ のどの点のどの近傍にも $A$ の元が存在することをいう．

ホイットニー $C^\infty$ 位相を入れた $C^\infty(\R^n,\R^m)$ は ベール空間 (Baire space) であることから，以下がわかります．

(定理)
ホイットニー $C^\infty$ 位相に関して， $C^\infty(\R^n,\R^m)$ の残留集合は稠密である．

実際，恣意的な仮定をおいたかに見えたモース関数は，これほど強い意味で一般的な存在なのです．

(定理)
モース関数はジェネリックである．

さて，ここからは最適化との関係を考えていきましょう．勾配を辿って関数を最適化するために，勾配法の軌跡を考えます．

(定義)
曲線 $x:\R\to\R^n$ で $$\frac{\pd}{\pd t}x(t) = -Df(x(t))$$ をみたすものを 積分曲線 (integral curve) という．

積分曲線の終点は勾配の消える点，すなわち臨界点になります．臨界点のなかでも積分曲線を引き込むものに特に興味があります．

(定義)
臨界点 $p\in\R^n$ が 安定 (stable) であるとは， $p$ の任意の近傍 $V\subseteq\R^n$ に対して $p$ のある近傍 $U\subseteq V$ が存在して， $x(0)\in U$ である積分曲線 $x:\R\to\R^n$ すべてが $x(t) \in V$ $(t\ge0)$ をみたすことをいう．

さて，ここまでで様々な最小点や臨界点を考えてきました．それらの関係を示します．

(定理)
モース関数 $f:\R^n\to\R$ について，以下のようにおく：

\begin{align}
X^\ast &:=\set{x\in\R^n\mid\mbox{$x$ は最小点}},\\
X^\ast_{\mathrm{local}} &:= \set{x\in\R^n\mid\mbox{$x$ は局所最小点}},\\
\Theta &:= \set{x\in\R^n\mid\mbox{$x$ は臨界点}},\\
\Theta_{\mathrm{stable}} &:= \set{x\in\R^n\mid\mbox{$x$ は安定臨界点}},\\
\Theta_{\mathrm{min}} &:= \set{x\in\R^n\mid\mbox{$x$ は指数0の臨界点}}.
\end{align}

このとき以下の関係が成り立つ：
$$
X^\ast \subseteq X^\ast_{\mathrm{local}} = \Theta_{\mathrm{stable}} = \Theta_{\mathrm{min}} \subseteq \Theta.
$$

つまり，モース関数において，最適化で求めるべき局所最小点は，安定臨界点でもあり極小点でもあります．したがって，勾配法またはヘッセ行列の固有値を計算することで局所最小点を求めることができます．この結果自体は最適化を知っている方には最適性条件として常識かもしれませんが，普段何気なく使っている定理をより一般的な視点からとらえなおすことができたのではないでしょうか．またこの関係がほとんどの関数で成立するという事実は初めて知った方も多いのではないでしょうか．いまの時点では単目的最適化の周知の事実を再解釈しただけに見えるかもしれませんが，これから多目的最適化に入ると，こうして視点を変えたことが本質的に効いてきます．

ここまでのまとめ：単目的最適化とモース理論の関係

• 単目的最適化とは，関数の（局所）最小点を求める問題です．
• ほとんどの関数はモース関数です．
• モースでない関数も，摂動すればモース関数になります．
• モース関数の局所最小点は，勾配法またはヘッセ行列の固有値を計算すれば求めることができます．

多目的最適化

さぁ，お待たせしました．多目的最適化です．単目的と比べて記号がややこしくなりますが，すべての議論は単目的最適化のケースとパラレルなので，分からなくなったら対応する単目的パートを読み返してみてください．単目的版の概念をよく理解したうえで「単にそれがベクトル値になっただけ」と思えば，飲み込みやすいと思います．

(定義)
関数 $f_1,\dots,f_m,g_1,\dots,g_l:\R^n\to\R$ が与えられたとき，集合 $X :=\set{x\in\R^n\mid g_1(x)\le0,\dots,g_l(x)\le0}$ 上で写像 $f:=(f_1,\dots,f_m):\R^n\to\R^m$ を最適化する問題を 多目的最適化問題 (multi-objective optimization problem) といい，以下のように書く：

\begin{split}
\minimize \ & f(x):=\par{f_1(x),\dots,f_m(x)}\\
\subjto   \ & g_1(x)\le0,\dots,g_l(x)\le0.
\end{split}

上記の定式化によれば，多目的最適化とはベクトル値関数の最適化ではありますが，成分関数を入れ替えただけの $(f_1,f_2)$ の最適化と $(f_2,f_1)$ の最適化を区別することには意味がありません．加えて，同じ関数を含む $(f_1,f_2,f_2)$ の最適化などもナンセンスでしょう．以下では，目的関数の並べ替えや重複を同一視して， 多目的最適化問題を目的関数の集合として扱います．

さて，目的関数が沢山あるときには，その一部の目的関数を最適化する問題も考えられます．

(定義)
多目的最適化問題 $f$ を目的関数の集合とみたとき，その部分集合 $g$ を $f$ の 部分問題 (subproblem) といい $g \subseteq f$ で表す．

目的関数が複数あれば，ほとんどの場合，それぞれの目的関数の最小点は異なります．すると，単目的最適化の意味で「ある目的関数を最適化すること」は「別の目的関数の最適化をあきらめること」にもなるわけです．多目的最適化では，このトレードオフを考慮して「最小化」することになります．目的関数値ベクトルの優劣を以下のように考えます．

• どの目的関数値を悪化させることもなく，いずれかの目的関数値を改善できるなら，それはより優れているといえる．
• ある目的関数値は改善するが，別の目的関数値は改悪するならば，どちらが良いかは判断がつかない．

(定義)
点 $f(x),f(y)\in\R^m$ について以下が成り立つとき， $f(x)$ は $f(y)$ を パレート優越 (Pareto dominate) するとをいい，$f(x)\dominates f(y)$ で表す：

• すべての $f_i \in f$ について $f_i(x) \le f_i(y)$
• ある $f_i \in f$ について $f_i(x) < f_i(y)$

さらに，すべての $f_i \in f$ について $f_i(x) < f_i(y)$ であるとき， $f(x)$ は $f(y)$ を 強パレート優越 (strongly Pareto dominate) するとをいい，$f(x)\sdominates f(y)$ で表す．

パレート順序 $\dominates$ や $\sdominates$ に関してこれ以上改善できない点を最適と考えます．

(定義)
点 $x\in X$ に対して $f(y)\dominates f(x)$ をみたす点 $y\in X$ が存在しないとき， $x$ を パレート点 (Pareto point) といい， $f(x)$ を パレート値 (Pareto value) という．点 $x\in X$ に対して $f(y)\sdominates f(x)$ をみたす点 $y\in X$ が存在しないとき， $x$ を 弱パレート点 (weak Pareto point) といい， $f(x)$ を 弱パレート値 (weak Pareto value) という．

これらの局所版も同様に定義します（定義は省略します）．

多目的最適化問題を単目的最適化問題に変換する スカラー化 (scalarization) とよばれる方法があります．色々な方法がありますが，ここではノルムを用いた方法を紹介します．

(定義)
関数 $f_1,\dots,f_m:\R^n\to\R$ と $p\ge1$, $w\in\Delta^{m-1}$について，以下の関数を 重み付き $L_p$-ノルム (weighted $L_p$-norm) という：$$f_{p,w}(x)=\par{\sum_{i=1}^n|w_i f_i(x)|^p}^{1/p}.$$ここで $\Delta^{m-1}:=\set{w\in[0,1]^m\mid\sum_{i=1}^m w_i=1}$ を 重み空間 (weight space) という．

ノルムの次数 $p$ を十分大きく選んで固定し，重み $w$ を動かしてできる様々な単目的最適化問題をそれぞれ最小化することで，もとの多目的最適化問題の解が網羅できます．

(定理)
関数 $f_1,\dots,f_m:\R^n\to\R$ の集合を $f$ とおく．$I\subseteq\set{1,\dots,m}$について， $f_I:=\set{f_i\in f\mid i\in I}$, $\Delta_I:=\set{w\in\Delta^{m-1}\mid w_i>0 (i\in I),w_j=0 (j\not\in I)}$ および以下のようにおく：

\begin{split}
X^\ast(I)&:=\set{x\in\R^n\mid\mbox{$x$ は $f_I$ のパレート点}},\\
X^\ast_{\mathrm{weak}}(I)&:=\set{x\in\R^n\mid\mbox{$x$ は $f_I$ の弱パレート点}},\\
X^\Delta_p(I)&:=\set{x\in\R^n\mid\mbox{$x$ は $f_{p,w}$ の最小点} (w\in\Delta_I)}.
\end{split}

$\min_{x\in\R} f_i(x)=0$ $(i=1,\dots,m)$ をみたすとき，ある $P\ge1$が存在してすべての $p>P$ について以下が成り立つ：$$X^\ast(I)\subseteq X^\ast_{\mathrm{weak}}(I)=X^\Delta_p(I).$$

これで単目的最適化の解法で多目的最適化も解けることになりました．なお実用上は， $f_i$ の最小値をゼロに揃える操作は探索中に動的に行い， $p\to\infty$ のmaxノルムが使われることが多いです（その場合，最適化には劣勾配を使うなどの工夫が必要です）．

特異点論

写像の1階微分と2階微分を考えます．1階微分は関数のケースの自然な一般化になっています．

(定義)
写像 $f$ のヤコビ行列を以下で定義する：

Df(x) :=
\begin{pmatrix}
\dfrac{\pd f_1(x)}{\pd x_1} & \cdots & \dfrac{\pd f_1(x)}{\pd x_n} \\
\vdots & \ddots & \vdots \\
\dfrac{\pd f_m(x)}{\pd x_1} & \cdots & \dfrac{\pd f_m(x)}{\pd x_n}
\end{pmatrix}

2階微分は写像の場合，座標によるので，少しテクニカルになります．

(定義)
TODO: ここで 一般化ヘシアン (generalized Hessian) を定義する．

特異点を定義します．

(定義)
写像 $f:\R^n\to\R^m$ に対して，点 $x\in\R^n$ が $\rank Df(x)<\min(n,m)$ をみたすとき， $x$ を 特異点 (singular point) といい，さもなければ 正則点 (regular point) という．

では，モース関数を写像に拡張してみましょう．関数のときと同じように $\mathcal R$ 同値を用いて写像の特異点を分類すると，特異点のタイプが無限に生じてしまうことが知られています．写像芽をソースの微分同相変換で同一視するだけでは，過剰な多様性が残ってしまうということです．この多様性は，関数から写像への移行，つまりターゲットの次元が上がったことによって生じたものでした．では，ターゲットについても微分同相変換で同一視すれば，適度な多様性におさまるのではないでしょうか．

(定義)
2つの写像芽 $f:(\R^n,p)\to(\R^m,q)$ と $g:(\R^n,p')\to(\R^m,q')$ が $\A$ 同値 ($\A$-equivalent) とは， $C^\infty$ 同相写像芽 $\phi:(\R^n,p)\to(\R^n,p')$, $\Phi:(\R^m,q)\to(\R^m,q')$ が存在して $\Phi\comp f=g\comp \phi$ と表せることをいう．

\begin{CD}
(\R^n,p)@>f>>(\R^m,q)\\
@V{\phi}VV @VV{\Phi}V \\
(\R^n,p')@>>g>(\R^m,q')\\
\end{CD}

これを用いてモース関数を一般化します．

(定義)
写像 $f:\R^n\to\R^m$ $(n\ge m)$の特異点 $p \in \R^n$ での写像芽 $f:(\R^n,p)\to(\R^m,q)$ が，ある $0\le\lambda n$ について以下の写像芽 $\phi_\lambda:(\R^n,0)\to(\R^m,0)$ と $\A$ 同値のとき， $p$ を 折り目特異点 (fold point) という：$$\phi(x) = (x_1, \dots, x_{m-1}, -x_m^2 - \dots - x_{m+\lambda-1}^2 + x_{m+\lambda}^2 + \dots + x_n^2).$$この $\lambda$ は $\A$ 同値を与える $C^\infty$ 同相写像芽の取り方によらない．これを $p$ の 指数 (index) という．すべての特異点が折り目特異点であるような写像を 折り目写像 (fold map) という．

最適化では「勾配が消える点」ではなく「勾配が反発する点」が重要になります．

(定義)
写像 $f:\R^n\to\R^m$ の点 $x\R^n$ が パレート臨界点 (Pareto critical point) とは， $$\par{\im Df(x)\cap\Pos}\ne\emptyset$$ が成り立つことをいう．ここで， $\Pos:=\set{x\in\R^m\mid x_i>0}$ である．

積分曲線の一般化として，パレート臨界点に行きつくような曲線を考えます．

(定義)
写像 $f=(f_1,\dots,f_m):\R^n\to\R^m$ に対して，曲線 $x:\R\to\R^n$ で$$\frac{\pd}{\pd t} f_i(x(t)) < 0 \quad \tforall t\in\R, i=1,\dots,m$$を満たすものを 許容曲線 (admissible curve) という．

許容曲線の終点はパレート臨界点です．パレート臨界点のなかでも許容曲線を引き込むパレート臨界点に特に興味があります．

(定義)
パレート臨界点 $p\in\R^n$ が 安定 (stable) であるとは， $p$ の任意の近傍 $V\subseteq\R^n$ に対して， $p$ のある近傍 $U\subseteq V$ が存在して，許容曲線 $x:\R\to\R^n$ のうち$$x(0)\in U$$であるものすべてが$$x(t)\in V \tforall t\ge0$$を満たすことをいう．

さて，そろそろタイトルの伏線を回収しましょう．特異点とパレート点には以下の関係があります．

(定理)
折り目写像 $f:\R^n\to\R^m$ $(n\ge m)$ について，以下のようにおく：

\begin{align}
X^\ast             &:=\set{x\in\R^n\mid\mbox{$x$ はパレート点}},\\
X^\ast_{\rm local} &:=\set{x\in\R^n\mid\mbox{$x$ は局所パレート点}},\\
\Theta             &:=\set{x\in\R^n\mid\mbox{$x$ はパレート臨界点}},\\
\Theta_{\rm stable}&:=\set{x\in\R^n\mid\mbox{$x$ は安定パレート臨界点}},\\
\Theta_{\rm min}   &:=\set{x\in\R^n\mid\mbox{$x$ は指数0のパレート臨界点}},\\
S                  &:=\set{x\in\R^n\mid\mbox{$x$ は特異点}}.
\end{align}

このとき，以下が成り立つ：$$X^\ast \subseteq X^\ast_{\rm local} = \Theta_{\rm stable} = \Theta_{\rm min} \subseteq \Theta \subseteq S$$

なんと！ すべてのパレート点は特異点 なのです！！言い換えれば，特異点を知ることはパレート点を知ることでもあります．だから多目的最適化にとって（分野的に） シンギュラリティは近い のです！

なお，この包含関係を利用した解法として，LovisonのSingular Continuationがあります．まず特異点集合を求めて，その中からパレート臨界点を抽出して，安定性を調べて，とやることで局所パレート点を網羅します．

解集合の構造

単目的最適化の解集合は，ジェネリックには1点（最小点）または加算個の孤立点（局所最小点）であることがモースの補題からわかります．では多目的最適化問題の解集合はどんな形になるのでしょうか？多目的の場合にも，ジェネリックな写像の解集合は整った構造をもっています．

(定理)
十分に正則 (sufficiently regular) [Lovison & Pecci (2017), Definition 30] な写像はジェネリックであり，その局所パレート点の集合は ホイットニー滑層分割 (Whitney stratification) [Lovison & Pecci (2017), Definition 16] できる．

定義は込み入っているので省略しますが，ホイットニー滑層分割とは，直観的にいえば，様々な次元の多様体をなめらかに貼り合わせたような図形です．さらに， [Lovison & Pecci (2017), Appendix] では，十分に正則な写像の局所パレート点と局所パレート値の集合の滑層分割を，パレート最適性の代数的必要十分条件であるKuo条件から計算する方法も提案しています．こうして複雑な形状をとりうる局所パレート点の集合を，多様体という理解しやすいものの集まりとして捉えることができるのです．めでたしめでたし．

数値的滑層分割

さて，これですべてうまくいったのでしょうか？Kuo条件を代数的に解く方法には以下のような弱点があります．

• 多数の変数をもつ問題で計算量爆発を起こす
• ブラックボックス問題が扱えない

産業界で現れる最適化問題は数十変数～数百変数をもつことが珍しくなく，ブラックボックス関数も登場しますので，そういったケースでは代数的なアプローチは難しそうです．一方で，そのような問題の解法としては数値計算に基づく手法が広く用いられており，実用上それなりに満足のいく近似解集合が得られるケースがよくあることが経験的に知られています⁶．では，局所パレート点集合や局所パレート値集合の滑層分割を数値的に求めることはできないのでしょうか？

ちょうど3Dグラフィクスでは三角形を貼り合わせて複雑な図形を表すように，パレート点集合を高次元三角形を貼り合わせて表すことを考えてみます．まず，三角形を高次元に拡張します．

(定義)
$\R^n$ の $k$-単体 ($k$-simplex) $(k\le n)$とは，一般の位置にある点 $p_0,\dots,p_k\in\R^n$ の凸包
$$
\bra{p_0,\dots,p_k} := \set{p\in\R^n\mid p=\sum_{i=0}^k w_i p_i, w_i\in\bra{0,1}}
$$である．特に，$\R^{k+1}$ の標準基底の凸包を $k$-標準単体 ($k$-standard simplex) といい， $\Delta^k$ で表す．

単体同士を面で貼り合わせることで，高次元の複雑な図形を表すことにします．

(定義)
単体の有限集合 $K$ が 単体複体 (simplicial complex) とは， $\sigma\subset\tau\in K\implies\sigma\in K$ と $\sigma,\tau\in K\implies\sigma\cap\tau\in K$ をみたすことをいう．単体複体 $K$ に対して $|K|:=\bigcup_{\sigma\in K}\sigma$ を 幾何学的実現 (geometric realization) という．

さて，単体のままでは「カクカク」なので，単体を曲げることで曲面も表せるように拡張しておきます．

(定義)
位相空間 $X$ の 三角形分割 (triangulation) とは，単体複体 $K$ と同相写像 $\phi:|K|\to X$ のペア $(K,\phi)$ をいう．

さいわい，ホイットニー滑層分割空間はそのようにして表現することができます．

(定理)
ホイットニー滑層分割可能な空間は三角形分割可能である．

では，貼り合わせの基本部品となる単体をどうやって求めればいいのでしょうか？この単体は，パレート点集合とパレート値集合の部分集合である必要があります．最も自然な方法は，そのような単体を解としてもつような問題を作りそれを解く，というシナリオでしょう．そのような問題を定義します．

(定義)
問題 $f$ が 単純 (simple) であるとは，すべての部分問題 $g \subseteq f$ が以下をみたすことをいう：

• (S1) 問題 $g:X\to\R^k$ のパレート点集合 $X^\ast(g)$ は $(k-1)$ 次元単体 $\Delta^{k-1}$ と同相
• (S2) 写像 $g|_{X^\ast(g)}: X^\ast(g)\to\R^k$ が$C^0$-埋め込み

ここで，写像 $f:X\to Y$ が $C^0$-埋め込み ($C^0$-embedding) とは，同相写像 $\hat f:X\to f(X)$ と包含写像 $\iota:f(X)\to Y$ の合成で $f=\iota\comp\hat f$ と表せることをいう．

これらの条件から，パレート点集合とパレート値集合が単体と同相であることがわかります．

(定理)
単純な問題 $f$ とその $k$ 目的部分問題 $g\subseteq f$ は以下をみたす：
$$X^\ast(g) \homeo g(X^\ast(g)) \homeo f(X^\ast(g)) \homeo \Delta^{k-1}.$$

それだけでなく，なんと面関係まで込めて単体になります．

(定理)
単純な問題 $f$ とその部分問題 $g\subseteq f$ は以下をみたす：

\begin{align}
\bd X^\ast(g)      &= \bigsqcup_{h\subset g} X^\ast(h),\\
\bd f(X^\ast(g))   &= \bigsqcup_{h\subset g} f(X^\ast(h)),\\
f(\bd X^\ast(g))   &= \bd   f(X^\ast(g)),\\
f(\intr X^\ast(g)) &= \intr f(X^\ast(g)).\\
\end{align}

そして，すべての部分問題の弱パレート点はパレート点です．

(定理)
単純な問題 $f$ の部分問題 $g\subseteq f$ は以下をみたす：$$X^\ast(g)=X^\ast_{\rm weak}(g).$$

以前にみたように，重み付き $L_p$ ノルム法によるスカラー化で得られる解は弱パレート点であることから，単純な問題のパレート点はスカラー化によって過不足なく網羅できることになります．

単純な問題それ自体はジェネリックではありません．しかし，パレート点集合を三角形分割するためには，「各パレート点の近傍を単純な問題で表せる」という性質はジェネリックであってほしいですね．

(定義)
問題 $f:X\to\R^m$ が 局所的に単純 (locally simple) とは，任意のパレート点 $x\in X^\ast(f)$ に対して， $x$ の近傍 $U$ が存在して，$f|_U:U\to\R^m$ が単純な問題となることをいう．

以下の問題を考えていきましょう．

(問題)
局所的に単純な問題はジェネリックか．

折り目写像はモース関数の自然な一般化になっているのでした．まずは折り目写像が局所的に単純かどうかを確認してみましょう．そのために大事な性質があります．

(定理)
折り目写像 $f$ の特異点集合 $S(f)$ への制限 $f|_{S(f)}:S(f)\to\R^m$ は $C^\infty$-はめ込みである．
ここで，写像 $f:X\to Y$ が $C^\infty$-はめ込み ($C^\infty$-immersion) とは，各点 $x\in X$ の近傍 $U$ で $f|_U:U\to Y$ が $C^\infty$ 同相写像であることをいう．

このことからすぐに以下のことがわかります．

(系)
折り目写像は局所的に単純な問題である．
[2018/02/16] 反例が見つかりました．

文献が見つからないのでここで証明しておきます．

(証明)
近傍は単体と同相にとれるので，(S1)は自明．折り目写像は $(n\ge m)$ なので，パレート点集合は特異点集合の部分集合であった．はめ込みの制限ははめ込みなので，$f|_{X^\ast(f)}:X^\ast(f)\to\R^m$ははめ込み．はめ込みは局所的に埋め込みなので，(S2)をみたす．
[2018/02/16] 部分問題については(S1)を満たさない反例が見つかりました．

モース関数はジェネリックなのでした．そして，折り目写像はモース関数を自然に一般化したものです．そのような写像に対して「単純な問題を局所的に貼り合わせて複雑な問題を表す」ことができるということは，このアプローチがジェネリックに通用することにも期待がもてそうです．ところが，折り目写像はジェネリックではないことが知られています．写像の場合には，二次形式では表せない特異点も豊富に生じるということです．

一体どんな写像がジェネリックなのかが気になります．それは，1970年代にトムやマザーらによって調べられました．以下では彼らによる構造安定性の理論を紹介します．摂動を加えても構造が変わらないような写像を考えます．

(定義)
写像 $f:\R^n\to\R^m$ が $C^\infty$ 安定 ($C^\infty$ stable) とは，$f$ の近傍 $U\subseteq C^\infty(\R^n,\R^m)$ が存在して，任意の $g\in U$ が $f$ に $C^\infty$ 同値であることをいう．ここで，写像 $f,g:\R^n\to\R^m$ が$C^\infty$ 同値とは，$C^\infty$ 同相写像 $\phi:\R^n\to\R^n,\Phi:\R^m\to\R^m$ が存在して $\Phi\comp f=g\comp\phi$ が成り立つことをいう．

\begin{CD}
\R^n@>f>>\R^m\\
@V{\phi}VV @VV{\Phi}V \\
\R^n@>>g>\R^m\\
\end{CD}

さらに上記の $C^\infty$ をすべて $C^0$ に取り換えたものを $C^0$ 安定 ($C^0$ stable) という．

そのような安定写像はジェネリックです．

(定理)
$C^0$ 安定写像はジェネリックである．一方， $C^\infty$ 安定写像がジェネリックであるのは，次元対 $(n,m)$ が以下のいずれかに該当するとき，かつそのときにかぎる：

• $n < \frac 6 7 m + \frac 8 7 (m-n\ge4)$
• $n < \frac 6 7 m + \frac 9 7 (3\ge m-n\ge0)$
• $m < 8 (m-n = -1)$
• $m < 6 (m-n = -2)$
• $m < 7 (m-n \le -3)$

この次元対を 結構次元 (nice dimension) という．

ほとんどの多目的最適化問題では， $n\gg m$ なので，最後のケースに該当します．6目的以下ならば， $C^\infty$ 安定写像はジェネリックだと思っていいでしょう．7目的以上では $C^0$ 安定写像を考える必要があります．

では，安定写像には折り目特異点以外にどんな特異点が生じるのでしょうか．じつは， $C^\infty$ 安定写像の特異点の分類はすでにわかっています．とはいえ完全な分類表を紹介するのは大変なので，ここでは低次元の例を紹介することにします．

(定理)
写像 $f:\R^2\to\R^2$ の安定特異点の $\A$ 型は，以下の2つである：

• 折り目 (fold): $f(x_1,x_2)=(x_1^2,x_2)$
• カスプ (cusp): $f(x_1,x_2)=(x_1^3-x_1x_2,x_2)$

おわりに：特異点論による多目的最適化の体系的理解に向けて

今後の発展のために，特に重要と思われる未解決問題を紹介して終わりたいと思います．

(問題)
パレート点の特異点型をパレート $\A$ 同値に基づいて分類せよ．ここで，パレート $\A$ 同値とは， $\A$ 同値であって，同値関係を与える $C^\infty$ 同相写像芽 $\Phi$ がパレート順序を保存するように制限したもの，すなわち以下をみたすものをいう．
$$f(x) \dominates f(y) \Leftrightarrow \Phi\comp f(x) \dominates \Phi\comp f(x)$$

特異点の分類に用いられる $\A$ 同値ですが，これはターゲットの座標変換を行うために，「ある点がパレート点であるかどうか」を変えてしまいます．そこで，パレート点の分類においてはパレート順序を保存するような変換のもとで同値類を考えたほうがよさそうです．パレート $\A$ 同値ではターゲットの変換が相当に制限されます．順序を保つつ変換は，せいぜい

• 成分の並べ替え
• 成分ごとの単調変換

くらいでしょう．負の数をかけることもできないので，線形変換さえも自由に行うことはできません．こうしてみると，パレート $\A$ 同値はほとんど $\mathcal R$ 同値に近いように思えます． $\mathcal R$ 同値では特異点型が無限に生じることを思い出すと，パレート $\A$ 同値も細かすぎる分類かもしれません．しかし，いま分類したいものは「特異点」ではなく，「パレート点」です．特異点のなかにはパレート点にはなりえないものもあるのです．実際，パレート値は必ず像の境界に位置するため，奇数次の $A_k$ 型特異点は登場しえないことが分かります．特異点型のサブセットを詳しく調べるために， $\A$ 同値よりも細かい分類を行うことは合理的だと思います．パレート $\A$ 同値がそのために適した同値関係かどうかは，今後上記の問題に答えていく過程でよく検討する必要があるでしょう．

(問題)
安定写像を最適化する問題の（局所）パレート点およびパレート値の集合を三角形分割する方法を作れ．

これまでの議論で，局所パレート点や局所パレート値の集合が三角形分割可能であることは示されました．しかし，具体的に三角形分割を構成する方法は，単純な問題に対してしか分かっていません．より一般的な問題に対して，三角形分割を行うアルゴリズムが必要です．理論的には，ひとつめの問題が解けるにしたがって，集合をどのように分割すべきかが見えてくるでしょう．アルゴリズム的には，高次元へのスケーラビリティが重要になると思います．世の中には5～10目的問題の応用事例もありますので，その解は4～9次元になります．2017年現在，4次元以上の単体複体のデータ構造やアルゴリズムに関しては，あまり効率の良いものがありません．複体には入れ子構造があり大半の頂点は面に寄与しないので，もしかしたら ZDD (Zero-suppressed binary Decision Diagram) などを応用すると改善できるかもしれません．アルゴリズマーのみなさんはぜひ挑戦してみてください．

(問題)
以上の理論を，境界付きのケースへ拡張せよ．

これまで，簡単のために無制約の場合を扱ってきました．しかし，現実の最適化問題には制約付き問題が多く，制約付き問題では制約境界に解が存在する場合が多いです．単目的最適化に対しては，滑層分割モース理論があります．この理論をベクトル値に拡張する必要があります．

文献紹介

単目的最適化はNesterovが網羅的な教科書です．凸解析についてはRockafellarが有名です．この分野はWebの講義資料が充実しているのでそれでいい気もします．

多目的最適化はMiettinen，日本語の教科書としては中山がよいでしょう．内容はほぼ同じです．凸計画問題の解のトポロジーに関してはLucが唯一の教科書です．部分問題の解の関係についてはEhrgottにまとまっています．
多目的進化計算ならDebですが，この分野は近年発展が早く，若干時代遅れな内容になりつつあります．

モース理論と特異点論は泉屋からとりました．解集合の構造についてはLovisonからとりましたが，すでに背景を分かっている人向けの記述になっているので，この分野の開拓者であるSmaleの6部作から入るのがいいと思います．

1. あくまでもアナロジーであって，両者の間に科学的な関係はありません． ↩

2. 一部＝僕の周辺ですが． ↩

3. この記事を書くために調べて初めて気付いたのですが，WEBで読める多目的最適化の入門記事ってほとんどないんですね．日本オペレーションズ・リサーチ学会のOR Wikiに多目的最適化のページくらいでしょうか．とはいえこれは「辞典」なので，すでに分かっている人向けの読み物な気がします．初学者向けに内容をかみ砕いたストーリー性のある入門記事が増えれば，多目的最適化ももっと流行るはずなのになぁ．そんな思いもあってこの記事を書いています． ↩

4. 割愛したトピックも最適化に応用することができるはずです．しかし，導入には多くの準備が必要になることに加え，これらの多目的版が一般向けに紹介できるほど完成されていないため今回は見送ります． ↩

5. この部分はかなり端折った書き方をしています．より丁寧な説明は，泉屋, 3.2節などを参照してください． ↩

6. ブラックボックスですので，理論的な保証はありません． ↩