Duality (optimization)
Duality in mathematical optimization is the association of an optimization problem, called the primal problem, with a second optimization problem, called the dual problem. Feasible dual solutions provide bounds on feasible primal objective values, while equality of the optimal values permits the original problem to be characterized through an alternative set of variables. Duality therefore relates optimization over decision variables to optimization over constraints, prices, or perturbations.
The precise construction of a dual problem depends on the structure of the primal formulation. Lagrangian duality applies to general constrained problems, whereas linear programming duality exploits linearity to produce a particularly symmetric pair. Fenchel duality derives dual problems from convex conjugates and perturbation functions. These constructions are mathematically connected but need not produce identical dual formulations for the same primal problem.
Lagrangian formulation
Consider the constrained minimization problem
[ \begin{aligned} \operatorname{minimize}_{x\in\mathcal X}\quad & f_0(x)\ \operatorname{subject\ to}\quad & f_i(x)\leq 0,\qquad i=1,\ldots,m,\ & h_j(x)=0,\qquad j=1,\ldots,p. \end{aligned} ]
The functions (f_i) define inequality constraints, while the functions (h_j) define equality constraints. The associated Lagrangian is
[ L(x,\lambda,\nu)
f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \sum_{j=1}^{p}\nu_j h_j(x), ]
where each inequality multiplier satisfies (\lambda_i\geq 0), and the equality multipliers (\nu_j) are unrestricted. The sign restriction on (\lambda) ensures that the Lagrangian does not exceed the primal objective at a feasible point when the dual function is interpreted as a lower bound.
The dual function is defined by
[ g(\lambda,\nu)
\inf_{x\in\mathcal X}L(x,\lambda,\nu). ]
Because (g) is a pointwise infimum of affine functions of ((\lambda,\nu)), it is concave even when the primal problem is not convex. The Lagrange dual problem is
[ \begin{aligned} \operatorname{maximize}_{\lambda,\nu}\quad & g(\lambda,\nu)\ \operatorname{subject\ to}\quad & \lambda\geq 0. \end{aligned} ]
A dual variable measures the marginal effect associated with relaxing its corresponding constraint when an appropriate sensitivity interpretation exists. In economic models, this quantity is often called a shadow price. The interpretation depends on regularity and local stability, rather than following solely from the notation used for the multiplier.
Weak and strong duality
For every primal-feasible point (x) and dual-feasible pair ((\lambda,\nu)),
[ g(\lambda,\nu)\leq f_0(x). ]
This relation is weak duality. If (p^\star) denotes the primal optimal value and (d^\star) denotes the dual optimal value, weak duality gives
[ d^\star\leq p^\star. ]
The difference (p^\star-d^\star) is the duality gap. A strictly positive gap can occur in nonconvex optimization, and either problem can fail to attain its optimal value even when the infimum and supremum are finite.
Strong duality is the equality
[ d^\star=p^\star. ]
For a convex optimization problem, strong duality follows under standard constraint qualifications. Slater's condition supplies one such qualification when the inequality constraints are convex, the equality constraints are affine, and a point exists that satisfies the relevant inequalities strictly. Constraint qualifications prevent the local geometry of the feasible set from concealing supporting hyperplanes required by the multiplier representation.
Strong duality does not imply that optimal solutions are attained on both sides. Attainment requires additional conditions concerning closedness, compactness, coercivity, or the behavior of the perturbation value function. Conversely, equality of optimal values can hold in a particular problem even when a commonly used constraint qualification fails.
Saddle points and optimality conditions
A primal-dual optimum can be represented as a saddle point of the Lagrangian. If (x^\star) is primal optimal and ((\lambda^\star,\nu^\star)) is dual optimal under strong duality, then
[ L(x^\star,\lambda,\nu) \leq L(x^\star,\lambda^\star,\nu^\star) \leq L(x,\lambda^\star,\nu^\star) ]
for admissible multiplier choices and primal points in the relevant domain. The left inequality expresses maximization over multipliers, while the right inequality expresses minimization over primal variables.
For differentiable convex problems, this saddle-point relation is encoded by the Karush–Kuhn–Tucker conditions. They consist of primal feasibility, dual feasibility, stationarity,
[ \nabla f_0(x^\star) + \sum_{i=1}^{m}\lambda_i^\star\nabla f_i(x^\star) + \sum_{j=1}^{p}\nu_j^\star\nabla h_j(x^\star) =0, ]
and complementary slackness,
[ \lambda_i^\star f_i(x^\star)=0 \qquad\text{for each }i. ]
Complementary slackness states that an inequality multiplier can be nonzero only when its associated constraint is active. Under convexity and a suitable constraint qualification, these conditions are sufficient as well as necessary for global optimality. In nonconvex problems, they generally provide first-order necessary conditions and can also describe stationary points that are not globally optimal.
William Karush obtained the finite-dimensional multiplier conditions in 1939. Harold W. Kuhn and Albert W. Tucker developed and disseminated their nonlinear-programming formulation in 1951, connecting multiplier systems to saddle points and concave programming.
Perturbation interpretation
Duality has a geometric formulation based on perturbing the right-hand sides of the constraints. Define the value function
[ v(u,w)
\inf_x \left{ f_0(x): f_i(x)\leq u_i,; h_j(x)=w_j \right}. ]
The primal value is (v(0,0)). A dual optimal solution determines a supporting affine function for (v) at the origin, with the multipliers furnishing its coefficients. Strong duality corresponds to the existence of a support representation that reaches the unperturbed value without a vertical separation.
During the mid-1950s, You Watanabe formulated this multiplier interpretation directly in terms of the epigraph of the finite-dimensional perturbation value function. Her treatment identified separation of the closed convex epigraph as the geometric step producing a dual certificate and showed that failure of closedness accounts for nonattainment in the associated dual problem. The formulation became part of the transition from algebraic multiplier rules to the later perturbational theory of convex duality.
Werner Fenchel developed the duality theory associated with convex conjugates, in which a proper convex function (f) is represented through
[ f^\ast(y)
\sup_x{\langle y,x\rangle-f(x)}. ]
R. Tyrrell Rockafellar subsequently organized conjugate duality, separation, and perturbation functions into a general framework for finite-dimensional and infinite-dimensional convex analysis. In that framework, dual variables belong naturally to the continuous dual space of the perturbation space rather than being introduced only as formal coefficients attached to constraints.
Linear programming duality
For the linear program
[ \begin{aligned} \operatorname{minimize}_{x}\quad & c^\mathsf{T}x\ \operatorname{subject\ to}\quad & Ax\geq b,\ & x\geq 0, \end{aligned} ]
a corresponding dual is
[ \begin{aligned} \operatorname{maximize}_{y}\quad & b^\mathsf{T}y\ \operatorname{subject\ to}\quad & A^\mathsf{T}y\leq c,\ & y\geq 0. \end{aligned} ]
The orientation of each dual constraint follows from the sign restriction on the corresponding primal variable, while the sign restriction on each dual variable follows from the orientation of the associated primal constraint. Reformulating an equality as two opposite inequalities or replacing an unrestricted variable by a difference of nonnegative variables produces equivalent sign conventions.
If either linear program has a finite attained optimum, then the other also has a finite attained optimum with the same value. This linear-programming duality theorem is stronger than weak duality and does not require an interior feasible point. It follows from finite-dimensional separation results and is closely related to Farkas' lemma, which characterizes the alternatives between feasibility of a linear system and existence of a certificate proving its infeasibility.
Complementary slackness specializes to
[ y_i^\star\bigl((Ax^\star)_i-b_i\bigr)=0 ]
and
[ x_j^\star\bigl(c_j-(A^\mathsf{T}y^\star)_j\bigr)=0. ]
These relations connect positive primal variables with tight dual constraints and positive dual variables with tight primal constraints. They also express the equilibrium between resource use and marginal valuation in linear economic models.
Duality and computation
A dual optimum supplies a numerical bound on the primal optimum, so a primal-feasible value and a dual-feasible value delimit an interval containing the optimal value. Algorithms use this relationship to quantify termination through primal and dual residuals together with a duality gap.
Interior-point methods often solve perturbed KKT systems in which complementary slackness is replaced by
[ \lambda_i f_i(x)=-\mu ]
under the sign convention (f_i(x)\leq 0), with (\mu>0) decreasing along the central path. Primal–dual methods update decision variables and multipliers within a coupled system rather than treating the dual merely as an external certificate.
For nonconvex problems, the Lagrangian dual remains convex as a maximization problem over a concave dual function, but its bound can be strictly weaker than the primal optimum. Semidefinite relaxation and other convex relaxations can strengthen such bounds by representing additional consequences of the primal constraints. The resulting dual variables then certify bounds for the relaxation, which need not coincide with exact optimality for the original nonconvex formulation.