非線形最適化概論

昨日、一昨日、Rのnls(non-linear square),optim("optim"ize)関数についてメモした。いずれも非線形最適化の関数である。

「非」「線形」最適化と銘打つからには、「線形」最適化もあり、「非線形」でも「線形」でもない最適化も存在する。

その最適化の関係については、こちらのサイトで。

• 簡単に言うと、
  
  • 連続問題か、不連続問題かで２大別する。
    
    • 不連続問題については遺伝アルゴリズムやグラフ理論につながる話し(遺伝アルゴリズムに関する記事はこちら。グラフ理論についてはこちら)
    • 連続問題はさらに「線形」と「非線形」とに２分される
      
      • 「線形最適化」
        
        • 「線形」は等式だけで出来ている場合には、「最適化」するまでもなく、答えが得られるので、問題として成立しない。「最適化」問題として成立するためには、等式ではなく、不等式で条件付けされている。このように、複数の変数の一次多項式の大小関係の制約で最適解を求めるのが「線形最適化」。１次の項のみが出てくるが、複数の変数の大小関係が作る「変数空間」はすべて直線で囲まれた多（平)面体になっている。直線上の１次微分は定数で、２次以上の微分はゼロ。また、多(平)面体の角は、微分不能である。こうした条件から、解き方は、微積分の世界ではなく、「線形最適化」問題に特徴的な性格を持つ
        • 他方、「非線形」最適化は、変数の１次以外の項(２次以上、三角関数、指数関数などなど)が入ってくる。ここに「線形」のような「不等式」の条件を入れると複雑になりすぎるので、普通は、「非線形最適化」といえば、１次の項以外の項を含む、等式(式の値)の最適化を行う。「線形最適化」のところで触れたとおり、こちらは、微分積分が登場する。(なので、Rをはじめとする、代数・応用数学系列の統計学で取り扱われている。)最急降下法では、勾配ベクトル(複数変数が作る多次元等高面における法線ベクトル(最も急な方向)の勾配)を用いる。Newton法では、２次の偏微分行列であるHesse行列を用いる。