Lecture Notes on Valid Inequalities and Duality in Linear Programming

Author

Your Name

Published

January 30, 2025

Introduction

This lecture explores the fundamental concepts of valid inequalities and duality within the framework of linear programming. We will begin by defining and characterizing valid inequalities, distinguishing between direct and indirect approaches to derive them. We will then delve into the concept of duality, understanding its motivation through upper bounds on the objective function. We will derive the dual problem, explore the strong and weak duality theorems, and analyze the relationships between primal and dual solutions. This lecture aims to provide a comprehensive understanding of these essential topics in linear programming.

Valid Inequalities

Direct Valid Inequalities

Consider a system of linear equations $Ax = b$. A linear combination of these equations can be obtained by multiplying each equation by a scalar multiplier and summing them up. Let $U = [u_1, u_2, \dots, u_m]$ be a vector of multipliers. Multiplying the system $Ax = b$ by $U$ from the left conceptually means taking a linear combination of the rows of $A$ and the components of $b$. If we denote the rows of $A$ as $a_i^T$ and components of $b$ as $b_i$, then for each row $i$, we have $a_i^T x = b_i$. Multiplying the $i$-th equation by $u_i$ and summing over all rows gives:

\[\sum_{i=1}^{m} u_i (a_i^T x) = \sum_{i=1}^{m} u_i b_i\]

This can be rewritten in matrix notation as $UAx = Ub$. Since this equation is derived directly from the original system, it is always valid for any solution $x$ that satisfies $Ax = b$.

If we relax the equality to an inequality of the form "less than or equal to", we obtain a valid inequality. Thus, $UAx \leq Ub$ is a valid inequality for the system $Ax = b$. We call such inequalities direct valid inequalities.

Consider the system of equations: \[\begin{aligned} 2x_1 - 3x_2 + x_3 &= 1 \\ -x_1 + 2x_2 + 2x_3 &= -2 \end{aligned}\] Let’s choose multipliers $U = [3, -1]$. Multiplying the first equation by $3$ and the second by $-1$, we get: \[\begin{aligned} 3(2x_1 - 3x_2 + x_3) &= 3(1) \Rightarrow 6x_1 - 9x_2 + 3x_3 = 3 \\ -1(-x_1 + 2x_2 + 2x_3) &= -1(-2) \Rightarrow x_1 - 2x_2 - 2x_3 = 2 \end{aligned}\] Summing these equations, we obtain: \[(6x_1 - 9x_2 + 3x_3) + (x_1 - 2x_2 - 2x_3) = 3 + 2\]Relaxing the equality to inequality, we get a direct valid inequality:This inequality is valid for any solution $(x_1, x_2, x_3)$ that satisfies the original system of equations.

Indirect Valid Inequalities

Indirect valid inequalities are derived from direct valid inequalities by further relaxation. This relaxation involves either decreasing the coefficients on the left-hand side of the inequality or increasing the right-hand side.

Suppose we have a direct valid inequality $\alpha x \leq \beta$, where $\alpha$ is a row vector and $\beta$ is a scalar, obtained from a linear combination of the system equations. An indirect valid inequality can be obtained by:

Relaxing Coefficients: Decreasing the coefficients of variables on the left-hand side, especially for non-negative variables. If $x \geq 0$, and we replace $\alpha$ with $\alpha'$ such that $\alpha'_j \leq \alpha_j$ for all $j$, then $\alpha' x \leq \alpha x$.
Relaxing the Right-Hand Side: Increasing the right-hand side constant. If we replace $\beta$ with $\beta'$ such that $\beta' \geq \beta$, then $\alpha x \leq \beta \leq \beta'$.

Combining these relaxations, if $\alpha x \leq \beta$ is a direct valid inequality, then for any $\alpha'$ such that $\alpha'_j \leq \alpha_j$ for all $j$ and any $\beta' \geq \beta$, the inequality $\alpha' x \leq \beta'$ is an indirect valid inequality.

Starting with the direct valid inequality from the previous example: $7x_1 - 11x_2 + x_3 \leq 5$. We can derive indirect valid inequalities by relaxing coefficients and the right-hand side.

