In
is always greater than or equal to 0.
This means that for any minimization problem, called the
primal problem, the solution to the primal problem is always greater than or equal to the solution to the
dual maximization problem.
[1]: 225 Alternatively, the solution to a primal maximization problem is always less than or equal to the solution to the dual minimization problem.
Weak duality is in contrast to strong duality, which states that the primal optimal objective and the dual optimal objective are equal. Strong duality only holds in certain cases.[2]
Uses
Many primal-dual approximation algorithms are based on the principle of weak duality.[3]
Weak duality theorem
Consider a linear programming problem,
![{\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{maximize}}}\quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b,\\&x\geq 0,\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6b32c5a8442a465a43bb3421592a68542b16cb6) | | (1) |
where
is
and
is
. The dual problem of (1) is
![{\displaystyle {\begin{aligned}{\underset {y\in \mathbb {R} ^{m}}{\text{minimize}}}\quad &b^{\top }y\\{\text{subject to}}\quad &A^{\top }y\geq c,\\&y\geq 0.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e90dbcd22a0c8819372c0e68aae0f2cb58b8413)
| | (2) |
The weak duality theorem states that
for every solution
to the primal problem (1) and every solution
to the dual problem (2).
Namely, if
is a feasible solution for the primal maximization
linear program
and
![{\displaystyle (y_{1},y_{2},....,y_{m})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe9a28509cb4d902a3b54e4a583b2e55a9d529c1)
is a feasible solution for the dual minimization linear program, then the weak duality theorem can be stated as
![{\displaystyle \sum _{j=1}^{n}c_{j}x_{j}\leq \sum _{i=1}^{m}b_{i}y_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b716bc934987a44e32270560775adfc5756ff2cc)
, where
![{\displaystyle c_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a844d180d176af828d1636d4e85aa534d0b77baa)
and
![{\displaystyle b_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40a8c2db2990a53c683e75961826167c5adac7c3)
are the coefficients of the respective objective functions.
Proof:
cTx
= xTc
≤ xTATy
≤ bTy
Generalizations
More generally, if
is a feasible solution for the primal maximization problem and
is a feasible solution for the dual minimization problem, then weak duality implies
where
and
are the objective functions for the primal and dual problems respectively.
See also
References