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:
- Compressed Sensing: Laurent El Ghaoui et al. demonstrate in Testing the nullspace property using semidefinite programming that adding redundant column-wise norm bounds restricts the relaxed feasible set, providing tighter performance certificates for individual measurement matrices.
- Robust Beamforming: Yongwei Huang et al. tighten a restricted Linear Matrix Inequality (LMI) relaxation for robust beamforming in Robust Downlink Transmit Optimization Under Quantized Channel Feedback via the Strong Duality for QCQP by incorporating additional valid convex constraints.
- Adaptive Signal Processing: For robust adaptive beamforming under non-convex uncertainty sets, Hao Fu et al. incorporate additional valid linear constraints into an LMI relaxation in Robust Adaptive Beamforming via Worst-Case SINR Maximization With Nonconvex Uncertainty Sets, reducing the feasible region to facilitate the recovery of optimal rank-one solutions.
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.