最適化メモ①：最適解と極値，最大最小値

　新年明けましておめでとうございます．サカシタです．2020年もよろしくお願いいたします．

　これまで最適化，特に自分が研究で使っているトポロジー最適化について理解不足を感じるときが多々あったため，本を読んで学んだことをブログ記事にして理解を深めていこうと思います．タイトルに①とあるように，シリーズものとして記事を投稿していく予定です．このシリーズでは，「最適化と変分法」（東京大学工学教程編纂委員会編，寒野善博・土谷隆著）を読んで学んだこと，疑問に思い調べたことを記録します．

　最適化は物流コストの最小化，構造物の剛性最大化など日常生活の様々な場面で幅広く利用されている技術です．対象読者は私のように最適化を勉強しようとしている方ですが，そうでない方にもさわりだけでも掴んでもらえるような文章になるよう努力します．

最適化とは？
- 数学的な記述
最適解の存在有無・種類
大域的最適解・局所最適解，最小値，極小値の関係

最適化とは？

　最適化とは，与えられた条件（ex. 解のとりうる範囲）のもとで，対象となる関数を最小にする解，あるいは最大にする解を求めることを指します．

数学的な記述

　文章だけでは厳密性に欠けるので，今一度数学的に記述します．最適化問題とは，集合 $S$ と関数 $f:S \rightarrow R$ *1が与えられたときに，条件 $x \in S$ を満たす $x$ のうち， $f(x)$ を最小にするものを求める問題です．論文などでは以下のように書かれます．

${ \begin{align} &\textrm{Minimize} & f(x)\\ &\textrm{subject to} & x \in S \end{align} }$

　ここで， $f(x)$ が対象となる関数（目的関数）， $x \in S$ が与えられた条件（制約）となります．上記の問題は厳密には $f(x)$ をMinimize，つまり最小化しているので，最小化問題と呼ばれます．最適化問題にはもちろん関数を最大化する解を求める最大化問題もありますが， $-f(x)$ や $1/f(x)$ を目的関数とした最小化問題を解くことと，目的関数を $f(x)$ とした最大化問題を解くことは同じなので，以降のシリーズ記事では主に最小化問題を取り扱います．

　さて，最適化問題は目的関数 $f$ ，実行可能領域 $S$ の性質によって様々な問題に分類されます．ここでは，実行可能領域 $S$ の性質に着目して，最適化問題を連続最適化，離散最適化の2種類に大別します．まず連続最適化は $S \in \mathbb{R}^n$ で連続的な集合である最適化問題です．一方で，離散最適化は $S$ が整数ベクトルの集合や有限集合のような離散的な集合である最適化問題をいいます．離散最適化は現実世界で物量の個数を変数 $x$ とする最適化問題などに有用です．例として下図の $x \in \mathbb{R}$ を変数とした1変数最適化問題をあげると，連続最適化では太線の[1.3,7.6]，離散最適化では $x$ 軸上の0,1,2,...の整数が $S$ になりえます．この図にある $x_1$ , $x_2$ は区間[1.3,7.6]を実行可能領域 $S$ とした連続最適化において，それぞれ大域的最適解，局所最適解と呼ばれるもので，定義は後で説明します．

　「最適化と変分法」，またそれに準拠する本シリーズ記事では，導関数の必要な勾配法という最適化アルゴリズムについて説明するので，連続最適化，かつ $f$ が連続である場合を主に扱います．ちなみに， $f$ の性質（線形性，凸性など）による問題の分類も今後の記事で取りあげる予定です．

最適解の存在有無・種類

　最適解にも2種類の大別があります．その説明をする前に，そもそも解の存在の有無について，明示しておきたいと思います．最適化問題には最適解が存在するような気がしますが，解が存在しない場合もあります．解の存在有無を判別するのも最適化を解くことの一部です．以下の記述は，「最適化と変分法」から引用です．

1. 実行可能領域において目的関数の値が下に有界であり，実際に下限を達成する実行可能解が存在する．
2. 実行可能領域において目的関数の値が下に有界であるが，実際に下限を達成する実行可能解が存在しない．
3. 実行可能領域において目的関数の値が下に有界でない．
$S=\emptyset$

　「下限を達成する実行可能解」が最適解を指します．(1.2)，(1.3)，(2)は最適解が存在しません．(1.2)は，例えば [tex:y=e^-x] のような，ある値に漸近するもののその値をとる $x$ は一意に求められない関数を指します．(1.3)は， $y=-x$ などが例にあげられます．

　(1.1)を満たしていることが前提として，最適解には大域的最適解と局所最適解の2種類が存在します．　 $\overline{x} \in S$ として， $\overline{x}$ が条件

${ \begin{align} f(x) \geqq f(\overline{x}), \ \ \forall{x} \in S \end{align} }$

を満たすとき， $\overline{x}$ は大域的最適解です．また， $\overline{x}$ の近傍 $N(\overline{x})$ が存在して条件

${ \begin{align} f(x) \geqq f(\overline{x}), \ \ \forall{x} \in N(\overline{x}) \cap S \end{align} }$

が成り立つとき， $\overline{x}$ は局所最適解となります．先の図（下に同じものを再掲します）では，[tex:x{1}] が大域的最適解，[tex:x{2}] が局所最適解です．

大域的最適解・局所最適解，最小値，極小値の関係

　ここまでの説明を本で読みながら私が疑問に思ったのは，局所最適解は極小値と同じなのか違うのか？ということです．これを考えるために，極小値の定義を振り返ります．　　 $x_0$ の近傍 $N(x_0)$ に属する任意の点 $x$ に対して，

${ \begin{align} f(x) \geqq f(x_0), \ \ \forall{x} \in N(x_0) \cap \mathbb{R}^n \end{align} }$

であれば $x_0$ は極小値です．これより，制約が存在しない最適化問題（無制約最適化問題）の場合，局所最適解は極小値と同義になります*2．同様に，無制約最適化問題であれば，大域的最適解は最小値となりえます．

　次回は， $f:\mathbb{R}^n\rightarrow\mathbb{R}$ の無制約最適化問題における最適解が満たす条件について学びます．誤りがあれば，サカシタまでご連絡ください．それではまた．

*1:関数の記述でよく見られる2種類の矢印 $\rightarrow$ と $\mapsto$ の違いが気になって調べたところ，これらは明確に異なり， $\mapsto$ は元の対応を表すため， $\rightarrow$ に比べてより狭義で使われるようです．

*2:ちなみに $x \neq x_0$ について $f(x) > f(x_0)$ の場合は狭義の極小値，同様に $x \neq \overline{x}$ について $f(x) > f(\overline{x})$ は狭義の局所最適解と呼ばれます．