Tightening Convex Relaxations with Redundant Constraints

28 concepts22 papers1 proposal

In optimization, adding a constraint that is already logically implied by your existing constraints seems completely pointless. If you already know that $x^2 = 1$, explicitly adding the constraint $x^3 = x$ contributes no new information. In the original non-convex problem, this new constraint is entirely redundant.

Yet, across fields as diverse as computer vision, robotics, signal processing, and neural network verification, researchers are discovering that injecting these "useless" redundant constraints is the secret to solving hard non-convex problems.

When we translate a difficult non-convex problem into a tractable convex relaxation—such as a Semidefinite Program (SDP) or a Lagrangian dual—the rules of redundancy change. Constraints that were redundant in the original non-convex space suddenly become powerful geometric shears in the relaxed space, slicing away invalid solutions and forcing the relaxation to yield the exact global optimum.

The Geometry of Lifting

To understand why redundant constraints become informative, we have to look at how convex relaxations operate. Many non-convex problems are difficult because of non-linear interactions or manifold constraints (such as requiring a matrix to be a valid 3D rotation).

A common way to handle this is to "lift" the problem into a higher-dimensional space. In a Semidefinite Relaxation (SDR), we replace a vector of variables $x$ with a higher-dimensional matrix $X$ that is meant to represent the outer product $xx^T$. In the original non-convex problem, $X$ must satisfy a strict rank-one constraint ($\text{rank}(X) = 1$). Because the rank-one constraint is non-convex, the relaxation drops it entirely, requiring only that $X$ be positive semidefinite ($X \succeq 0$).

Original Non-Convex Space (Hard)       Lifted Convex Relaxed Space (Easy)
     [ Strict Manifold / Rank-1 ]              [ Expanded Feasible Set ]
               │                                         │
               ▼                                         ▼
      Redundant constraints                     These same constraints 
     add no new information.                   slice away high-rank, 
                                               physically invalid solutions!

By dropping the rank constraint, we vastly expand the feasible region. The solver is now free to choose matrices $X$ that are high-rank. These high-rank solutions represent physically or mathematically impossible states in our original problem, leading to a "loose" relaxation and a wide duality gap.

This is where redundancy saves us. If we take an algebraic identity that is trivially true for the vector $x$ and "lift" it into the matrix space $X$, it is often not automatically satisfied by high-rank matrices. By explicitly adding this lifted, redundant constraint to our convex program, we slice away large portions of the high-rank feasible region without touching any of the valid rank-one solutions.

As Jean B. Lasserre demonstrates in A Lagrangian relaxation view of linear and semidefinite hierarchies, systematically adding redundant constraints formed by the products of original polynomial constraints allows Lagrangian relaxations to eventually converge to the true global optimum. By enriching the objective and constraint structures with these higher-order interaction terms, we force the higher-dimensional relaxed variables to respect the implicit algebraic structure of the original lower-dimensional space.

Taxonomy of Redundant Constraints

Depending on the domain, these redundant constraints stem from geometry, physics, or pure logic.

Geometric and Manifold Tautologies

In computer vision and robotics, variables frequently represent physical rotations or coordinates on a sphere. Jesus Briales et al. show in Convex Global 3D Registration with Lagrangian Duality that adding logically redundant quadratic constraints—such as row/column orthonormality and handedness—tightens the Lagrangian dual relaxation of 3D alignment problems enough to guarantee exact global registration.

For relative pose estimation, Jesus Briales et al. leverage lifted sphere and rotation manifold constraints in A Certifiably Globally Optimal Solution to the Non-Minimal Relative Pose Problem to ensure the relaxed solution matches the global optimum. When dealing with non-central camera rigs, Ji Zhao 0001 et al. incorporate redundant constraints derived from rotation group orbitopes in A Certifiably Globally Optimal Solution to Generalized Essential Matrix Estimation, successfully restricting the relaxed search space to valid physical manifolds.

Algebraic and Logical Tautologies

In discrete optimization and neural network verification, constraints often represent logical bounds or activation functions. Jianting Yang et al. inject implicit algebraic relationships, termed tautologies, to verify binary neural networks in Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization, drastically tightening the resulting bounds without altering the underlying feasible set.

