imported>WikiSysop |
imported>Macdonald-ross |
| Line 1: |
Line 1: |
| == Duality ==
| | '''William Donald Hamilton''' [[Royal Society|FRS]] (1 August 1936 – 7 March 2000) was an [[English people|English]] [[evolutionary biology|evolutionary biologist]] whom [[Richard Dawkins]] praised as one of the greatest [[evolution]]ary theorists of the 20th century.<ref>[http://www.edge.org/3rd_culture/hamilton/hamilton_index.html Obituary by Richard Dawkins – ''The Independent'' – 10 March 2000]</ref> |
|
| |
|
| Consider the following LP:
| | Hamilton became famous through his [[Theory|theoretical]] work on [[kin selection]] and [[altruism]]. He explained its [[Genetics|genetic]] basis, and this was a key part of the gene-centered view of [[evolution]]. In doing this, he became one of the forerunners of [[sociobiology]], as popularized by [[E.O. Wilson]]. Hamilton was certainly a big influence on Dawkins. He also published important work on [[sex ratio]]s and the [[evolution of sex]]. From 1984 to his death in 2000, he was the [[Royal Society]] Research Professor at [[Oxford University]]. He died of [[malaria]] contracted in the [[Democratic Republic of the Congo]]. |
| :<math>
| |
| \begin{align}
| |
| \text{minimize} && 7x_1+x_2+5x_3\\
| |
| \text{subject to} &&
| |
| x_1-x_2+3x_3 &\ge 10\\
| |
| &&
| |
| 5x_1-2x_2-x_3 &\ge 6\\
| |
| && x_1,x_2,x_3 &\ge 0
| |
| \end{align}
| |
| </math>
| |
|
| |
|
| Let <math>OPT</math> be the value of the optimal solution. We want to estimate the upper and lower bound of <math>OPT</math>.
| | == Hamilton's equation == |
| | Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.<ref>Hamilton W.D. 1996. ''Narrow roads of geneland: the collected papers of W.D. Hamilton'', vol 1. Freeman, Oxford.</ref> The gene will spread if '''r'''x'''b''' is greater than '''c''': |
| | :<math>rb > c \ </math> |
| | where: |
| | * <math>c \ </math> is the reproductive cost to the altruist, |
| | * <math>b \ </math> is the reproductive benefit to the recipient of the altruistic behavior, and |
| | * <math>r \ </math> is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness". |
|
| |
|
| Since <math>OPT</math> is the minimum over the feasible set, every feasible solution forms an upper bound for <math>OPT</math>. For example <math>\boldsymbol{x}=(2,1,3)</math> is a feasible solution, thus <math>OPT\le 7\cdot 2+1+5\cdot 3=30</math>.
| | == Collected papers == |
| | Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors. |
|
| |
|
| For the lower bound, the optimal solution must satisfy the two constraints:
| | * Hamilton W.D. 1996. ''Narrow roads of gene land vol. 1: Evolution of social behaviour''. Freeman, Oxford. ISBN 0-7167-4530-5 |
| :<math>
| | * Hamilton W.D. 2002. ''Narrow roads of gene land vol. 2: Evolution of sex''. Oxford University Press, Oxford. ISBN 0-19-850336-9 |
| \begin{align}
| | * Hamilton W.D. 2005. ''Narrow roads of gene land, vol. 3: Last words'' (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5 |
| x_1-x_2+3x_3 &\ge 10,\\
| |
| 5x_1-2x_2-x_3 &\ge 6.\\
| |
| \end{align}
| |
| </math>
| |
| Since the <math>x_i</math>'s are restricted to be nonnegative, term-by-term comparison of coefficients shows that
| |
| :<math>7x_1+x_2+5x_3\ge(x_1-x_2+3x_3)+(5x_1-2x_2-x_3)\ge 16.</math> | |
| The idea behind this lower bound process is that we are finding suitable nonnegative multipliers (in the above case the multipliers are all 1s) for the constraints so that when we take their sum, the coefficient of each <math>x_i</math> in the sum is dominated by the coefficient in the objective function. It is important to ensure that the multipliers are nonnegative, so they do not reverse the direction of the constraint inequality.
| |
|
| |
|
| To find the best lower bound, we need to choose the multipliers in such a way that the sum is as large as possible. Interestingly, the problem of finding the best lower bound can be formulated as another LP:
| | == References == |
| | {{Reflist}} |
|
| |
|
| ::<math>
| | {{DEFAULTSORT:Hamilton, William Donald}} |
| \begin{align}
| | [[Category:1936 births]] |
| \text{maximize} && 10y_1+6y_2\\
| | [[Category:2000 deaths]] |
| \text{subject to} &&
| | [[Category:English mathematicians]] |
| y_1+5y_2 &\le 7\\
| | [[Category:Geneticists]] |
| &&
| | [[Category:English evolutionary biologists]] |
| -y_1+2y_2 &\le 1\\
| | [[Category:Fellows of the Royal Society]] |
| &&3y_1-y_2 &\le 5\\
| |
| && y_1,y_2&\ge 0
| |
| \end{align}
| |
| </math>
| |
| | |
| Here <math>y_1</math> and <math>y_2</math> were chosen to be nonnegative multipliers for the first and the second constraint, respectively. We call the first LP the '''primal program''' and the second LP the '''dual program'''. By definition, every feasible solution to the dual program gives a lower bound for the primal program.
| |
| | |
| === LP duality ===
| |
| Given an LP in canonical form, called the '''primal''' LP:
| |
| :<math> | |
| \begin{align}
| |
| \text{minimize} && \boldsymbol{c}^T\boldsymbol{x}\\
| |
| \text{subject to} &&
| |
| A\boldsymbol{x} &\ge\boldsymbol{b}\\
| |
| && \boldsymbol{x} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| </math>
| |
| | |
| the '''dual''' LP is defined as follows:
| |
| :<math>
| |
| \begin{align}
| |
| \text{maximum} && \boldsymbol{b}^T\boldsymbol{y}\\
| |
| \text{subject to} &&
| |
| A^T\boldsymbol{y} &\le\boldsymbol{c}\\
| |
| && \boldsymbol{y} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| </math>
| |
| | |
| We then give some examples.
| |
| | |
| ;Surviving problem (diet problem)
| |
| Let us consider the surviving problem. Suppose we have <math>n</math> types of natural food, each containing up to <math>m</math> types of vitamins. The <math>j</math>th food has <math>a_{ij}</math> amount of vitamin <math>i</math>, and the price of the <math>j</math>th food is <math>c_j</math>. We need to consume <math>b_i</math> amount of vitamin <math>i</math> for each <math>1\le i\le m</math> to keep a good health. We want to minimize the total costs of food while keeping healthy. The problem can be formalized as the following LP:
| |
| :<math>
| |
| \begin{align}
| |
| \text{minimize} \quad& c_1x_1+c_2x_2+\cdots+c_nx_n\\
| |
| \begin{align}
| |
| \text{subject to} \\
| |
| \\
| |
| \end{align}
| |
| \quad &
| |
| \begin{align} a_{i1}x_{1}+a_{i2}x_{2}+\cdots+a_{in}x_{n} &\le b_{i} &\quad& \forall 1\le i\le m\\
| |
| x_{j}&\ge 0 &\quad& \forall 1\le j\le n
| |
| \end{align}
| |
| \end{align}
| |
| </math>
| |
| The dual LP is
| |
| :<math> | |
| \begin{align}
| |
| \text{maximize} \quad& b_1y_1+b_2y_2+\cdots+b_ny_m\\
| |
| \begin{align}
| |
| \text{subject to} \\
| |
| \\
| |
| \end{align}
| |
| \quad &
| |
| \begin{align} a_{1j}y_{1}+a_{2j}y_{2}+\cdots+a_{mj}y_{m} &\le c_{j} &\quad& \forall 1\le j\le n\\
| |
| y_{i}&\ge 0 &\quad& \forall 1\le i\le m
| |
| \end{align}
| |
| \end{align}
| |
| </math>
| |
| The problem can be interpreted as follows: A food company produces <math>m</math> types of vitamin pills. The company wants to design a pricing system such that
| |
| * The vitamin <math>i</math> has a nonnegative price <math>y_i</math>.
| |
| * The price system should be competitive to any natural food. A costumer cannot replace the vitamins by any natural food and get a cheaper price, that is, <math>\sum_{i=1}^my_ja_{ij}\le c_j</math> for any <math>1\le j\le n</math>.
| |
| * The company wants to find the maximal profit, assuming that the customer only buy exactly the necessary amount of vitamins (<math>b_i</math> for vitamin <math>i</math>).
| |
| | |
| ;Maximum flow problem
| |
| In the last lecture, we defined the maximum flow problem, whose LP is
| |
| :<math> | |
| \begin{align}
| |
| \text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
| |
| \begin{align}
| |
| \text{subject to} \\
| |
| \\
| |
| \\
| |
| \\
| |
| \end{align}
| |
| \quad &
| |
| \begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
| |
| \sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
| |
| f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
| |
| \end{align}
| |
| \end{align}
| |
| </math>
| |
| where directed graph <math>G(V,E)</math> is the flow network, <math>s\in V</math> is the source, <math>t\in V</math> is the sink, and <math>c_{uv}</math> is the capacity of directed edge <math>(u,v)\in E</math>.
| |
| | |
| We add a new edge from <math>t</math> to <math>s</math> to <math>E</math>, and let the capacity be <math>c_{ts}=\infty</math>. Let <math>E'</math> be the new edge set. The LP for the max-flow problem can be rewritten as:
| |
| :<math>
| |
| \begin{align}
| |
| \text{maximize} \quad& f_{ts}\\
| |
| \begin{align}
| |
| \text{subject to} \\
| |
| \\
| |
| \\
| |
| \\
| |
| \end{align}
| |
| \quad &
| |
| \begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
| |
| \sum_{u:(u,v)\in E'}f_{uv}-\sum_{w:(v,w)\in E'}f_{vw} &\le0 &\quad& \forall v\in V\\
| |
| f_{uv}&\ge 0 &\quad& \forall (u,v)\in E'
| |
| \end{align}
| |
| \end{align}
| |
| </math>
| |
| The second set of inequalities seem weaker than the original conservation constraint of flows, however, if this inequality holds at every node, then in fact it must be satisfied with equality at every node, thereby implying the flow conservation.
| |
| | |
| To obtain the dual program we introduce variables <math>d_{uv}</math> and <math>p_v</math> corresponding to the two types of inequalities in the primal. The dual LP is:
| |
| :<math>
| |
| \begin{align}
| |
| \text{minimize} \quad& \sum_{(u,v)\in E}c_{uv}d_{uv}\\
| |
| \begin{align}
| |
| \text{subject to} \\
| |
| \\
| |
| \\
| |
| \\
| |
| \end{align}
| |
| \quad &
| |
| \begin{align} d_{uv}-p_u+p_v &\ge 0 &\quad& \forall (u,v)\in E\\
| |
| p_s-p_t &\ge1 \\
| |
| d_{uv} &\ge 0 &\quad& \forall (u,v)\in E\\
| |
| p_v&\ge 0 &\quad& \forall v\in V
| |
| \end{align}
| |
| \end{align}
| |
| </math>
| |
| It is more helpful to consider its integer version:
| |
| :<math>
| |
| \begin{align}
| |
| \text{minimize} \quad& \sum_{(u,v)\in E}c_{uv}d_{uv}\\
| |
| \begin{align}
| |
| \text{subject to} \\
| |
| \\
| |
| \\
| |
| \\
| |
| \end{align}
| |
| \quad &
| |
| \begin{align} d_{uv}-p_u+p_v &\ge 0 &\quad& \forall (u,v)\in E\\
| |
| p_s-p_t &\ge1 \\
| |
| d_{uv} &\in\{0,1\} &\quad& \forall (u,v)\in E\\
| |
| p_v&\in\{0,1\} &\quad& \forall v\in V
| |
| \end{align}
| |
| \end{align}
| |
| </math>
| |
| In the last lecture, we know that the LP for max-flow is totally unimordular, so is this dual LP, therefore the optimal solutions to the integer program are the optimal solutions to the LP.
| |
| | |
| The variables <math>p_v</math> defines a bipartition of vertex set <math>V</math>. Let <math>S=\{v\in V\mid p_v=1\}</math>. The complement <math>\bar{S}=\{v\in V\mid p_v=1\}</math>.
| |
| | |
| For 0/1-valued variables, the only way to satisfy <math>p_s-p_t\ge1</math> is to have <math>p_s=1</math> and <math>p_t=0</math>. Therefore, <math>(S,\bar{S})</math> is an <math>s</math>-<math>t</math> cut.
| |
| | |
| In an optimal solution, <math>d_{uv}=1</math> if and only if <math>u\in S,v\in\bar{S}</math> and <math>(u,v)\in E</math>. Therefore, the objective function of an optimal solution <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math> is the capacity of the minimum <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.
| |
| | |
| === Duality theorems ===
| |
| Let the primal LP be:
| |
| :<math>
| |
| \begin{align}
| |
| \text{minimize} && \boldsymbol{c}^T\boldsymbol{x}\\
| |
| \text{subject to} &&
| |
| A\boldsymbol{x} &\ge\boldsymbol{b}\\
| |
| && \boldsymbol{x} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| </math>
| |
| | |
| Its dual LP is:
| |
| :<math>
| |
| \begin{align}
| |
| \text{maximum} && \boldsymbol{b}^T\boldsymbol{y}\\
| |
| \text{subject to} &&
| |
| A^T\boldsymbol{y} &\le\boldsymbol{c}\\
| |
| && \boldsymbol{y} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| </math>
| |
| | |
| {{Theorem|Theorem|
| |
| : The dual of a dual is the primal.
| |
| }}
| |
| {{Proof|
| |
| The dual program can be written as the following minimization in canonical form:
| |
| :<math>
| |
| \begin{align}
| |
| \min && -\boldsymbol{b}^T\boldsymbol{y}\\
| |
| \text{s.t.} &&
| |
| -A^T\boldsymbol{y} &\ge-\boldsymbol{c}\\
| |
| && \boldsymbol{y} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| </math>
| |
| Its dual is:
| |
| :<math>
| |
| \begin{align}
| |
| \max && -\boldsymbol{c}^T\boldsymbol{x}\\
| |
| \text{s.t.} &&
| |
| -A\boldsymbol{x} &\le-\boldsymbol{b}\\
| |
| && \boldsymbol{x} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| </math>
| |
| which is equivalent to the primal:
| |
| :<math>
| |
| \begin{align}
| |
| \min && \boldsymbol{c}^T\boldsymbol{x}\\
| |
| \text{s.t.} &&
| |
| A\boldsymbol{x} &\ge\boldsymbol{b}\\
| |
| && \boldsymbol{x} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| | |
| We have shown that feasible solutions of a dual program can be used to lower bound the optimum of the primal program. This is formalized by the following important theorem.
| |
| | |
| {{Theorem|Theorem (Weak duality theorem)|
| |
| :If there exists an optimal solution to the primal LP:
| |
| ::<math>
| |
| \begin{align}
| |
| \min && \boldsymbol{c}^T\boldsymbol{x}\\
| |
| \text{s.t.} &&
| |
| A\boldsymbol{x} &\ge\boldsymbol{b}\\
| |
| && \boldsymbol{x} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| </math>
| |
| :then,
| |
| ::<math>
| |
| \begin{align}
| |
| \begin{align}
| |
| \min && \boldsymbol{c}^T\boldsymbol{x}\\
| |
| \text{s.t.} &&
| |
| A\boldsymbol{x} &\ge\boldsymbol{b}\\
| |
| && \boldsymbol{x} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| &\begin{align}
| |
| \ge\\
| |
| \\
| |
| \\
| |
| \end{align}&\quad
| |
| \begin{align}
| |
| \max && \boldsymbol{b}^T\boldsymbol{y}\\
| |
| \text{s.t.} &&
| |
| A^T\boldsymbol{y} &\le\boldsymbol{c}\\
| |
| && \boldsymbol{y} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| {{proof|
| |
| Let <math>\boldsymbol{x}</math> be an arbitrary feasible solution to the primal LP, and <math>\boldsymbol{y}</math> be an arbitrary feasible solution to the dual LP.
| |
| | |
| We estimate <math>\boldsymbol{y}^TA\boldsymbol{x}</math> in two ways. Recall that <math>A\boldsymbol{x} \ge\boldsymbol{b}</math> and <math>A^T\boldsymbol{y} \le\boldsymbol{c}</math>, thus
| |
| :<math>\boldsymbol{y}^T\boldsymbol{b}\le\boldsymbol{y}^TA\boldsymbol{x}\le\boldsymbol{c}^T\boldsymbol{x}</math>.
| |
| | |
| Since this holds for any feasible solutions, it must also hold for the optimal solutions.
| |
| }}
| |
| | |
| A harmonically beautiful result is that the optimums of the primal LP and its dual are equal. This is called the strong duality theorem of linear programming.
| |
| | |
| {{Theorem|Theorem (Strong duality theorem)|
| |
| :If there exists an optimal solution to the primal LP:
| |
| ::<math>
| |
| \begin{align}
| |
| \min && \boldsymbol{c}^T\boldsymbol{x}\\
| |
| \text{s.t.} &&
| |
| A\boldsymbol{x} &\ge\boldsymbol{b}\\
| |
| && \boldsymbol{x} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| </math>
| |
| :then,
| |
| ::<math>
| |
| \begin{align}
| |
| \begin{align}
| |
| \min && \boldsymbol{c}^T\boldsymbol{x}\\
| |
| \text{s.t.} &&
| |
| A\boldsymbol{x} &\ge\boldsymbol{b}\\
| |
| && \boldsymbol{x} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| &\begin{align}
| |
| =\\
| |
| \\
| |
| \\
| |
| \end{align}&\quad
| |
| \begin{align}
| |
| \max && \boldsymbol{b}^T\boldsymbol{y}\\
| |
| \text{s.t.} &&
| |
| A^T\boldsymbol{y} &\le\boldsymbol{c}\\
| |
| && \boldsymbol{y} &\ge \boldsymbol{0}
| |
| \end{align}
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| | |
| == Matroid ==
| |
| | |
| === Kruskal's greedy algorithm for MST ===
| |
| | |
| === Matroids ===
| |
| Let <math>X</math> be a finite set and <math>\mathcal{F}\subseteq 2^X</math> be a family of subsets of <math>X</math>. A member set <math>S\in\mathcal{F}</math> is called '''maximal''' if <math>S\cup\{x\}\not\in\mathcal{F}</math> for any <math>x\in X\setminus S</math>.
| |
| | |
| For <math>Y\subseteq X</math>, denote <math>\mathcal{F}_Y=\{S\in\mathcal{F}\mid S\subseteq Y\}</math>. Obviously,<math>\mathcal{F}_Y=\mathcal{F}\cap 2^Y\,</math>.
| |
| | |
| {{Theorem|Definition|
| |
| :A set system <math>\mathcal{F}\subseteq 2^X</math> is a '''matroid''' if it satisfies:
| |
| :*(hereditary) if <math>T\subseteq S\in\mathcal{F}</math> then <math>T\in\mathcal{F}</math>;
| |
| :*(matroid property) for every <math>Y\subseteq X</math>, all maximal <math>S\in\mathcal{F}_Y</math> have the same <math>|S|</math>.
| |
| }}
| |
| | |
| Suppose <math>\mathcal{F}</math> is a matroid. Some matroid terminologies:
| |
| * Each member set <math>S\in\mathcal{F}</math> is called an '''independent set'''.
| |
| * A maximal independent subset of a set <math>Y\subset X</math>, i.e., a maximal <math>S\in\mathcal{F}_Y</math>, is called a '''basis''' of <math>Y</math>.
| |
| * The size of the maximal <math>S\in\mathcal{F}_Y</math> is called the '''rank''' of <math>Y</math>, denoted <math>r(Y)</math>.
| |
| | |
| ==== Graph matroids ====
| |
| Let <math>G(V,E)</math> be a graph. Define a set system with ground set <math>E</math> as
| |
| :<math>\mathcal{F}=\{S\subseteq E\mid \text{there is no cycle in }S\}.</math>
| |
| That is, <math>\mathcal{F}</math> is the set of all forests in <math>G</math>.
| |
| | |
| We claim that <math>\mathcal{F}</math> is a matroid.
| |
| | |
| First, <math>\mathcal{F}</math> is hereditary since any subgraph of a forest must also be a forest.
| |
| | |
| We then verify the matroid property of <math>\mathcal{F}</math>. Let <math>Y\subseteq E</math> be an arbitrary subgraph of <math>G</math>. Suppose <math>Y</math> has <math>k</math> connected components. For any maximal forest <math>S</math> in <math>Y</math> (i.e., <math>S</math> is a spanning forest in <math>Y</math>), it holds that <math>|S|=n-k</math>. In other words, for any <math>Y\subseteq E</math>, all maximal member of <math>\mathcal{F}_Y</math> have the same cardinality.
| |
| | |
| Therefore, <math>\mathcal{F}</math> is a matroid. Each independent set (of matroid) is a forest in <math>G</math>. For any subgraph <math>Y\subseteq G</math>, the rank of <math>Y</math> is the size of a spanning forest of <math>Y</math>.
| |
| | |
| ==== Linear matroids ====
| |
| Let <math>A</math> be an <math>m\times n</math> matrix. Define a set system <math>\mathcal{F}\subseteq 2^{[n]}</math> as
| |
| :<math>\mathcal{F}=\{S\subseteq [n]\mid S\text{ is a set of linearly independent columns in }A\}.</math>
| |
| | |
| <math>\mathcal{F}</math> is hereditary since every any subset of a set of linearly independent vectors is still linearly independent.
| |
| | |
| For any subset <math>Y\subseteq [n]</math> of columns of <math>A</math>. Let <math>B</math> be the submatrix composed by these columns. Then <math>\mathcal{F}_Y</math> contains all sets of linearly independent columns of <math>B</math>. Clearly, all maximal such sets have the same size, which is the column-rank of <math>B</math>.
| |
| | |
| Therefore, <math>\mathcal{F}</math> is a matroid. Each independent set (of matroid) is a linearly independent set of columns of matrix <math>A</math>. For any set <math>Y\subseteq[n]</math> of columns of matrix <math>A</math>, the rank of <math>Y</math> is the column-rank of the submatrix defined by the columns in <math>Y</math>.
| |
| | |
| === Greedy algorithms on weighted matroids ===
| |
| | |
| === Matroid intersections ===
| |