Geometry of Linear Optimization: Polyhedra, Vertices, and Basic Feasible Solutions

Central Problem of Linear Optimization

Formulation and Standard Form

Linear optimization (also known as linear programming) seeks to maximize or minimize a linear objective function subject to linear constraints. The central problem is typically expressed as:

• General Form: $\text{maximize} \quad c^T x$ $\text{subject to} \quad Ax \leq b$ $x \geq 0$

• Standard Form: $\text{minimize} \quad c^T x$ $\text{subject to} \quad Ax = b$ $x \geq 0$

• Characteristics:

  • Objective function is linear in $x$.

  • Constraints are linear equalities or inequalities.

  • Feasible region is defined by intersection of half-spaces.

Transformations

Linear programs can be transformed between forms by introducing slack variables or converting inequalities to equalities.

• Example Transformation: $a^T x \leq b \implies a^T x + s = b, \quad s \geq 0$

Geometric Insights and Examples

Feasible Region and Optimal Solutions

The feasible region of a linear program is a convex polyhedron, defined by the intersection of half-spaces. The optimal solution, if it exists, is found at a vertex (corner point) of the polyhedron.

• Example: $\text{maximize} \quad x_1 + x_2$ $\text{subject to} \quad x_1 \leq 2, \; x_2 \leq 2, \; x_1 + x_2 \leq 3, \; x_1, x_2 \geq 0$ Graphical Solution: The feasible region is a polygon in $\mathbb{R}^2$; the optimal value is at a vertex.

Polyhedra

Definitions

• Hyperplane: The set $\{x \mid a^T x = b\}$ is called a hyperplane.

• Halfspace: The set $\{x \mid a^T x \leq b\}$ is called a halfspace.

• Polyhedron: The intersection of finitely many halfspaces is a polyhedron.

Properties

• Polyhedra are convex sets.

• Vertices (corners) are points where constraints intersect.

Corners and Extreme Points

Extreme Points

An extreme point of a polyhedron $P = \{x \mid Ax \leq b\}$ is a point that cannot be written as a convex combination of other points in $P$.

• Vertex: A vertex is an intersection of $n$ constraints in $n$-dimensional space.

• Basic Feasible Solution (BFS): A solution to $Ax = b, x \geq 0$ where $n$ linearly independent constraints are active.

Degeneracy

• If more than $n$ constraints are active at a point, the solution is degenerate.

Equivalence of Definitions

Extreme points, vertices, and basic feasible solutions are equivalent in the context of polyhedra defined by linear constraints.

• Theorem: For $P = \{x \mid Ax \leq b\}$, a point $x$ is a BFS if and only if it is an extreme point.

Construction of Basic Feasible Solutions

Procedure

• Select $n$ linearly independent constraints.

• Solve the system $A_B x_B = b$ for the basic variables $x_B$.

• Set non-basic variables to zero.

Example

• Given $A$ and $b$, select columns corresponding to basic variables, solve for $x_B$.

Existence and Optimality of BFS

Existence

• If the feasible region is non-empty and bounded, there exists at least one BFS.

Optimality

• If an optimal solution exists, it is attained at a BFS (vertex of the polyhedron).

Conceptual Algorithm

Basic Steps

• Start at a corner (BFS).

• Visit neighboring corners that improve the objective function.

• Repeat until no improvement is possible (optimal solution found).

Summary Table: Key Concepts in Linear Optimization Geometry

Term	Definition	Role in Optimization
Polyhedron	Intersection of halfspaces	Feasible region
Vertex	Intersection of $n$ constraints	Potential optimal solution
Extreme Point	Cannot be written as convex combination of other points	Equivalent to BFS
Basic Feasible Solution (BFS)	$n$ linearly independent active constraints	Corner point, candidate for optimality
Degeneracy	More than $n$ active constraints	Multiple BFS at same point

Additional info: These notes are foundational for understanding the geometry of linear programming, which is closely related to calculus topics such as optimization, but do not directly cover calculus chapters listed above. However, the mathematical structure and geometric intuition are useful for advanced calculus and applied mathematics students.