第3回：最適化問題の基礎

  • 最適化問題や凸計画問題という名称を知ること
  • 導関数を求めることで極大値・極小値を求めること
  • ある函数が凸であることを示せるようにすること
  • ラグランジュの乗数法で、凸計画問題が解けるようにすること

何らかの制約の下で、ある函数を最大化あるいは最小化する条件および値を求める問題のことを最適化問題と呼びます。つまり、最適化問題は最大化問題と最小化問題の総称です。統計的分析の際には、確率が最大になるところ、つまり可能性が最も高いところを求めることがしばしば必要となってきます。確率を函数と見なせば、確率を最大になるところを求めることは、最適化問題になります。このため、統計分析をしっかりとこなせるようになるためには、最適化問題に慣れ親しむことが重要になってきます。

最適化問題には様々な種類のものがありますが、このうち凸計画問題と呼ばれる形式の問題は比較的単純なので、これについて見ていきたいと思います。凸計画問題とは、最大化あるいは最小化の対象となる函数が、凸函数であるような最適化問題です。凸函数というのは、単純に言えば、その函数をグラフに描いたとき、その境界線より上がへこみのない形（＝凸集合）になるような函数です。例えば、指数関数は凸函数です。数学的に厳密に言うと、函数f上の任意の2点x, yに対し、t ∈ [0, 1] なる任意のtについて、以下の不等式が成り立つ場合、この函数を凸函数と呼びます。

  • f ((1- t ) x + t y ) ≤ (1 - t ) f ( x ) + t f ( y )

そして、目的関数が凸函数で、その実行可能領域が凸集合であるような最適化問題が凸計画問題と呼ばれることになあります。凸集合とは、へこみのない形になるような集合です。

凸計画問題を解くときは、特に制約がなければ、微分して0になる点を探すようにします。微分して0になるとき、極値を取ることが多いので、これで解ける可能性があります。微分して0になる点は、代数方程式の形で計算できることもあります。もし、計算できない場合はニュートン法などの数値計算を行えば近似解を求められます。

制約条件がある場合、ラグランジュの乗数法などを用いることができます。

  • 最大化問題において、最大「解」と最大「値」は何が違うのでしょうか。
  • 凸集合、凸函数とは何でしょうか。定義を調べてみてください。
  • ある函数fの2階微分f''が正または0であることが、fが凸函数であることの必要十分条件となることを示してください。
  • 自然言語処理において、どのような場合に最適化問題を解く必要が出てくるのでしょうか。