Exploiting algebraic structure in global optimization and the Belgian chocolate problem

DOI10.1007/S10898-018-0659-5zbMATH Open1417.90117arXiv1708.08114OpenAlexW2752564485WikidataQ129901992 ScholiaQ129901992MaRDI QIDQ1756771FDOQ1756771

Authors: Nigel Boston, Zachary B. Charles 

Publication date: 21 December 2018

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: The Belgian chocolate problem involves maximizing a parameter {delta} 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 {delta}. By contrast, our method locates the largest known value of {delta} 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 {delta}. Using this approach, we find the largest known value of {delta} to date, {delta} = 0.9808348. We also demonstrate that in low degree settings, our method recovers previously known upper bounds on {delta} and that prior methods converge towards the {delta} we find.

Full work available at URL: https://arxiv.org/abs/1708.08114

Recommendations

• Global optimization with polynomials and the problem of moments
• Global optimization of polynomials over real algebraic sets
• An introduction to polynomial and semi-algebraic optimization
• Solving global optimization problems over polynomials with GloptiPoly 2.1
• Optimization over polynomials: selected topics

zbMATH Keywords

global optimizationstabilitycontrol theoryBelgian chocolate problemsimultaneous stabilization

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Nonconvex programming, global optimization (90C26)

Cites Work

• Algorithm 795
• Simultaneous stabilization of linear systems
• On the Total Nonnegativity of the Hurwitz Matrix
• A branch-and-reduce approach to global optimization
• Some applications of randomized algorithms for control system design
• Global optimization in stabilizing controller design
• Gol'dberg's constants

Uses Software

• PHCpack

This page was built for publication: Exploiting algebraic structure in global optimization and the Belgian chocolate problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756771)