Lecture Notes on Polyhedra and Valid Inequalities

Author

Your Name

Published

January 30, 2025

Introduction

In this lecture, we will explore the concept of polyhedra in standard form and delve into the theory of valid inequalities. We aim to understand how to characterize and construct these inequalities, which are crucial in the study of linear programming and optimization. We will also introduce Farkas’ Lemma, a fundamental theorem that provides a necessary and sufficient condition for the validity of inequalities, and finally, we will connect these concepts to duality in linear programming.

Polyhedra and Valid Inequalities

Defining a Polyhedron in Standard Form

Let us consider a polyhedron $P$ defined as the set of all vectors $x$ such that $Ax = b$ and $x \geq 0$. This is the standard form representation commonly used in linear programming. Here, $A$ is an $M \times N$ matrix, meaning it has $M$ rows and $N$ columns. Consequently, we are working in $\mathbb{R}^N$, and $P$ is a polyhedron in $N$-dimensional space.

Introducing Valid Inequalities

An inequality of the form $\alpha x \leq \beta$, where $\alpha \in \mathbb{R}^N$ is a vector and $\beta \in \mathbb{R}$ is a scalar, is called a valid inequality for the polyhedron $P$ if $\alpha x \leq \beta$ for every $x \in P$.

In essence, a valid inequality is satisfied by every point within the polyhedron. Conversely, an inequality is not valid if there exists at least one point in the polyhedron that does not satisfy it.

Geometric Interpretation: Hyperplanes and Polyhedra

Geometrically, a valid inequality $\alpha x \leq \beta$ defines a hyperplane. If the inequality is valid, this hyperplane separates the space such that the entire polyhedron lies on one side of the hyperplane (specifically, the side defined by $\alpha x \leq \beta$). If the inequality is not valid, the hyperplane intersects the polyhedron, meaning some points of $P$ satisfy $\alpha x \leq \beta$, while others do not satisfy it (or satisfy $\alpha x > \beta$).

The Goal: Characterizing All Valid Inequalities

Our primary goal is to characterize all valid inequalities for a given polyhedron $P = \{x \in \mathbb{R}^N : Ax = b, x \geq 0\}$. We want to understand the structure of these inequalities and how they can be derived from the defining equations of the polyhedron.

Constructing Valid Inequalities

Valid inequalities can be categorized into two main types: direct and indirect.

Direct Valid Inequalities

Direct valid inequalities are derived directly from the system of equations $Ax = b$ that define the polyhedron.

Linear Combinations of Constraint Equations

Direct inequalities are obtained through linear combinations of the equations in the system $Ax = b$. Consider a vector of multipliers $U = (u_1, u_2, \ldots, u_M) \in \mathbb{R}^M$. We can multiply each row of the matrix $A$ by a corresponding multiplier $u_i$ and sum these rows. This is equivalent to pre-multiplying the equation $Ax = b$ by a row vector $U$.

Let $\alpha = U A$ and $\beta = U b$. Then, the equation $\alpha x = \beta$ is a linear combination of the equations in $Ax = b$.

Deriving a Direct Inequality

Since $\alpha x = \beta$ holds for all $x \in P$ (as it is derived from $Ax=b$), it follows that the inequality $\alpha x \leq \beta$ is also valid for $P$. This is because if $\alpha x = \beta$, then it is certainly true that $\alpha x \leq \beta$.

Therefore, a method to generate direct valid inequalities is to:

Choose a vector of multipliers $U \in \mathbb{R}^M$.
Calculate $\alpha = U A$ and $\beta = U b$.
The inequality $\alpha x \leq \beta$ is a direct valid inequality for $P$.

In component form, if we take $U = (u_1, \ldots, u_M)$, then $\alpha = \sum_{i=1}^M u_i A_i$ and $\beta = \sum_{i=1}^M u_i b_i$, where $A_i$ is the $i$-th row of $A$ and $b_i$ is the $i$-th component of $b$.

Indirect Valid Inequalities

Indirect valid inequalities are obtained by relaxing direct valid inequalities. Relaxation involves making the left-hand side "smaller" or the right-hand side "larger" in a way that preserves validity.

Relaxing Direct Inequalities

Starting with a direct valid inequality $\gamma x \leq \delta$, we can derive further valid inequalities by relaxing it.

Decreasing Left-Hand Side Coefficients

