Strong duality is a condition inmathematical optimization in which the primal optimal objective and thedual optimal objective are equal. By definition, strong duality holds if and only if theduality gap is equal to 0. This is opposed toweak duality (the primal problem has optimal value greater than or equal to the dual problem, in other words theduality gap is greater than or equal to zero).

Each of the following conditions is sufficient for strong duality to hold:

• ${\displaystyle F=F^{\ast \ast }}$ where${\displaystyle F}$ is theperturbation function relating the primal and dual problems and${\displaystyle F^{\ast \ast }}$ is thebiconjugate of${\displaystyle F}$ (follows by construction of theduality gap)
• ${\displaystyle F}$ is convex and lowersemi-continuous (equivalent to the first point by theFenchel–Moreau theorem)
• the primal problem is alinear optimization problem
• Slater's condition for aconvex optimization problem.^[1][2]

Under certain conditions (called "constraint qualification"), if a problem is polynomial-time solvable, then it has strong duality (in the sense ofLagrangian duality). It is an open question whether the opposite direction also holds, that is, if strong duality implies polynomial-time solvability.^[3]

• Convex optimization
• Linear programming#Duality
• Dual linear program

• Linear programming
• Convex optimization

• Articles with short description
• Short description matches Wikidata