Example 1: Decrease coefficients on the left and increase the right-hand side. Replace $7$ with $5$, $-11$ remains $-11$, $1$ with $1/2$, and $5$ with $6$. Indirect valid inequality: $5x_1 - 11x_2 + \frac{1}{2}x_3 \leq 6$.
Example 2: Decrease coefficients on the left and increase the right-hand side further. Replace $7$ with $3$, $-11$ with $-15$, $1$ with $0$, and $5$ with $8$. Indirect valid inequality: $3x_1 - 15x_2 \leq 8$.
Example 3: Decrease coefficients on the left only. Replace $7$ with $1$, $-11$ remains $-11$, $1$ with $-1$, and $5$ remains $5$. Indirect valid inequality: $x_1 - 11x_2 - x_3 \leq 5$.

All these inequalities are valid for solutions of the original system.

Characterizing Valid Inequalities

A crucial result characterizes all valid inequalities for a polyhedron $P = \{x \mid Ax = b, x \geq 0\}$. It states that to obtain any valid inequality, one must essentially follow the process described for direct and indirect inequalities.

A linear inequality $\alpha x \leq \beta$ is a valid inequality for the polyhedron $P = \{x \mid Ax = b, x \geq 0\}$ if and only if there exists a vector of multipliers $U$ such that $\alpha$ is a relaxation of the linear combination of the rows of $A$ (i.e., $\alpha \leq UA$) and $\beta$ is a relaxation (upper bound) of the linear combination of the components of $b$ (i.e., $\beta \geq Ub$).

More formally, this means there exists a vector $U$ and a vector $\alpha'$ such that $\alpha \leq \alpha' = UA$ and $\beta \geq Ub$. Since $\alpha \leq \alpha'$, we have $\alpha x \leq \alpha' x = UAx$. And since $UAx = Ub$ for feasible $x$ (from linear combination of $Ax=b$), and $\beta \geq Ub$, we have $\alpha x \leq UAx = Ub \leq \beta$. Thus, $\alpha x \leq \beta$ is indeed a valid inequality. This theorem states the converse is also true: every valid inequality can be obtained in this way.

Farkas’ Lemma and Valid Inequalities

This characterization of valid inequalities is closely related to Farkas’ Lemma, often referred to as the Lemma of Alternatives. Farkas’ Lemma provides conditions for the existence or non-existence of solutions to systems of linear inequalities.

Consider the polyhedron $P = \{x \mid Ax = b, x \geq 0\}$, and assume it is non-empty. We are interested in when the system $Ax = b, x \geq 0, \alpha x > \beta$ has no solution. If this system has no solution, it means for all $x \in P$, it must be that $\alpha x \leq \beta$, hence $\alpha x \leq \beta$ is a valid inequality for $P$.

Farkas’ Lemma (in a form related to valid inequalities) states:

The inequality $\alpha x \leq \beta$ is a valid inequality for the polyhedron $P = \{x \mid Ax = b, x \geq 0\}$ if and only if there exists a vector $U$ such that $U^T A \geq \alpha^T$ and $U^T b \leq \beta$.

In terms of row vectors, this is equivalent to saying there exists a row vector $U$ such that $UA \geq \alpha$ and $Ub \leq \beta$. This condition exactly matches the characterization of indirect valid inequalities. Thus, Farkas’ Lemma provides a theoretical foundation for understanding and generating valid inequalities.

The proof of this theorem, as mentioned in the transcription, is not trivial and often involves techniques from simplex method or geometric arguments. The simplex-based proof utilizes the concept of optimal bases and reduced costs to construct a solution for the system $UA \geq \alpha, Ub \leq \beta$ from an optimal solution of maximizing $\alpha x$ over $P$.

It is important to note that when deriving valid inequalities from a system of equations ($Ax=b$), the multipliers $U$ can be of any sign (positive or negative). However, if the starting system is in canonical form with inequalities (e.g., $Ax \leq b, x \geq 0$), and we want to combine these inequalities to derive new valid inequalities, the multipliers must be non-negative to preserve the direction of the inequalities when summing them.

Duality in Linear Programming

Motivation for the Dual Problem

Upper Bounds and the Objective Function

