Geometry of Linear Programming and Polyhedra

Author

Your Name

Published

January 30, 2025

Introduction

This lecture explores the geometric interpretation of the solution set of a linear programming (LP) problem. We will delve into the concepts of polyhedra, polytopes, and their properties. The main objectives are to understand:

The definition and properties of polyhedra and polytopes.
The concept of dimension and how it relates to the constraints of a linear program.
The definition of faces, facets, edges, and vertices of a polyhedron.
The relationship between vertices of a polyhedron and basic feasible solutions of the system defining it.
The Weyl-Minkowski theorem and the two representations of a polytope (external and internal).

Polyhedron: The intersection of a finite number of half-spaces.
Polytope: A bounded polyhedron.
Dimension: The number of linearly independent directions within a polyhedron.
Face: The intersection of a polyhedron with a supporting hyperplane.
Facet: A face of dimension one less than the dimension of the polyhedron.
Edge: A face of dimension 1.
Vertex: A face of dimension 0; an extreme point.
Basic Feasible Solution: A solution to the LP constraints that corresponds to a vertex of the polyhedron.
Convex Combination: A linear combination of points where the coefficients are non-negative and sum to 1.
Convex Hull: The set of all possible convex combinations of a set of points.

These concepts are fundamental to understanding the geometry of linear programming and will be used throughout the course to analyze and solve LP problems. The connection between the geometric properties of polyhedra and the algebraic properties of linear programs will be a recurring theme.

Polyhedra and Polytopes

The solution set of a linear programming problem forms a polyhedron. This is a fundamental concept in the geometry of linear programming.

A polyhedron is the intersection of a finite number of half-spaces. Formally, a polyhedron $P \subset \mathbb{R}^n$ can be represented as: \[P = \{x \in \mathbb{R}^n \mid Ax \leq b \}\] where $A \in \mathbb{R}^{m \times n}$ is a matrix and $b \in \mathbb{R}^m$ is a vector. Each row of $A$ and the corresponding element of $b$ define a half-space.

A half-space in $\mathbb{R}^n$ is a set of points satisfying a linear inequality of the form $a^Tx \leq \beta$, where $a \in \mathbb{R}^n$ is a non-zero vector and $\beta \in \mathbb{R}$ is a scalar.

A polytope is a bounded polyhedron. In other words, a polytope is a polyhedron that can be enclosed within a ball of finite radius. Formally, a polytope $P$ is a polyhedron for which there exists a real number $M > 0$ such that $\|x\| \leq M$ for all $x \in P$.

A set $S \subset \mathbb{R}^n$ is bounded if there exists a real number $M > 0$ such that for all $x \in S$, the Euclidean norm $\|x\| \leq M$. This means that all points in the set are within a finite distance from the origin.

Example: A cube or a tetrahedron in $\mathbb{R}^3$ are examples of polytopes. A line in $\mathbb{R}^2$ is a polyhedron but not a polytope, as it extends infinitely.

A cube in (^3) is an example of a polytope.

A line in (^2) is a polyhedron but not a polytope.

In essence, a polyhedron is a general geometric object defined by linear inequalities, while a polytope is a special case of a polyhedron that is also bounded. This distinction is crucial for understanding the behavior of linear programming algorithms, as the boundedness of a polytope often simplifies the analysis and guarantees the existence of optimal solutions.

Dimension of a Polyhedron

The dimension of a polyhedron is a measure of its "size" within the space it resides. A polyhedron can have a dimension equal to the dimension of the ambient space (full-dimensional) or less.

A cube in $\mathbb{R}^3$ is full-dimensional because it occupies a 3-dimensional volume.
A square in $\mathbb{R}^2$ is full-dimensional because it occupies a 2-dimensional area.
A square in $\mathbb{R}^3$ is not full-dimensional; it has dimension 2 within a 3-dimensional space.
A cube in $\mathbb{R}^4$ is not full-dimensional; it has dimension 3 within a 4-dimensional space.

The dimension of a polyhedron $P$, denoted as $\text{dim}(P)$, is the maximum number of affinely independent points in $P$ minus 1. Equivalently, it is the dimension of the affine hull of $P$.

A set of points $x_1, x_2, ..., x_k$ in $\mathbb{R}^n$ is affinely independent if the vectors $x_2 - x_1, x_3 - x_1, ..., x_k - x_1$ are linearly independent.

