「大人の教養・知識・気付き」を伸ばすブログ

一流の大人（ビジネスマン、政治家、リーダー…）として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。データ分析・語学に力点を置いています。　→現在、コンサルタントの雛になるべく、少しずつ勉強中です(※2024年1月21日改訂)。

MENU

最適化問題を解く（その01/X）

やりなおしの数学 最適化

はじめに

　統計学にしても経済学にしても、応用数学の中でも非常に重要な分野である「最適化問題」を


最適化手法入門 データサイエンス入門シリーズ

最適化手法入門 データサイエンス入門シリーズ

Amazon


などを参考に学んでいきます。

1.　最適化の概要

　工学における最適化は、制約集合の下で最良のシステム設計を探す過程で、社会の多くの場面で用いられ、理工学の基礎や応用に多様に関わっている。データから有意義な情報を抽出する分析手法では、その多くが最適化に立脚している。最適化は関数の大域的最小値を求めることに関心がある。その最小値は勾配が0となるところで生じる。しかし勾配が0だからといって最適だとは限らない。

1.1　最適化問題とは

　「与えられた条件を満たす解のうちある関数の値を最小(または最大)にするものを求めること」を最適化という。
　より数学的に定式化すると、最適化問題とは、集合Sおよび関数f:S\rightarrow\mathbb{R}が与えられたときに、


\begin{aligned} \mathrm{Minimize}\ \ \ &f(\boldsymbol{x})\\ \mathrm{subject\ to}\ \ \ &\boldsymbol{x}\in S \end{aligned}


を満たすような\boldsymbol{x}\in Sを求める問題を言う*1。この最適化問題に対して、fを目的関数、Sを実行可能領域、条件\boldsymbol{x}\in Sを制約と呼ぶ。また制約を満たす点\boldsymbol{x}\in Sを実行可能解という*2。またfの最小値を実現する実行可能解\boldsymbol{x}を最適解と呼び、そのときの目的関数の値を最適値という。
　用語をまとめると以下のようになる：

制約 解が満たすべき、与えられた条件
目的関数 最小(または最大)とする対象となる、良くしたい評価尺度
決定変数(または設計変数)*3 決定したい数
実行可能解 最適化問題の制約を満たす(だけの)解*4
実行可能領域(または許容領域) 実行可能解の集合
最適解 実行可能解のうち、目的関数を最小(または最大)にするようなもの
最適値 最適解における目的関数の値


目的関数を最小にするような最適解を求める場合の最適化問題を特に最小化問題、最大にするような最適解を求める場合を最大化問題と呼ぶ。
　なお最小化問題\mathrm{Minimize}\ f(\boldsymbol{x})は


\begin{aligned} \mathrm{Minimize}\ f(\boldsymbol{x})\ \Leftrightarrow\ \mathrm{Maximize}\ -f(\boldsymbol{x}) \end{aligned}


と最大化問題と等価であるから、最適化問題では最小化ないし最大化の一方のみに言及する。

1.1.1　最適化の設計

　多くの学問が最適化をその中核に置いている。応用先に応じ対象指標は効率性、安全性および精確性を持たなければならない。その設計で制約となるのがコスト、重み、そして構造的な頑健性である。


最適化デザインにおけるプロセス

1.2　最適解の概念

1.2.1　最適解の存在と実行可能性

　最適化問題

\begin{aligned} \mathrm{Minimize}\ \ \ &f(\boldsymbol{x})\\ \mathrm{subject\ to}\ \ \ &\boldsymbol{x}\in S \end{aligned}

においては、解について以下の4パターンに帰着できる：

　 (1) 　 実行可能解が存在する(S\neq\emptyset)。
　 　 (a) 実行可能領域において目的関数が下に有界であり、実際に下限を達成するような実行可能解が存在する。
　 　 (b) 実行可能領域において目的関数が下に有界であるものの、実際に下限を達成するような実行可能解が存在しない。
　 　 (c) 実行可能領域において目的関数が下に有界でない。
　 (2) 　 実行可能解が存在しない(S=\emptyset)。


(1)が成り立つ場合、最適化問題は実行可能であるという。(2)の場合を実行不可能であるという。

1.2.2　大域的最適解と局所最適解

