The Gold Standard of Complementarity Problems

Chapter index

For two scalar quantities a and b, complementarity means a ≥ 0, b ≥ 0 and ab = 0. The compact notation 0 ≤ a ⟂ b ≥ 0 records all three requirements. At least one quantity is zero. Both may be zero. The condition does not require exactly one to be positive.

Draw the feasible pairs in the a–b plane. They lie on the nonnegative horizontal axis and the nonnegative vertical axis, including their shared origin. The interior of the positive quadrant is excluded because both factors would be positive. Points on the negative extensions of either axis are also excluded, even though their product is zero.

This picture immediately catches two common mistakes. The pair (−2, 0) satisfies the product equation but violates nonnegativity. The pair (2, 3) satisfies both inequalities but violates the product equation. Neither is complementary. The pairs (2, 0), (0, 3) and (0, 0) all satisfy the complete condition.

Why the zero–zero case matters

The origin can represent a transition between regimes. A contact may just close before a positive reaction develops. A resource constraint may be binding while its marginal value is zero. A route may have no flow even though its cost ties with a used route. Excluding the origin would remove these legitimate boundary cases.

The symbol ⟂ resembles perpendicularity because nonnegative vectors with zero inner product have disjoint positive components. It should not be interpreted as a statement about a physical right angle. In a model, each pair has its own meaning and units. A gap could be measured in millimetres and a force in newtons; their product is a mathematical condition, not a declaration that the two quantities have the same dimension.

Before calculating, write a sentence for each side of every pair. If you cannot explain why both sides should be nonnegative and why they cannot both be positive, the complementarity symbol is hiding a modelling decision that still needs to be made.

Contents · Next chapter

A nonlinear complementarity problem asks for a vector z such that z ≥ 0, F(z) ≥ 0 and zᵀF(z) = 0. The inequalities hold component by component. Since each product zᵢFᵢ(z) is nonnegative, a zero sum means that every individual product is zero. There is no cancellation between positive and negative terms when the inequalities are satisfied.

If F(z) = Mz + q for a matrix M and vector q, this becomes a linear complementarity problem, often abbreviated LCP. The word linear describes the mapping. The full feasible condition still contains the products zᵢwᵢ = 0, where w = Mz + q. It is not simply a linear system, and it is not automatically a linear programme.

There need not be an objective function to minimise. Some complementary systems come from optimality conditions; others describe an equilibrium under a set of behavioural or physical assumptions. Finding an equilibrium and finding a socially preferred outcome are different tasks. An equilibrium can satisfy the stated rules while performing poorly against a separate measure of cost, fairness or resilience.

Ferris and Pang’s primary survey of engineering and economic applications documents this distinction through contact, transport and economic models. Its value here is the modelling principle: identify what the equations express before attaching an optimisation claim to their solution.

A useful model record

Record the unknowns, their allowed ranges, the mapping F, the pairing order and the data used to build it. If there are three variables, there should be three identified complementarity partners in the standard NCP form. Additional conservation equations or free variables need an explicitly broader formulation; they must not disappear because the compact notation looks convenient.

Also distinguish the model from the algorithm. “Solve the complementarity problem” specifies the target conditions. A particular iterative method, starting point or stopping tolerance is a way of approaching that target. Those implementation choices may affect whether a solution is found without changing the mathematical definition of a solution.

Previous chapter · Contents · Next chapter

Consider z ≥ 0, w = 2z − 6 ≥ 0 and zw = 0. There are two possible branches. If z = 0, then w = −6, which violates w ≥ 0. If w = 0, then 2z − 6 = 0, giving z = 3. This produces w = 0 and satisfies all conditions. The unique solution is therefore (z, w) = (3, 0).

Change only the constant: w = 2z + 6. The branch z = 0 gives w = 6 and is valid. The branch w = 0 gives z = −3 and is invalid. The unique solution is now (0, 6). Solving the equation w = 0 without checking the lower bound would return an inadmissible negative decision.

For the family w = 2z − b, the complete answer is z = max(0, b/2). When b > 0, z is positive and w is zero. When b < 0, z is zero and w = −b is positive. At b = 0, both are zero. The formula is continuous but changes slope at the transition.

