深層学習や機械学習を勉強していると、目的関数を最小化するために、データからパラメータを学習することが多々あると思います。
実はこの内容自体は、最適化数学の文脈で語ることができます。今回は、数理最適化について、初心者向けにわかりやすく解説していきます。
数理最適化の登場人物
数理最適化においては、登場人物として、決定変数(decision variable)、目的関数(objective function)、制約関数(constraint)が登場します。
- 決定変数 (decision variable)
- 目的関数(objective function)
- 制約関数 (constraint)
まず、これらについて解説していきます。
決定変数(decision variable)
決定変数としては、最適化する変数の集合のことをいいます。決定変数が連続的な場合は、連続最適化問題、決定変数が、離散的な問題は、組合せ最適化問題と呼ばれています。深層学習などは、基本的にパラメータの集合が連続値を取りうるため、連続最適化問題に分類されます。
組合せ最適化問題はさらに詳しく分類されます。決定変数が離散的な値をとる場合に組み合わせ最適化問題に分類されますが、さらに決定変数の取りうる値が、整数値で限定される場合は、整数最適化問題(Integer optimization problem)と呼ばれます。一方で、整数値をとる決定変数と、実数値(連続値)をとる決定変数が両方存在する場合は、混合整数最適化問題(Mixted Integer Optimization Problem, MIP)と呼ばれています。
ここで、決定変数は1つだけでなく、一般的には2個以上複数あるのが普通です。
次のポイントは押さえておくと良いでしょう。
- 決定変数が、連続的か離散的かで、連続最適化問題と組合せ最適化問題に分類される
- 組合せ最適化問題の中で、全ての決定変数が整数である場合は、整数計画化問題、整数値をととる決定変数と、実数値をとる決定変数の両方が存在する場合は、混合整数最適化問題と呼ぶ
目的関数(objective function)
目的関数は、最適化の指針とするための関数です。コスト関数とも呼ばれています。数理最適化では、目的関数を最小化、もしくは最大化する決定変数の値を決定することになります。
そのため、最適化問題として現実の問題を定式化する場合には、現実問題で最大化（最小化）したい指標を定め、それを目的関数として設定することになります。
制約(constraint)
数理最適化において、制約は非常に重要な要素で、決定変数が取りうる領域を制約で指定します。
線形・非線形性
最適化問題には、線形や非線形という枠組みも存在する。目的関数と制約が、決定変数の線形の形で与えられる場合、線形最適化問題(Linear Optimization Problem)と呼ぶ。また、これ以外に、目的関数と制約が、決定変数の非線形な形で与えられている場合、非線形最適化問題(NonLinear Optimization Problem)と呼ばれます。
線形・非線形の概念は、連続最適化問題、組合せ最適化問題の両方に対して存在する概念であることは意識しておきましょう。
厳密解法と近似解法
最適解問題を解く場合、厳密解法と近似解法の2つがあります。
厳密解法は与えられた問題に対して、厳密解を求める手法です。厳密解は何かしらの数理的な手法に基づいて、厳密な最適解を求めることができる手法です。しかし、実際には計算量の問題などから厳密解法を利用できないことが多く、一般的には近似解法が広く利用されます。近似解放はメタヒューリスティック(実験的手法)と呼ばれ、それなりに筋の良い近似解を実験的に求める手法になっています。
関数の凸性・非凸性
数理最適化においては、凸性・非凸性という概念が存在します。これについては、非常に難しい概念のため、次回の記事で解説したいと思います。