Exploiting algebraic structure in global optimization and the Belgian chocolate problem

• Published in: Journal of global optimization 2018-10, Vol.72 (2), p.241-254
• Main Authors: Charles, Zachary, Boston, Nigel
• Format: Article
• Language: English
• Subjects: Algebra; Chocolate; Combinatorial analysis; Computer Science; Constraining; Global optimization; Iterative methods; Markov analysis; Mathematical analysis; Mathematics; Mathematics and Statistics; Methods; Operations Research/Decision Theory; Optimization; Real Functions; Upper bounds
• ISSN: 0925-5001; 1573-2916
• DOI: 10.1007/s10898-018-0659-5

The Belgian chocolate problem involves maximizing a parameter δ over a non-convex region of polynomials. In this paper we detail a global optimization method for this problem that outperforms previous such methods by exploiting underlying algebraic structure. Previous work has focused on iterative methods that, due to the complicated non-convex feasible region, may require many iterations or result in non-optimal δ . By contrast, our method locates the largest known value of δ in a non-iterative manner. We do this by using the algebraic structure to go directly to large limiting values, reducing the problem to a simpler combinatorial optimization problem. While these limiting values are not necessarily feasible, we give an explicit algorithm for arbitrarily approximating them by feasible δ . Using this approach, we find the largest known value of δ to date, δ = 0.9808348 . We also demonstrate that in low degree settings, our method recovers previously known upper bounds on δ and that prior methods converge towards the δ we find.