Complementarity Constraint

• Also called: complementarity condition, contact complementarity
• Category: Planning & manipulation › Trajectory optimisation
• Tags: contact, trajectory-optimization, nonlinear-programming, physics-simulation, legged-robots

A pair of nonnegativity conditions with a zero product, so at most one quantity can be positive; used to model contact, where force exists only if the gap is zero.

Definition

A complementarity constraint links two quantities that must both be nonnegative and whose product must be zero, written 0 ≤ a ⊥ b ≥ 0. At any solution at least one of the two is zero, and either may be positive only while the other stays at zero. The structure appears whenever a system switches between two regimes without an explicit switch variable, and it is the basis of the linear complementarity problem (LCP) and of mathematical programs with complementarity constraints.

Rigid contact is the standard robotics example. The distance φ(q) between a foot or finger and a surface must be nonnegative, the normal contact force λ must be nonnegative because surfaces can only push, and the force can be nonzero only when the distance is zero: 0 ≤ φ(q) ⊥ λ ≥ 0. Coulomb friction can be written with further complementarity conditions linking sliding velocity to whether the friction force is on the edge of the friction cone. Time-stepping rigid-body simulators developed in the 1990s, including the schemes of Stewart and Trinkle and of Anitescu and Potra, solve an LCP or a related complementarity problem at every step to find contact impulses. In trajectory optimization, Posa, Cantu and Tedrake (2014) added these constraints directly to a direct-transcription problem, so that the optimizer chooses when and where contacts are made and broken without the contact sequence being specified in advance.

The approach avoids the integer variables a mixed-integer formulation would use for contact on and off, but it brings its own difficulty. Complementarity constraints are nonconvex and violate the constraint qualifications that standard nonlinear programming solvers rely on, so solvers can stall or converge slowly. Common remedies are relaxing the product condition to φλ ≤ ε and tightening ε over a sequence of solves, moving the product into the cost as a penalty, or using solvers designed for complementarity problems. Good initial guesses matter a great deal, which is why contact-implicit optimizers are often warm started from simpler solutions.

Why it matters

Contact is the defining feature of legged locomotion and manipulation, and complementarity constraints are the standard exact way to write rigid contact in equations. They let simulators compute contact forces consistently and let optimizers discover contact timing, rather than requiring an engineer to fix the gait or contact sequence beforehand.

Key applications

• Contact-implicit trajectory optimization for legged robots and manipulation
• Time-stepping rigid-body simulation with contact and friction
• Landing, jumping and impact planning
• Modeling unilateral constraints such as joint limits and cables
• Differentiable physics formulations of contact

In practice

An engineer plans a landing for a quadruped dropped from a height. The trajectory optimization uses direct transcription with knot points every few milliseconds; for each foot and knot it adds the height of the foot above the ground and the vertical ground reaction force as variables with the conditions height ≥ 0, force ≥ 0 and height × force ≤ ε. The first solve uses a loose ε and an initial guess from a simple falling motion; each later solve tightens ε and is warm started from the previous solution. The final plan shows which feet touch down first and how the forces ramp up, and the engineer checks that the remaining complementarity violation is small enough that the plan does not rely on forces at a distance.

Common misconceptions

• Complementarity constraints make contact planning convex — they remove integer variables but are nonconvex and numerically hard for standard solvers
• A solution with a small relaxed product is physically exact — with φλ ≤ ε the optimizer can exploit small forces at small distances, so ε and the remaining violation must be checked
• All physics engines solve contact as a complementarity problem — many use penalty or compliant contact models or convex relaxations instead of strict complementarity

Who should know this

• Trajectory optimization and legged locomotion engineers
• Physics simulation developers
• Manipulation researchers planning through contact
• Numerical optimization practitioners in robotics

Related technologies

• Linear Complementarity Problem (LCP)
• MPCC (Mathematical Program with Complementarity Constraints)
• IPOPT
• Drake
• PATH Solver

Related terms

• Contact mode
• Mixed-Integer Programming
• Direct Collocation
• Penalty-Based Contact Model
• Coulomb Friction
• Warm Start

Related projects

• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
• ProtoMotions: NVIDIA framework for training simulated digital humans and humanoid robots on GPUs
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• PHC: Physics-based perpetual humanoid controller with fail-state recovery for real-time avatars
• SOFA Framework: Real-time physics simulation framework for medical simulation and soft tissue modeling
• Extreme Parkour with Legged Robots: RL system for legged robot parkour trained in under 20 hours