Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
Abstract
Can a local solver return the guaranteed globally optimal solution to a nonconvex mixed-integer polynomial power grid optimization problem? By mixing low-rank semidefinite programming (SDP) and moment-based lifting in the Lasserre hierarchy, this paper provides anecdotal evidence in the affirmative. Specifically, we iteratively tighten a moment-based relaxation of the AC Optimal Transmission Switching (AC-OTS) problem, including higher order moment-based constraints, rooted in the Lasserre hierarchy, until it is tight (i.e., primal feasible). We then re-solve this problem using a local, low-rank SDP solver (Knitro), plugging the associated dual variables into a bounding Lagrange dual function. By demonstrating primal and dual objective agreement and primal feasibility, we confirm the solution as the exact, global solution. From these initial results, we hypothesize that mixing (i) low-rank (i.e., highly scalable) SDP methods with (ii) moment-based relaxation tightening could be a scalable alternative to global branch-and-bound-based methods.
Related
- On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
- A short proof of a range-relative FPTAS for polynomial integer optimization over bounded polyhedra
- Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization
- ILP-BO: Integer Linear Programming-Based Black-Box Optimization
- Fast Randomized Entropically Regularized Semidefinite Programming
BibTeX
@misc{chevalier2026lowrank,
title = {{Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization}},
author = {Samuel Chevalier},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38435},
eprint = {2609.38435},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38435},
}
RIS
TY - UNPB
TI - Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
AU - Samuel Chevalier
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38435
UR - https://arxiv.org/abs/2609.38435
AB - Can a local solver return the guaranteed globally optimal solution to a nonconvex mixed-integer polynomial power grid optimization problem? By mixing low-rank semidefinite programming (SDP) and moment-based lifting in the Lasserre hierarchy, this paper provides anecdotal evidence in the affirmative. Specifically, we iteratively tighten a moment-based relaxation of the AC Optimal Transmission Switching (AC-OTS) problem, including higher order moment-based constraints, rooted in the Lasserre hierarchy, until it is tight (i.e., primal feasible). We then re-solve this problem using a local, low-rank SDP solver (Knitro), plugging the associated dual variables into a bounding Lagrange dual function. By demonstrating primal and dual objective agreement and primal feasibility, we confirm the solution as the exact, global solution. From these initial results, we hypothesize that mixing (i) low-rank (i.e., highly scalable) SDP methods with (ii) moment-based relaxation tightening could be a scalable alternative to global branch-and-bound-based methods.
ER -