Finding largest small polygons with GloptiPoly

Didier Henrion (1, 2) , Frédéric Messine (3, 4)

1 FEL CTU - Faculty of Electrical Engineering [Prague]
2 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
3 ENSEEIHT - Ecole Nationale Supérieure d'Electrotechnique, d'Electronique, d'Informatique, d'Hydraulique et de Télécommunications
4 IRIT-APO - Algorithmes Parallèles et Optimisation

A small polygon is a convex polygon of unit diameter. We are interested in small polygons which have the largest area for a given number of vertices $n$. Many instances are already solved in the literature, namely for all odd $n$, and for $n=4, 6$ and $8$. Thus, for even $n\geq 10$, instances of this problem remain open. Finding those largest small polygons can be formulated as nonconvex quadratic programming problems which can challenge state-of-the-art global optimization algorithms. We show that a recently developed technique for global polynomial optimization, based on a semidefinite programming approach to the generalized problem of moments and implemented in the public-domain Matlab package GloptiPoly, can successfully find largest small polygons for $n=10$ and $n=12$. Therefore this significantly improves existing results in the domain. When coupled with accurate convex conic solvers, GloptiPoly can provide numerical guarantees of global optimality, as well as rigorous guarantees relying on interval arithmetic.

Domaines: Optimisation et contrôle [math.OC]

Didier Henrion, Frédéric Messine. Finding largest small polygons with GloptiPoly. Journal of Global Optimization, 2013, 56 (3), pp.1017-1028. ⟨10.1007/s10898-011-9818-7⟩. ⟨hal-00578944⟩