Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization

arXiv:2609.38435 · eess.SY, cs.SY, math.OC · Submitted 2026-09-29 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa, and with me are Dev and Taro, guest researcher.

Dev: Today's paper: "Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization".

Rosa: 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…

Dev: First, who's behind it and why it matters.

Paper summary: Dev: So, wrapping up our discussion on "Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization," the core finding is that mixing low-rank semidefinite programming with moment-based lifting allows a local solver to return the guaranteed globally optimal solution for this nonconvex mixed-integer polynomial problem.

Rosa: It's interesting because they are tackling a very difficult optimization landscape, and their approach is to iteratively tighten the moment-based relaxation of the AC Optimal Transmission Switching problem until it’s tight, and then re-solve that tighter model using a local, low-rank SDP solver called Knitro.

Taro: The implication for autonomy research is that this suggests a viable way to tackle highly constrained problems where you need absolute certainty about the solution quality, even if the underlying problem structure remains complex. It gives us a tool to approach hard optimization tasks with certified global results rather than just good approximations.

Dev: That's right; it confirms that by using these specific techniques, we can move beyond standard local solvers for certain types of mixed-integer polynomial problems and get a guaranteed global solution, provided the primal objective matches the dual bound and the solution is feasible in the original AC-OTS problem.

Rosa: Looking at the authors and title, it really shows how deep they went into combining different mathematical frameworks—low-rank SDP for scalability and moment lifting for relaxation—to achieve this result on a power grid optimization problem. It’s a very specific combination of tools applied to show what’s possible in theory.

Taro: I think the real impact lies in showing that even with nonconvexity and mixed-integer variables, we can develop structured methods that yield provable global optimality when they are applied correctly to specific models like AC-OTS. This opens up avenues for more complex scheduling or resource allocation problems where such guarantees matter.

Dev: It seems the main point is demonstrating a path from a difficult nonconvex problem to a verifiable global optimum using this hybrid SDP method, which has some tangible results on small test cases, even if it doesn't solve the entire real-world operational deployment challenge on its own.

Rosa: So, in simple terms, this paper provides anecdotal evidence that for these specific nonconvex mixed-integer polynomial power grid optimization problems, you can use a local solver to find the exact global solution by carefully combining low-rank SDP and moment lifting as described in "Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization."

Conclusion: Rosa: So, we’ve been diving deep into this paper that tackles the AC Optimal Transmission Switching problem using low-rank SDP and moment lifting to find guaranteed global solutions for those tricky mixed-integer polynomial problems.

Dev: It’s wild how they managed to combine low-rank matrices with those moment constraints to tame a notoriously hard optimization landscape, Rosa. I'm still trying to wrap my head around the specific loop rate and latency implications of running that kind of lifting process on real grid data.

Taro: From an autonomy standpoint, what really strikes me is how they address the uncertainty when things go wrong; this paper shows a way to get a provable global optimum even in these highly constrained scenarios.

Rosa: Exactly, Taro, and looking at the title itself, "Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization," it just tells you we’re using structural simplification to solve a massive headache.

Dev: And I'm curious about the authors; who are they on this team? Knowing their background might explain why they chose this specific combination of SDP and moment-based lifting over other relaxation techniques.

Taro: I think the real implication here is that we could apply these kinds of rigorous mathematical frameworks to any complex scheduling or resource allocation problem in autonomous systems where a guaranteed global result is needed for safety.

Rosa: That’s a big thought, Taro, but I wonder how quickly this kind of lifting methodology can be adapted when we take it out of the controlled lab environment and try to apply it to actual field robotics scenarios.

Dev: That brings up my concern about robustness; if we move this from a theoretical model to an operational control loop, how stable is the performance, and what happens if there’s a sudden failure in the underlying constraint set?

Taro: The paper suggests that the methodology itself provides a strong foundation for handling those failures because it targets global optimality, which means we’re not just getting a local fix when things misbehave.

Rosa: It sounds like this work is really pushing the boundaries of what’s possible with these mathematical tools, and it makes me wonder if other complex systems can benefit from this kind of structured approach to guarantee optimal outcomes.

Dev: Before we move on to those broader implications, I just want to make sure we nail down the practical limits; what are the specific conditions under which this guaranteed global optimality holds true for a real-world power system scenario?

Samuel Chevalier

