Weak duality

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 maximization problem, called the primal problem, the solution to the primal 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.[1]

Uses

Many primal-dual approximation algorithms are based on the principle of weak duality.[2]

Weak duality theorem

The primal problem:

Maximize cTx subject to A xb, x ≥ 0;

The dual problem,

Minimize bTy subject to ATyc, y ≥ 0.

The weak duality theorem states cTxbTy.

Namely, if is a feasible solution for the primal maximization linear program and is a feasible solution for the dual minimization linear program, then the weak duality theorem can be stated as , where and are the coefficients of the respective objective functions.

Proof: cTx = xTcxTATybTy

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

  1. Boţ, Radu Ioan; Grad, Sorin-Mihai; Wanka, Gert (2009), Duality in Vector Optimization, Berlin: Springer-Verlag, p. 1, doi:10.1007/978-3-642-02886-1, ISBN 978-3-642-02885-4, MR 2542013.
  2. Gonzalez, Teofilo F. (2007), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, p. 2-12, ISBN 9781420010749.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.