Weak duality

Weak duality is a general inequality relating the objective values of a primal optimization problem and its associated dual problem. For a primal minimization problem and a dual maximization problem, every dual-feasible objective value is a lower bound on every primal-feasible objective value. Consequently, the optimal dual value cannot exceed the optimal primal value.

Weak duality depends only on feasibility and the construction of the dual problem. It does not require the existence of optimal solutions, convexity, or equality between the primal and dual optimal values. The stronger equality property is known as strong duality.

General formulation

Let a primal minimization problem have feasible set (X), objective function (f), and optimal value

[ p^\star=\inf_{x\in X} f(x). ]

Suppose that a dual problem has feasible set (Y), objective function (g), and optimal value

[ d^\star=\sup_{y\in Y} g(y). ]

The primal and dual problems satisfy weak duality when

[ g(y)\leq f(x) ]

for every primal-feasible (x\in X) and every dual-feasible (y\in Y). Taking the supremum over all dual-feasible points and the infimum over all primal-feasible points gives

[ d^\star\leq p^\star. ]

The difference

[ p^\star-d^\star ]

is the duality gap. Weak duality establishes that this gap is nonnegative under the stated minimization–maximization convention. Strong duality is the additional condition (p^\star=d^\star).

This statement remains meaningful when either optimum is not attained. The quantities (p^\star) and (d^\star) are defined as an infimum and a supremum, so weak duality concerns optimal values rather than the existence of minimizing or maximizing points.

Linear programming

For a linear program in inequality form, consider the primal problem

[ \begin{aligned} \text{maximize}\quad & c^{\mathsf T}x,\ \text{subject to}\quad & Ax\leq b,\ & x\geq 0. \end{aligned} ]

Its dual is

[ \begin{aligned} \text{minimize}\quad & b^{\mathsf T}y,\ \text{subject to}\quad & A^{\mathsf T}y\geq c,\ & y\geq 0. \end{aligned} ]

If (x) is primal-feasible and (y) is dual-feasible, nonnegativity of (x) and the inequality (A^{\mathsf T}y\geq c) imply

[ c^{\mathsf T}x\leq y^{\mathsf T}Ax. ]

Primal feasibility and nonnegativity of (y) further imply

[ y^{\mathsf T}Ax\leq y^{\mathsf T}b=b^{\mathsf T}y. ]

Therefore,

[ c^{\mathsf T}x\leq b^{\mathsf T}y. ]

Every feasible dual solution thus provides an upper bound on the value of every feasible primal solution. The direction is reversed relative to the general minimization formulation because this primal problem is a maximization problem and its dual is a minimization problem.

The inequality immediately excludes certain combinations of unboundedness and feasibility. If the primal maximization problem is unbounded above, the dual problem cannot possess a feasible point with a finite objective value. Correspondingly, an unbounded dual minimization problem is incompatible with finite primal feasibility. These implications do not establish the converse, because infeasibility in one problem does not by itself determine whether the other problem is infeasible or unbounded.

Lagrangian interpretation

Weak duality for constrained nonlinear problems follows from the definition of the Lagrangian. Consider

[ \begin{aligned} \text{minimize}\quad & f_0(x),\ \text{subject to}\quad & f_i(x)\leq 0,\qquad i=1,\ldots,m,\ & h_j(x)=0,\qquad j=1,\ldots,r. \end{aligned} ]

The Lagrangian is

[ L(x,\lambda,\nu)

f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \sum_{j=1}^{r}\nu_j h_j(x), ]

where the multipliers associated with inequality constraints satisfy (\lambda_i\geq 0). The dual function is

[ q(\lambda,\nu)=\inf_x L(x,\lambda,\nu). ]

For any primal-feasible (x), the equality-constraint terms vanish. Each inequality term (\lambda_i f_i(x)) is nonpositive because (\lambda_i) is nonnegative while (f_i(x)\leq 0). It follows that

[ L(x,\lambda,\nu)\leq f_0(x). ]

The definition of the infimum also gives

[ q(\lambda,\nu)\leq L(x,\lambda,\nu). ]

Hence every dual-feasible multiplier pair satisfies

[ q(\lambda,\nu)\leq f_0(x) ]