The affine hull of a set of points $S \subset \mathbb{R}^n$, denoted as $\text{aff}(S)$, is the set of all affine combinations of points in $S$. An affine combination of points $x_1, ..., x_k$ is a linear combination $\sum_{i=1}^k \lambda_i x_i$ where $\sum_{i=1}^k \lambda_i = 1$.

The dimension of a polyhedron is reduced when constraints are equalities instead of inequalities. This is because each linearly independent equality constraint reduces the degrees of freedom by one.

Example (in $\mathbb{R}^2$):

Consider a polyhedron defined by inequalities in the plane. Adding inequalities generally maintains the dimension. However, if we have two inequalities that force the solution to lie on a line (one saying "stay below the line" and the other "stay above the line"), the polyhedron becomes a line segment, reducing its dimension to 1.

Adding inequalities in (^2). The shaded triangle represents the polyhedron defined by (x + y ), (x ), and (y ). The dashed lines represent the equations (x + y = 2) and (x + y = 1). If we replace (x + y ) with (x + y = 3), the polyhedron reduces to the line segment (ab).

Example (in $\mathbb{R}^3$):

A cube can be defined by six orthogonal planes (inequalities). Adding more planes with various angles creates a shape like a diamond. If we introduce a constraint that forces the solution to lie on a plane (equality), the cube or diamond becomes a 2-dimensional figure on that plane.

Introducing an equality constraint in (^3). The cube is defined by inequalities. Adding the plane (z=2) (an equality) reduces the polyhedron to the square on that plane.

Formally, if a system $Ax \leq b$ (a canonical form LP) contains implicit equations, the dimension of the polyhedron $P = \{x \in \mathbb{R}^n \mid Ax \leq b\}$ is:

\[\text{dim}(P) = n - \text{rank}(A_=)\]

where $n$ is the dimension of the ambient space and $A_=$ is the submatrix of $A$ corresponding to the rows that are satisfied as equalities by all points in $P$. These rows form the largest set of linearly independent equations that are implicitly contained in $Ax \leq b$.

If the polyhedron is full-dimensional, there are no implicit equations, only true inequalities. In other words, $\text{rank}(A_=) = 0$.

A polyhedron $P \subset \mathbb{R}^n$ is full-dimensional if $\text{dim}(P) = n$. This means that the polyhedron occupies a non-zero volume in the $n$-dimensional space.

Vertices and Basic Solutions

Vertices, also known as extreme points, are fundamental to understanding the geometry of polyhedra and their connection to linear programming. We have already defined vertices as faces of dimension 0. Here is an alternative, equivalent definition:

A point $x$ in a polyhedron $P$ is a vertex (or extreme point) if it cannot be expressed as a convex combination of two other distinct points in $P$. Formally, if $x = \lambda y + (1-\lambda)z$ for some $y, z \in P$ and $0 < \lambda < 1$, then $x = y = z$.

A convex combination of two points $y$ and $z$ is a point of the form $\lambda y + (1-\lambda)z$, where $0 \leq \lambda \leq 1$. Geometrically, this represents all points on the line segment connecting $y$ and $z$.

Example:

Consider the prism in Figure 5. Vertex C cannot be expressed as $\frac{1}{2}P + \frac{1}{2}Q$ for any $P, Q \neq C$ in the polyhedron. If we try to write C as a convex combination of two points in the prism, we will find that at least one of those points must be C itself.

Vertex C in the prism.

Now, let’s establish the connection between vertices of a polyhedron and basic feasible solutions of the corresponding linear program.

Let $P = \{x \in \mathbb{R}^n \mid Ax = b, x \geq 0\}$ be a non-empty polyhedron in standard form, where $A \in \mathbb{R}^{m \times n}$ has full row rank. A point $x \in P$ is a vertex of $P$ if and only if $x$ is a basic feasible solution.

A basic feasible solution (BFS) of a linear program in standard form ($Ax = b, x \geq 0$) is a solution where at least $n-m$ components of $x$ are zero, and the columns of $A$ corresponding to the non-zero components are linearly independent.