　一般に、最適化問題で真の最適解を求めることは容易であるとは限らない。その場合、制約を少し緩めた解を求めることが実用上、少なくない。そこで解の最適性について、いくつかのパターンを考える必要がある。
　まずすべての実行可能解のうち、目的関数を最小(または最大)にするような実行可能解を大域的最適解という。すなわち、fを目的関数、Sを実行可能領域として、


\begin{aligned} {}^{\exists}\bar{x}\in S\left({}^{\forall}x\in S\left(f(\bar{x})\leq f(x)\right)\right) \end{aligned}


が成立するときに、\bar{x}を大域的最適解という。
　これに対し、その値の近傍において目的関数の値がより小さい(大きい)値が存在しないような実行可能解を局所的最適解という。すなわちある\varepsilon\gt0に対してN(\bar{x})=\{x\in S|x\in(\bar{x}-\varepsilon,\bar{x}+\varepsilon)\}とおくとき、


\begin{aligned} {}^{\exists}\bar{x}\in S\left({}^{\forall}x\in N(\bar{x})\left(f(\bar{x})\leq f(x)\right)\right) \end{aligned}


が成立するとき、\bar{x}をを局所的最適解という。


最適化における臨界点

1.3　連続最適化と離散最適化

　最適化問題をその特徴で分類することを考えると、①実行可能解が有限個であるもの、②実行可能解が無限個である(連続的に変化できる)もの、の2つに分けられ、前者を離散最適化問題、後者を連続最適化問題という。

1.4　理論の枠組み：凸計画，線形計画，非線形計画

　最適化問題の難しさや特徴は、目的関数fおよび実行可能領域Sの性質に応じて様々である。典型的な最適化問題を分類する。先にまとめておくと以下のとおりである：

凸計画問題 実行可能領域が凸集合であり目的関数が凸関数である最適化問題
線形計画問題 実行可能領域が多面体で目的関数が1次式であるような最適化問題
非線形計画問題 目的関数（および制約）が必ずしも1次式でないような最適化問題
整数計画問題 変数が整数値のみを取るような最適化問題
多目的最適化問題 競合関係にある複数の目的関数を同時に最適化する必要のある最適化問題
変分問題 無限次元での(汎関数の)最適化問題
1.4.1　線形計画問題

　最適化問題

\begin{aligned} \mathrm{Minimize}\ \ \ &{}^{t}\boldsymbol{c}\boldsymbol{x}\\ \mathrm{subject\ to}\ \ \ &{}^{t}\boldsymbol{a}_i\boldsymbol{x}=b_i,\ i=1,\cdots,m,\\ &{}^{t}\boldsymbol{p}_l\boldsymbol{x}=q_l,\ l=1,\cdots,k \end{aligned}

を線形計画問題という。
　これの実行可能領域Sは線形方程式および線形不等式で表される集合


\begin{aligned} S=\left\{\boldsymbol{x}\in\mathbb{R}^n|{}^{t}\boldsymbol{a}_i\boldsymbol{x}=b_i,{}^{t}\boldsymbol{p}_l\boldsymbol{x}\leq q_l\right\},i=1,\cdots,m,l=1,\cdots,k \end{aligned}


である。このような一次式のみで表される集合を多面体という。解きたい問題を線型計画問題として定式化しその最適解を求める方法論を線形計画(法)という。
　実行可能領域Sが多面体で目的関数fが凸な二次関数であるような問題を凸2次計画問題という。

1.4.2　凸計画問題

　集合S\subset\mathbb{R}^nが任意の点\boldsymbol{x},\boldsymbol{y}\in Sに対して条件


\begin{aligned} {}^{\forall}\lambda\in[0,1]\left(\lambda\boldsymbol{x}+(1-\lambda)\boldsymbol{y}\in S\right) \end{aligned}


を満たすとき、Sを凸集合という。
　またf: \mathbb{R}^n\rightarrow\mathbb{R}が任意の点\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^nに対して条件


\begin{aligned} {}^{\forall}\lambda\in[0,1]\left(\lambda f(\boldsymbol{x})+(1-\lambda)f(\boldsymbol{y})\geq f(\lambda\boldsymbol{x}+(1-\lambda)\boldsymbol{y})\right) \end{aligned}


