凸最適化

とつさいてきか

「最良の答え」を探す問題のうち、偽の答えにつかまることがなく、短い時間で必ず本当の最良にたどり着ける形をしたもの。

条件を満たす中でいちばん良い答えを探す問題では、一般には、近くと比べて最良に見えるだけの答えにつかまってしまうことがあります。お椀のように底が一つしかない形の問題(凸な問題)なら、下っていけば必ず本当の底に着きます。計算にかかる時間の上限も、あらかじめ見積もれます。

ロケットを噴射しながら狙った地点に降ろす軌道の計算は、そのままでは凸ではありません。2007年、アチクメシェとプローエンは、この問題を、答えを変えずに凸な形に書き換えられることを示しました^[1]。短時間で確実に解けるので、機体に載せた計算機が降下中に何度も解き直せます。もとは火星着陸のための研究で、のちに再使用ロケットの着陸に使われました。