**Proof idea** - **Vertex implies BFS:** If x is a vertex, we can show that the columns of A corresponding to its positive components are linearly independent. If not, we can express x as a convex combination of two other points in P, contradicting the vertex definition. - **BFS implies Vertex:** If x is a BFS, we can show that it cannot be written as a convex combination of two other points in P. If it could, we would arrive at a contradiction regarding the linear independence of the columns in the basis.

This theorem is crucial because it connects the geometric concept of a vertex to the algebraic concept of a basic feasible solution. It tells us that when we are looking for optimal solutions to a linear program, we can focus on the basic feasible solutions, which correspond to the vertices of the polyhedron. The simplex method, which we will study later, exploits this connection by moving from one vertex to another, searching for the optimal solution.

Weyl-Minkowski Theorem

The Weyl-Minkowski theorem, also known as Minkowski’s theorem for polytopes or the finite basis theorem for polytopes, establishes a fundamental connection between the external and internal representations of polytopes.

A set $P \subset \mathbb{R}^n$ is a polytope if and only if there exists a finite set of points $V = \{v_1, v_2, ..., v_k\}$ in $\mathbb{R}^n$ such that $P$ is the convex hull of $V$, i.e., $P = \text{conv}(V)$.

The convex hull of a set of points $V = \{v_1, v_2, ..., v_k\}$, denoted as $\text{conv}(V)$, is the set of all possible convex combinations of those points. Formally: \[\text{conv}(V) = \left\{ \sum_{i=1}^k \lambda_i v_i \mid \lambda_i \geq 0, \sum_{i=1}^k \lambda_i = 1 \right\}\] Geometrically, the convex hull is the smallest convex set that contains all the points in $V$.

This theorem provides two equivalent ways of representing a polytope:

External Representation (H-representation): Defined by a set of linear inequalities (half-spaces). This is the representation we have been using so far, where a polytope $P$ is described as $P = \{x \in \mathbb{R}^n \mid Ax \leq b\}$.
Internal Representation (V-representation): Defined by a finite set of points (vertices) whose convex hull is the polytope. In this representation, a polytope $P$ is described as $P = \text{conv}\{v_1, v_2, ..., v_k\}$, where $v_1, ..., v_k$ are the vertices of $P$.

Example:

Consider a square in $\mathbb{R}^2$ with vertices (0,0), (1,0), (1,1), and (0,1).

A square represented as a polytope.

External Representation: The square can be described by the following inequalities: \[x \geq0, \quad x \leq 1, \quad y \geq 0, \quad y \leq 1\] In matrix form, $Ax \leq b$, where \[A = \begin{pmatrix} -1 & 0 \\ 1 & 0 \\ 0 & -1 \\ 0 & 1 \end{pmatrix}, \quad b = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 1 \end{pmatrix}\]
Internal Representation: The square can be described as the convex hull of its vertices: \[P = \text{conv}\{(0,0), (1,0), (1,1), (0,1)\}\]

The Weyl-Minkowski theorem states that these two representations are equivalent. We can always find a set of inequalities that defines the same polytope as the convex hull of a given set of vertices, and vice versa.

This duality between the external and internal representations is crucial in various areas of optimization, computational geometry, and computer science. For example, some algorithms are more efficient when working with the external representation, while others are better suited for the internal representation. The ability to switch between these representations is a powerful tool in the study of polytopes and their applications.

Conclusion

In this lecture, we delved into the geometric interpretation of linear programming solutions, focusing on the key concepts of polyhedra and polytopes. Here’s a summary of what we have learned:

The solution set of a linear program forms a polyhedron. If this polyhedron is bounded, it is called a polytope.
The dimension of a polyhedron is determined by the number of variables minus the rank of the matrix representing the equality constraints that are implicitly contained in the system of inequalities. Each independent equality constraint reduces the dimension by one.
Faces, facets, edges, and vertices are important features of polyhedra.
- Facets are faces of dimension one less than the polyhedron itself and are crucial for defining the polyhedron.
- Edges are faces of dimension 1.
- Vertices are faces of dimension 0, also known as extreme points.
Vertices are special points that cannot be expressed as a convex combination of two other distinct points within the polyhedron. They correspond to the basic feasible solutions of the linear program.
The Weyl-Minkowski theorem provides a crucial link between the two representations of a polytope:
- The external representation (H-representation) using inequalities.
- The internal representation (V-representation) using the convex hull of vertices.
This theorem states that every polytope can be represented in both ways, and these representations are equivalent.

