The small octagon with longest perimeter

Charles Audet, Pierre Hansen and Frederic Messine
Journal of Combinatorial Theory, Series A
Volume 114, Issue 1 , January 2007, Pages 135-150
http://dx.doi.org/10.1016/j.jcta.2006.04.002

直径1の凸八角形の周長の最大値を定めている．Reinhardt (1922) による未解決問題だったらしい．
手法としては，まず問題を31個の場合に分ける．
そのうちの1つをまず大域的最適化問題として定式化して，その緩和を解く．
この緩和が1変数最適化問題になるので，適当な手法 (論文ではMapleを使っている) で解く．
その緩和が元の問題の実行可能解を返して，最適値が3.121147134...になることが分かった．
あとは，他の場合の最適値がこれより小さくなることを示す．
そのためにまず幾何的な論法でいくつかの場合を除外する．
そして，残った場合についてはまた大域的最適化問題として定式化する．
今度は緩和を解いても十分ではないので真の大域的最適解を求めようとする．
そのために区間演算などの精度保証付き数値計算技法を用いている．
これによって，最大周長が3.121147134...であることが示される．
この数字は厳密であり，1変数関数の制約付き最適化問題の最適値として書けているので，その意味でも厳密に最大周長が分かったことになるわけである．
ちなみに正凸八角形の最大周長は3.0615...であり，各辺の長さが同一な凸八角形の最大周長は3.0956...である．
論文の最後にそれらの図も描かれている．