Consider a linear programming problem in standard form (Primal Problem): \[\begin{aligned} \text{Maximize } & c^T x \\ \text{subject to } & Ax = b \\ & x \geq 0 \end{aligned}\] Let $P = \{x \mid Ax = b, x \geq 0\}$ be the feasible region, and let $Z_P$ be the optimal value of the primal problem, i.e., $Z_P = \max \{c^T x \mid x \in P\}$.

We are interested in finding valid inequalities for $P$ of the form $c^T x \leq C_0$. Each such valid inequality provides an upper bound $C_0$ on the optimal value $Z_P$. We seek the tightest upper bound, which is the smallest possible value of $C_0$ for which $c^T x \leq C_0$ is a valid inequality for all $x \in P$.

Finding the best (smallest) upper bound can be formulated as an optimization problem itself. We want to find a valid inequality $c^T x \leq C_0$ such that $C_0$ is minimized.

Deriving the Dual Problem

Using Multipliers

From the previous section, we know that any valid inequality for $P$ can be derived using multipliers. We want to find multipliers $U \in \mathbb{R}^m$ such that the direct valid inequality $UAx \leq Ub$ is related to our objective function $c^T x$. Specifically, we want to find $U$ such that the left-hand side $UAx$ somehow "dominates" or is related to $c^T x$, and the right-hand side $Ub$ provides an upper bound.

We aim to construct a valid inequality of the form $c^T x \leq C_0$ using the multipliers $U$. According to Farkas’ Lemma and the characterization of valid inequalities, we need to find $U$ such that $UA \geq c^T$ (or $(UA)^T \geq c$, i.e., $A^T U^T \geq c$) and we want to minimize the upper bound $C_0 = Ub$.

Minimizing the Upper Bound

To minimize the upper bound $C_0 = Ub$, we need to solve an optimization problem in terms of $U$. The conditions derived from wanting $UA \geq c^T$ (or $A^T U^T \geq c$) become the constraints of this new problem.

Thus, we formulate the Dual Problem as follows: \[\begin{aligned} \text{Minimize } & U b \\ \text{subject to } & U A \geq c^T \\ & U \in \mathbb{R}^m \text{ (unrestricted in sign)} \end{aligned}\] Here, $U = [u_1, u_2, \dots, u_m]$ are the dual variables, corresponding to the multipliers of the primal constraints $Ax = b$.

The Primal and Dual Problems

Standard Form Primal

Primal Problem (P): \[\begin{aligned} \text{Maximize } & c^T x \\ \text{subject to } & Ax = b \\ & x \geq 0 \end{aligned}\] Optimal value: $Z_P = \max \{c^T x \mid Ax = b, x \geq 0\}$.

Canonical Form Dual

Dual Problem (D): \[\begin{aligned} \text{Minimize } & b^T U^T \\ \text{subject to } & A^T U^T \geq c \\ & U^T \in \mathbb{R}^m \text{ (unrestricted in sign)} \end{aligned}\] Using row vector notation for $U$: Dual Problem (D): \[\begin{aligned} \text{Minimize } & U b \\ \text{subject to } & U A \geq c^T \\ & U \in \mathbb{R}^m \end{aligned}\] Optimal value: $Z_D = \min \{U b \mid UA \geq c^T, U \in \mathbb{R}^m\}$.

Strong Duality Theorem

The Strong Duality Theorem is a fundamental result in linear programming that establishes a precise relationship between the optimal values of the primal and dual problems.

If the primal linear programming problem (P) has an optimal solution $x^*$, then the dual linear programming problem (D) also has an optimal solution $U^*$, and the optimal values are equal: $c^T x^* = U^* b$.

This theorem states that if an optimal solution exists for the primal problem, then an optimal solution also exists for the dual problem, and their optimal objective function values are the same. This confirms our intuition that the tightest upper bound on the primal objective value is indeed equal to the maximum primal objective value itself.

Weak Duality Theorem

The Weak Duality Theorem provides a relationship between any feasible solution of the primal problem and any feasible solution of the dual problem, even if they are not optimal.

Let $x$ be any feasible solution to the primal problem (P), and let $U$ be any feasible solution to the dual problem (D). Then, $c^T x \leq U b$.

