TL;DR
This paper introduces GloptiPoly, a MATLAB toolbox that leverages semidefinite programming (SDP) via the SeDuMi solver to find global optima for polynomial optimization problems. It offers a user-friendly interface for defining complex polynomial problems and provides a robust framework for generating a sequence of lower bounds that converge to the global optimum, often reaching it at low computational cost.
What Problem Does This Paper Address?
Many real-world optimization problems involve minimizing or maximizing polynomial functions subject to polynomial constraints. These problems can be notoriously difficult to solve globally, especially when the objective function or constraints are non-convex, leading to multiple local optima. Traditional methods often get stuck in local minima, failing to find the true global best solution. The challenge is to develop a systematic and reliable approach to find the guaranteed global optimum for such problems.
Methods
GloptiPoly tackles this challenge by reformulating the non-convex polynomial optimization problem into a sequence of convex Linear Matrix Inequality (LMI) relaxations. The core idea is based on the theory of moments and semidefinite programming. For a given relaxation order, GloptiPoly constructs an LMI problem that provides a lower bound on the global optimum. By increasing the relaxation order, these lower bounds monotonically converge to the true global optimum. The toolbox interfaces with the SeDuMi solver to efficiently solve these LMIs. GloptiPoly also includes features for automatically detecting global optimality and extracting the optimal solutions when they are found. It offers flexible ways to define polynomial problems, including symbolic definition with DefiPoly and handling of integer constraints.
Datasets
Not discussed in the paper. The paper focuses on the methodology and presents numerical experiments on various benchmark problems from existing literature (e.g., problems from [4, Pb. 8.2.5], [4, Pb. 3.5], [4, Pb. 4.9], [4, Pb. 13.2.1.1], Max-Cut problems, Rosenbrock's banana function).
Key Insights and Ideas
- LMI Relaxations for Global Polynomial Optimization: The fundamental insight is that non-convex polynomial optimization problems can be systematically relaxed into a sequence of convex LMI problems. This sequence provides a powerful tool for bounding and finding global optima.
- Monotonic Convergence: The sequence of lower bounds generated by increasing LMI relaxation orders is guaranteed to converge monotonically to the global optimum. This provides a strong theoretical foundation for the method.
- Automatic Global Optimality Detection: GloptiPoly incorporates mechanisms to automatically detect when the global optimum has been reached, rather than just providing a lower bound. This is a crucial practical feature.
- User-Friendly Interface: The toolbox aims to make complex polynomial optimization accessible through MATLAB, with features like symbolic definition (DefiPoly) and clear input/output structures.
- Handling Integer Constraints: The ability to incorporate integer constraints directly into the LMI framework extends the applicability of GloptiPoly to mixed-integer polynomial optimization.
Key Results
- GloptiPoly successfully solves a range of small- and medium-scale non-convex polynomial optimization problems, often reaching the global optimum at low computational cost.
- For several benchmark problems, the global optimum was reached with LMI relaxations of modest order (e.g., order 3 or 4).
- The paper demonstrates the effectiveness of GloptiPoly on various examples, including the six-hump camel back function, ellipse intersection problems, and quadratic programming problems, often achieving exact global optima.
- Performance tables show that computational time and LMI size increase with relaxation order, but for many problems, the optimum is found quickly.
Limitations and Future Work
- Variable Limitation: The current version of GloptiPoly has a limitation on the number of variables it can handle, particularly for quadratic problems (e.g., more than 19 variables can be problematic). The authors state this limitation should be removed in the future.
- Computational Cost: While often efficient, the computational cost (LMI size and CPU time) can increase significantly with the relaxation order, especially for problems with high degrees or many variables.
- Conditioning: Problems involving polynomial bases with increasing powers can be badly conditioned. The authors suggest scaling variables or using alternative bases like Chebyshev polynomials.
- Future Work: The authors mention the need to remove the variable limitation and suggest exploring alternative bases for improved conditioning. They also highlight the potential for GloptiPoly to be a general-purpose tool for a wide range of non-convex optimization problems.
Summary updated