Interpret the answer before moving on

For a teaching interpretation, let z represent a nonnegative activity and let w represent its marginal cost minus a fixed marginal benefit. With cost slope 2z and benefit b, positive activity requires marginal balance. At zero activity, the cost-minus-benefit expression must be nonnegative; otherwise increasing activity would offer an improvement under this model.

This interpretation depends on the signs just stated. If you define F as benefit minus cost instead, you must change the inequality orientation appropriately. A verbal explanation that uses one sign convention while the code uses the opposite convention can produce a perfectly solved but incorrect model.

Check the transition numerically with b = −0.2, 0 and 0.2. The corresponding activities are 0, 0 and 0.1. At the middle value, a small positive change activates the decision, while a small negative change leaves it at zero. A derivative estimated across this switch is averaging different regimes, not measuring a single smooth response law.

Previous chapter · Contents · Next chapter

Let w₁ = 2z₁ + z₂ − 1 and w₂ = z₁ + 2z₂ − 3. We require z₁, z₂, w₁ and w₂ to be nonnegative, together with z₁w₁ = 0 and z₂w₂ = 0. Unlike two separate scalar problems, changing either variable changes both partners.

First assume z₁ = z₂ = 0. Then w = (−1, −3), so the inequalities fail. Next assume w₁ = 0 and z₂ = 0. The first equation gives z₁ = 1/2, but w₂ = 1/2 − 3 = −5/2, so this branch also fails.

Now assume z₁ = 0 and w₂ = 0. The second equation gives z₂ = 3/2. Then w₁ = 3/2 − 1 = 1/2. Every quantity is nonnegative, and both products vanish. This branch gives a valid solution: z = (0, 3/2), w = (1/2, 0).

Finally assume w₁ = w₂ = 0. Solving 2z₁ + z₂ = 1 and z₁ + 2z₂ = 3 yields z₁ = −1/3 and z₂ = 5/3. The negative first component invalidates the branch. We have checked all four branch choices and found exactly one solution.

What the calculation teaches

The unconstrained equation solution lies outside the nonnegative region. Clipping its negative component to zero is not enough: setting z₁ = 0 while keeping z₂ = 5/3 gives w₂ = 1/3, so z₂w₂ is positive. The remaining active equation must be solved again. Correct handling of the boundary changes the other variable from 5/3 to 3/2.

For a small problem, listing branches is transparent and complete. For n pairs, there are up to 2ⁿ branch labels, and degenerate solutions can appear under several labels. Enumeration is therefore a teaching and checking technique, not a claim of efficient scalability. Its lasting lesson is that equations selected by an assumed regime must always be followed by checks of the inequalities that justify that regime.

Previous chapter · Contents · Next chapter

Consider minimising Q(z) = z₁² + z₁z₂ + z₂² − z₁ − 3z₂ over z ≥ 0. Its gradient is exactly the mapping in the previous chapter. At a positive coordinate, a small increase or decrease is permitted, so the corresponding derivative must vanish at a differentiable minimum. At a zero coordinate, a small increase is permitted but a decrease is not; the corresponding derivative must be nonnegative.

These conditions combine into 0 ≤ z ⟂ ∇Q(z) ≥ 0. They reproduce the LCP solution z* = (0, 3/2). Evaluating the objective gives Q(z*) = 9/4 − 9/2 = −9/4.

We can prove global optimality directly. Write d = z − z*. Expanding the quadratic gives Q(z) − Q(z*) = (1/2)d₁ + d₁² + d₁d₂ + d₂². Since z₁ ≥ 0 and z*₁ = 0, d₁ ≥ 0. Also d₁² + d₁d₂ + d₂² = (d₁ + d₂/2)² + 3d₂²/4, which is nonnegative and zero only when d = 0. Thus every different feasible z has a larger objective.

A certificate has assumptions

Here complementarity identifies the unique global minimiser because the quadratic is strictly convex. For a general nonconvex differentiable objective, first-order complementary conditions alone do not establish global optimality. They can hold at points that are not minima. The proof must use the actual structure of the objective, not the reassuring appearance of the conditions.