Proof. Proof. Since $U$ is feasible for the dual, we have $UA \geq c^T$. Since $x$ is feasible for the primal, we have $x \geq 0$. Thus, multiplying $UA \geq c^T$ by $x$ (from the right, and taking transpose to handle row/column vectors consistently, or simply considering component-wise multiplication and summation), we get $(UA)x \geq c^T x$, or $U(Ax) \geq c^T x$. Since $x$ is primal feasible, $Ax = b$. Substituting this, we get $Ub \geq c^T x$, or $c^T x \leq Ub$. ◻

This theorem implies that any dual feasible solution’s objective value provides an upper bound for the objective value of any primal feasible solution.

Relationships Between Primal and Dual Solutions

Feasibility, Boundedness, and Optimality

The relationships between the feasibility, boundedness, and optimality of the primal and dual problems can be summarized in the following table:

Primal (P) / Dual (D)	Optimal Solution	Unbounded	Infeasible
Optimal Solution	Yes, $Z_P = Z_D$	No	No
Unbounded	No	No	Yes
Infeasible	No	Yes	Yes/No

More specifically, we have the following cases:

If both primal and dual have feasible solutions, then both have optimal solutions and $Z_P = Z_D$.
If the primal is unbounded (objective function can go to $+\infty$), then the dual is infeasible (no feasible solution).
If the dual is unbounded (objective function can go to $-\infty$), then the primal is infeasible (no feasible solution).
It is possible for both the primal and dual to be infeasible.

Case where both primal and dual are infeasible Consider the primal problem: \[\begin{aligned} \text{Maximize } & x_1 + 2x_2 \\ \text{subject to } & x_1 - x_2 = 1 \\ & x_1 - x_2 = 2 \\ & x_1, x_2 \geq 0 \end{aligned}\] This primal problem is clearly infeasible because $x_1 - x_2$ cannot be simultaneously equal to $1$ and $2$.

The dual problem is: \[\begin{aligned} \text{Minimize } & u_1 + 2u_2 \\ \text{subject to } & u_1 + u_2 \geq 1 \\ & -u_1 - u_2 \geq 2 \\ & u_1, u_2 \in \mathbb{R} \end{aligned}\] The constraints are $u_1 + u_2 \geq 1$ and $-(u_1 + u_2) \geq 2$, which is equivalent to $u_1 + u_2 \leq -2$. It is impossible to satisfy both $u_1 + u_2 \geq 1$ and $u_1 + u_2 \leq -2$ simultaneously. Therefore, the dual problem is also infeasible.

The Dual of the Dual

A remarkable property of duality is that the dual of the dual problem is the primal problem itself.

Consider a primal problem in canonical form (maximization): \[\begin{aligned} \text{Maximize } & c^T x \\ \text{subject to } & Ax \leq b \\ & x \geq 0 \end{aligned}\] Its dual (minimization form) is: \[\begin{aligned} \text{Minimize } & b^T u \\ \text{subject to } & A^T u \geq c \\ & u \geq 0 \end{aligned}\] Now, let’s take the dual of this dual problem. To do this systematically, we can rewrite the dual in a "maximization-like" form and standard form if needed, but for canonical form, we can directly apply the duality transformation again. If we consider the minimization dual as the "primal" now, and derive its dual, we will find that we return to the original maximization problem (with possibly variable names changed).

In general, the duality transformation is involutory, meaning applying it twice returns to the original problem. This symmetry and reciprocity between primal and dual problems are fundamental aspects of linear programming duality theory.

Conclusion

This lecture provided an introduction to valid inequalities and duality in linear programming. We learned how to derive direct and indirect valid inequalities and their characterization using Farkas’ Lemma. We then explored the concept of duality, understanding how the dual problem arises from seeking the tightest upper bounds on the primal objective function. We discussed the derivation of the dual problem for a standard form primal, and stated the Strong and Weak Duality Theorems, highlighting the relationships between primal and dual solutions in terms of feasibility, boundedness, and optimality. Finally, we noted the property that the dual of the dual is the primal, emphasizing the symmetric nature of duality.

Further study could involve exploring applications of duality, such as in sensitivity analysis, economic interpretation of dual variables, and algorithms for solving linear programs based on duality. Understanding duality is crucial for a deeper comprehension of linear programming and its applications.

