Hybrid Methods in Polynomial Optimisation

Johannes Aspman, Gilles Bareilles, Vyacheslav Kungurtsev, Jakub Mareček, Martin TakáčarXiv 2023 · DOI · arXiv

Abstract

The Moment/Sum-of-squares hierarchy provides a way to compute the global minimizers of polynomial optimization problems (POP), at the cost of solving a sequence of increasingly large semidefinite programs (SDPs). We consider large-scale POPs, for which interior-point methods are no longer able to solve the resulting SDPs. We propose an algorithm that combines a first-order method for solving the SDP relaxation, and a second-order method on a non-convex problem obtained from the POP. The switch from the first to the second-order method is based on a quantitative criterion, whose satisfaction ensures that Newton's method converges quadratically from its first iteration. This criterion leverages the point-estimation theory of Smale and the active-set identification. We illustrate the methodology to obtain global minimizers of large-scale optimal power flow problems.

Introduction

Polynomial Optimization Problems (POPs) are foundational to fields like power systems engineering and robotics. The standard approach for solving them is the Lasserre (Moment/Sum-of-Squares) hierarchy, which transforms non-convex POPs into a sequence of convex Semidefinite Programs (SDPs).

However, a significant scalability barrier exists: as problem size or hierarchy order increases, the resulting SDPs become computationally overwhelming for traditional interior-point methods. While First-Order Methods (FOMs) are memory-efficient and can handle larger problems, they often struggle to reach high numerical precision, exhibiting a "tailing off" effect. This research introduces a hybrid method that combines the scalability of FOMs with the high-speed precision of second-order Newton methods.

Methodology: The Two-Phase Hybrid Algorithm

The proposed algorithm operates in two distinct phases, bridged by a rigorous mathematical trigger:

  1. Phase 1 (First-Order Warm-up): A first-order method (coordinate descent on a Burer-Monteiro reformulation) solves the SDP relaxation to provide a low-accuracy global minimizer approximation.
  2. Active Set Identification: KKT residuals from Phase 1 identify likely "active" inequality constraints, simplifying the problem into a system of smooth equality constraints.
  3. The Switch (Smale’s $\alpha$-$\beta$ Theory): Instead of using heuristic iteration counts, the algorithm employs a quantitative "$\alpha$-test" based on Steve Smale’s point-estimation theory. This test identifies when a point is an "approximate zero," guaranteeing that Newton’s method will converge quadratically from the very first step.
Illustrative example showing the feasible region (a) and the convergence of the $\alpha$-test criterion (b).
  1. Phase 2 (Newton Finish): Once the $\alpha$-test is satisfied, the algorithm switches to Newton’s method on the reduced problem, achieving floating-point precision (e.g., $10^{-16}$) within a few iterations.

Experimental Evaluation

The methodology was evaluated using standard benchmarks for Alternating Current Optimal Power Flow (ACOPF), including IEEE 30-bus, 118-bus, and 300-bus systems. An illustrative 2D polynomial problem was also used to visualize the behavior of the $\alpha$-test and basins of attraction. The method successfully solved a 2383-bus Polish power grid instance, demonstrating its capability on large-scale real-world problems.

Key Results and Discussion

The algorithm consistently demonstrated a sharp drop in infeasibility and error once the switch to the second-order method occurred.

Convergence behavior showing the transition through hierarchy orders to the final Newton phase triggered by the $\alpha$-test.

Key findings include:

  • Quadratic Convergence: In the 118-bus case, Newton's method reached high precision in approximately 6 iterations post-switch.
  • Robustness: The $\alpha$-test effectively prevented "false starts" that occur when switching too early based on simple iteration counts, which can lead to oscillations in objective values.
  • Scalability: The method successfully solved the 2383-bus Polish grid problem, a task where traditional interior-point SDP solvers often fail due to dimensionality.

Conclusion

By leveraging the algebraic properties of polynomials, this hybrid approach turns the heuristic "switch" into a rigorous mathematical trigger. While the method shows great promise for large-scale problems like ACOPF, future work will focus on global optimality verification without high-precision SDP solutions and extending the first-order phase to higher-order hierarchies.

Summary updated

Abstract

The Moment/Sum-of-squares hierarchy provides a way to compute the global minimizers of polynomial optimization problems (POP), at the cost of solving a sequence of increasingly large semidefinite programs (SDPs). We consider large-scale POPs, for which interior-point methods are no longer able to solve the resulting SDPs. We propose an algorithm that combines a first-order method for solving the SDP relaxation, and a second-order method on a non-convex problem obtained from the POP. The switch from the first to the second-order method is based on a quantitative criterion, whose satisfaction ensures that Newton's method converges quadratically from its first iteration. This criterion leverages the point-estimation theory of Smale and the active-set identification. We illustrate the methodology to obtain global minimizers of large-scale optimal power flow problems.
BibTeX
@misc{aspman2023hybrid,
  author = {Johannes Aspman and Gilles Bareilles and Vyacheslav Kungurtsev and Jakub Mareček and Martin Takáč},
  title = {{Hybrid Methods in Polynomial Optimisation}},
  year = {2023},
  eprint = {2305.16122},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.16122},
}
Figure