Can the gap be negative?

Not for valid finite primal and dual optimal values in this minimization convention.

Can a positive optimal gap persist indefinitely?

Yes, for the same primal - dual formulation.

AI Glossary / Mathematics and optimization / Advanced

Duality gap

Definition

The duality gap is the difference between the optimal values of a primal optimization problem and its associated dual. For a minimization primal with finite optimal value p* and a Lagrange dual with finite optimal value d*, it is p* − d*. Weak duality ensures this difference is nonnegative. A zero gap means strong duality holds; a positive gap means this dual construction does not reach the primal optimum.

What it means

A feasible primal decision provides a cost that can actually be achieved within the model. A dual-feasible choice provides a lower bound on the best possible cost. Comparing these values helps distinguish a good available decision from a certified optimum.
Two related quantities need careful labeling. The optimal duality gap compares the best possible values on both sides. A current primal - dual gap compares a particular feasible objective with a particular valid dual bound. The latter can shrink as computation progresses even when the former is already zero. A remaining current gap does not, by itself, prove an intrinsic gap between the two optimization problems.

How it works

For a minimization problem, let x be primal-feasible and let λ represent dual-feasible multipliers, with any equality multipliers included as needed. Weak duality gives g(λ) ≤ d* ≤ p* ≤ f(x). Therefore f(x) − g(λ) bounds the objective improvement still possible from the current decision.
The current gap decomposes into three nonnegative parts: f(x) − p*, p* − d*, and d* − g(λ). These represent primal suboptimality, the optimal duality gap, and dual suboptimality. Improving either candidate addresses its corresponding part; it cannot remove an intrinsic positive optimal gap.
These statements assume the relevant values are finite. Infeasibility, unboundedness and undefined expressions involving infinities require separate analysis. In numerical software, approximate feasibility and the validity of the reported bound also matter before a small difference can serve as a certificate.

Three practical examples

A planning solver reports a feasible cost of 102 and a valid lower bound of 100. The plan is at most two objective units above the unknown optimum. The report does not establish that the optimal duality gap is two.
A discrete optimization model has a dual relaxation whose best value remains below the achievable optimum. Additional iterations on that unchanged dual cannot eliminate the intrinsic difference. A stronger formulation or different bounding method may help.
An optimization team uses an absolute stopping tolerance. If a valid current gap is below that tolerance, it has an objective-quality certificate for the model. This does not automatically certify every decision variable's closeness to an optimal decision.

Think of it this way

Imagine a feasible purchase price above a justified price floor. Better offers can lower the price, while better evidence can raise the floor. The distance between today's offer and today's floor measures remaining uncertainty. Even the strongest floor available from a particular method may stop below the lowest achievable price. That final separation is the optimal gap for that method's dual construction.

Worked example

Consider minimizing x subject to x belonging to {0, 1} and x ≥ 1/2. Only x = 1 satisfies both requirements, so the primal optimum is p* = 1.
Keep the discrete domain in the inner optimization and move the inequality into the Lagrangian. Written as 1/2 − x ≤ 0, it receives a multiplier λ ≥ 0. Thus L(x, λ) = x + λ(1/2 − x).
At x = 0, the Lagrangian equals λ/2. At x = 1, it equals 1 − λ/2. Taking the smaller of the two gives g(λ) = min(λ/2, 1 − λ/2).
For any λ, the smaller of these expressions cannot exceed their average, which is 1/2. At λ = 1, both expressions equal 1/2, so this upper limit is attained. The dual optimum is therefore d* = 1/2, and the optimal duality gap is 1 − 1/2 = 1/2.
The arithmetic shows why additional dual iterations cannot close the gap: every multiplier produces a bound at most 1/2. Nevertheless, the bound is valid. At λ = 0 the bound is zero; at λ = 1 it improves to 1/2; at λ = 2 it returns to zero. The best dual bound remains useful even though it does not certify the attainable cost of one as optimal by equality alone.

Illustrative case study

In a fictional review of the worked model, an analyst reports the feasible decision x = 1 and the multiplier λ = 0. The current primal - dual gap is one. After changing the multiplier to one, the gap falls to one-half. The decision itself has not improved; only the lower bound has improved.
A colleague suggests allowing every real x between zero and one. That altered model admits x = 1/2 and achieves cost one-half. It explains the numerical value of the bound, but it changes the original discrete decision requirement. A fractional result cannot be presented as a feasible solution to the original problem.
The team records the original optimum, the dual optimum and the relaxed model separately. It concludes that the positive gap is a property of this formulation and dual, not evidence that the optimizer merely needs more time.

Common misconceptions and mistakes

A small gap is meaningful only when the upper and lower bounds are valid and use the same objective convention. Subtracting an infeasible candidate's objective from an arbitrary solver estimate does not create a certificate.
Zero optimal gap concerns values; it does not by itself guarantee that both optima are attained. Relative-gap definitions also vary. Check the denominator, treatment of zero or negative objectives, and software convention before comparing percentages across tools.

Business use

Report the feasible objective, justified lower bound, absolute difference and stopping rule together. Explain whether the difference is a current certificate or a known optimal duality gap. Keep objective accuracy separate from feasibility tolerances, operational suitability and model quality.

Check your understanding

What is the worked primal optimum?

Answer: One. Which multiplier attains the best dual bound? λ = 1.

Why is x = 1/2 not an original feasible decision?

Answer: The original domain contains only zero and one.

Related terms

Dual problem
Lagrangian
primal problem
weak duality
strong duality
lower bound
relaxation
optimality certificate

Learn next

Compare current gaps with optimal gaps, then study constraint qualifications and stronger relaxations.

Sources

Aalto Dictionary of Machine Learning, duality gap. https://aaltodictionaryofml.github.io/ADictML_Main.pdf Stephen Boyd and Lieven Vandenberghe, Convex Optimization slides, chapter 5: weak and strong duality. https://web.stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf The discrete example and fictional review are original teaching illustrations.

Previous: DualDICE Next: Dueling bandit