Polyhedra and polytopes provide a geometric framework for understanding linear programming.
The dimension of a polyhedron reflects the degrees of freedom within the solution set.
Facets are essential for defining a polyhedron, and vertices correspond to basic feasible solutions.
The Weyl-Minkowski theorem highlights the duality between the external and internal representations of polytopes.

Follow-up Questions:

These are some interesting questions that arise from our discussion and will be explored in future lectures:

How does the simplex method relate to the vertices of a polyhedron?
- Hint: The simplex method
Can we determine the number of vertices of a polyhedron based on its defining inequalities?
- Hint: This is a complex problem in general. However, for certain classes of polyhedra, there are results that relate the number of vertices to the number of inequalities and the dimension of the space.
How can we efficiently convert between the external (H-representation) and internal (V-representation) representations of a polytope?
- Hint: This is known as the vertex enumeration problem (given the inequalities, find the vertices) and the facet enumeration problem (given the vertices, find the inequalities). There are algorithms for both problems, but their complexity can be high in the worst case.

Addressing Previous Remarks:

Connection between vertices and basic solutions: This was clarified in Section [sec:vertices_basic_solutions] with Theorem [thm:vertex_basic_solution], which states that a point is a vertex of a polyhedron if and only if it is a basic feasible solution of the corresponding linear program.
Definitions of "convex hull" and "convex combination": These were explicitly defined in the boxes following Definition [def:vertex_alternative] and Theorem [thm:weyl_minkowski].

Next Lecture Preview:

In the next lecture, we will discuss the simplex method and its connection to the geometry of polyhedra. We will explore how the algorithm leverages the concepts we have learned, particularly the relationship between vertices and basic feasible solutions, to efficiently traverse the vertices of the polyhedron and find the optimal solution to a linear program. We will see how the simplex method provides a practical way to solve linear programs by exploiting their geometric properties.