For example, minimise f(z) = −(z − 1)² on the interval [0, 2]. At the interior point z = 1, the derivative is zero, yet this point is a maximum. The endpoints have objective −1, while the stationary point has objective 0. A solver for first-order equations can therefore return a stationary point without solving the original minimisation task.

For more general constrained programmes, constraint qualifications affect when multiplier conditions are necessary. Convexity and feasibility affect when they are sufficient. The safe explanation names the claim being made: a complementary equilibrium, a stationary point, a local minimum or a global minimum. These are not interchangeable labels.

Previous chapter · Contents · Next chapter

The existing Hungarian algorithm and optimal assignment article gives a specialist route into complementary slackness. A tiny example makes the relationship concrete. Suppose two workers must each receive one of two jobs, with costs 3 and 8 for the first worker and 7 and 4 for the second.

There are only two complete assignments. The diagonal assignment costs 3 + 4 = 7. The crossed assignment costs 8 + 7 = 15. Enumeration already proves that the diagonal choice is best, but we can also build a certificate that generalises beyond this tiny case.

Choose row potentials u = (3, 4) and column potentials v = (0, 0). Each sum uᵢ + vⱼ is at most its corresponding cost. The reduced costs are therefore 0, 5, 3 and 0. Any complete assignment uses each row and column once, so its total cost is at least u₁ + u₂ + v₁ + v₂ = 7.

The diagonal assignment uses only zero reduced-cost positions and reaches this lower bound. If xᵢⱼ denotes the selected assignment amount and rᵢⱼ the nonnegative reduced cost, then xᵢⱼrᵢⱼ = 0 for every pair. A selected positive assignment has zero reduced cost; an unused position may have positive reduced cost.

A zero reduced cost does not mean zero original cost

Both selected original costs are positive. The zeroes measure equality with the potential-based bound, not free labour or free service. Similarly, an unused position can have zero reduced cost in a different example; complementarity does not require it to be selected. The row and column constraints still decide whether the positions can form a complete assignment.

This example explains why a list of zero products alone is not an optimality proof. We also checked assignment feasibility and every reduced-cost inequality. The matching objective and bound complete the certificate. Removing any of these ingredients can turn a convincing-looking numerical pattern into an unsupported conclusion.

Previous chapter · Contents · Next chapter

Imagine a one-dimensional, frictionless, static teaching model. Let g be the gap between an object and a rigid stop, with g ≥ 0. Let r ≥ 0 be the compressive contact reaction. A simple compliance relation is g = g₀ + cr, where c > 0 and g₀ is the gap predicted without contact reaction.

Require gr = 0. If the free gap g₀ is positive, the object is separated and r = 0, giving g = g₀. If g₀ is negative, the free prediction would penetrate the stop. The contact branch imposes g = 0 and yields r = −g₀/c, which is positive. At g₀ = 0, both quantities can be zero.

Take c = 0.5 millimetres per newton and g₀ = −2 millimetres. The reaction is 4 newtons, and substitution gives g = −2 + 0.5 × 4 = 0 millimetres. With the same compliance but g₀ = 1 millimetre, the valid state is r = 0 and g = 1 millimetre.

Why solving the equality everywhere fails

If you insist on g = 0 even when g₀ = 1 millimetre, the equation returns r = −2 newtons. That would be an attractive reaction, which the frictionless nonadhesive stop in this model cannot provide. Complementarity lets separation occur rather than forcing an unphysical force to maintain contact.

The example does not model adhesion, friction, impact, plastic deformation or a flexible stop with its own dynamics. Adding these mechanisms may change the equations and admissible force laws. In particular, a static complementary condition is not by itself an impact law or an energy balance. Its role is to enforce the one-sided relationship assumed in this simplified setting.

For a real calculation, verify the sign convention with an easily understood case before scaling up. A positive external displacement away from the stop should not generate a compressive reaction. If it does, inspect the direction used for displacement, gap and force before adjusting solver settings.

Previous chapter · Contents · Next chapter