--- title: "Lecture Notes on Valid Inequalities and Duality in Linear Programming" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture explores the fundamental concepts of valid inequalities and duality within the framework of linear programming. We will begin by defining and characterizing valid inequalities, distinguishing between direct and indirect approaches to derive them. We will then delve into the concept of duality, understanding its motivation through upper bounds on the objective function. We will derive the dual problem, explore the strong and weak duality theorems, and analyze the relationships between primal and dual solutions. This lecture aims to provide a comprehensive understanding of these essential topics in linear programming. # Valid Inequalities ## Direct Valid Inequalities Consider a system of linear equations $Ax = b$. A linear combination of these equations can be obtained by multiplying each equation by a scalar multiplier and summing them up. Let $U = [u_1, u_2, \dots, u_m]$ be a vector of multipliers. Multiplying the system $Ax = b$ by $U$ from the left conceptually means taking a linear combination of the rows of $A$ and the components of $b$. If we denote the rows of $A$ as $a_i^T$ and components of $b$ as $b_i$, then for each row $i$, we have $a_i^T x = b_i$. Multiplying the $i$-th equation by $u_i$ and summing over all rows gives: $$\sum_{i=1}^{m} u_i (a_i^T x) = \sum_{i=1}^{m} u_i b_i$$ This can be rewritten in matrix notation as $UAx = Ub$. Since this equation is derived directly from the original system, it is always valid for any solution $x$ that satisfies $Ax = b$. If we relax the equality to an inequality of the form \"less than or equal to\", we obtain a **valid inequality**. Thus, $UAx \leq Ub$ is a valid inequality for the system $Ax = b$. We call such inequalities **direct valid inequalities**. ::: tcolorbox Consider the system of equations: $$\begin{aligned} 2x_1 - 3x_2 + x_3 &= 1 \\ -x_1 + 2x_2 + 2x_3 &= -2 \end{aligned}$$ Let's choose multipliers $U = [3, -1]$. Multiplying the first equation by $3$ and the second by $-1$, we get: $$\begin{aligned} 3(2x_1 - 3x_2 + x_3) &= 3(1) \Rightarrow 6x_1 - 9x_2 + 3x_3 = 3 \\ -1(-x_1 + 2x_2 + 2x_3) &= -1(-2) \Rightarrow x_1 - 2x_2 - 2x_3 = 2 \end{aligned}$$ Summing these equations, we obtain: $$(6x_1 - 9x_2 + 3x_3) + (x_1 - 2x_2 - 2x_3) = 3 + 2$$Relaxing the equality to inequality, we get a direct valid inequality:This inequality is valid for any solution $(x_1, x_2, x_3)$ that satisfies the original system of equations. ::: ## Indirect Valid Inequalities Indirect valid inequalities are derived from direct valid inequalities by further relaxation. This relaxation involves either decreasing the coefficients on the left-hand side of the inequality or increasing the right-hand side. Suppose we have a direct valid inequality $\alpha x \leq \beta$, where $\alpha$ is a row vector and $\beta$ is a scalar, obtained from a linear combination of the system equations. An **indirect valid inequality** can be obtained by: - **Relaxing Coefficients**: Decreasing the coefficients of variables on the left-hand side, especially for non-negative variables. If $x \geq 0$, and we replace $\alpha$ with $\alpha'$ such that $\alpha'_j \leq \alpha_j$ for all $j$, then $\alpha' x \leq \alpha x$. - **Relaxing the Right-Hand Side**: Increasing the right-hand side constant. If we replace $\beta$ with $\beta'$ such that $\beta' \geq \beta$, then $\alpha x \leq \beta \leq \beta'$. Combining these relaxations, if $\alpha x \leq \beta$ is a direct valid inequality, then for any $\alpha'$ such that $\alpha'_j \leq \alpha_j$ for all $j$ and any $\beta' \geq \beta$, the inequality $\alpha' x \leq \beta'$ is an indirect valid inequality. ::: tcolorbox Starting with the direct valid inequality from the previous example: $7x_1 - 11x_2 + x_3 \leq 5$. We can derive indirect valid inequalities by relaxing coefficients and the right-hand side. - **Example 1**: Decrease coefficients on the left and increase the right-hand side. Replace $7$ with $5$, $-11$ remains $-11$, $1$ with $1/2$, and $5$ with $6$. Indirect valid inequality: $5x_1 - 11x_2 + \frac{1}{2}x_3 \leq 6$. - **Example 2**: Decrease coefficients on the left and increase the right-hand side further. Replace $7$ with $3$, $-11$ with $-15$, $1$ with $0$, and $5$ with $8$. Indirect valid inequality: $3x_1 - 15x_2 \leq 8$. - **Example 3**: Decrease coefficients on the left only. Replace $7$ with $1$, $-11$ remains $-11$, $1$ with $-1$, and $5$ remains $5$. Indirect valid inequality: $x_1 - 11x_2 - x_3 \leq 5$. All these inequalities are valid for solutions of the original system. ::: ## Characterizing Valid Inequalities A crucial result characterizes all valid inequalities for a polyhedron $P = \{x \mid Ax = b, x \geq 0\}$. It states that to obtain any valid inequality, one must essentially follow the process described for direct and indirect inequalities. ::: tcolorbox A linear inequality $\alpha x \leq \beta$ is a valid inequality for the polyhedron $P = \{x \mid Ax = b, x \geq 0\}$ if and only if there exists a vector of multipliers $U$ such that $\alpha$ is a relaxation of the linear combination of the rows of $A$ (i.e., $\alpha \leq UA$) and $\beta$ is a relaxation (upper bound) of the linear combination of the components of $b$ (i.e., $\beta \geq Ub$). ::: More formally, this means there exists a vector $U$ and a vector $\alpha'$ such that $\alpha \leq \alpha' = UA$ and $\beta \geq Ub$. Since $\alpha \leq \alpha'$, we have $\alpha x \leq \alpha' x = UAx$. And since $UAx = Ub$ for feasible $x$ (from linear combination of $Ax=b$), and $\beta \geq Ub$, we have $\alpha x \leq UAx = Ub \leq \beta$. Thus, $\alpha x \leq \beta$ is indeed a valid inequality. This theorem states the converse is also true: every valid inequality can be obtained in this way. ## Farkas' Lemma and Valid Inequalities This characterization of valid inequalities is closely related to Farkas' Lemma, often referred to as the Lemma of Alternatives. Farkas' Lemma provides conditions for the existence or non-existence of solutions to systems of linear inequalities. Consider the polyhedron $P = \{x \mid Ax = b, x \geq 0\}$, and assume it is non-empty. We are interested in when the system $Ax = b, x \geq 0, \alpha x > \beta$ has no solution. If this system has no solution, it means for all $x \in P$, it must be that $\alpha x \leq \beta$, hence $\alpha x \leq \beta$ is a valid inequality for $P$. Farkas' Lemma (in a form related to valid inequalities) states: ::: tcolorbox The inequality $\alpha x \leq \beta$ is a valid inequality for the polyhedron $P = \{x \mid Ax = b, x \geq 0\}$ if and only if there exists a vector $U$ such that $U^T A \geq \alpha^T$ and $U^T b \leq \beta$. ::: In terms of row vectors, this is equivalent to saying there exists a row vector $U$ such that $UA \geq \alpha$ and $Ub \leq \beta$. This condition exactly matches the characterization of indirect valid inequalities. Thus, Farkas' Lemma provides a theoretical foundation for understanding and generating valid inequalities. The proof of this theorem, as mentioned in the transcription, is not trivial and often involves techniques from simplex method or geometric arguments. The simplex-based proof utilizes the concept of optimal bases and reduced costs to construct a solution for the system $UA \geq \alpha, Ub \leq \beta$ from an optimal solution of maximizing $\alpha x$ over $P$. It is important to note that when deriving valid inequalities from a system of equations ($Ax=b$), the multipliers $U$ can be of any sign (positive or negative). However, if the starting system is in canonical form with inequalities (e.g., $Ax \leq b, x \geq 0$), and we want to combine these inequalities to derive new valid inequalities, the multipliers must be non-negative to preserve the direction of the inequalities when summing them. # Duality in Linear Programming ## Motivation for the Dual Problem ### Upper Bounds and the Objective Function Consider a linear programming problem in standard form (Primal Problem): $$\begin{aligned} \text{Maximize } & c^T x \\ \text{subject to } & Ax = b \\ & x \geq 0 \end{aligned}$$ Let $P = \{x \mid Ax = b, x \geq 0\}$ be the feasible region, and let $Z_P$ be the optimal value of the primal problem, i.e., $Z_P = \max \{c^T x \mid x \in P\}$. We are interested in finding valid inequalities for $P$ of the form $c^T x \leq C_0$. Each such valid inequality provides an upper bound $C_0$ on the optimal value $Z_P$. We seek the **tightest** upper bound, which is the smallest possible value of $C_0$ for which $c^T x \leq C_0$ is a valid inequality for all $x \in P$. Finding the best (smallest) upper bound can be formulated as an optimization problem itself. We want to find a valid inequality $c^T x \leq C_0$ such that $C_0$ is minimized. ## Deriving the Dual Problem ### Using Multipliers From the previous section, we know that any valid inequality for $P$ can be derived using multipliers. We want to find multipliers $U \in \mathbb{R}^m$ such that the direct valid inequality $UAx \leq Ub$ is related to our objective function $c^T x$. Specifically, we want to find $U$ such that the left-hand side $UAx$ somehow \"dominates\" or is related to $c^T x$, and the right-hand side $Ub$ provides an upper bound. We aim to construct a valid inequality of the form $c^T x \leq C_0$ using the multipliers $U$. According to Farkas' Lemma and the characterization of valid inequalities, we need to find $U$ such that $UA \geq c^T$ (or $(UA)^T \geq c$, i.e., $A^T U^T \geq c$) and we want to minimize the upper bound $C_0 = Ub$. ### Minimizing the Upper Bound To minimize the upper bound $C_0 = Ub$, we need to solve an optimization problem in terms of $U$. The conditions derived from wanting $UA \geq c^T$ (or $A^T U^T \geq c$) become the constraints of this new problem. Thus, we formulate the **Dual Problem** as follows: $$\begin{aligned} \text{Minimize } & U b \\ \text{subject to } & U A \geq c^T \\ & U \in \mathbb{R}^m \text{ (unrestricted in sign)} \end{aligned}$$ Here, $U = [u_1, u_2, \dots, u_m]$ are the dual variables, corresponding to the multipliers of the primal constraints $Ax = b$. ## The Primal and Dual Problems ### Standard Form Primal **Primal Problem (P):** $$\begin{aligned} \text{Maximize } & c^T x \\ \text{subject to } & Ax = b \\ & x \geq 0 \end{aligned}$$ Optimal value: $Z_P = \max \{c^T x \mid Ax = b, x \geq 0\}$. ### Canonical Form Dual **Dual Problem (D):** $$\begin{aligned} \text{Minimize } & b^T U^T \\ \text{subject to } & A^T U^T \geq c \\ & U^T \in \mathbb{R}^m \text{ (unrestricted in sign)} \end{aligned}$$ Using row vector notation for $U$: **Dual Problem (D):** $$\begin{aligned} \text{Minimize } & U b \\ \text{subject to } & U A \geq c^T \\ & U \in \mathbb{R}^m \end{aligned}$$ Optimal value: $Z_D = \min \{U b \mid UA \geq c^T, U \in \mathbb{R}^m\}$. ## Strong Duality Theorem The Strong Duality Theorem is a fundamental result in linear programming that establishes a precise relationship between the optimal values of the primal and dual problems. ::: tcolorbox If the primal linear programming problem (P) has an optimal solution $x^*$, then the dual linear programming problem (D) also has an optimal solution $U^*$, and the optimal values are equal: $c^T x^* = U^* b$. ::: This theorem states that if an optimal solution exists for the primal problem, then an optimal solution also exists for the dual problem, and their optimal objective function values are the same. This confirms our intuition that the tightest upper bound on the primal objective value is indeed equal to the maximum primal objective value itself. ## Weak Duality Theorem The Weak Duality Theorem provides a relationship between any feasible solution of the primal problem and any feasible solution of the dual problem, even if they are not optimal. ::: tcolorbox Let $x$ be any feasible solution to the primal problem (P), and let $U$ be any feasible solution to the dual problem (D). Then, $c^T x \leq U b$. ::: ::: proof *Proof.* Since $U$ is feasible for the dual, we have $UA \geq c^T$. Since $x$ is feasible for the primal, we have $x \geq 0$. Thus, multiplying $UA \geq c^T$ by $x$ (from the right, and taking transpose to handle row/column vectors consistently, or simply considering component-wise multiplication and summation), we get $(UA)x \geq c^T x$, or $U(Ax) \geq c^T x$. Since $x$ is primal feasible, $Ax = b$. Substituting this, we get $Ub \geq c^T x$, or $c^T x \leq Ub$. ◻ ::: This theorem implies that any dual feasible solution's objective value provides an upper bound for the objective value of any primal feasible solution. ## Relationships Between Primal and Dual Solutions ### Feasibility, Boundedness, and Optimality The relationships between the feasibility, boundedness, and optimality of the primal and dual problems can be summarized in the following table: ::: center Primal (P) / Dual (D) Optimal Solution Unbounded Infeasible ----------------------- ------------------ ----------- ------------ Optimal Solution Yes, $Z_P = Z_D$ No No Unbounded No No Yes Infeasible No Yes Yes/No ::: More specifically, we have the following cases: 1. If both primal and dual have feasible solutions, then both have optimal solutions and $Z_P = Z_D$. 2. If the primal is unbounded (objective function can go to $+\infty$), then the dual is infeasible (no feasible solution). 3. If the dual is unbounded (objective function can go to $-\infty$), then the primal is infeasible (no feasible solution). 4. It is possible for both the primal and dual to be infeasible. ::: tcolorbox **Case where both primal and dual are infeasible** Consider the primal problem: $$\begin{aligned} \text{Maximize } & x_1 + 2x_2 \\ \text{subject to } & x_1 - x_2 = 1 \\ & x_1 - x_2 = 2 \\ & x_1, x_2 \geq 0 \end{aligned}$$ This primal problem is clearly infeasible because $x_1 - x_2$ cannot be simultaneously equal to $1$ and $2$. The dual problem is: $$\begin{aligned} \text{Minimize } & u_1 + 2u_2 \\ \text{subject to } & u_1 + u_2 \geq 1 \\ & -u_1 - u_2 \geq 2 \\ & u_1, u_2 \in \mathbb{R} \end{aligned}$$ The constraints are $u_1 + u_2 \geq 1$ and $-(u_1 + u_2) \geq 2$, which is equivalent to $u_1 + u_2 \leq -2$. It is impossible to satisfy both $u_1 + u_2 \geq 1$ and $u_1 + u_2 \leq -2$ simultaneously. Therefore, the dual problem is also infeasible. ::: ## The Dual of the Dual A remarkable property of duality is that the dual of the dual problem is the primal problem itself. Consider a primal problem in canonical form (maximization): $$\begin{aligned} \text{Maximize } & c^T x \\ \text{subject to } & Ax \leq b \\ & x \geq 0 \end{aligned}$$ Its dual (minimization form) is: $$\begin{aligned} \text{Minimize } & b^T u \\ \text{subject to } & A^T u \geq c \\ & u \geq 0 \end{aligned}$$ Now, let's take the dual of this dual problem. To do this systematically, we can rewrite the dual in a \"maximization-like\" form and standard form if needed, but for canonical form, we can directly apply the duality transformation again. If we consider the minimization dual as the \"primal\" now, and derive its dual, we will find that we return to the original maximization problem (with possibly variable names changed). In general, the duality transformation is involutory, meaning applying it twice returns to the original problem. This symmetry and reciprocity between primal and dual problems are fundamental aspects of linear programming duality theory. # Conclusion This lecture provided an introduction to valid inequalities and duality in linear programming. We learned how to derive direct and indirect valid inequalities and their characterization using Farkas' Lemma. We then explored the concept of duality, understanding how the dual problem arises from seeking the tightest upper bounds on the primal objective function. We discussed the derivation of the dual problem for a standard form primal, and stated the Strong and Weak Duality Theorems, highlighting the relationships between primal and dual solutions in terms of feasibility, boundedness, and optimality. Finally, we noted the property that the dual of the dual is the primal, emphasizing the symmetric nature of duality. Further study could involve exploring applications of duality, such as in sensitivity analysis, economic interpretation of dual variables, and algorithms for solving linear programs based on duality. Understanding duality is crucial for a deeper comprehension of linear programming and its applications.