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:
- 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.
- Active Set Identification: KKT residuals from Phase 1 identify likely "active" inequality constraints, simplifying the problem into a system of smooth equality constraints.
- 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.
- 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.
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