非線形最適化問題は確率的勾配降下法で解けるのか？

極地が一つしか無い線形計画問題でなら、部分的な最適化を繰り返すと全体の最適化になる、というのはなんとなくわかります。
非線形最適化問題であっても、部分的な最適化を繰り返すことで全体の最適化になるのでしょうか？

質問者からの補足コメント

• では、勾配法と確率的勾配降下を比較した時、確率的勾配降下のほうが比較的良い解に収束しやすい、ということはないでしょうか？

  No.1の回答に寄せられた補足コメントです。 補足日時：2018/03/07 23:07

No.2 ベストアンサー 回答者： stomachman 回答日時： 2018/03/07 23:44

No.1へのコメントについて、そりゃそうでしょ。

局所解にトラップされる心配を無視している方法と、何らか対策してる方法とを比べれば、そりゃ後者の方が良くなかったら対策になっとらんわけで。

No.1 回答者： stomachman 回答日時： 2018/03/07 19:38

Negative。

非線形の度合いにも依りますけれども、一般に、ちょびっとずつ改良するというやり方は局所解にトラップされるということがしばしば起こります。評価関数の谷底を目指して進んで行ったら、途中でモグラの穴に落ち込んで、それより下には進めなくなってしまった、ということです。これを避けるために、いろんな所から出発してみるだとか、収束しそうになったらわざとかき回す「焼き鈍し法」だとか、評価関数を最初に平滑化しとくだとか、評価関数全体を「傾け」ても転がり出さないかをチェックするとか、ま、いろいろ数値計算上の工夫はありますけれども、それだけじゃ「間違いなく、ここが最適である」という証明にはならん。（なぜなら、どこかに小さいけれど底なしの井戸みたいな穴が存在するかも知れんから。）「ここが最適だ」と保証したければ、モデル（制約条件）に固有の性質をうまく使って証明する必要があります。