--- title: "Geometry of Linear Programming and Polyhedra" 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 geometric interpretation of the solution set of a linear programming (LP) problem. We will delve into the concepts of polyhedra, polytopes, and their properties. The main objectives are to understand: - The definition and properties of **polyhedra** and **polytopes**. - The concept of **dimension** and how it relates to the constraints of a linear program. - The definition of **faces**, **facets**, **edges**, and **vertices** of a polyhedron. - The relationship between **vertices** of a polyhedron and **basic feasible solutions** of the system defining it. - The **Weyl-Minkowski theorem** and the two representations of a polytope (**external** and **internal**). ::: tcolorbox - **Polyhedron**: The intersection of a finite number of half-spaces. - **Polytope**: A bounded polyhedron. - **Dimension**: The number of linearly independent directions within a polyhedron. - **Face**: The intersection of a polyhedron with a supporting hyperplane. - **Facet**: A face of dimension one less than the dimension of the polyhedron. - **Edge**: A face of dimension 1. - **Vertex**: A face of dimension 0; an extreme point. - **Basic Feasible Solution**: A solution to the LP constraints that corresponds to a vertex of the polyhedron. - **Convex Combination**: A linear combination of points where the coefficients are non-negative and sum to 1. - **Convex Hull**: The set of all possible convex combinations of a set of points. ::: These concepts are fundamental to understanding the geometry of linear programming and will be used throughout the course to analyze and solve LP problems. The connection between the geometric properties of polyhedra and the algebraic properties of linear programs will be a recurring theme. # Polyhedra and Polytopes The solution set of a linear programming problem forms a **polyhedron**. This is a fundamental concept in the geometry of linear programming. ::: tcolorbox []{#def:polyhedron label="def:polyhedron"} A polyhedron is the intersection of a finite number of half-spaces. Formally, a polyhedron $P \subset \mathbb{R}^n$ can be represented as: $$P = \{x \in \mathbb{R}^n \mid Ax \leq b \}$$ where $A \in \mathbb{R}^{m \times n}$ is a matrix and $b \in \mathbb{R}^m$ is a vector. Each row of $A$ and the corresponding element of $b$ define a half-space. ::: ::: tcolorbox A half-space in $\mathbb{R}^n$ is a set of points satisfying a linear inequality of the form $a^Tx \leq \beta$, where $a \in \mathbb{R}^n$ is a non-zero vector and $\beta \in \mathbb{R}$ is a scalar. ::: ::: tcolorbox []{#def:polytope label="def:polytope"} A polytope is a bounded polyhedron. In other words, a polytope is a polyhedron that can be enclosed within a ball of finite radius. Formally, a polytope $P$ is a polyhedron for which there exists a real number $M > 0$ such that $\|x\| \leq M$ for all $x \in P$. ::: ::: tcolorbox A set $S \subset \mathbb{R}^n$ is bounded if there exists a real number $M > 0$ such that for all $x \in S$, the Euclidean norm $\|x\| \leq M$. This means that all points in the set are within a finite distance from the origin. ::: **Example:** A cube or a tetrahedron in $\mathbb{R}^3$ are examples of polytopes. A line in $\mathbb{R}^2$ is a polyhedron but not a polytope, as it extends infinitely. <figure id="fig:cube_polytope"> <figcaption>A cube in $\mathbb{R}^3$ is an example of a polytope.</figcaption> </figure> <figure id="fig:line_polyhedron"> <figcaption>A line in $\mathbb{R}^2$ is a polyhedron but not a polytope.</figcaption> </figure> In essence, a polyhedron is a general geometric object defined by linear inequalities, while a polytope is a special case of a polyhedron that is also bounded. This distinction is crucial for understanding the behavior of linear programming algorithms, as the boundedness of a polytope often simplifies the analysis and guarantees the existence of optimal solutions. # Dimension of a Polyhedron The dimension of a polyhedron is a measure of its \"size\" within the space it resides. A polyhedron can have a dimension equal to the dimension of the ambient space (full-dimensional) or less. - A cube in $\mathbb{R}^3$ is full-dimensional because it occupies a 3-dimensional volume. - A square in $\mathbb{R}^2$ is full-dimensional because it occupies a 2-dimensional area. - A square in $\mathbb{R}^3$ is not full-dimensional; it has dimension 2 within a 3-dimensional space. - A cube in $\mathbb{R}^4$ is not full-dimensional; it has dimension 3 within a 4-dimensional space. ::: tcolorbox []{#def:dimension label="def:dimension"} The dimension of a polyhedron $P$, denoted as $\text{dim}(P)$, is the maximum number of affinely independent points in $P$ minus 1. Equivalently, it is the dimension of the affine hull of $P$. ::: ::: tcolorbox A set of points $x_1, x_2, ..., x_k$ in $\mathbb{R}^n$ is affinely independent if the vectors $x_2 - x_1, x_3 - x_1, ..., x_k - x_1$ are linearly independent. ::: ::: tcolorbox The affine hull of a set of points $S \subset \mathbb{R}^n$, denoted as $\text{aff}(S)$, is the set of all affine combinations of points in $S$. An affine combination of points $x_1, ..., x_k$ is a linear combination $\sum_{i=1}^k \lambda_i x_i$ where $\sum_{i=1}^k \lambda_i = 1$. ::: The dimension of a polyhedron is reduced when constraints are equalities instead of inequalities. This is because each linearly independent equality constraint reduces the degrees of freedom by one. **Example (in $\mathbb{R}^2$):** Consider a polyhedron defined by inequalities in the plane. Adding inequalities generally maintains the dimension. However, if we have two inequalities that force the solution to lie on a line (one saying \"stay below the line\" and the other \"stay above the line\"), the polyhedron becomes a line segment, reducing its dimension to 1. <figure id="fig:dimension_r2"> <figcaption>Adding inequalities in $\mathbb{R}^2$. The shaded triangle represents the polyhedron defined by $x + y \leq 3$, $x \geq 0$, and $y \geq 0$. The dashed lines represent the equations $x + y = 2$ and $x + y = 1$. If we replace $x + y \leq 3$ with $x + y = 3$, the polyhedron reduces to the line segment $ab$.</figcaption> </figure> **Example (in $\mathbb{R}^3$):** A cube can be defined by six orthogonal planes (inequalities). Adding more planes with various angles creates a shape like a diamond. If we introduce a constraint that forces the solution to lie on a plane (equality), the cube or diamond becomes a 2-dimensional figure on that plane. <figure id="fig:dimension_r3"> <figcaption>Introducing an equality constraint in $\mathbb{R}^3$. The cube is defined by inequalities. Adding the plane $z=2$ (an equality) reduces the polyhedron to the square on that plane.</figcaption> </figure> Formally, if a system $Ax \leq b$ (a canonical form LP) contains implicit equations, the dimension of the polyhedron $P = \{x \in \mathbb{R}^n \mid Ax \leq b\}$ is: $$\text{dim}(P) = n - \text{rank}(A_=)$$ where $n$ is the dimension of the ambient space and $A_=$ is the submatrix of $A$ corresponding to the rows that are satisfied as equalities by all points in $P$. These rows form the largest set of linearly independent equations that are implicitly contained in $Ax \leq b$. If the polyhedron is full-dimensional, there are no implicit equations, only true inequalities. In other words, $\text{rank}(A_=) = 0$. ::: tcolorbox A polyhedron $P \subset \mathbb{R}^n$ is full-dimensional if $\text{dim}(P) = n$. This means that the polyhedron occupies a non-zero volume in the $n$-dimensional space. ::: # Faces, Facets, Edges, and Vertices Faces are important features of a polyhedron, representing its boundaries. They are defined as follows: ::: tcolorbox []{#def:face label="def:face"} Let $P = \{x \in \mathbb{R}^n \mid Ax \leq b\}$ be a polyhedron. A face of $P$ is a set $F$ of the form $$F = P \cap \{x \in \mathbb{R}^n \mid a^T x = \beta \}$$ where $a^T x \leq \beta$ is a valid inequality for $P$. In other words, a face is the intersection of $P$ with a supporting hyperplane. ::: ::: tcolorbox An inequality $a^T x \leq \beta$ is valid for a polyhedron $P$ if it is satisfied by all points in $P$, i.e., $a^T x \leq \beta$ for all $x \in P$. ::: ::: tcolorbox A hyperplane $H = \{x \in \mathbb{R}^n \mid a^T x = \beta\}$ is a supporting hyperplane for a polyhedron $P$ if $a^T x \leq \beta$ is a valid inequality for $P$ and $P \cap H \neq \emptyset$. ::: Faces of a polyhedron are themselves polyhedra of smaller dimensions. We can categorize faces based on their dimension: - **Facets**: Faces of dimension $k-1$, where $k$ is the dimension of the polyhedron. These are the \"largest\" proper faces. - **Edges**: Faces of dimension 1. These are line segments connecting vertices. - **Vertices**: Faces of dimension 0. These are single points, also called extreme points. **Example:** Consider a 3-dimensional polyhedron like a prism. <figure id="fig:prism_faces"> <figcaption>A prism as an example of a 3-dimensional polyhedron. The shaded area EFGH is a facet (2-dimensional), the red line segment BF is an edge (1-dimensional), and the green point A is a vertex (0-dimensional).</figcaption> </figure> In this prism: - **Facets** are 2-dimensional (e.g., the rectangle EFGH, the triangles ABE and CDG). - **Edges** are 1-dimensional (e.g., the line segments AB, BF, FG, etc.). - **Vertices** are 0-dimensional (e.g., the points A, B, C, D, E, F, G, H). ::: tcolorbox An inequality $a^T x \leq \beta$ is facet-defining for a polyhedron $P$ if it is valid for $P$ and the face $F = P \cap \{x \in \mathbb{R}^n \mid a^T x = \beta\}$ has dimension $\text{dim}(P) - 1$. ::: Two polyhedra are identical if and only if they have the same facet-defining inequalities. This highlights the importance of facets in characterizing a polyhedron. # Vertices and Basic Solutions Vertices, also known as extreme points, are fundamental to understanding the geometry of polyhedra and their connection to linear programming. We have already defined vertices as faces of dimension 0. Here is an alternative, equivalent definition: ::: tcolorbox []{#def:vertex_alternative label="def:vertex_alternative"} A point $x$ in a polyhedron $P$ is a vertex (or extreme point) if it cannot be expressed as a convex combination of two other distinct points in $P$. Formally, if $x = \lambda y + (1-\lambda)z$ for some $y, z \in P$ and $0 < \lambda < 1$, then $x = y = z$. ::: ::: tcolorbox A convex combination of two points $y$ and $z$ is a point of the form $\lambda y + (1-\lambda)z$, where $0 \leq \lambda \leq 1$. Geometrically, this represents all points on the line segment connecting $y$ and $z$. ::: **Example:** Consider the prism in Figure [5](#fig:prism_faces){reference-type="ref" reference="fig:prism_faces"}. Vertex C cannot be expressed as $\frac{1}{2}P + \frac{1}{2}Q$ for any $P, Q \neq C$ in the polyhedron. If we try to write C as a convex combination of two points in the prism, we will find that at least one of those points must be C itself. <figure id="fig:prism_vertex_c"> <figcaption>Vertex C in the prism.</figcaption> </figure> Now, let's establish the connection between vertices of a polyhedron and basic feasible solutions of the corresponding linear program. ::: tcolorbox []{#thm:vertex_basic_solution label="thm:vertex_basic_solution"} Let $P = \{x \in \mathbb{R}^n \mid Ax = b, x \geq 0\}$ be a non-empty polyhedron in standard form, where $A \in \mathbb{R}^{m \times n}$ has full row rank. A point $x \in P$ is a vertex of $P$ if and only if $x$ is a basic feasible solution. ::: ::: tcolorbox A basic feasible solution (BFS) of a linear program in standard form ($Ax = b, x \geq 0$) is a solution where at least $n-m$ components of $x$ are zero, and the columns of $A$ corresponding to the non-zero components are linearly independent. ::: \*\*Proof idea\*\* - \*\*Vertex implies BFS:\*\* If x is a vertex, we can show that the columns of A corresponding to its positive components are linearly independent. If not, we can express x as a convex combination of two other points in P, contradicting the vertex definition. - \*\*BFS implies Vertex:\*\* If x is a BFS, we can show that it cannot be written as a convex combination of two other points in P. If it could, we would arrive at a contradiction regarding the linear independence of the columns in the basis. This theorem is crucial because it connects the geometric concept of a vertex to the algebraic concept of a basic feasible solution. It tells us that when we are looking for optimal solutions to a linear program, we can focus on the basic feasible solutions, which correspond to the vertices of the polyhedron. The simplex method, which we will study later, exploits this connection by moving from one vertex to another, searching for the optimal solution. # Weyl-Minkowski Theorem The Weyl-Minkowski theorem, also known as Minkowski's theorem for polytopes or the finite basis theorem for polytopes, establishes a fundamental connection between the external and internal representations of polytopes. ::: tcolorbox []{#thm:weyl_minkowski label="thm:weyl_minkowski"} A set $P \subset \mathbb{R}^n$ is a polytope if and only if there exists a finite set of points $V = \{v_1, v_2, ..., v_k\}$ in $\mathbb{R}^n$ such that $P$ is the convex hull of $V$, i.e., $P = \text{conv}(V)$. ::: ::: tcolorbox The convex hull of a set of points $V = \{v_1, v_2, ..., v_k\}$, denoted as $\text{conv}(V)$, is the set of all possible convex combinations of those points. Formally: $$\text{conv}(V) = \left\{ \sum_{i=1}^k \lambda_i v_i \mid \lambda_i \geq 0, \sum_{i=1}^k \lambda_i = 1 \right\}$$ Geometrically, the convex hull is the smallest convex set that contains all the points in $V$. ::: This theorem provides two equivalent ways of representing a polytope: - **External Representation (H-representation)**: Defined by a set of linear inequalities (half-spaces). This is the representation we have been using so far, where a polytope $P$ is described as $P = \{x \in \mathbb{R}^n \mid Ax \leq b\}$. - **Internal Representation (V-representation)**: Defined by a finite set of points (vertices) whose convex hull is the polytope. In this representation, a polytope $P$ is described as $P = \text{conv}\{v_1, v_2, ..., v_k\}$, where $v_1, ..., v_k$ are the vertices of $P$. **Example:** Consider a square in $\mathbb{R}^2$ with vertices (0,0), (1,0), (1,1), and (0,1). <figure id="fig:square_polytope"> <figcaption>A square represented as a polytope.</figcaption> </figure> - **External Representation**: The square can be described by the following inequalities: $$x \geq0, \quad x \leq 1, \quad y \geq 0, \quad y \leq 1$$ In matrix form, $Ax \leq b$, where $$A = \begin{pmatrix} -1 & 0 \\ 1 & 0 \\ 0 & -1 \\ 0 & 1 \end{pmatrix}, \quad b = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 1 \end{pmatrix}$$ - **Internal Representation**: The square can be described as the convex hull of its vertices: $$P = \text{conv}\{(0,0), (1,0), (1,1), (0,1)\}$$ The Weyl-Minkowski theorem states that these two representations are equivalent. We can always find a set of inequalities that defines the same polytope as the convex hull of a given set of vertices, and vice versa. This duality between the external and internal representations is crucial in various areas of optimization, computational geometry, and computer science. For example, some algorithms are more efficient when working with the external representation, while others are better suited for the internal representation. The ability to switch between these representations is a powerful tool in the study of polytopes and their applications. # Conclusion In this lecture, we delved into the geometric interpretation of linear programming solutions, focusing on the key concepts of polyhedra and polytopes. Here's a summary of what we have learned: - The solution set of a linear program forms a **polyhedron**. If this polyhedron is bounded, it is called a **polytope**. - The **dimension** of a polyhedron is determined by the number of variables minus the rank of the matrix representing the equality constraints that are implicitly contained in the system of inequalities. Each independent equality constraint reduces the dimension by one. - **Faces**, **facets**, **edges**, and **vertices** are important features of polyhedra. - **Facets** are faces of dimension one less than the polyhedron itself and are crucial for defining the polyhedron. - **Edges** are faces of dimension 1. - **Vertices** are faces of dimension 0, also known as extreme points. - **Vertices** are special points that cannot be expressed as a convex combination of two other distinct points within the polyhedron. They correspond to the **basic feasible solutions** of the linear program. - The **Weyl-Minkowski theorem** provides a crucial link between the two representations of a polytope: - The **external representation** (H-representation) using inequalities. - The **internal representation** (V-representation) using the convex hull of vertices. This theorem states that every polytope can be represented in both ways, and these representations are equivalent. ::: tcolorbox - Polyhedra and polytopes provide a geometric framework for understanding linear programming. - The dimension of a polyhedron reflects the degrees of freedom within the solution set. - Facets are essential for defining a polyhedron, and vertices correspond to basic feasible solutions. - The Weyl-Minkowski theorem highlights the duality between the external and internal representations of polytopes. ::: **Follow-up Questions:** These are some interesting questions that arise from our discussion and will be explored in future lectures: - How does the **simplex method** relate to the vertices of a polyhedron? - *Hint*: The simplex method - Can we determine the number of vertices of a polyhedron based on its defining inequalities? - *Hint*: This is a complex problem in general. However, for certain classes of polyhedra, there are results that relate the number of vertices to the number of inequalities and the dimension of the space. - How can we efficiently convert between the external (H-representation) and internal (V-representation) representations of a polytope? - *Hint*: This is known as the vertex enumeration problem (given the inequalities, find the vertices) and the facet enumeration problem (given the vertices, find the inequalities). There are algorithms for both problems, but their complexity can be high in the worst case. **Addressing Previous Remarks:** - **Connection between vertices and basic solutions**: This was clarified in Section [\[sec:vertices_basic_solutions\]](#sec:vertices_basic_solutions){reference-type="ref" reference="sec:vertices_basic_solutions"} with Theorem [\[thm:vertex_basic_solution\]](#thm:vertex_basic_solution){reference-type="ref" reference="thm:vertex_basic_solution"}, which states that a point is a vertex of a polyhedron if and only if it is a basic feasible solution of the corresponding linear program. - **Definitions of \"convex hull\" and \"convex combination\":** These were explicitly defined in the boxes following Definition [\[def:vertex_alternative\]](#def:vertex_alternative){reference-type="ref" reference="def:vertex_alternative"} and Theorem [\[thm:weyl_minkowski\]](#thm:weyl_minkowski){reference-type="ref" reference="thm:weyl_minkowski"}. **Next Lecture Preview:** In the next lecture, we will discuss the **simplex method** and its connection to the geometry of polyhedra. We will explore how the algorithm leverages the concepts we have learned, particularly the relationship between vertices and basic feasible solutions, to efficiently traverse the vertices of the polyhedron and find the optimal solution to a linear program. We will see how the simplex method provides a practical way to solve linear programs by exploiting their geometric properties.