Suppose a total flow D must choose between two routes. Let x₁ + x₂ = D, with nonnegative flows. In an illustrative model, route costs are c₁ = 10 + x₁ and c₂ = 14 + 0.5x₂. Assume travellers are individually negligible, know these costs and choose a minimum-cost route. Let λ denote the minimum available cost at equilibrium.

The conditions are 0 ≤ xᵢ ⟂ cᵢ(x) − λ ≥ 0 for each route, together with conservation of flow. A used route has cost λ. An unused route cannot be cheaper than λ, but may be more expensive. This is an equilibrium condition under the stated behavioural assumptions.

For D = 2, placing all flow on route one gives costs 12 and 14. Choose λ = 12. The first pair has positive flow and zero excess cost; the second has zero flow and excess cost 2. All conditions hold. Forcing equal costs on both routes would incorrectly require a negative flow on route two.

For D = 8, both routes are used. Solve 10 + x₁ = 14 + 0.5x₂ with x₁ + x₂ = 8. Substitution gives 1.5x₁ = 8, so x₁ = 16/3 and x₂ = 8/3. Both route costs are 46/3. The positive flows justify the equality branch we assumed.

Equilibrium is not a universal best outcome

The route equations express individual minimum-cost choice. They do not automatically minimise total travel cost. For this model at D = 8, total cost is T = x₁(10 + x₁) + x₂(14 + 0.5x₂). Substituting x₂ = 8 − x₁ gives T = 144 − 12x₁ + 1.5x₁². Its minimum occurs at x₁ = 4 and x₂ = 4, with total cost 120.

At the individual equilibrium, total cost is 8 × 46/3 = 368/3, approximately 122.67. The difference arises because a traveller’s choice does not account for all congestion effects on others. These numbers belong only to our illustrative curves. They show why verifying equilibrium conditions does not settle a separate question about collective welfare.

Previous chapter · Contents · Next chapter

For the nonnegative orthant, complementarity is equivalent to the variational inequality F(z)ᵀ(y − z) ≥ 0 for every y ≥ 0. The equivalence can be derived directly, making the connection useful rather than merely terminological.

Suppose z and F(z) are nonnegative and their inner product is zero. Then F(z)ᵀ(y − z) = F(z)ᵀy ≥ 0 for any nonnegative y. Thus complementarity implies the variational inequality.

Conversely, suppose the variational inequality holds at a feasible z. Choose y = z + teᵢ for t > 0, where eᵢ changes only coordinate i. This gives tFᵢ(z) ≥ 0, so every component of F(z) is nonnegative. Next choose y = 0, obtaining −F(z)ᵀz ≥ 0. Nonnegativity gives the opposite inequality, so the inner product must be zero.

Broader feasible sets change the coordinate rules

The derivation relied on every nonnegative y being allowed. With a budget equation, coupled inequalities or another feasible set, those individual test directions may no longer be feasible. The general variational inequality remains useful, but the simple coordinatewise form needs to be derived for the actual set.

For a box with lower and upper bounds, the coordinate rule is different at each boundary: at a lower bound the associated F component is nonnegative, at an upper bound it is nonpositive, and in the interior it is zero. If the coordinate is fixed by equal lower and upper bounds, there is no feasible movement and this directional rule imposes no sign condition on that component.

The Variational Inequalities guide is the next step for feasible-direction reasoning beyond the orthant. Complementarity is a precise special structure within that wider landscape. Keeping the connection explicit prevents two errors: treating every equilibrium as an optimisation problem and applying orthant-specific sign rules to an unrelated feasible region.

Previous chapter · Contents · Next chapter

Given a computed candidate z, recompute F(z) from the original equations. Check the lower bounds on z, the lower bounds on F(z), and each product zᵢFᵢ(z). Use declared tolerances and report which pair has the largest violation. Checking only the sum of products is unsafe if negative components have not first been excluded.

For example, z = (1, 1) and w = (1, −1) have zᵀw = 0. Nevertheless w₂ is negative, and neither componentwise product is zero. The apparent cancellation is evidence that a necessary part of the test was omitted.

A useful alternative residual for the standard NCP is Rᵢ(z) = min(zᵢ, Fᵢ(z)). All residual components are exactly zero if and only if the complementary conditions hold. If the minimum is zero, neither entry can be negative and at least one is zero. This establishes the equivalence without relying on a product that can become tiny merely because one factor is tiny.