University of Vermont

eess.SY, cs.SY, math.OC

Submitted: 2026-09-29

Updated: 2026-09-29

Comments: Submitted to Allerton 2026

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: 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

Key concepts

AC Optimal Transmission Switching (AC-OTS) Problem
This is a specific type of power grid optimization problem that involves deciding which transmission lines to switch on or off optimally. It is challenging because it includes both continuous variables (like voltage levels) and binary variables (for switching decisions), making it nonconvex and difficult to solve globally.
Low-Rank Semidefinite Programming (SDP)
This is a mathematical technique used as a relaxation method. Instead of solving the original complex problem directly, the researchers reformulate it into an SDP where one key matrix has a low rank. This simplification makes the resulting optimization problem computationally easier to solve using specialized low-rank SDP solvers.
Moment-Based Lifting Strategy
This is a method used to tighten initial mathematical relaxations. It involves systematically generating new constraints (cuts) based on products of existing constraints and variables. This process helps push the solution closer to the true, difficult global optimum of the original problem.
Global Optimality Check
Since the solver only guarantees a solution for a simplified version, a check is needed to confirm it's truly global. The paper uses a dual bound derived from the moment matrix trace. If the solver's result matches this bound and satisfies feasibility in the original problem, it is declared globally optimal.

Terminology

Summary

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.

The gist

By mixing low-rank SDP and moment-based relaxation tightening, this approach confirms that a local solver can find the exact, global solution to a mixed-integer polynomial AC Optimal Transmission Switching (AC-OTS) problem.

How it works: Problem Formulation and Canonicalization

The paper models the AC Optimal Transmission Switching (AC-OTS) problem in its full, nonconvex trilinear form involving voltage and binary variables. To apply lifting methods, this formulation is relaxed into a lifted SDP. The canonicalization involves constructing a vector of variables and an outer product matrix X that represents the problem structure: X = [1 x x T x ⊗s x] / z (Equation 9). This leads to a minimization problem involving the cost matrix C, moment constraints, and a term involving the rotated second order cone (RSOC) cut capturing quadratic generation costs.

How it works: Moment-Based Lifting Strategy

To tighten the initial relaxation, the paper proposes using RLT cuts exclusively rather than computationally expensive localizing matrices. RLT cuts are generated by taking products of constraints with variables, such as Product of inequality constraint ⟨Bi, X⟩ ≥ 0 and squared variable x2j. Result: x2j · ⟨Bi, X⟩ ≥ 0. The lifting is organized using tuples of tuples to represent monomials. A crucial step involves identifying linking constraints via a binary exponent filter and a tuple linking function to generate equality constraint matrices, which are then added to the set V.

How it works: Low-Rank SDP Solution Procedure

The final step solves the lifted SDP using a low-rank SDP solver (Knitro). The procedure involves:

  1. Choosing cuts based on heuristics like binary fuzziness or dual variable magnitude.

  2. Lifting by generating associated moment submatrices (e.g., xiX).

  3. Collecting missing monomials and expanding the monomial basis vector to ensure necessary terms are available for the RLT cuts.

  4. Rebuilding all optimization matrices (C, Ai, Bi, Ki) using the expanded basis vector ν˜ and lifted matrix X˜.

  5. Adding linking constraints via the binary exponent filter and tuple linking function to update set V.

  6. Solving the final low-rank SDP problem: cp = min x,t ⟨C, X⟩ + t (23a) s.t. λ0: ⟨A0, X⟩ = 1 (23b) λi: ⟨Ai, X⟩ = 0, ∀i ∈ E ∪ V ∪ Re (23c) µi: ⟨Bi, X⟩ ≥ 0, ∀i ∈ I ∪ M ∪ Rn (23d) s: t ≥ X i∈G ⟨Ki, X⟩2 (23e) X = Xr i=1 xix T i (23f).

How it works: Global Optimality Check

Since the low-rank SDP solution is only guaranteed to be a global solution for the convex relaxation, a feasibility test is required. The paper derives a dual bound d(λ, µ, s) using trace constraint on moment matrix X: tr(X) ≤ ρ. At optimality, if the primal objective cp matches this dual bound d(λ, µ, s), and the solution is feasible in the original AC-OTS problem (8), then it is declared globally optimal. This confirms that zero duality gap does not imply global optimality for the nonconvex problem itself.

