{{Short description|Concept in optimization}} 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.<ref>{{cite book | vauthors=((Boyd, S. P.)), ((Vandenberghe, L.)) | date= 2004 | title=Convex optimization | publisher=Cambridge University Press | url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf | isbn=978-0-521-83378-3}}</ref>{{rp|225}} Alternatively, the solution to a primal maximization problem is always less than or equal to the solution to the dual minimization problem. So, in short: weak duality states that any solution feasible for the dual problem is a lower bound to the solution of the primal problem.<ref>{{Cite web |title=Fundamentals of Linear Algebra and Optimization; Weak and Strong Duality |url=http://www.cis.upenn.edu/~cis5150/13_06-Weak-Strong.pdf |website=CIS UPenn |format=PDF |date=2020-11-23 |access-date=2025-12-11 |archive-date=2025-08-19 |archive-url=https://web.archive.org/web/20250819052600/http://www.cis.upenn.edu/~cis5150/13_06-Weak-Strong.pdf |url-status=bot: unknown }}</ref>
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.<ref>{{citation | last1 = Boţ | first1 = Radu Ioan | last2 = Grad | first2 = Sorin-Mihai | last3 = Wanka | first3 = Gert | doi = 10.1007/978-3-642-02886-1 | isbn = 978-3-642-02885-4 | location = Berlin | mr = 2542013 | page = 1 | publisher = Springer-Verlag | title = Duality in Vector Optimization | url = https://books.google.com/books?id=nwB0qExrF00C&pg=PA1 | year = 2009}}.</ref>
==Uses== Many primal-dual approximation algorithms are based on the principle of weak duality.<ref>{{citation|title=Handbook of Approximation Algorithms and Metaheuristics|first=Teofilo F.|last=Gonzalez|authorlink= Teofilo F. Gonzalez |publisher=CRC Press|year=2007|isbn=9781420010749|page=2{{hyphen}}12<!-- this is not a page range; do not replace the hyphen by a dash-->|url=https://books.google.com/books?id=QK3_VU8ngK8C&pg=SA2-PA12}}.</ref>
==Weak duality theorem== <!--- TODO: Change to a more general type of optimization problem, as given in Boyd, chapter 5. The ''primal'' problem: <math display="block>\begin{aligned} \underset{x \in \mathbb{R}^n}{\text{minimize}}\quad & f_0(x) \\ \text{subject to}\quad & f_i(x) \leq 0, \quad i= 1, \dots, m, & h_i(x) = 0, \quad i= 1, \dots, p. \end{aligned} </math> -->
Consider a linear programming problem, {{NumBlk|:| <math display="block>\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}</math>|{{EquationRef|1}}}} where <math>A</math> is <math>m \times n</math> and <math>b</math> is <math>m \times 1</math>. The ''dual'' problem of ({{EquationNote|1}}) is {{NumBlk|:| <math display="block>\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}</math> |{{EquationRef|2}}}}
The weak duality theorem states that <math>c^\top x^* \leq b^\top y^*</math> for every solution <math>x^*</math> to the primal problem ({{EquationNote|1}}) and every solution <math>y^*</math> to the dual problem ({{EquationNote|2}}).
Namely, if <math>(x_1,x_2,....,x_n)</math> is a feasible solution for the primal maximization linear program and <math>(y_1,y_2,....,y_m)</math> is a feasible solution for the dual minimization linear program, then the weak duality theorem can be stated as <math>\sum_{j=1}^n c_j x_j \leq \sum_{i=1}^m b_i y_i </math>, where <math> c_j </math> and <math> b_i </math> are the coefficients of the respective objective functions.
Proof: {{math| '''c'''<sup>T</sup>'''x''' {{=}} '''x'''<sup>T</sup>'''c''' ≤ '''x'''<sup>T</sup>''A''<sup>T</sup>'''y''' ≤ '''b'''<sup>T</sup>'''y''' }}
===Generalizations=== More generally, if <math>x</math> is a feasible solution for the primal maximization problem and <math>y</math> is a feasible solution for the dual minimization problem, then weak duality implies <math>f(x) \leq g(y)</math> where <math>f</math> and <math>g</math> are the objective functions for the primal and dual problems respectively.
==See also== *Convex optimization *Max–min inequality
==References== {{reflist}}
Category:Linear programming Category:Convex optimization