Approximate zero needs a scale

Suppose one variable measures a displacement in metres while its partner measures force in newtons. Taking their numerical minimum without nondimensionalising makes the residual depend on the chosen units. Select meaningful positive reference scales for variables and equations, transform both sides consistently and also report violations in original units.

A small residual is not automatically a small error in the unknown. In the scalar family F(z) = ε(z − 1), with tiny positive ε, the candidate z = 0 has a very small equation-side violation although the exact complementary solution is z = 1. The mapping is poorly conditioned in that scale. To turn residual size into a distance guarantee requires an appropriate error bound or stability argument.

When presenting a result, distinguish “the checked residual is below the stated tolerance” from “the decision is accurate to six decimal places.” The first is a reproducible numerical statement. The second needs additional information about conditioning and the relationship between residual and solution error.

Previous chapter · Contents · Next chapter

An active-set method guesses which member of each complementary pair is zero, solves the resulting equations and revises the guess when signs fail. Our four-branch calculation is the smallest transparent version of that idea. Large algorithms avoid naively exploring every possible label, but still have to negotiate changes of regime.

Another approach rewrites complementarity through a residual such as the componentwise minimum and seeks a zero. The resulting function is generally nonsmooth at switching points. Treating it as an ordinary smooth function everywhere can give an invalid derivative or an unreliable step.

The official GAMS PATH documentation, written by the solver’s developers, describes a Newton-based complementarity solver, model conventions and difficulties involving scaling and singularity. Consult its current documentation for implementation details. A solver’s success message should be followed by independent checks of the equations and complementary conditions you intended to model.

A failed iteration is not a mathematical nonexistence proof

An iteration may stall because of an unsuitable starting point, inaccurate derivatives, poor scaling, a singular local system or a model with no solution. These possibilities require different responses. Retrying with another start can be informative, but repeated failure still does not by itself prove that the equations admit no solution.

Conversely, obtaining the same answer from several starts does not prove uniqueness. The starts may lie in the same attraction region. To support uniqueness, use a mathematical property of the mapping or an exhaustive argument appropriate to a small problem. To support existence, a verified candidate is enough; to prove nonexistence requires ruling out every admissible candidate.

Keep an independent checker separate from the code that chooses regimes. If both share the same erroneous sign reversal or missing equation, agreement between them can be misleading. A checker built directly from the written model is more useful than a second display of the solver’s own internal residual.

Previous chapter · Contents · Next chapter

Simple scalar examples show why these are different questions. With F(z) = 1, z = 0 is the unique complementary solution. With F(z) = −1, there is no solution because the equation-side inequality can never hold. With F(z) = 0 for all z, every nonnegative z is a solution.

For a nonlinear example, take F(z) = (z − 1)(z − 2). At z = 0, F(0) = 2, so zero is a solution. The positive roots z = 1 and z = 2 are also solutions because F vanishes there. Thus the problem has three solutions, even though a numerical method might report only one of them.

Degeneracy refers here to a pair with both entries zero. It can make an active-set label ambiguous, but it does not necessarily imply multiple solutions. The scalar problem F(z) = z has the unique solution z = 0, and that solution has a zero–zero pair. Uniqueness and strict positivity of one member of every pair are separate properties.

A direct uniqueness argument under strong monotonicity

Suppose two complementary solutions are x and y. Nonnegativity and their zero own-products imply (x − y)ᵀ(F(x) − F(y)) = −xᵀF(y) − yᵀF(x) ≤ 0. If the mapping is strongly monotone, this same expression is at least m‖x − y‖² for some m > 0. Both statements can hold only when x = y.

This proves at most one solution under that assumption. It does not, by this argument alone, construct a solution or establish existence on an arbitrary domain. In the two-variable worked example, enumeration supplies existence, while the positive quadratic form supplies the relevant strictness. Keeping these proof jobs separate makes the conclusion easier to inspect.

Previous chapter · Contents · Next chapter