Case Study Test Results

Testing on a 3-bus test case showed effectiveness:

  1. Lifting results demonstrated success, reaching a globally optimal solution with exact binary values and a rank-1 voltage profile by lift number 6.

  2. Re-solving the lifted model using Knitro showed that when the search space was expanded to r = 8 and r = 9, Knitro could find a solution, but for r ≥ 10, the magnitude of negative slack matrix eigenvalues dropped by orders of magnitude, indicating a certified global solution.

  3. The paper concludes that this approach provides an actual mixed-integer polynomial AC-OTS problem can be solved to guaranteed global optimality with a local solver.

Conclusion

The paper demonstrates that a local, low-rank SDP solver (Knitro) can provide a guaranteed globally optimal and feasible solution to a nonconvex, mixed integer polynomial optimization problem.

Improvements for AI systems

Here are the specific improvements that could be made to AI systems, based on the methodologies and findings presented in this scientific paper:

  1. Improved Scalability for Nonconvex Mixed-Integer Problems:

  2. Guaranteed Global Optimality for Power Grid Scheduling/Control:

  3. Efficient Solving of Large-Scale Low-Rank Optimization Subproblems:

  4. Automated Search Strategy for Complex Combinatorial Problems:

Here is a detailed breakdown of what the improved AI system can do in each area:

  1. Improved Scalability for Nonconvex Mixed-Integer Problems:

In the current landscape, solving large, realistic optimization problems (like those in power grids) often requires exponentially slow branch-and-bound methods. The paper introduces a hybrid approach combining moment-based relaxation tightening (from the Lasserre hierarchy) with low-rank semidefinite programming (LR-SDP). An improved AI system could utilize this to tackle models that are too large or complex for traditional solvers.

The improved system can:

  • Solve large, nonconvex mixed-integer polynomial problems (like AC Optimal Transmission Switching) that are intractable for standard branch-and-bound.

  • Achieve convergence on the global optimum in problems with massive constraint sets (e.g., 10k+ constraints) by leveraging the scalability of low-rank SDP solvers instead of relying solely on exhaustive search or complex cut generation.

  1. Guaranteed Global Optimality for Power Grid Scheduling/Control:

The paper provides a rigorous method to verify that a locally found solution is indeed the guaranteed global optimum by constructing and analyzing a Lagrange dual bound derived from the lifted SDP formulation. An improved AI system could integrate this verification step directly into its decision-making pipeline.

The improved system can:

  • Generate optimal power grid schedules (e.g., optimal transmission switching, generator dispatch) with mathematical certainty that the solution is globally optimal, rather than relying on heuristics or local search methods that might get stuck in local minima.

  • Ensure the generated control sequences are robust against global optimality gaps by incorporating a formal duality check as a final validation layer.

  1. Efficient Solving of Large-Scale Low-Rank Optimization Subproblems:

The paper specifically demonstrates how to leverage low-rank SDP solvers (like Knitro) by exploiting the structure of the problem through moment-based lifting and monomial basis expansion. This bypasses the need to solve large, dense SDPs, which are computationally expensive.

The improved system can:

  • Solve complex subproblems within a larger optimization framework (e.g., an inner loop of an outer heuristic) much faster than standard SDP methods by exploiting low-rank structures inherent in physical systems (like voltage profiles or flow matrices).

  • Handle high-dimensional problems efficiently by decomposing the problem into low-rank factors, drastically reducing the number of variables and constraints that need to be processed.

  1. Automated Search Strategy for Complex Combinatorial Problems:

The paper outlines a systematic, iterative lifting routine (Steps 1 through 8) for progressively tightening relaxations via RLT cuts, dynamic monomial basis expansion, and constraint linking. This forms a sophisticated search strategy rather than a single static solve.

The improved system can:

  • Employ an adaptive search strategy where the complexity of the relaxation is dynamically managed based on real-time feedback (e.g., dual variable magnitudes or constraint tightness).

  • Automatically determine the minimal necessary expansion of its monomial basis vector to satisfy specific lifting requirements, ensuring computational efficiency while guaranteeing convergence toward a global solution.

  • Implement an automated mechanism to select the most effective RLT cuts in each iteration, optimizing the trade-off between relaxation tightness and computational cost.

Sources

Related papers