を満たすとき、fを凸関数と呼ぶ。
　\boldsymbol{x}={}^{t}(x_1,\cdots,x_n)\in\mathbb{R}^nの最適化問題


\begin{aligned} \mathrm{Minimize}\ \ \ &f(\boldsymbol{x})\\ \mathrm{subject\ to}\ \ \ &\boldsymbol{x}\in S \end{aligned}


において、実行可能領域S\subset\mathbb{R}^nが凸集合であり目的関数f:\mathbb{R}^n\rightarrow\mathbb{R}が凸関数である場合を凸計画問題という。またこの問題は変数tを新たに導入して


\begin{aligned} \mathrm{Minimize}\ \ \ &t\\ \mathrm{subject\ to}\ \ \ &t\geq f(\boldsymbol{x})\\ &\boldsymbol{x}\in S \end{aligned}


と書き換えても同値である。
　最適化の理論では線形か否かよりも凸性を持つか否かで扱いやすさが分かれる。

1.4.3　非線形計画問題

　非線形計画問題は一般に、\boldsymbol{x}\in\mathbb{R}^nについてf,g_1,\cdots,g_m,h_1,\cdots,h_kをn変数実関数(かつ普通は微分可能と仮定)として


\begin{aligned} \mathrm{Minimize}\ \ \ &f(\boldsymbol{x})\\ \mathrm{subject\ to}\ \ \ &g_i(\boldsymbol{x})\leq0,\ i=1,\cdots,m,\\ &h_l(\boldsymbol{x})=0,\ l=1,\cdots,k \end{aligned}


と定式化できるような最適化問題である。g_i(\boldsymbol{x})\leq0を不等式制約、h_l(\boldsymbol{x})=0を等式制約という。等式制約も不等式制約も無い最適化問題を無制約最適化問題といい、少なくとも一方があるものを制約付き最適化問題という。


定義1.1　制約付き最適化問題　f:\mathbb{R}^n\rightarrow\mathbb{R},g_i:\mathbb{R}^n\rightarrow\mathbb{R},i=1,\cdots,m,h_j:\mathbb{R}^n\rightarrow\mathbb{R},j=1,\cdots,lに対して、

\begin{aligned} g_i(\boldsymbol{x})&=0,&\ i=1,\cdots,m g_i(\boldsymbol{x})&\leq0,&\ j=1,\cdots,l \end{aligned}

の下でf(\boldsymbol{x})を\boldsymbol{x}\in\mathbb{R}^nについて最小化(最大化)する問題を制約付き最適化問題という。



定義1.2　無制約最適化問題　f:\mathbb{R}^n\rightarrow\mathbb{R}に対して、f(\boldsymbol{x})を\boldsymbol{x}\in\mathbb{R}^nについて最小化(最大化)する問題を無制約最適化問題という。

1.4.4　整数計画問題

　変数が整数値のみを取るような最適化問題を整数計画問題という。特に変数が0,1のみを取るような整数計画問題を0-1整数計画問題という。取り得る値が整数に限られた変数を整数変数という。一部が連続変数で残りが整数変数であるような問題を混合整数計画問題と呼ぶ。

1.4.5　多目的最適化問題

　(普通は)競合関係にある複数の目的関数を同時に最適化する必要のある問題を多目的最適化問題という。多目的最適化問題は通常、2つ以上の目的関数を同時に改善できないような実行可能解を指す\mathrm{Pareto}最適解を可能な限り見出し、意思決定者がその中から最も好ましい解を選ぶという手順を取る。

1.4.6　変分問題

　無限次元での最適化問題を変分問題という。多くの微分方程式が変分問題としても記述できるため、変分問題は工学において多くの応用がある。

次回

power-of-awareness.com

参考文献

*1:最大化(\mathrm{Maximize})もf(\boldsymbol{x})=-f(\boldsymbol{x})と置き換えれば最小化問題に置き換えられるため、以降は最小化問題を扱えばよい。

*2:最適かどうかではなく、単に制約を満たすのみの点である。

*3:単に変数ともいう。

*4:目的関数の値については何も言及していない。

プライバシーポリシー お問い合わせ