Return to the coupled example, but replace the first constant by a parameter a: w₁ = 2z₁ + z₂ − a and w₂ = z₁ + 2z₂ − 3. Keep nonnegativity and componentwise complementarity. Before reading the answer, predict when z₁ first becomes positive as a increases.

For a ≤ 3/2, the solution is z₁ = 0 and z₂ = 3/2. The corresponding w₁ = 3/2 − a is nonnegative, while w₂ = 0. At a = 3/2, the first pair becomes zero–zero. Increasing a further makes that old regime infeasible because w₁ would become negative.

For 3/2 ≤ a ≤ 6, set both w components to zero. Solving gives z₁ = (2a − 3)/3 and z₂ = (6 − a)/3. These are nonnegative precisely over the stated interval. At a = 6, the second variable reaches zero.

For a ≥ 6, set z₂ = 0 and w₁ = 0. Then z₁ = a/2 and w₂ = a/2 − 3 ≥ 0. The three formulas join continuously at the boundaries, but their derivatives differ. This is why sensitivity within one regime must not be extended indefinitely across a switch.

Check three changed contexts

At a = 1, the solution is (0, 1.5), reproducing the original case. At a = 3, the solution is (1, 1), with w = (0, 0). At a = 8, the solution is (4, 0), with w = (0, 1). Substitute each answer into both original equations and check every product; the exercise is complete only after those checks.

Now change the model rather than the parameter: impose an upper bound z₁ ≤ 1. The old orthant formulation no longer describes all feasible movements at that upper boundary. The box complementarity rule or explicit multiplier conditions must be used. Transfer means recognising which reasoning survives and which assumption has changed, not merely inserting a new number into the previous formula.

Previous chapter · Contents · Next chapter

What should I inspect when a result looks impossible?

Start with the pairing and signs. A force paired with the wrong gap, a multiplier paired with the wrong slack, or a benefit-minus-cost expression given the cost-minus-benefit inequality can invalidate the whole model. Then recompute original equations, bounds and products. Only after these checks should you investigate tolerances, derivatives and algorithm settings.

If a result is feasible but implausible, inspect the assumptions. The route-choice example assumes known costs and individually negligible travellers. The contact example assumes a static nonadhesive interaction. A numerically correct solution can expose a missing mechanism rather than a failed solver. Write down what observable evidence would challenge the assumptions.

Does complementarity mean exactly one quantity is zero?

No. At least one is zero, and both can be zero. The parameter transitions in Chapter 13 demonstrate why the shared zero case must remain admissible. Treating the condition as an exclusive either-or rule excludes real boundary solutions and can cause unnecessary switching in an implementation.

Can I just minimise the sum of squared products?

Not without the other conditions. Zero products allow negative entries, and minimising a residual can stop at a positive residual value. If you use a merit function, retain the correct bounds, inspect the actual residual at termination and distinguish a local minimum of the merit function from a zero that solves the complementary system.

Is a complementarity problem the same as an optimisation problem with complementarity constraints?

No. A complementarity problem seeks a state satisfying the conditions. An optimisation problem with complementarity constraints additionally chooses among admissible states according to an objective, often with other design variables. Adding that objective changes the mathematical task and can introduce substantial difficulty. A solved equilibrium subproblem does not automatically solve the surrounding design problem.

What is a useful learning sequence?

Begin by testing individual pairs, including negative and zero–zero cases. Solve the scalar family, then enumerate the coupled two-variable branches. Derive the quadratic certificate and the assignment lower bound. Next explain the contact and route-choice models in words before reproducing their equations. Finally solve the changed-parameter exercise without consulting the formulas.

For a practical computational project, implement the two-variable branch enumeration and an independent original-equation checker. Sweep a across the transition values and plot both variables and both partners. Verify the three analytical regimes rather than merely admiring a smooth-looking graph. Record failed branches and the precise inequality each violates.

Continue with the Variational Inequalities root for general feasible sets, and the Hungarian algorithm specialist article for a concrete primal–dual certificate. The primary Ferris–Pang survey broadens the application landscape, while the official PATH manual supplies current solver guidance. The durable skill is to connect the meaning of each pair to a calculation that someone else can independently check.

Previous chapter · Contents · Gold Standard master