A polyhedral homotopy algorithm for computing critical points of polynomial programs

Authors Julia Lindberg, Leonid Monin, Kemal Rose

Publication date 8 February 2023

Nonconvex programming, global optimization (90C26) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Numerical algebraic geometry (65H14) Polynomial optimization (90C23)

Abstract: In this paper we propose a method that uses Lagrange multipliers and numerical algebraic geometry to find all critical points, and therefore globally solve, polynomial optimization problems. We design a polyhedral homotopy algorithm that explicitly constructs an optimal start system, circumventing the typical bottleneck associated with polyhedral homotopy algorithms. The correctness of our algorithm follows from intersection theoretic computations of the algebraic degree of polynomial optimization programs and relies on explicitly solving the tropicalization of a corresponding Lagrange system. We present experiments that demonstrate the superiority of our algorithm over traditional homotopy continuation algorithms.

This page was built for publication: A polyhedral homotopy algorithm for computing critical points of polynomial programs

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