Dual linear program

The dual of a given linear program (LP) is another LP that is derived from the original (the primal) LP in the following schematic way: * Each variable in the primal LP becomes a constraint in the dual LP; * Each constraint in the primal LP becomes a variable in the dual LP; * The objective direction is inversed – maximum in the primal becomes minimum in the dual and vice versa. The weak duality theorem states that the objective value of the dual LP at any feasible solution is always a bound on the objective of the primal LP at any feasible solution (upper or lower bound, depending on whether it is a maximization or minimization problem). In fact, this bounding property holds for the optimal values of the dual and primal LPs. The strong duality theorem states that, moreover, if the primal has an optimal solution then the dual has an optimal solution too, and the two optima are equal. These theorems belong to a larger class of duality theorems in optimization. The strong duality theorem is one of the cases in which the duality gap (the gap between the optimum of the primal and the optimum of the dual) is 0.

The dual of a given linear program (LP) is another LP that is derived from the original (the primal) LP in the following schematic way: Each variable in the primal LP becomes a constraint in the dual LP; Each constraint in the primal LP becomes a variable in the dual LP; The objective direction is inversed – maximum in the primal becomes minimum in the dual and vice versa. The weak duality theorem states that the objective value of the dual LP at any feasible solution is always a bound on the objective of the primal LP at any feasible solution (upper or lower bound, depending on whether it is a maximization or minimization problem). In fact, this bounding property holds for the optimal values of the dual and primal LPs. The strong duality theorem states that, moreover, if the primal has an optimal solution then the dual has an optimal solution too, and the two optima are equal. These theorems belong to a larger class of duality theorems in optimization. The strong duality theorem is one of the cases in which the duality gap (the gap between the optimum of the primal and the optimum of the dual) is 0. A list of m constraints. Each constraint j is: a_{j 1} x_1 +\cdots + a_{j n} x_n \lesseqqgtr b_j where the symbol before the b_j can be one of \geq or \leq or = . The dual LP is constructed as follows. Each primal constraint becomes a dual variable. So there are m variables: y_1 ,\ldots, y_m . The sign constraint of each dual variable is "opposite" to the sign of its primal constraint. So " \geq b_j " becomes y_j \leq 0 and " \leq b_j " becomes y_j \geq 0 and " = b_j " becomes y_j \in \mathbb{R} . The dual objective function is \text{minimize } ~~~ b_1 y_1 +\cdots + b_m y_m Each primal variable becomes a dual constraint. So there are n constraints. The coefficient of a dual variable in the dual constraint is the coefficient of its primal variable in its primal constraint. So each constraint i is: a_{1 i} y_1 +\cdots + a_{m i} y_m \lesseqqgtr c_i , where the symbol before the c_i is similar to the sign constraint on variable i in the primal LP. So x_i \leq 0 becomes " \leq c_i " and x_i \geq 0 becomes " \geq c_i " and x_i \in \mathbb{R} becomes " = c_i ". From this algorithm, it is easy to see that the dual of the dual is the primal. = x T c [since this just a scalar product of the two vectors] ≤ x T (A T y) [since A T y ≥ c by the dual constraints, and x ≥ 0] = (x T A T )y [by associativity] = (Ax) T y [by properties of transpose] ≤ b T y [since Ax ≤ b by the primal constraints, and y ≥ 0] Weak duality implies: max x c T x ≤ min y b T y In particular, if the primal is unbounded (from above) then the dual has no feasible solution, and if the dual is unbounded (from below) then the primal has no feasible solution. The strong duality theorem says that if one of the two problems has an optimal solution, so does the other one and that the bounds given by the weak duality theorem are tight, i.e.: max x c T x = min y b T y The strong duality theorem is harder to prove; the proofs usually use the weak duality theorem as a sub-routine. One proof uses the simplex algorithm and relies on the proof that, with the suitable pivot rule, it provides a correct solution. The proof establishes that, once the simplex algorithm finishes with a solution to the primal LP, it is possible to read from the final tableau, a solution to the dual LP. So, by running the simplex algorithm, we obtain solutions to both the primal and the dual simultaneously. Another proof uses the Farkas lemma. 1. The weak duality theorem implies that finding a single feasible solution is as hard as finding an optimal feasible solution. Suppose we have an oracle that, given an LP, finds an arbitrary feasible solution (if one exists). Given the LP "Maximize c T x subject to Ax ≤ b, x ≥ 0", we can construct another LP by combining this LP with its dual. The combined LP has both x and y as variables: Maximize 1 subject to Ax ≤ b, A T y ≥ c, c T x ≥ b T y, x ≥ 0, y ≥ 0 If the combined LP has a feasible solution (x,y), then by weak duality, c T x = b T y. So x must be a maximal solution of the primal LP and y must be a minimal solution of the dual LP. If the combined LP has no feasible solution, then the primal LP has no feasible solution either. 2. The strong duality theorem provides a "good characterization" of the optimal value of an LP in that it allows us to easily prove that some value t is the optimum of some LP. The proof proceeds in two steps: Show a feasible solution to the primal LP with value t; this proves that the optimum is at least t. Show a feasible solution to the dual LP with value t; this proves that the optimum is at most t. \text{subject to } & 5 x_1 + 6 x_2 = 7 \\ & x_1\geq 0, x_2\geq 0 \end{align} Applying the recipe above gives the following dual LP, with one variable and two constraints: \begin{align} \text{minimize } & 7 y_1 \\ \text{subject to } & 5 y_1 \geq 3 \\ & 6 y_1 \geq 4 \\ & y_1\in \mathbb{R} \end{align} It is easy to see that the maximum of the primal LP is attained when x 1 is minimized to its lower bound (0) and x 2 is maximized to its upper bound under the constraint (7/6). The maximum is 4 ⋅ 7/6 = 14/3. Similarly, the minimum of the dual LP is attained when y 1 is minimized to its lower bound under the constraints: the first constraint gives a lower bound of 3/5 while the second constraint gives a stricter lower bound of 4/6, so the actual lower bound is 4/6 and the minimum is 7 ⋅ 4/6 = 14/3. In accordance with the strong duality theorem, the maximum of the primal equals the minimum of the dual. We use this example to illustrate the proof of the weak duality theorem. Suppose that, in the primal LP, we want to get an upper bound on the objective 3 x_1 + 4 x_2 . We can use the constraint multiplied by some coefficient, say y_1 . For any y_1 we get: y_1\cdot (5 x_1 + 6 x_2) = 7 y_1 . Now, if y_1\cdot 5 x_1 \geq 3 x_1 and y_1\cdot 6 x_2 \geq 4 x_2 , then y_1\cdot (5 x_1 + 6 x_2) \geq 3 x_1 + 4 x_2 , so 7 y_1 \geq 3 x_1 + 4 x_2 . Hence, the objective of the dual LP is an upper bound on the objective of the primal LP. =\rho \mathbf p^{T} \\ \mathbf A \mathbf z =\rho {\mathbf z} \\ \end{matrix} where \mathbf p^{T} and \mathbf z are the left and right eigenvectors of the square matrix \mathbf A , respectively, and \rho is the eigenvalue. The above eigenequations for the square matrix can be extended to von Neumann's general equilibrium model: \begin{matrix} \mathbf p^{T}\mathbf A \geq \rho\mathbf p^{T}\mathbf B \\ \mathbf A \mathbf z \leq \rho \mathbf B {\mathbf z} \\ \end{matrix} where the economic meanings of \mathbf p and \mathbf z are the equilibrium prices of various goods and the equilibrium activity levels of various economic agents, respectively. The von Neumann's equilibrium model can be further extended to the following structural equilibrium model with \mathbf A and \mathbf B as matrix-valued functions: \begin{matrix} \mathbf p^{T}\mathbf A(\mathbf p, \mathbf u, \mathbf z) \geq \rho\mathbf p^{T}\mathbf B(\mathbf p, \mathbf u, \mathbf z)\\ \mathbf A(\mathbf p, \mathbf u, \mathbf z) \mathbf z \leq \rho \mathbf B(\mathbf p, \mathbf u, \mathbf z) {\mathbf z}\\ \end{matrix} where the economic meaning of \mathbf u is the utility levels of various consumers. A special case of the above model is \begin{matrix} \mathbf p^{T}\mathbf A(u) \geq\mathbf p^{T}\mathbf B\\ \mathbf A(u) \mathbf z \leq \mathbf B {\mathbf z} \end{matrix} This form of the structural equilibrium model and linear programming problems can often be converted to each other, that is, the solutions to these two types of problems are often consistent. If we define \mathbf A(u)=\begin{bmatrix} \mathbf 0& u\\ \mathbf A& \mathbf 0 \\ \end{bmatrix} , \mathbf B=\begin{bmatrix} \mathbf c^T & 0\\ \mathbf 0 & \mathbf b \\ \end{bmatrix} , \mathbf p=\begin{bmatrix} 1 \\ \mathbf y \\ \end{bmatrix} , \mathbf z=\begin{bmatrix} \mathbf x \\ 1 \\ \end{bmatrix} , then the structural equilibrium model can be written as \begin{bmatrix} \mathbf y^{T}\mathbf A & u \\ \end{bmatrix} \geq \begin{bmatrix} \mathbf c^T & \mathbf y^{T}\mathbf b \\ \end{bmatrix} \begin{bmatrix} u \\ \mathbf A \mathbf x \\ \end{bmatrix} \leq \begin{bmatrix} \mathbf c^T \mathbf x \\ \mathbf b\\ \end{bmatrix} Let us illustrate the structural equilibrium model with the previously discussed tiny example. In this example, we have \mathbf A=\begin{bmatrix} 5&6 \end{bmatrix} , \mathbf A(u)=\begin{bmatrix} 0& 0& u\\ 5&6&0 \\ \end{bmatrix} and \mathbf B=\begin{bmatrix} 3& 4& 0\\ 0 & 0&7 \\ \end{bmatrix} . To solve the structural equilibrium model, we obtain \mathbf p^*=(1, 2/3)^T, \quad \mathbf z^*=(0, 7/6, 1)^T, \quad u^*=14/3 These are consistent with the solutions to the linear programming problems. We substitute the above calculation results into the structural equilibrium model, obtaining \begin{matrix} \mathbf p^{T}\mathbf A(u)=(10/3, 4, 14/3) \geq (3, 4, 14/3)= \mathbf p^{T}\mathbf B \\ \mathbf A(u) \mathbf z = (14/3, 7)^T \leq (14/3, 7)^T=\mathbf B {\mathbf z} \end{matrix}

Text derived from https://en.wikipedia.org/w/index.php?oldid=1353262196 under CC BY-SA 4.0; modifications have been made.