Since we are considering polyhedra defined with $x \geq 0$, if we have a valid inequality $\gamma x \leq \delta$, and we choose a new vector $\gamma'$ such that $\gamma' \leq \gamma$ component-wise (i.e., $\gamma'_j \leq \gamma_j$ for all $j$), then $\gamma' x \leq \gamma x$ because $x \geq 0$. Since $\gamma x \leq \delta$, it follows that $\gamma' x \leq \delta$ is also a valid inequality. Thus, decreasing the coefficients on the left-hand side of a valid inequality (while keeping the right-hand side constant) results in another valid inequality.

Increasing Right-Hand Side Constants

Similarly, if we have a valid inequality $\gamma x \leq \delta$, and we choose a new constant $\delta'$ such that $\delta' \geq \delta$, then if $\gamma x \leq \delta$, it is certainly true that $\gamma x \leq \delta'$. Thus, increasing the constant on the right-hand side of a valid inequality (while keeping the left-hand side coefficients constant) results in another valid inequality.

Combining these relaxation methods, if $\gamma x \leq \delta$ is a valid inequality, and we have $\gamma' \leq \gamma$ and $\delta' \geq \delta$, then $\gamma' x \leq \delta'$ is also a valid inequality.

Summary: Direct vs. Indirect Inequalities

Direct Valid Inequalities: Obtained by linear combinations of the equations $Ax = b$, resulting in $\alpha x \leq \beta$ where $\alpha = U A$ and $\beta = U b$ for some $U \in \mathbb{R}^M$.
Indirect Valid Inequalities: Obtained by relaxing direct valid inequalities. This involves decreasing coefficients on the left-hand side and/or increasing the constant on the right-hand side of a direct valid inequality.

It turns out that every valid inequality for a polyhedron $P = \{x : Ax = b, x \geq 0\}$ can be obtained either directly or indirectly from the system $Ax = b$. This is a crucial result that will be formalized by Farkas’ Lemma.

Illustrative Example

A Specific System of Equations

Consider the following system of equations: \[\begin{aligned} 2x_1 + x_3 &= 1 \\ 2x_2 + 2x_3 &= 1 \end{aligned}\] with $x_1, x_2, x_3 \geq 0$. We want to derive valid inequalities for the polyhedron defined by this system.

Generating a Direct Valid Inequality

Let’s choose multipliers $u_1$ and $u_2$ for the first and second equations, respectively. Multiplying the first equation by $u_1$ and the second by $u_2$ gives: \[\begin{aligned} 2u_1 x_1 + u_1 x_3 &= u_1 \\ 2u_2 x_2 + 2u_2 x_3 &= u_2 \end{aligned}\] Summing these equations, we get: \[2u_1 x_1 + 2u_2 x_2 + (u_1 + 2u_2) x_3 = u_1 + u_2\] Thus, a direct valid inequality is: \[2u_1 x_1 + 2u_2 x_2 + (u_1 + 2u_2) x_3 \leq u_1 + u_2\]

For example, let $u_1 = 5$ and $u_2 = 3$. Then the inequality becomes: \[(2 \times 5) x_1 + (2 \times 3) x_2 + (5 + 2 \times 3) x_3 \leq 5 + 3\] \[10x_1 + 6x_2 + 11x_3 \leq 8\] This is a direct valid inequality.

Relaxing to Obtain an Indirect Valid Inequality

Starting with the direct inequality $10x_1 + 6x_2 + 11x_3 \leq 8$, we can relax it. For instance, decrease the coefficient of $x_3$ from 11 to 10 and increase the right-hand side from 8 to 9. We obtain an indirect valid inequality: \[10x_1 + 6x_2 + 10x_3 \leq 9\] This is valid because it is obtained by relaxing a direct valid inequality.

An Inequality Not Directly Obtainable

Consider the inequality: \[x_1 + x_2 + x_3 \leq 1\] We claim this is a valid inequality for the given system. To see why, from the first equation $2x_1 + x_3 = 1$, we have $2x_1 \leq 1$ and $x_3 \leq 1$. From the second equation $2x_2 + 2x_3 = 1$, we have $2x_2 \leq 1$ and $2x_3 \leq 1$, so $x_2 \leq 1/2$ and $x_3 \leq 1/2$. Adding the original equations gives $2x_1 + 2x_2 + 3x_3 = 2$. Dividing by 2 gives $x_1 + x_2 + \frac{3}{2}x_3 = 1$. Since $x_3 \geq 0$, we have $x_1 + x_2 + x_3 \leq x_1 + x_2 + \frac{3}{2}x_3 = 1$. Thus, $x_1 + x_2 + x_3 \leq 1$ is indeed a valid inequality.

Demonstrating the Necessity of Relaxation

Let’s try to obtain $x_1 + x_2 + x_3 \leq 1$ directly. We would need to find $u_1, u_2$ such that: \[\begin{aligned} 2u_1 &= 1 \\ 2u_2 &= 1 \\ u_1 + 2u_2 &= 1 \end{aligned}\] From the first two equations, $u_1 = 1/2$ and $u_2 = 1/2$. However, substituting these into the third equation gives $u_1 + 2u_2 = 1/2 + 2(1/2) = 3/2 \neq 1$. Thus, there are no multipliers that directly yield the inequality $x_1 + x_2 + x_3 \leq 1$.

However, if we take $u_1 = u_2 = 1/2$, the direct inequality is: \[x_1 + x_2 + \frac{3}{2}x_3 \leq 1\] Now, by relaxing the coefficient of $x_3$ from $3/2$ to $1$, we obtain the indirect valid inequality $x_1 + x_2 + x_3 \leq 1$. This example illustrates that some valid inequalities are only obtainable through relaxation of direct inequalities.

Farkas’ Lemma: A Fundamental Theorem

The Core Result: Necessary and Sufficient Condition

Farkas’ Lemma provides a fundamental result in linear programming and the theory of valid inequalities. It gives a necessary and sufficient condition for an inequality to be valid for a polyhedron in standard form. Essentially, it formalizes the idea that all valid inequalities are relaxations of direct inequalities.

Formal Statement of Farkas’ Lemma

Let $A$ be an $M \times N$ matrix, $b \in \mathbb{R}^M$, $\alpha \in \mathbb{R}^N$, and $\beta \in \mathbb{R}$. Assume the polyhedron $P = \{x \in \mathbb{R}^N : Ax = b, x \geq 0\}$ is non-empty. Then, the system of inequalities: \[\begin{aligned} Ax &= b \label{eq:system3_1} \\ \alpha x &> \beta \label{eq:system3_2} \\ x &\geq 0 \label{eq:system3_3} \end{aligned}\] (System 3) has no solution if and only if the system of inequalities: \[\begin{aligned} U A &\geq \alpha \label{eq:system4_1} \\ U b &\leq \beta \label{eq:system4_2} \end{aligned}\] (System 4) has a solution for some $U \in \mathbb{R}^M$.

Interpretation of the First System (No Solution)

The statement that System 3 has no solution means that there is no $x \in P$ for which $\alpha x > \beta$. This is equivalent to saying that for all $x \in P$, $\alpha x \leq \beta$. In other words, System 3 having no solution is equivalent to $\alpha x \leq \beta$ being a valid inequality for $P$.

Therefore, Farkas’ Lemma states that $\alpha x \leq \beta$ is a valid inequality for $P$ if and only if there exists a vector $U \in \mathbb{R}^M$ such that $U A \geq \alpha$ and $U b \leq \beta$. This precisely means that a valid inequality is obtained by relaxing a direct inequality.

Proof of Farkas’ Lemma

We need to prove both directions of the "if and only if" statement.

Part 1: If System 4 has a solution, then System 3 has no solution

Assume System 4 has a solution, say $U^*$. Then we have $U^* A \geq \alpha$ and $U^* b \leq \beta$. Suppose, for contradiction, that System 3 also has a solution, say $x^*$. Then we have $A x^* = b$, $\alpha x^* > \beta$, and $x^* \geq 0$.

Since $U^* A \geq \alpha$ and $x^* \geq 0$, we can multiply the inequality $U^* A \geq \alpha$ by $x^*$ (component-wise and sum), obtaining: \[(U^* A) x^* \geq \alpha x^*\] Since $A x^* = b$, we have $(U^* A) x^* = U^* (A x^*) = U^* b$. Thus, \[U^* b \geq \alpha x^*\] However, from System 4, we know $U^* b \leq \beta$, and from System 3, we know $\alpha x^* > \beta$. Combining these, we get: \[\beta \geq U^* b \geq \alpha x^* > \beta\] This implies $\beta > \beta$, which is a contradiction. Therefore, if System 4 has a solution, then System 3 cannot have a solution.

Part 2: If System 3 has no solution, then System 4 has a solution

Assume System 3 has no solution. This means for every $x \in P = \{x : Ax = b, x \geq 0\}$, we have $\alpha x \leq \beta$. We want to show that System 4 has a solution.

Consider the linear programming problem: \[\text{Maximize } \alpha x \quad \text{subject to } Ax = b, x \geq 0\] Since we assumed $P = \{x : Ax = b, x \geq 0\}$ is non-empty, the problem is feasible. Furthermore, since System 3 has no solution, it means for all feasible $x$, $\alpha x \leq \beta$. Thus, the objective function $\alpha x$ is bounded above by $\beta$ on the feasible region. Therefore, the linear program has an optimal solution, and the optimal value is finite and less than or equal to $\beta$. Let $x^*$ be an optimal basic feasible solution obtained by the simplex method. Let $B$ be the optimal basis.

Leveraging Linear Programming and the Simplex Method

When the simplex method terminates at an optimal solution, we have reduced costs that are non-positive for maximization problems. Let’s partition the variables into basic variables $x_B$ and non-basic variables $x_N$. Similarly, partition $\alpha = (\alpha_B, \alpha_N)$ and $A = [A_B, A_N]$. The reduced cost for a non-basic variable $x_j$ is given by $c_j - c_B B^{-1} A_j \leq 0$, where $c = \alpha^T$. In our vector notation, this translates to $\alpha_N^T - \alpha_B^T A_B^{-1} A_N \leq 0$ (component-wise). Let $U = \alpha_B^T A_B^{-1}$. Then the reduced cost condition becomes $\alpha_N^T - U A_N \leq 0$, or $\alpha_N^T \leq U A_N$. For basic variables, the reduced cost is zero, so $\alpha_B^T - U A_B = \alpha_B^T - \alpha_B^T A_B^{-1} A_B = \alpha_B^T - \alpha_B^T = 0$, so $\alpha_B^T \leq U A_B$ also holds. Combining these, we have $\alpha^T \leq U A$, or in row vector form, $UA \geq \alpha$.

Constructing a Solution for the Second System

Let $U = \alpha_B^T A_B^{-1}$. We have shown that $UA \geq \alpha$. Now we need to show $Ub \leq \beta$. The optimal value of the linear program is $\alpha x^* = \alpha_B x_B^* = \alpha_B A_B^{-1} b = U b$. Since the optimal value is less than or equal to $\beta$ (because $\alpha x \leq \beta$ for all feasible $x$), we have $Ub \leq \beta$.

Thus, we have found a vector $U = \alpha_B^T A_B^{-1}$ such that $UA \geq \alpha$ and $Ub \leq \beta$. Therefore, System 4 has a solution.

This completes the proof of Farkas’ Lemma.

Significance: Characterizing Valid Inequalities

Farkas’ Lemma provides a powerful tool for characterizing valid inequalities. It confirms that every valid inequality for a polyhedron $P = \{x : Ax = b, x \geq 0\}$ is indeed a relaxation of a direct inequality obtained from linear combinations of the equations $Ax = b$. This result is fundamental in understanding the structure of polyhedra and in developing algorithms for optimization problems.

Duality in Linear Programming

Valid Inequalities and Upper Bounds on the Objective Function

Consider a linear programming problem in standard form: \[\text{Maximize } cx \quad \text{subject to } Ax = b, x \geq 0\] Let $P = \{x : Ax = b, x \geq 0\}$ be the feasible region. We are interested in finding valid inequalities of the form $cx \leq \beta$ for $P$. Each such valid inequality provides an upper bound $\beta$ on the optimal objective function value.

Using Valid Inequalities to Bound the Optimal Value

If $cx \leq \beta$ is a valid inequality for $P$, then for any feasible solution $x \in P$, the objective value $cx$ is at most $\beta$. Therefore, the maximum possible value of $cx$ over $P$, denoted as $z^* = \max \{cx : x \in P\}$, must also satisfy $z^* \leq \beta$.

The Tightest Upper Bound

We want to find the tightest possible upper bound, i.e., the smallest $\beta$ such that $cx \leq \beta$ is a valid inequality. This smallest $\beta$ will be exactly equal to the optimal value $z^*$, assuming the problem is bounded.

Formulating the Dual Problem

According to Farkas’ Lemma, $cx \leq \beta$ is a valid inequality if and only if there exists a vector $U$ such that $UA \geq c$ and $Ub \leq \beta$. To find the tightest upper bound, we want to minimize $\beta$ subject to the existence of such a $U$. Since we want to minimize $\beta$ and we have the condition $Ub \leq \beta$, to minimize $\beta$, we should try to make $\beta$ as close to $Ub$ as possible. The best we can do is to set $\beta = Ub$.

Minimizing the Right-Hand Side of a Valid Inequality

So, we want to solve the problem: \[\text{Minimize } \beta \quad \text{subject to } \exists U \text{ such that } UA \geq c \text{ and } Ub \leq \beta\] Since we want to minimize $\beta$ and we must have $Ub \leq \beta$, the optimal choice for $\beta$ will be $\beta = Ub$. Thus, we can reformulate the problem as: \[\text{Minimize } Ub \quad \text{subject to } UA \geq c\] where $U \in \mathbb{R}^M$ is the variable.

Connecting to Farkas’ Lemma and Multipliers

This minimization problem is formulated in terms of the multipliers $U$ that define direct valid inequalities. We are seeking the multipliers that give us the smallest upper bound on $cx$.

Deriving the Dual Linear Program

Minimization Problem in Canonical Form

The problem we derived is: \[\text{Minimize } Ub \quad \text{subject to } UA \geq c\] This is a linear programming problem in minimization form. Let’s rewrite it in a more standard form using column vectors. Let $y = U^T$. Then $U = y^T$. The problem becomes: \[\text{Minimize } b^T y \quad \text{subject to } (y^T A)^T \geq c^T\] \[\text{Minimize } b^T y \quad \text{subject to } A^T y \geq c^T\] \[\text{Minimize } b^T y \quad \text{subject to } A^T y \geq c, \quad y \in \mathbb{R}^M\] Here, $y$ is a column vector of variables, and it is unconstrained in sign. This is the dual linear program in canonical form corresponding to the primal problem: \[\text{Maximize } cx \quad \text{subject to } Ax = b, x \geq 0\]

The Dual Problem Definition

Given the primal linear program in standard form: \[\begin{aligned} \text{Maximize } & cx \\ \text{subject to } & Ax = b \\ & x \geq 0 \end{aligned}\] The dual linear program is defined as: \[\begin{aligned} \text{Minimize } & b^T y \\ \text{subject to } & A^T y \geq c \\ & y \in \mathbb{R}^M \text{ (unconstrained)} \end{aligned}\]

Primal vs. Dual Forms: Vector Notation

In vector notation, if the primal is: \[\begin{aligned} \max & \ c^T x \\ \text{s.t. } & Ax = b \\ & x \geq 0 \end{aligned}\] The dual is: \[\begin{aligned} \min & \ b^T y \\ \text{s.t. } & A^T y \geq c \\ & y \text{ unconstrained} \end{aligned}\] The duality theory of linear programming establishes a strong relationship between the optimal solutions of the primal and dual problems, which we will explore further in subsequent lectures.

Conclusion

In this lecture, we introduced the concept of valid inequalities for polyhedra in standard form and explored methods to construct them, including direct and indirect approaches. We presented Farkas’ Lemma, a cornerstone theorem that characterizes valid inequalities and provides a necessary and sufficient condition for their validity. Finally, we began to see how the study of valid inequalities naturally leads to the formulation of the dual problem in linear programming.

Key Takeaways:

Valid inequalities are crucial for understanding the feasible region of linear programs.
Direct valid inequalities are linear combinations of constraint equations.
Indirect valid inequalities are relaxations of direct inequalities.
Farkas’ Lemma provides a fundamental characterization of valid inequalities.
The concept of valid inequalities is intrinsically linked to the formulation of the dual linear program.

Further Thinking:

How can we systematically generate all relevant valid inequalities for a given polyhedron?
What are the implications of Farkas’ Lemma for solving linear programming problems?
How does the duality theory help in understanding the sensitivity of optimal solutions to changes in problem parameters?

These questions will guide our exploration in future lectures as we delve deeper into linear programming and optimization theory.

--- title: "Lecture Notes on Polyhedra and Valid Inequalities" 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 In this lecture, we will explore the concept of polyhedra in standard form and delve into the theory of valid inequalities. We aim to understand how to characterize and construct these inequalities, which are crucial in the study of linear programming and optimization. We will also introduce Farkas' Lemma, a fundamental theorem that provides a necessary and sufficient condition for the validity of inequalities, and finally, we will connect these concepts to duality in linear programming. # Polyhedra and Valid Inequalities ## Defining a Polyhedron in Standard Form Let us consider a polyhedron $P$ defined as the set of all vectors $x$ such that $Ax = b$ and $x \geq 0$. This is the standard form representation commonly used in linear programming. Here, $A$ is an $M \times N$ matrix, meaning it has $M$ rows and $N$ columns. Consequently, we are working in $\mathbb{R}^N$, and $P$ is a polyhedron in $N$-dimensional space. ## Introducing Valid Inequalities ::: tcolorbox An inequality of the form $\alpha x \leq \beta$, where $\alpha \in \mathbb{R}^N$ is a vector and $\beta \in \mathbb{R}$ is a scalar, is called a valid inequality for the polyhedron $P$ if $\alpha x \leq \beta$ for every $x \in P$. ::: In essence, a valid inequality is satisfied by every point within the polyhedron. Conversely, an inequality is not valid if there exists at least one point in the polyhedron that does not satisfy it. ### Geometric Interpretation: Hyperplanes and Polyhedra Geometrically, a valid inequality $\alpha x \leq \beta$ defines a hyperplane. If the inequality is valid, this hyperplane separates the space such that the entire polyhedron lies on one side of the hyperplane (specifically, the side defined by $\alpha x \leq \beta$). If the inequality is not valid, the hyperplane intersects the polyhedron, meaning some points of $P$ satisfy $\alpha x \leq \beta$, while others do not satisfy it (or satisfy $\alpha x > \beta$). ## The Goal: Characterizing All Valid Inequalities Our primary goal is to characterize all valid inequalities for a given polyhedron $P = \{x \in \mathbb{R}^N : Ax = b, x \geq 0\}$. We want to understand the structure of these inequalities and how they can be derived from the defining equations of the polyhedron. # Constructing Valid Inequalities Valid inequalities can be categorized into two main types: direct and indirect. ## Direct Valid Inequalities Direct valid inequalities are derived directly from the system of equations $Ax = b$ that define the polyhedron. ### Linear Combinations of Constraint Equations Direct inequalities are obtained through linear combinations of the equations in the system $Ax = b$. Consider a vector of multipliers $U = (u_1, u_2, \ldots, u_M) \in \mathbb{R}^M$. We can multiply each row of the matrix $A$ by a corresponding multiplier $u_i$ and sum these rows. This is equivalent to pre-multiplying the equation $Ax = b$ by a row vector $U$. Let $\alpha = U A$ and $\beta = U b$. Then, the equation $\alpha x = \beta$ is a linear combination of the equations in $Ax = b$. ### Deriving a Direct Inequality Since $\alpha x = \beta$ holds for all $x \in P$ (as it is derived from $Ax=b$), it follows that the inequality $\alpha x \leq \beta$ is also valid for $P$. This is because if $\alpha x = \beta$, then it is certainly true that $\alpha x \leq \beta$. Therefore, a method to generate direct valid inequalities is to: 1. Choose a vector of multipliers $U \in \mathbb{R}^M$. 2. Calculate $\alpha = U A$ and $\beta = U b$. 3. The inequality $\alpha x \leq \beta$ is a direct valid inequality for $P$. In component form, if we take $U = (u_1, \ldots, u_M)$, then $\alpha = \sum_{i=1}^M u_i A_i$ and $\beta = \sum_{i=1}^M u_i b_i$, where $A_i$ is the $i$-th row of $A$ and $b_i$ is the $i$-th component of $b$. ## Indirect Valid Inequalities Indirect valid inequalities are obtained by relaxing direct valid inequalities. Relaxation involves making the left-hand side \"smaller\" or the right-hand side \"larger\" in a way that preserves validity. ### Relaxing Direct Inequalities Starting with a direct valid inequality $\gamma x \leq \delta$, we can derive further valid inequalities by relaxing it. ### Decreasing Left-Hand Side Coefficients Since we are considering polyhedra defined with $x \geq 0$, if we have a valid inequality $\gamma x \leq \delta$, and we choose a new vector $\gamma'$ such that $\gamma' \leq \gamma$ component-wise (i.e., $\gamma'_j \leq \gamma_j$ for all $j$), then $\gamma' x \leq \gamma x$ because $x \geq 0$. Since $\gamma x \leq \delta$, it follows that $\gamma' x \leq \delta$ is also a valid inequality. Thus, decreasing the coefficients on the left-hand side of a valid inequality (while keeping the right-hand side constant) results in another valid inequality. ### Increasing Right-Hand Side Constants Similarly, if we have a valid inequality $\gamma x \leq \delta$, and we choose a new constant $\delta'$ such that $\delta' \geq \delta$, then if $\gamma x \leq \delta$, it is certainly true that $\gamma x \leq \delta'$. Thus, increasing the constant on the right-hand side of a valid inequality (while keeping the left-hand side coefficients constant) results in another valid inequality. Combining these relaxation methods, if $\gamma x \leq \delta$ is a valid inequality, and we have $\gamma' \leq \gamma$ and $\delta' \geq \delta$, then $\gamma' x \leq \delta'$ is also a valid inequality. ## Summary: Direct vs. Indirect Inequalities ::: tcolorbox - **Direct Valid Inequalities:** Obtained by linear combinations of the equations $Ax = b$, resulting in $\alpha x \leq \beta$ where $\alpha = U A$ and $\beta = U b$ for some $U \in \mathbb{R}^M$. - **Indirect Valid Inequalities:** Obtained by relaxing direct valid inequalities. This involves decreasing coefficients on the left-hand side and/or increasing the constant on the right-hand side of a direct valid inequality. ::: It turns out that every valid inequality for a polyhedron $P = \{x : Ax = b, x \geq 0\}$ can be obtained either directly or indirectly from the system $Ax = b$. This is a crucial result that will be formalized by Farkas' Lemma. # Illustrative Example ## A Specific System of Equations Consider the following system of equations: $$\begin{aligned} 2x_1 + x_3 &= 1 \\ 2x_2 + 2x_3 &= 1 \end{aligned}$$ with $x_1, x_2, x_3 \geq 0$. We want to derive valid inequalities for the polyhedron defined by this system. ## Generating a Direct Valid Inequality Let's choose multipliers $u_1$ and $u_2$ for the first and second equations, respectively. Multiplying the first equation by $u_1$ and the second by $u_2$ gives: $$\begin{aligned} 2u_1 x_1 + u_1 x_3 &= u_1 \\ 2u_2 x_2 + 2u_2 x_3 &= u_2 \end{aligned}$$ Summing these equations, we get: $$2u_1 x_1 + 2u_2 x_2 + (u_1 + 2u_2) x_3 = u_1 + u_2$$ Thus, a direct valid inequality is: $$2u_1 x_1 + 2u_2 x_2 + (u_1 + 2u_2) x_3 \leq u_1 + u_2$$ ::: tcolorbox For example, let $u_1 = 5$ and $u_2 = 3$. Then the inequality becomes: $$(2 \times 5) x_1 + (2 \times 3) x_2 + (5 + 2 \times 3) x_3 \leq 5 + 3$$ $$10x_1 + 6x_2 + 11x_3 \leq 8$$ This is a direct valid inequality. ::: ## Relaxing to Obtain an Indirect Valid Inequality Starting with the direct inequality $10x_1 + 6x_2 + 11x_3 \leq 8$, we can relax it. For instance, decrease the coefficient of $x_3$ from 11 to 10 and increase the right-hand side from 8 to 9. We obtain an indirect valid inequality: $$10x_1 + 6x_2 + 10x_3 \leq 9$$ This is valid because it is obtained by relaxing a direct valid inequality. ## An Inequality Not Directly Obtainable Consider the inequality: $$x_1 + x_2 + x_3 \leq 1$$ We claim this is a valid inequality for the given system. To see why, from the first equation $2x_1 + x_3 = 1$, we have $2x_1 \leq 1$ and $x_3 \leq 1$. From the second equation $2x_2 + 2x_3 = 1$, we have $2x_2 \leq 1$ and $2x_3 \leq 1$, so $x_2 \leq 1/2$ and $x_3 \leq 1/2$. Adding the original equations gives $2x_1 + 2x_2 + 3x_3 = 2$. Dividing by 2 gives $x_1 + x_2 + \frac{3}{2}x_3 = 1$. Since $x_3 \geq 0$, we have $x_1 + x_2 + x_3 \leq x_1 + x_2 + \frac{3}{2}x_3 = 1$. Thus, $x_1 + x_2 + x_3 \leq 1$ is indeed a valid inequality. ### Demonstrating the Necessity of Relaxation Let's try to obtain $x_1 + x_2 + x_3 \leq 1$ directly. We would need to find $u_1, u_2$ such that: $$\begin{aligned} 2u_1 &= 1 \\ 2u_2 &= 1 \\ u_1 + 2u_2 &= 1 \end{aligned}$$ From the first two equations, $u_1 = 1/2$ and $u_2 = 1/2$. However, substituting these into the third equation gives $u_1 + 2u_2 = 1/2 + 2(1/2) = 3/2 \neq 1$. Thus, there are no multipliers that directly yield the inequality $x_1 + x_2 + x_3 \leq 1$. However, if we take $u_1 = u_2 = 1/2$, the direct inequality is: $$x_1 + x_2 + \frac{3}{2}x_3 \leq 1$$ Now, by relaxing the coefficient of $x_3$ from $3/2$ to $1$, we obtain the indirect valid inequality $x_1 + x_2 + x_3 \leq 1$. This example illustrates that some valid inequalities are only obtainable through relaxation of direct inequalities. # Farkas' Lemma: A Fundamental Theorem ## The Core Result: Necessary and Sufficient Condition Farkas' Lemma provides a fundamental result in linear programming and the theory of valid inequalities. It gives a necessary and sufficient condition for an inequality to be valid for a polyhedron in standard form. Essentially, it formalizes the idea that all valid inequalities are relaxations of direct inequalities. ## Formal Statement of Farkas' Lemma ::: tcolorbox Let $A$ be an $M \times N$ matrix, $b \in \mathbb{R}^M$, $\alpha \in \mathbb{R}^N$, and $\beta \in \mathbb{R}$. Assume the polyhedron $P = \{x \in \mathbb{R}^N : Ax = b, x \geq 0\}$ is non-empty. Then, the system of inequalities: $$\begin{aligned} Ax &= b \label{eq:system3_1} \\ \alpha x &> \beta \label{eq:system3_2} \\ x &\geq 0 \label{eq:system3_3} \end{aligned}$$ (System 3) has no solution if and only if the system of inequalities: $$\begin{aligned} U A &\geq \alpha \label{eq:system4_1} \\ U b &\leq \beta \label{eq:system4_2} \end{aligned}$$ (System 4) has a solution for some $U \in \mathbb{R}^M$. ::: ### Two Related Systems of Inequalities System 3 attempts to find a point in the polyhedron $P$ that violates the inequality $\alpha x \leq \beta$. System 4 seeks a set of multipliers $U$ that define a direct valid inequality $U A x \leq U b$ such that $U A \geq \alpha$ and $U b \leq \beta$. ### Interpretation of the First System (No Solution) The statement that System 3 has no solution means that there is no $x \in P$ for which $\alpha x > \beta$. This is equivalent to saying that for all $x \in P$, $\alpha x \leq \beta$. In other words, System 3 having no solution is equivalent to $\alpha x \leq \beta$ being a valid inequality for $P$. Therefore, Farkas' Lemma states that $\alpha x \leq \beta$ is a valid inequality for $P$ if and only if there exists a vector $U \in \mathbb{R}^M$ such that $U A \geq \alpha$ and $U b \leq \beta$. This precisely means that a valid inequality is obtained by relaxing a direct inequality. ## Proof of Farkas' Lemma We need to prove both directions of the \"if and only if\" statement. ### Part 1: If System 4 has a solution, then System 3 has no solution Assume System 4 has a solution, say $U^*$. Then we have $U^* A \geq \alpha$ and $U^* b \leq \beta$. Suppose, for contradiction, that System 3 also has a solution, say $x^*$. Then we have $A x^* = b$, $\alpha x^* > \beta$, and $x^* \geq 0$. Since $U^* A \geq \alpha$ and $x^* \geq 0$, we can multiply the inequality $U^* A \geq \alpha$ by $x^*$ (component-wise and sum), obtaining: $$(U^* A) x^* \geq \alpha x^*$$ Since $A x^* = b$, we have $(U^* A) x^* = U^* (A x^*) = U^* b$. Thus, $$U^* b \geq \alpha x^*$$ However, from System 4, we know $U^* b \leq \beta$, and from System 3, we know $\alpha x^* > \beta$. Combining these, we get: $$\beta \geq U^* b \geq \alpha x^* > \beta$$ This implies $\beta > \beta$, which is a contradiction. Therefore, if System 4 has a solution, then System 3 cannot have a solution. ### Part 2: If System 3 has no solution, then System 4 has a solution Assume System 3 has no solution. This means for every $x \in P = \{x : Ax = b, x \geq 0\}$, we have $\alpha x \leq \beta$. We want to show that System 4 has a solution. Consider the linear programming problem: $$\text{Maximize } \alpha x \quad \text{subject to } Ax = b, x \geq 0$$ Since we assumed $P = \{x : Ax = b, x \geq 0\}$ is non-empty, the problem is feasible. Furthermore, since System 3 has no solution, it means for all feasible $x$, $\alpha x \leq \beta$. Thus, the objective function $\alpha x$ is bounded above by $\beta$ on the feasible region. Therefore, the linear program has an optimal solution, and the optimal value is finite and less than or equal to $\beta$. Let $x^*$ be an optimal basic feasible solution obtained by the simplex method. Let $B$ be the optimal basis. #### Leveraging Linear Programming and the Simplex Method When the simplex method terminates at an optimal solution, we have reduced costs that are non-positive for maximization problems. Let's partition the variables into basic variables $x_B$ and non-basic variables $x_N$. Similarly, partition $\alpha = (\alpha_B, \alpha_N)$ and $A = [A_B, A_N]$. The reduced cost for a non-basic variable $x_j$ is given by $c_j - c_B B^{-1} A_j \leq 0$, where $c = \alpha^T$. In our vector notation, this translates to $\alpha_N^T - \alpha_B^T A_B^{-1} A_N \leq 0$ (component-wise). Let $U = \alpha_B^T A_B^{-1}$. Then the reduced cost condition becomes $\alpha_N^T - U A_N \leq 0$, or $\alpha_N^T \leq U A_N$. For basic variables, the reduced cost is zero, so $\alpha_B^T - U A_B = \alpha_B^T - \alpha_B^T A_B^{-1} A_B = \alpha_B^T - \alpha_B^T = 0$, so $\alpha_B^T \leq U A_B$ also holds. Combining these, we have $\alpha^T \leq U A$, or in row vector form, $UA \geq \alpha$. #### Constructing a Solution for the Second System Let $U = \alpha_B^T A_B^{-1}$. We have shown that $UA \geq \alpha$. Now we need to show $Ub \leq \beta$. The optimal value of the linear program is $\alpha x^* = \alpha_B x_B^* = \alpha_B A_B^{-1} b = U b$. Since the optimal value is less than or equal to $\beta$ (because $\alpha x \leq \beta$ for all feasible $x$), we have $Ub \leq \beta$. Thus, we have found a vector $U = \alpha_B^T A_B^{-1}$ such that $UA \geq \alpha$ and $Ub \leq \beta$. Therefore, System 4 has a solution. This completes the proof of Farkas' Lemma. ## Significance: Characterizing Valid Inequalities ::: tcolorbox Farkas' Lemma provides a powerful tool for characterizing valid inequalities. It confirms that every valid inequality for a polyhedron $P = \{x : Ax = b, x \geq 0\}$ is indeed a relaxation of a direct inequality obtained from linear combinations of the equations $Ax = b$. This result is fundamental in understanding the structure of polyhedra and in developing algorithms for optimization problems. ::: # Duality in Linear Programming ## Valid Inequalities and Upper Bounds on the Objective Function Consider a linear programming problem in standard form: $$\text{Maximize } cx \quad \text{subject to } Ax = b, x \geq 0$$ Let $P = \{x : Ax = b, x \geq 0\}$ be the feasible region. We are interested in finding valid inequalities of the form $cx \leq \beta$ for $P$. Each such valid inequality provides an upper bound $\beta$ on the optimal objective function value. ### Using Valid Inequalities to Bound the Optimal Value If $cx \leq \beta$ is a valid inequality for $P$, then for any feasible solution $x \in P$, the objective value $cx$ is at most $\beta$. Therefore, the maximum possible value of $cx$ over $P$, denoted as $z^* = \max \{cx : x \in P\}$, must also satisfy $z^* \leq \beta$. ### The Tightest Upper Bound We want to find the tightest possible upper bound, i.e., the smallest $\beta$ such that $cx \leq \beta$ is a valid inequality. This smallest $\beta$ will be exactly equal to the optimal value $z^*$, assuming the problem is bounded. ## Formulating the Dual Problem According to Farkas' Lemma, $cx \leq \beta$ is a valid inequality if and only if there exists a vector $U$ such that $UA \geq c$ and $Ub \leq \beta$. To find the tightest upper bound, we want to minimize $\beta$ subject to the existence of such a $U$. Since we want to minimize $\beta$ and we have the condition $Ub \leq \beta$, to minimize $\beta$, we should try to make $\beta$ as close to $Ub$ as possible. The best we can do is to set $\beta = Ub$. ### Minimizing the Right-Hand Side of a Valid Inequality So, we want to solve the problem: $$\text{Minimize } \beta \quad \text{subject to } \exists U \text{ such that } UA \geq c \text{ and } Ub \leq \beta$$ Since we want to minimize $\beta$ and we must have $Ub \leq \beta$, the optimal choice for $\beta$ will be $\beta = Ub$. Thus, we can reformulate the problem as: $$\text{Minimize } Ub \quad \text{subject to } UA \geq c$$ where $U \in \mathbb{R}^M$ is the variable. ### Connecting to Farkas' Lemma and Multipliers This minimization problem is formulated in terms of the multipliers $U$ that define direct valid inequalities. We are seeking the multipliers that give us the smallest upper bound on $cx$. ## Deriving the Dual Linear Program ### Minimization Problem in Canonical Form The problem we derived is: $$\text{Minimize } Ub \quad \text{subject to } UA \geq c$$ This is a linear programming problem in minimization form. Let's rewrite it in a more standard form using column vectors. Let $y = U^T$. Then $U = y^T$. The problem becomes: $$\text{Minimize } b^T y \quad \text{subject to } (y^T A)^T \geq c^T$$ $$\text{Minimize } b^T y \quad \text{subject to } A^T y \geq c^T$$ $$\text{Minimize } b^T y \quad \text{subject to } A^T y \geq c, \quad y \in \mathbb{R}^M$$ Here, $y$ is a column vector of variables, and it is unconstrained in sign. This is the dual linear program in canonical form corresponding to the primal problem: $$\text{Maximize } cx \quad \text{subject to } Ax = b, x \geq 0$$ ### The Dual Problem Definition Given the primal linear program in standard form: $$\begin{aligned} \text{Maximize } & cx \\ \text{subject to } & Ax = b \\ & x \geq 0 \end{aligned}$$ The dual linear program is defined as: $$\begin{aligned} \text{Minimize } & b^T y \\ \text{subject to } & A^T y \geq c \\ & y \in \mathbb{R}^M \text{ (unconstrained)} \end{aligned}$$ ### Primal vs. Dual Forms: Vector Notation In vector notation, if the primal is: $$\begin{aligned} \max & \ c^T x \\ \text{s.t. } & Ax = b \\ & x \geq 0 \end{aligned}$$ The dual is: $$\begin{aligned} \min & \ b^T y \\ \text{s.t. } & A^T y \geq c \\ & y \text{ unconstrained} \end{aligned}$$ The duality theory of linear programming establishes a strong relationship between the optimal solutions of the primal and dual problems, which we will explore further in subsequent lectures. # Conclusion In this lecture, we introduced the concept of valid inequalities for polyhedra in standard form and explored methods to construct them, including direct and indirect approaches. We presented Farkas' Lemma, a cornerstone theorem that characterizes valid inequalities and provides a necessary and sufficient condition for their validity. Finally, we began to see how the study of valid inequalities naturally leads to the formulation of the dual problem in linear programming. **Key Takeaways:** - Valid inequalities are crucial for understanding the feasible region of linear programs. - Direct valid inequalities are linear combinations of constraint equations. - Indirect valid inequalities are relaxations of direct inequalities. - Farkas' Lemma provides a fundamental characterization of valid inequalities. - The concept of valid inequalities is intrinsically linked to the formulation of the dual linear program. **Further Thinking:** - How can we systematically generate all relevant valid inequalities for a given polyhedron? - What are the implications of Farkas' Lemma for solving linear programming problems? - How does the duality theory help in understanding the sensitivity of optimal solutions to changes in problem parameters? These questions will guide our exploration in future lectures as we delve deeper into linear programming and optimization theory.