Tightening Semidefinite Relaxations with Redundant Constraints

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 240 papers58 conceptsfrozen 2026-10-04

In optimization, we often face a frustrating trade-off: we can either solve a problem quickly using local search and risk getting stuck in a "local minimum," or we can search for the "global optimum" and face exponential computation times. For critical tasks like robot navigation, power grid management, and neural network verification, a "good enough" local solution isn't always sufficient—we need the best possible answer and a way to prove it.

The emerging consensus across computer vision, robotics, and signal processing is that we can bridge this gap using Semidefinite Programming (SDP) relaxations. The secret to making these relaxations work isn't just better solvers, but a counter-intuitive mathematical trick: adding "redundant" constraints that tell the solver things it technically already knows.

The Geometry of the Relaxation Gap

To understand why redundant constraints matter, we first have to understand the "relaxation gap." Most difficult problems in combinatorial optimization or geometry are non-convex, meaning their feasible regions have "dents" or are composed of disconnected islands.

When we "relax" a problem into a convex one (like an SDP), we are essentially wrapping a tight rubber band around these islands to create a smooth, convex shape called a convex hull. We then solve the problem over this simpler shape. If we are lucky, the solution to the relaxed problem lands exactly on one of our original "islands." If we are unlucky, the solution lands in the empty space between them—the "gap."

As Weijun Xie and Yongchun Li explore in On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems, the "exactness" of a relaxation depends on how closely the boundary of this convex hull matches the original non-convex set.

The Power of Redundancy

A redundant constraint is a mathematical tautology—a statement that is logically implied by the existing rules. For example, if we know $x^2 = 1$, then it is redundant to say $x^3 = x$. In a standard solver, adding such a statement would be a waste of memory.

However, in the context of SDP relaxations, these constraints are transformative. When we "lift" a problem into the higher-dimensional space of matrices (the hallmark of SDP), these redundant identities become linear constraints that slice away parts of the relaxed feasible set that do not correspond to any real-world solution.

Researchers like Jesus Briales and Javier González Jiménez 0001 have used this to solve the 3D registration problem. By adding redundant quadratic constraints—such as the fact that the rows of a rotation matrix must be orthonormal—they can "tighten" the relaxation so effectively that the solver is guaranteed to find the globally optimal alignment, often 100x faster than previous global methods.

Systematic Tightening via Hierarchies

How do we find these "magic" redundant constraints? One systematic approach is the Moment-SOS (Sum-of-Squares) hierarchy, pioneered by Jean B. Lasserre.

In A Lagrangian relaxation view of linear and semidefinite hierarchies, Lasserre explains that we can generate a sequence of increasingly tight relaxations by multiplying existing polynomial constraints together. Each new product is technically redundant, but it adds a new "layer" of structural information. As the degree of these products increases, the relaxation is proven to eventually converge to the true global optimum.

This isn't just theoretical. In Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization, Jianting Yang and colleagues show that injecting these "tautologies" into first-order SDP relaxations can improve the accuracy of neural network verification bounds by up to 55%.

Applications Across Domains

The strategy of "tightening through redundancy" is appearing in nearly every field that deals with non-convex physics or logic:

The Numerical Limits of Tightness

While adding constraints helps "tighten" the math, it can sometimes "break" the solver. As networks or problems get deeper, the conditions required for numerical stability can disappear—a phenomenon dubbed the "interior-point vanishing problem" in recent verification research.

Furthermore, Zi Wang and Bin Hu note in LipDiff that while redundant constraints improve accuracy, they must be carefully integrated—for instance, by using them to facilitate "exact penalty methods"—to ensure that the resulting large-scale problems remain solvable by efficient first-order methods.

By treating redundancy not as a waste, but as a source of structural guidance, researchers are turning once-impossible non-convex problems into manageable, certifiably optimal convex ones.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 22 papers
  2. Version 1 · 2026-10-04 · 40 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_redundant_constraint_tightening_2298d26d,
  title = {redundant constraint tightening},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/redundant-constraint-tightening/rdr_2298d26d0b2041b6acdd31b9b204a7d1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_tightening_semidefinite_relaxations_with_2298d26d_v1,
  title = {Tightening Semidefinite Relaxations with Redundant Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tightening-semidefinite-relaxations-with-redundant-constraints/rdr_2298d26d0b2041b6acdd31b9b204a7d1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}