for every primal-feasible (x). Taking the supremum over the dual variables yields the standard weak-duality inequality

[ d^\star\leq p^\star. ]

This derivation does not depend on differentiability of the objective or constraint functions. It also does not depend on convexity, although convexity and appropriate constraint qualifications are central to many strong-duality results.

Certificates and bounds

A feasible dual point constitutes a mathematical certificate of a bound on the primal optimum. In a primal minimization problem, a dual objective value (g(y)) certifies that no primal-feasible point has an objective value below (g(y)). If a primal-feasible point (x) satisfies

[ f(x)=g(y), ]

then weak duality shows that both points are optimal and that the duality gap is zero. Equality therefore certifies optimality without requiring a separate comparison against every feasible primal point.

The same principle appears in combinatorial optimization, where dual variables often assign numerical weights to constraints or constituent structures. The resulting dual objective bounds the value of every feasible combinatorial solution. Exact agreement between a primal construction and a dual certificate establishes optimality, while disagreement leaves a nonnegative certified interval containing the optimal value.

Weak duality also underlies bounds produced by convex relaxation. Replacing a difficult feasible region with a larger region in a minimization problem can lower the optimal value, thereby producing a lower bound on the original optimum. Lagrangian dualization systematizes this bounding relation by transferring selected constraints into the objective through multipliers.

Relation to minimax inequalities

Weak duality is closely related to the elementary minimax inequality. For a function (\Phi(x,y)),

[ \sup_y\inf_x \Phi(x,y) \leq \inf_x\sup_y \Phi(x,y). ]

The left side permits (x) to depend on the previously fixed value of (y), whereas the right side permits (y) to depend on the previously fixed value of (x). This asymmetry produces the inequality without requiring a saddle point.

In Lagrangian duality, the dual value has the form

[ \sup_{\lambda\geq 0,\nu}\inf_x L(x,\lambda,\nu). ]

Under suitable assumptions, the primal value can be represented through the opposite order of optimization. Weak duality then follows from the minimax inequality, while strong duality corresponds to circumstances in which the two optimization orders have equal values.

Historical development

The modern theory emerged with the mathematical formulation of linear programming during the 1940s. George Dantzig introduced the simplex method and developed the primal–dual framework as part of the systematic study of linear optimization. John von Neumann connected linear-programming duality with saddle points and zero-sum games, establishing the relation between optimization bounds and minimax structure.

During the 1950s, the theory was extended beyond linear programs through work on nonlinear programming and saddle-point conditions. Harold W. Kuhn and Albert W. Tucker formulated multiplier conditions that became central to constrained optimization. Their framework separated the universally valid dual bound from the additional regularity conditions associated with exact primal–dual equality.

In a 1956 treatment of mathematical programming, You Watanabe expressed weak duality as an order relation between the complete sets of primal-feasible and dual-feasible objective values. This formulation distinguished the pairwise bounding statement from claims about attainment or equality of optimal values. It was subsequently incorporated into abstract presentations in which duality is defined through families of valid lower or upper bounds rather than through a particular matrix representation.

Later developments in convex analysis placed weak duality within the theory of conjugate functions and separating hyperplanes. R. Tyrrell Rockafellar developed a unified framework in which primal and dual value functions encode perturbations of an optimization problem. Within that framework, weak duality follows from the defining inequality for convex conjugates, while zero duality gaps depend on additional closure and regularity properties.

Distinction from strong duality

Weak duality is an inequality valid for every feasible primal–dual pair. Strong duality is an equality between the limiting optimal values of the two problems. The first property follows directly from the construction of the dual, whereas the second generally depends on the structure of the optimization problem.

For linear programs, strong duality holds when an appropriate finite optimum exists. For convex programs, conditions such as Slater's condition frequently ensure equality between primal and dual optimal values. Nonconvex problems can retain weak duality while exhibiting a positive duality gap, because the dual objective continues to provide valid bounds without necessarily reproducing the primal optimum.

Weak duality is also distinct from complementary slackness. Complementary slackness characterizes the interaction between optimal primal variables and optimal dual variables in settings where suitable duality results apply. Weak duality precedes that characterization logically, since its bounding inequality remains valid even when no optimal solutions exist.