For continuous functions, William R. Strahl et al. show in Constructing Tight Quadratic Relaxations for Global Optimization: I. Outer-Approximating Twice-Differentiable Convex Functions that incorporating known linear constraints allows quadratic underestimators to be significantly tighter by permitting overestimation in structurally infeasible regions. Similarly, Duan Li 0002 et al. show in Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming that combining seemingly redundant linear constraints with linearization techniques yields significantly tighter relaxations for non-convex quadratically constrained quadratic programs (QCQPs).

Physical and Structural Invariants

Physical laws provide natural redundancy. For contact-rich manipulation planning, Shao Yuan Chew Chia demonstrates in Towards Tight Convex Relaxations for Contact-Rich Manipulation that expressing physics and dynamics across multiple reference frames introduces redundant constraints that narrow the gap between convex relaxations and non-convex physics.

In optimal transport, Junyu Chen et al. tighten semidefinite relaxations of the Gromov-Wasserstein distance in Semidefinite Relaxations of the Gromov-Wasserstein Distance by enforcing linear constraints like marginal consistency and non-negativity, preventing the relaxed matrix variables from becoming loose or unbounded.

Certifiable Optimality and Noise Robustness

The ultimate payoff of tightening relaxations with redundant constraints is certifiable global optimality. When a convex relaxation is sufficiently tight, the optimal solution to the relaxed problem will naturally satisfy the dropped non-convex constraints (e.g., the matrix solution will be exactly rank-one). When this happens, we have found the exact global minimum of the original NP-hard problem in polynomial time, and the solver can mathematically prove its optimality after the fact.

This exact recovery is especially vital in high-noise environments where standard relaxations break down. For instance, in robot trajectory estimation using range-only measurements, Abhishek Goudar et al. show in Optimal Initialization Strategies for Range-Only Trajectory Estimation that integrating redundant constraints ensures the SDP relaxation remains tight, preventing the solver from converging to physically invalid, high-rank solutions.

In A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers, Heng Yang et al. demonstrate that adding redundant quadratic constraints allows their algorithm to recover the exact global optimum for rotation search even when up to 95% of the data consists of outliers. Similarly, Linus Härenstam-Nielsen et al. utilize redundant mathematical identities in Semidefinite Relaxations for Robust Multiview Triangulation to preserve the convex structure of the optimization landscape under severe noise, ensuring the solver consistently reaches the true global minimum.

This principle also extends to signal processing and matrix certification:

Computational Efficiency and Scaling

Intuitively, adding more constraints to an optimization problem should make it slower. However, identifying the right redundant constraints can actually accelerate convergence or enable entirely new algorithmic formulations by providing a cleaner, more structured optimization landscape.

In inverse kinematics, Tarun Yenamandra et al. find in Convex Optimisation for Inverse Kinematics that incorporating mathematically implied geometric constraints provides additional structure that guides the optimization process directly toward the true minimum, bypassing the local minima traps that plague local solvers. For structured matrix problems, Utkan Onur Candogan et al. note in A note on convex relaxations for the inverse eigenvalue problem that adding redundant orthogonality constraints yields a massive boost in solution accuracy without a proportional increase in computational overhead.

Furthermore, redundant constraints can unlock structural properties that make problems compatible with faster solvers. In On the Scalability and Memory Efficiency of Semidefinite Programs for Lipschitz Constant Estimation of Neural Networks, Zi Wang et al. introduce redundant quadratic constraints to enforce an explicit trace constraint. This structural modification enables an exact penalty formulation, making the problem compatible with highly scalable first-order eigenvalue optimization methods and allowing SDP-based estimation to scale to large neural networks for the first time.

By treating redundancy not as waste, but as a tool to bridge the gap between lower-dimensional non-convex geometry and higher-dimensional convex spaces, these approaches turn seemingly intractable global optimization problems into reliable, certifiable engineering tools.

Key Foundational Work

A Lagrangian relaxation view of linear and semidefinite hierarchies (2013) — contributed 2 concept elements to this direction.
Testing the nullspace property using semidefinite programming (2011) — contributed 1 concept elements to this direction.
Message-Passing Algorithms for Quadratic Programming Formulations of MAP Estimation. (2011) — contributed 1 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_redundant_constraint_tightening_2298d26d_v2,
  title = {redundant constraint tightening},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/redundant-constraint-tightening/rdr_2298d26d0b2041b6acdd31b9b204a7d1/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake