Geometric Interpretation of the Simplex Method

Author

Your Name

Published

January 30, 2025

Introduction

This lecture aims to provide an intuitive and graphical description of the Simplex method’s process. Starting from a feasible but non-optimal basis, the Simplex algorithm iteratively performs pivots, exchanging columns between those entering and leaving the basis. This basis change continues until an optimal basis is reached, at which point the algorithm identifies the "optimal solution". It is important to note that in linear programming problems, the optimal solutions found by the Simplex method are always basic solutions, characterized by having many zero components corresponding to the off-basis variables. While non-basic optimal solutions might exist, it can be demonstrated that if an optimal solution exists, there is always an optimal solution that is a basic solution. Therefore, by focusing solely on basic solutions, we do not lose the optimality.

Geometric Interpretation of the Simplex Method

The Simplex Algorithm’s Iterative Process

The Simplex algorithm starts from a feasible basis and iteratively performs pivots. Each pivot involves swapping columns, changing the basis from a non-optimal to an optimal one. This process continues until an optimal basis is found, indicating the optimal solution.

Basic Feasible Solutions and Optimality

In linear programming, the Simplex method always terminates at basic solutions. Optimal solutions determined by the Simplex are always basic solutions, meaning they contain many zeros corresponding to off-basis components. If optimal solutions exist, there’s always a basic optimal solution. Focusing on basic solutions ensures we do not miss the optimum.

Geometric Concepts

Polyhedra: Definition as Intersection of Semispaces

To understand the Simplex method geometrically, we need to introduce the concept of a polyhedron.

Given a vector $\alpha \in \mathbb{R}^n$ and a constant $\beta \in \mathbb{R}$, consider the inequality $\alpha x \leq \beta$. The set $HS(\alpha, \beta) = \{v \in \mathbb{R}^n \mid \alpha v \leq \beta \}$ is called a semispace in $\mathbb{R}^n$. The boundary of this semispace, $H(\alpha, \beta) = \{v \in \mathbb{R}^n \mid \alpha v = \beta \}$, is called a hyperplane. The vector $\alpha$ is the normal vector, perpendicular to this hyperplane.

In three-dimensional space, a hyperplane can be visualized as an infinitely extending sheet of paper. All points on one side of this hyperplane, including the hyperplane itself, form a semispace. In two-dimensional space (the Cartesian XY plane), a hyperplane is an infinite line. This line divides the plane, and all points on one side of the line, together with the line, constitute a semispace in $\mathbb{R}^2$.

A polyhedron is the intersection of a finite number of semispaces.

Consider a set of lines in a 2D plane, each defining a semispace. For example, lines with arrows indicating the feasible side. The intersection of all these semispaces creates a figure, like the shaded region in the transcription example. This type of figure is a polyhedron. In linear programming problems, especially in canonical and standard forms, the feasible region is always defined by a set of inequalities (and equalities which can be converted to inequalities). Thus, the feasible region of a linear programming problem is always a polyhedron.

A polyhedron in two dimensions is a convex figure with straight edges, formed by consecutive line segments. Semispaces are convex sets, and their intersection is also a convex set. A polyhedron in three dimensions can be imagined as a box or any shape with flat faces.

A parallelepiped (box) is a polyhedron. Each face of the box corresponds to a semispace, and the box is defined by the intersection of these semispaces.

A sphere (ball) is not a polyhedron. While a sphere can be described as an intersection of semispaces, it requires an infinite number of them. Imagine tangents at every point on a circle in 2D or a sphere in 3D. Each tangent defines a semispace containing the circle/sphere. However, as you move along the circumference/surface, you need infinitesimally many semispaces.

Polygons and polyhedra, defined by a finite number of intersecting semispaces, are "spiky" or "linear" without curvature. These shapes have points called vertices.

Polytopes: Bounded Polyhedra

A polyhedron is bounded if there exists a maximum length for any vector contained within it. In other words, the entire polyhedron can be enclosed within a ball of sufficiently large radius. A bounded polyhedron is also called a polytope.

A polytope is a special type of polyhedron where vectors cannot be arbitrarily long.

The polyhedron shown in the transcription (the shaded figure) is a polytope.

A polyhedron can be unbounded, containing arbitrarily long vectors.

A single semispace is an unbounded polyhedron. For instance, consider only one inequality. All vectors on one side of the hyperplane are feasible solutions, and some can be arbitrarily long.

Consider the non-negative orthant in $\mathbb{R}^2$ defined by $x_1 \geq 0$ and $x_2 \geq 0$. This region extends infinitely in the positive $x_1$ and $x_2$ directions and is an unbounded polyhedron, also known as a cone (right-angled cone in this case). It contains vectors of arbitrary length and cannot be contained within any ball of finite radius.

Polytopes are "closed" and do not extend to infinity in any direction.

Dimension of a Polyhedron and Full Dimensionality

The dimension of a polyhedron is an important concept.

A square on a plane (in $\mathbb{R}^2$) has dimension 2.
A line segment has dimension 1.
A point has dimension 0.
A cube (in $\mathbb{R}^3$) has dimension 3.

These are examples of hypercubes. A hypercube of dimension 1 is a segment [0, 1]. A hypercube of dimension 2 is a square of side 1. A hypercube of dimension 3 is a cube of side 1. We can generalize this to higher dimensions. A hypercube of dimension 4 is the product of four [0, 1] intervals in $\mathbb{R}^4$.

Intuitively, a polyhedron has dimension $k$ if it contains a $k$-dimensional hypercube (however small) but does not contain any hypercube of dimension $k+1$. A polyhedron of dimension $k$ in $\mathbb{R}^n$ is of full dimension if $k=n$.

A square is a 2-dimensional polyhedron. It contains a small square, so its dimension is at least 2. It does not contain a cube, so its dimension is 2. Even if this square is placed in $\mathbb{R}^3$, it remains 2-dimensional and is not of full dimension in $\mathbb{R}^3$.

A cube in $\mathbb{R}^3$ contains small cubes, so its dimension is 3. It is of full dimension in $\mathbb{R}^3$. However, in $\mathbb{R}^4$, it is not of full dimension.

Consider the polyhedron in $\mathbb{R}^3$ defined by: \[\begin{aligned} x_1 + x_2 + x_3 &= 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \\ x_3 &\geq 0 \end{aligned}\] This system includes an equation, $x_1 + x_2 + x_3 = 1$. An equation reduces the dimension. This polyhedron is a triangle in $\mathbb{R}^3$. It passes through points (1, 0, 0), (0, 1, 0), and (0, 0, 1). It is a 2-dimensional object in a 3-dimensional space.

In $\mathbb{R}^n$, a hyperplane (defined by one linear equation) has dimension $n-1$. Each independent linear equation in a system reduces the dimension of the solution space by one.

For the example above, $x_1 + x_2 + x_3 = 1$ defines a plane in $\mathbb{R}^3$. The additional inequalities $x_1 \geq 0, x_2 \geq 0, x_3 \geq 0$ restrict this plane to a triangular region. The dimension is reduced from 3 (of $\mathbb{R}^3$) by one due to the equation, resulting in a 2-dimensional polyhedron.

If a system of inequalities has no implicit equations, i.e., for every inequality, there are solutions that strictly satisfy it, then the polyhedron is of full dimension. If some inequalities must be satisfied as equalities for all feasible solutions, those are implicit equations and reduce the dimension.

Faces, Vertices, and Edges: Definitions and Properties

Consider a polyhedron in $\mathbb{R}^3$. It has faces, edges, and vertices.

For a polyhedron $P$, an inequality $\alpha x \leq \beta$ is a valid inequality if it is satisfied by all points $x \in P$.

If we take a valid inequality $\alpha x \leq \beta$ and consider the hyperplane $H = \{x \mid \alpha x = \beta \}$. If $P \cap H \neq \emptyset$, then $P \cap H$ is a face of the polyhedron $P$.

A face of a polyhedron $P$ defined by valid inequality $\alpha x \leq \beta$ is the intersection of $P$ with the hyperplane $H = \{x \mid \alpha x = \beta \}$, provided $P \cap H \neq \emptyset$.

A face of a polyhedron is itself a polyhedron (or polytope if $P$ is a polytope). Faces can have dimensions less than the dimension of $P$.

For a 3-dimensional polyhedron:

Facets: Faces of dimension 2 (dimension of $P$ - 1). Example: Triangle ABC in the example polyhedron.
Edges: Faces of dimension 1. Example: Line segment AB, BC, AC.
Vertices: Faces of dimension 0. Example: Points A, B, C. Also called extreme points.

The polyhedron itself is also considered a face of itself.

Correspondence Between Vertices and Basic Feasible Solutions

A crucial connection exists between vertices of a polyhedron and basic feasible solutions in linear programming.

Vertices of a polyhedron are in correspondence with basic feasible solutions. For every vertex of a polyhedron, there exists a basis such that the vertex is the basic feasible solution corresponding to that basis.

This means the Simplex method, which operates on basic feasible solutions, is geometrically moving between vertices of the feasible region (polyhedron).

Geometric Interpretation of Degeneracy

When the Simplex algorithm pivots and changes basis, geometrically, it corresponds to moving along an edge of the polyhedron.

Non-degenerate case: Changing basis usually means moving from one vertex to an adjacent vertex along an edge.
Degenerate case: If a solution is degenerate, changing the basis might not change the basic feasible solution itself. Geometrically, this means staying at the same vertex, but changing the basis representation of that vertex.

Degeneracy can be geometrically interpreted as a vertex being representable as an intersection of more than the minimum number of hyperplanes.

In $\mathbb{R}^2$, a vertex is typically the intersection of two lines. If more than two lines intersect at the same vertex, it can lead to degeneracy. Consider constraints $x_1 \leq 1, x_2 \leq 1, x_1 + x_2 \leq 2$. The point (1, 1) is a vertex. It is the intersection of $x_1 = 1$ and $x_2 = 1$, but also could be seen as intersection of $x_1 = 1$ and $x_1 + x_2 = 2$, or $x_2 = 1$ and $x_1 + x_2 = 2$. This multiple representation of a vertex is related to degeneracy.

In a non-degenerate case in $\mathbb{R}^2$, each vertex is an intersection of exactly two lines (active constraints). In the degenerate case, a vertex can be at the intersection of more than two lines. This allows for basis changes without moving to a different vertex.

The Simplex Algorithm as a Vertex Traversal

Movement Along Edges of the Feasible Region

The Simplex algorithm can be visualized as traversing the vertices of the feasible polyhedron. Each pivot, when it changes the basic solution, corresponds to moving from one vertex to an adjacent vertex along an edge of the feasible region.

Degeneracy: Remaining at a Vertex with Basis Change

In cases of degeneracy, a basis change might not result in moving to a new vertex. Instead, the algorithm may remain at the same vertex but with a different basis representation. Geometrically, this means that a vertex can be defined by more than the minimum number of constraints, allowing for different sets of active constraints (bases) at the same vertex.

Improving the Objective Function: The Simplex Direction

At each vertex, the Simplex algorithm chooses an edge to move along that improves the objective function. The direction of movement is determined by the entering variable and its reduced cost. The algorithm aims to move in a direction that increases (for maximization) or decreases (for minimization) the objective function value.

Minkowski’s Theorem and Optimality at a Vertex

Minkowski’s Theorem (more accurately, Krein-Milman theorem in this context, but Minkowski’s theorem on polytopes is relevant) supports the idea that for a polytope, the optimal solution is always attained at a vertex.

If a linear programming problem with a polytope feasible region has an optimal solution, then at least one optimal solution is a vertex of the polytope.

Proof. Proof. Let $P$ be a polytope, and $V_1, V_2, \ldots, V_T$ be its vertices. By Minkowski’s theorem, any point $x \in P$ can be written as a convex combination of vertices: $x = \sum_{i=1}^T \lambda_i V_i$, where $\lambda_i \geq 0$ and $\sum_{i=1}^T \lambda_i = 1$. Let $V$ be a vertex such that $c^T V \geq c^T V_i$ for all $i=1, \ldots, T$. For any $x \in P$: $c^T x = c^T \left( \sum_{i=1}^T \lambda_i V_i \right) = \sum_{i=1}^T \lambda_i (c^T V_i) \leq \sum_{i=1}^T \lambda_i (c^T V) = (c^T V) \sum_{i=1}^T \lambda_i = c^T V$ Thus, $c^T x \leq c^T V$ for all $x \in P$. Hence, $V$ is an optimal solution and is a vertex. ◻

This theorem justifies the Simplex method’s focus on vertices.

Greedy Nature of the Simplex Method and Potential Limitations

The Simplex method is a greedy algorithm. At each vertex, it chooses to move along an edge that provides an immediate improvement in the objective function. It does not look ahead to see if a temporarily worse move might lead to a better overall path.

Consider a path of vertices $A \rightarrow C_1 \rightarrow C_2 \rightarrow \ldots \rightarrow C_k$ to reach the optimal vertex $C_k$. A greedy approach might follow this long path. However, if from vertex $A$, moving to vertex $B$ (which might initially worsen the objective) allowed a direct edge to $C_k$, the path $A \rightarrow B \rightarrow C_k$ would be much shorter.

The Simplex method, being greedy, always chooses the locally best improving edge. This can sometimes lead to longer paths to the optimum compared to potentially taking a temporarily non-improving step. However, the greedy nature ensures progress at each step and avoids cycles in non-degenerate cases. In degenerate cases, cycling is possible but can be resolved with anti-cycling rules.

Conclusion

This lecture explored the geometric interpretation of the Simplex method. We established that the feasible region of a linear programming problem is a polyhedron, and in bounded cases, a polytope. Vertices of this polyhedron correspond to basic feasible solutions, and the Simplex algorithm operates by traversing these vertices along the edges of the polyhedron. The algorithm’s iterative process can be seen as a vertex-to-vertex movement, always aiming to improve the objective function value in a greedy manner. While this greedy approach is efficient in practice, it’s important to recognize its potential limitations in certain scenarios. The concept of degeneracy was also discussed in a geometric context, relating it to vertices being defined by more than the minimum number of constraints.

Further study could delve deeper into anti-cycling rules in degenerate cases and explore alternative optimization algorithms that might overcome the limitations of greedy approaches, although the Simplex method remains a highly effective and widely used algorithm for linear programming problems.

--- title: "Geometric Interpretation of the Simplex Method" 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 aims to provide an intuitive and graphical description of the Simplex method's process. Starting from a feasible but non-optimal basis, the Simplex algorithm iteratively performs pivots, exchanging columns between those entering and leaving the basis. This basis change continues until an optimal basis is reached, at which point the algorithm identifies the \"optimal solution\". It is important to note that in linear programming problems, the optimal solutions found by the Simplex method are always basic solutions, characterized by having many zero components corresponding to the off-basis variables. While non-basic optimal solutions might exist, it can be demonstrated that if an optimal solution exists, there is always an optimal solution that is a basic solution. Therefore, by focusing solely on basic solutions, we do not lose the optimality. # Geometric Interpretation of the Simplex Method ## The Simplex Algorithm's Iterative Process The Simplex algorithm starts from a feasible basis and iteratively performs pivots. Each pivot involves swapping columns, changing the basis from a non-optimal to an optimal one. This process continues until an optimal basis is found, indicating the optimal solution. ## Basic Feasible Solutions and Optimality In linear programming, the Simplex method always terminates at basic solutions. Optimal solutions determined by the Simplex are always basic solutions, meaning they contain many zeros corresponding to off-basis components. If optimal solutions exist, there's always a basic optimal solution. Focusing on basic solutions ensures we do not miss the optimum. ## Geometric Concepts ### Polyhedra: Definition as Intersection of Semispaces To understand the Simplex method geometrically, we need to introduce the concept of a polyhedron. ::: tcolorbox Given a vector $\alpha \in \mathbb{R}^n$ and a constant $\beta \in \mathbb{R}$, consider the inequality $\alpha x \leq \beta$. The set $HS(\alpha, \beta) = \{v \in \mathbb{R}^n \mid \alpha v \leq \beta \}$ is called a **semispace** in $\mathbb{R}^n$. The boundary of this semispace, $H(\alpha, \beta) = \{v \in \mathbb{R}^n \mid \alpha v = \beta \}$, is called a **hyperplane**. The vector $\alpha$ is the normal vector, perpendicular to this hyperplane. ::: In three-dimensional space, a hyperplane can be visualized as an infinitely extending sheet of paper. All points on one side of this hyperplane, including the hyperplane itself, form a semispace. In two-dimensional space (the Cartesian XY plane), a hyperplane is an infinite line. This line divides the plane, and all points on one side of the line, together with the line, constitute a semispace in $\mathbb{R}^2$. ::: tcolorbox A **polyhedron** is the intersection of a finite number of semispaces. ::: Consider a set of lines in a 2D plane, each defining a semispace. For example, lines with arrows indicating the feasible side. The intersection of all these semispaces creates a figure, like the shaded region in the transcription example. This type of figure is a polyhedron. In linear programming problems, especially in canonical and standard forms, the feasible region is always defined by a set of inequalities (and equalities which can be converted to inequalities). Thus, the feasible region of a linear programming problem is always a polyhedron. A polyhedron in two dimensions is a convex figure with straight edges, formed by consecutive line segments. Semispaces are convex sets, and their intersection is also a convex set. A polyhedron in three dimensions can be imagined as a box or any shape with flat faces. ::: tcolorbox A parallelepiped (box) is a polyhedron. Each face of the box corresponds to a semispace, and the box is defined by the intersection of these semispaces. ::: ::: tcolorbox A sphere (ball) is **not** a polyhedron. While a sphere can be described as an intersection of semispaces, it requires an infinite number of them. Imagine tangents at every point on a circle in 2D or a sphere in 3D. Each tangent defines a semispace containing the circle/sphere. However, as you move along the circumference/surface, you need infinitesimally many semispaces. ::: Polygons and polyhedra, defined by a finite number of intersecting semispaces, are \"spiky\" or \"linear\" without curvature. These shapes have points called vertices. ### Polytopes: Bounded Polyhedra ::: tcolorbox A polyhedron is **bounded** if there exists a maximum length for any vector contained within it. In other words, the entire polyhedron can be enclosed within a ball of sufficiently large radius. A bounded polyhedron is also called a **polytope**. ::: A polytope is a special type of polyhedron where vectors cannot be arbitrarily long. ::: tcolorbox The polyhedron shown in the transcription (the shaded figure) is a polytope. ::: A polyhedron can be unbounded, containing arbitrarily long vectors. ::: tcolorbox A single semispace is an unbounded polyhedron. For instance, consider only one inequality. All vectors on one side of the hyperplane are feasible solutions, and some can be arbitrarily long. Consider the non-negative orthant in $\mathbb{R}^2$ defined by $x_1 \geq 0$ and $x_2 \geq 0$. This region extends infinitely in the positive $x_1$ and $x_2$ directions and is an unbounded polyhedron, also known as a cone (right-angled cone in this case). It contains vectors of arbitrary length and cannot be contained within any ball of finite radius. ::: Polytopes are \"closed\" and do not extend to infinity in any direction. ### Dimension of a Polyhedron and Full Dimensionality The dimension of a polyhedron is an important concept. - A square on a plane (in $\mathbb{R}^2$) has dimension 2. - A line segment has dimension 1. - A point has dimension 0. - A cube (in $\mathbb{R}^3$) has dimension 3. These are examples of hypercubes. A hypercube of dimension 1 is a segment \[0, 1\]. A hypercube of dimension 2 is a square of side 1. A hypercube of dimension 3 is a cube of side 1. We can generalize this to higher dimensions. A hypercube of dimension 4 is the product of four \[0, 1\] intervals in $\mathbb{R}^4$. Intuitively, a polyhedron has dimension $k$ if it contains a $k$-dimensional hypercube (however small) but does not contain any hypercube of dimension $k+1$. A polyhedron of dimension $k$ in $\mathbb{R}^n$ is of full dimension if $k=n$. ::: tcolorbox A square is a 2-dimensional polyhedron. It contains a small square, so its dimension is at least 2. It does not contain a cube, so its dimension is 2. Even if this square is placed in $\mathbb{R}^3$, it remains 2-dimensional and is not of full dimension in $\mathbb{R}^3$. A cube in $\mathbb{R}^3$ contains small cubes, so its dimension is 3. It is of full dimension in $\mathbb{R}^3$. However, in $\mathbb{R}^4$, it is not of full dimension. ::: Consider the polyhedron in $\mathbb{R}^3$ defined by: $$\begin{aligned} x_1 + x_2 + x_3 &= 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \\ x_3 &\geq 0 \end{aligned}$$ This system includes an equation, $x_1 + x_2 + x_3 = 1$. An equation reduces the dimension. This polyhedron is a triangle in $\mathbb{R}^3$. It passes through points (1, 0, 0), (0, 1, 0), and (0, 0, 1). It is a 2-dimensional object in a 3-dimensional space. In $\mathbb{R}^n$, a hyperplane (defined by one linear equation) has dimension $n-1$. Each independent linear equation in a system reduces the dimension of the solution space by one. For the example above, $x_1 + x_2 + x_3 = 1$ defines a plane in $\mathbb{R}^3$. The additional inequalities $x_1 \geq 0, x_2 \geq 0, x_3 \geq 0$ restrict this plane to a triangular region. The dimension is reduced from 3 (of $\mathbb{R}^3$) by one due to the equation, resulting in a 2-dimensional polyhedron. If a system of inequalities has no implicit equations, i.e., for every inequality, there are solutions that strictly satisfy it, then the polyhedron is of full dimension. If some inequalities must be satisfied as equalities for all feasible solutions, those are implicit equations and reduce the dimension. ### Faces, Vertices, and Edges: Definitions and Properties Consider a polyhedron in $\mathbb{R}^3$. It has faces, edges, and vertices. ::: tcolorbox For a polyhedron $P$, an inequality $\alpha x \leq \beta$ is a **valid inequality** if it is satisfied by all points $x \in P$. ::: If we take a valid inequality $\alpha x \leq \beta$ and consider the hyperplane $H = \{x \mid \alpha x = \beta \}$. If $P \cap H \neq \emptyset$, then $P \cap H$ is a **face** of the polyhedron $P$. ::: tcolorbox A **face** of a polyhedron $P$ defined by valid inequality $\alpha x \leq \beta$ is the intersection of $P$ with the hyperplane $H = \{x \mid \alpha x = \beta \}$, provided $P \cap H \neq \emptyset$. ::: A face of a polyhedron is itself a polyhedron (or polytope if $P$ is a polytope). Faces can have dimensions less than the dimension of $P$. For a 3-dimensional polyhedron: - **Facets**: Faces of dimension 2 (dimension of $P$ - 1). Example: Triangle ABC in the example polyhedron. - **Edges**: Faces of dimension 1. Example: Line segment AB, BC, AC. - **Vertices**: Faces of dimension 0. Example: Points A, B, C. Also called extreme points. The polyhedron itself is also considered a face of itself. ### Valid Inequalities and Facets Valid inequalities define faces. Facets are particularly important. ### Redundant Constraints and Facet Defining Inequalities Not all inequalities defining a polyhedron are essential. Some are redundant. ::: tcolorbox Consider two systems defining the same polyhedron: System A: $$\begin{aligned} x_1 + x_2 &\leq 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{aligned}$$ System B: $$\begin{aligned} x_1 + x_2 &\leq 1 \\ x_1 &\leq 1 \\ x_2 &\leq 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{aligned}$$ Both systems define the same triangular region in $\mathbb{R}^2$. In System B, $x_1 \leq 1$ and $x_2 \leq 1$ are redundant constraints because if $x_1 + x_2 \leq 1$ and $x_1, x_2 \geq 0$, then $x_1 \leq 1$ and $x_2 \leq 1$ are automatically satisfied. ::: For defining a polyhedron, facet-defining inequalities are crucial and non-redundant. Two polyhedra are the same if and only if they have the same set of facets. Facet-defining inequalities are essential for describing a polyhedron minimally. ### Correspondence Between Vertices and Basic Feasible Solutions A crucial connection exists between vertices of a polyhedron and basic feasible solutions in linear programming. ::: tcolorbox Vertices of a polyhedron are in correspondence with basic feasible solutions. For every vertex of a polyhedron, there exists a basis such that the vertex is the basic feasible solution corresponding to that basis. ::: This means the Simplex method, which operates on basic feasible solutions, is geometrically moving between vertices of the feasible region (polyhedron). ### Geometric Interpretation of Degeneracy When the Simplex algorithm pivots and changes basis, geometrically, it corresponds to moving along an edge of the polyhedron. - **Non-degenerate case**: Changing basis usually means moving from one vertex to an adjacent vertex along an edge. - **Degenerate case**: If a solution is degenerate, changing the basis might not change the basic feasible solution itself. Geometrically, this means staying at the same vertex, but changing the basis representation of that vertex. Degeneracy can be geometrically interpreted as a vertex being representable as an intersection of more than the minimum number of hyperplanes. ::: tcolorbox In $\mathbb{R}^2$, a vertex is typically the intersection of two lines. If more than two lines intersect at the same vertex, it can lead to degeneracy. Consider constraints $x_1 \leq 1, x_2 \leq 1, x_1 + x_2 \leq 2$. The point (1, 1) is a vertex. It is the intersection of $x_1 = 1$ and $x_2 = 1$, but also could be seen as intersection of $x_1 = 1$ and $x_1 + x_2 = 2$, or $x_2 = 1$ and $x_1 + x_2 = 2$. This multiple representation of a vertex is related to degeneracy. ::: In a non-degenerate case in $\mathbb{R}^2$, each vertex is an intersection of exactly two lines (active constraints). In the degenerate case, a vertex can be at the intersection of more than two lines. This allows for basis changes without moving to a different vertex. # The Simplex Algorithm as a Vertex Traversal ## Movement Along Edges of the Feasible Region The Simplex algorithm can be visualized as traversing the vertices of the feasible polyhedron. Each pivot, when it changes the basic solution, corresponds to moving from one vertex to an adjacent vertex along an edge of the feasible region. ## Degeneracy: Remaining at a Vertex with Basis Change In cases of degeneracy, a basis change might not result in moving to a new vertex. Instead, the algorithm may remain at the same vertex but with a different basis representation. Geometrically, this means that a vertex can be defined by more than the minimum number of constraints, allowing for different sets of active constraints (bases) at the same vertex. ## Improving the Objective Function: The Simplex Direction At each vertex, the Simplex algorithm chooses an edge to move along that improves the objective function. The direction of movement is determined by the entering variable and its reduced cost. The algorithm aims to move in a direction that increases (for maximization) or decreases (for minimization) the objective function value. ## Minkowski's Theorem and Optimality at a Vertex Minkowski's Theorem (more accurately, Krein-Milman theorem in this context, but Minkowski's theorem on polytopes is relevant) supports the idea that for a polytope, the optimal solution is always attained at a vertex. ::: tcolorbox If a linear programming problem with a polytope feasible region has an optimal solution, then at least one optimal solution is a vertex of the polytope. ::: ::: proof *Proof.* Let $P$ be a polytope, and $V_1, V_2, \ldots, V_T$ be its vertices. By Minkowski's theorem, any point $x \in P$ can be written as a convex combination of vertices: $x = \sum_{i=1}^T \lambda_i V_i$, where $\lambda_i \geq 0$ and $\sum_{i=1}^T \lambda_i = 1$. Let $V$ be a vertex such that $c^T V \geq c^T V_i$ for all $i=1, \ldots, T$. For any $x \in P$: $c^T x = c^T \left( \sum_{i=1}^T \lambda_i V_i \right) = \sum_{i=1}^T \lambda_i (c^T V_i) \leq \sum_{i=1}^T \lambda_i (c^T V) = (c^T V) \sum_{i=1}^T \lambda_i = c^T V$ Thus, $c^T x \leq c^T V$ for all $x \in P$. Hence, $V$ is an optimal solution and is a vertex. ◻ ::: This theorem justifies the Simplex method's focus on vertices. ## Greedy Nature of the Simplex Method and Potential Limitations The Simplex method is a greedy algorithm. At each vertex, it chooses to move along an edge that provides an immediate improvement in the objective function. It does not look ahead to see if a temporarily worse move might lead to a better overall path. ::: tcolorbox Consider a path of vertices $A \rightarrow C_1 \rightarrow C_2 \rightarrow \ldots \rightarrow C_k$ to reach the optimal vertex $C_k$. A greedy approach might follow this long path. However, if from vertex $A$, moving to vertex $B$ (which might initially worsen the objective) allowed a direct edge to $C_k$, the path $A \rightarrow B \rightarrow C_k$ would be much shorter. The Simplex method, being greedy, always chooses the locally best improving edge. This can sometimes lead to longer paths to the optimum compared to potentially taking a temporarily non-improving step. However, the greedy nature ensures progress at each step and avoids cycles in non-degenerate cases. In degenerate cases, cycling is possible but can be resolved with anti-cycling rules. ::: # Conclusion This lecture explored the geometric interpretation of the Simplex method. We established that the feasible region of a linear programming problem is a polyhedron, and in bounded cases, a polytope. Vertices of this polyhedron correspond to basic feasible solutions, and the Simplex algorithm operates by traversing these vertices along the edges of the polyhedron. The algorithm's iterative process can be seen as a vertex-to-vertex movement, always aiming to improve the objective function value in a greedy manner. While this greedy approach is efficient in practice, it's important to recognize its potential limitations in certain scenarios. The concept of degeneracy was also discussed in a geometric context, relating it to vertices being defined by more than the minimum number of constraints. Further study could delve deeper into anti-cycling rules in degenerate cases and explore alternative optimization algorithms that might overcome the limitations of greedy approaches, although the Simplex method remains a highly effective and widely used algorithm for linear programming problems.