Weak duality explained

In applied mathematics, weak duality is a concept in optimization which states that the duality gap 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] 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, where

m x n

and

m x 1

. The dual problem of is

The weak duality theorem states that

c^\topx^*\leqb^\topy^*

for every solution

x^*

to the primal problem and every solution

y^*

to the dual problem .

Namely, if

(x_1,x_2,....,x_n)

is a feasible solution for the primal maximization linear program and

(y_1,y_2,....,y_m)

is a feasible solution for the dual minimization linear program, then the weak duality theorem can be stated as

	n
\sum
	j=1

c_jx_j\leq

	m
\sum
	i=1

b_iy_i

, where

c_j

and

b_i

are the coefficients of the respective objective functions.

Proof:

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

f(x)\leqg(y)

where

and

are the objective functions for the primal and dual problems respectively.

Notes and References

Book: ((Boyd, S. P.)), ((Vandenberghe, L.)) . 2004 . Convex optimization . Cambridge University Press . 978-0-521-83378-3.
.
.

Weak duality explained

Uses

Weak duality theorem

Generalizations

See also

Notes and References