🔎Convex Geometry Unit 5 – Polyhedral Theory and Farkas' Lemma

Key Concepts and Definitions

• Polyhedral theory studies the geometric properties and combinatorial structure of polyhedra, which are three-dimensional shapes with flat faces, straight edges, and sharp corners
  • Includes convex polyhedra (all points on a line segment connecting any two points of the polyhedron lie within the polyhedron) and non-convex polyhedra
• Farkas' lemma is a fundamental result in linear algebra and optimization that provides a characterization of the solvability of a system of linear inequalities
• Convex geometry is the study of convex sets, which are subsets of a vector space where the line segment connecting any two points in the set is entirely contained within the set
• Linear programming is a mathematical optimization technique that involves maximizing or minimizing a linear objective function subject to linear equality and inequality constraints
  • Polyhedral theory and Farkas' lemma play a crucial role in the development and analysis of linear programming algorithms
• Duality is a central concept in polyhedral theory and linear programming, relating the properties of a primal problem to its dual problem
  • The dual of a linear programming problem provides valuable insights into the structure and solvability of the original problem
• Vertex enumeration is the process of listing all the vertices (extreme points) of a polyhedron, which is a fundamental problem in polyhedral theory
• Face lattice of a polyhedron is a partially ordered set that captures the hierarchical structure of the faces (vertices, edges, facets) of the polyhedron

Historical Context and Development

• Polyhedral theory has its roots in ancient Greek geometry, with the study of regular polyhedra (Platonic solids) by mathematicians like Euclid and Archimedes
• Leonhard Euler's work on the relationship between the number of vertices, edges, and faces of a polyhedron (Euler's polyhedron formula) in the 18th century laid the foundation for modern polyhedral theory
• The development of linear programming in the mid-20th century, particularly the simplex method by George Dantzig, brought renewed interest in polyhedral theory
  • The simplex method relies on the polyhedral structure of the feasible region to find optimal solutions
• Farkas' lemma, named after the Hungarian mathematician Gyula Farkas, was first published in 1902 and has since become a fundamental tool in linear algebra and optimization
• The work of mathematicians like Victor Klee, Branko Grünbaum, and Alexander Schrijver in the latter half of the 20th century significantly advanced the field of polyhedral theory and its applications
• Recent developments in polyhedral theory include the study of polytopes (higher-dimensional analogues of polyhedra), combinatorial optimization, and the connections between polyhedral theory and algebraic geometry

Fundamental Principles of Polyhedral Theory

• Polyhedra can be represented as the intersection of a finite number of halfspaces, each defined by a linear inequality
  • This representation is known as the H-representation (halfspace representation) of a polyhedron
• Alternatively, polyhedra can be described as the convex hull of a finite set of points, which is the smallest convex set containing all the points
  • This representation is called the V-representation (vertex representation) of a polyhedron
• The Minkowski-Weyl theorem states that every polyhedron has both an H-representation and a V-representation, and these representations are equivalent
• The Euler-Poincaré formula relates the number of vertices (V), edges (E), and faces (F) of a convex polyhedron: $V - E + F = 2$
  • This formula holds for any convex polyhedron, regardless of its specific shape or symmetry
• The face lattice of a polyhedron captures the incidence relations between its faces, with the partial order defined by set inclusion
  • The face lattice is a graded poset, with the rank of a face being its dimension
• Polarity is a fundamental concept in polyhedral theory that associates a dual polyhedron to any given polyhedron
  • The polar of a polyhedron is obtained by taking the dual of each inequality in its H-representation
• The Farkas-Minkowski-Weyl theorem combines Farkas' lemma and the Minkowski-Weyl theorem to provide a complete characterization of the solvability of a system of linear inequalities

Farkas' Lemma: Statement and Significance

• Farkas' lemma states that for a matrix $A$ and a vector $b$, exactly one of the following two statements is true:
  1. There exists a vector $x$ such that $Ax = b$ and $x \geq 0$ (component-wise)
  2. There exists a vector $y$ such that $A^Ty \geq 0$ and $b^Ty < 0$
• The lemma provides a certificate of infeasibility for a system of linear inequalities
  • If the second statement holds, then the system $Ax = b, x \geq 0$ has no solution
• Farkas' lemma is equivalent to the strong duality theorem in linear programming, which states that if a primal problem has an optimal solution, then its dual problem also has an optimal solution with the same objective value
• The lemma has numerous applications in optimization, game theory, and economics
  • It is used to derive optimality conditions and duality results in linear and nonlinear programming
• Farkas' lemma can be generalized to infinite-dimensional spaces and convex cones, leading to the concept of Farkas-Minkowski-Weyl theorem
• The lemma is closely related to the separating hyperplane theorem, which states that any two disjoint convex sets can be separated by a hyperplane
  • Farkas' lemma can be seen as a special case of the separating hyperplane theorem for polyhedral convex sets

Geometric Interpretations and Visualizations

• Polyhedra can be visualized as three-dimensional shapes with flat faces, straight edges, and sharp corners
  • Examples include cubes, pyramids, prisms, and more complex shapes like the icosahedron and dodecahedron
• The H-representation of a polyhedron can be interpreted as the intersection of halfspaces, each defined by a linear inequality
  • Geometrically, each inequality represents a halfspace, and the polyhedron is the region where all the halfspaces intersect
• The V-representation of a polyhedron can be seen as the convex hull of a finite set of points
  • Visually, the convex hull is the smallest convex shape that encloses all the given points, forming the vertices of the polyhedron
• Farkas' lemma has a geometric interpretation in terms of the feasibility of a system of linear inequalities
  • If the first statement of the lemma holds, the system is feasible, and the solution set forms a convex polyhedral region
  • If the second statement holds, the system is infeasible, and there exists a separating hyperplane that strictly separates the solution set from the origin
• The face lattice of a polyhedron can be visualized as a Hasse diagram, with nodes representing the faces and edges representing the incidence relations
  • The Hasse diagram provides a hierarchical representation of the polyhedron's structure, from vertices to edges, facets, and the full-dimensional face
• Polarity can be visualized as a geometric duality between a polyhedron and its polar
  • The polar of a polyhedron is obtained by taking the dual of each inequality in its H-representation, resulting in a new polyhedron with interchanged roles of vertices and facets

Applications in Linear Programming

• Polyhedral theory and Farkas' lemma are fundamental tools in the development and analysis of linear programming algorithms
• The feasible region of a linear programming problem is a convex polyhedron, defined by the intersection of linear equality and inequality constraints
  • The optimal solution of a linear program always lies at a vertex of the feasible polyhedron
• The simplex method, a popular algorithm for solving linear programs, exploits the polyhedral structure of the feasible region
  • The method moves from vertex to vertex along the edges of the polyhedron until an optimal solution is found
• Farkas' lemma is used to derive the strong duality theorem in linear programming, which relates the optimal values of the primal and dual problems
  • The lemma provides a certificate of infeasibility for the primal or dual problem, helping to identify unbounded or infeasible cases
• Polyhedral theory is also used in the study of integer programming, where the variables are restricted to integer values
  • The convex hull of the integer feasible solutions forms a polyhedron, and polyhedral techniques can be used to develop efficient algorithms for solving integer programs
• Sensitivity analysis in linear programming relies on the polyhedral structure of the feasible region
  • Changes in the objective function coefficients or the right-hand side of the constraints can be analyzed using the vertex representation of the polyhedron
• Polyhedral theory is applied in the development of cutting plane methods, which iteratively refine the feasible region by adding new linear inequalities (cuts) to improve the approximation of the integer hull

Proofs and Theoretical Foundations

• The proofs of many fundamental results in polyhedral theory rely on techniques from linear algebra, convex analysis, and combinatorics
• The Minkowski-Weyl theorem, which establishes the equivalence of the H-representation and V-representation of a polyhedron, can be proved using the separating hyperplane theorem and the concept of polarity
  • The proof involves showing that every polyhedron can be expressed as the convex hull of its vertices and the intersection of a finite number of halfspaces
• Farkas' lemma can be proved using the separating hyperplane theorem and the properties of convex cones
  • The proof proceeds by considering the convex cone generated by the columns of the matrix $A$ and the vector $b$, and applying the separating hyperplane theorem to derive the two alternative statements
• The strong duality theorem in linear programming can be derived from Farkas' lemma by considering the primal and dual problems as systems of linear inequalities
  • The proof involves applying Farkas' lemma to the primal and dual systems and using the complementary slackness conditions to establish the relationship between the optimal solutions
• The Euler-Poincaré formula for convex polyhedra can be proved using induction on the number of faces and the properties of the face lattice
  • The proof relies on the combinatorial structure of the polyhedron and the incidence relations between its faces
• The duality between a polyhedron and its polar can be established using the properties of the dual cone and the polar of a convex set
  • The proof involves showing that the polar of a polyhedron is itself a polyhedron, and the polar of the polar is the original polyhedron
• Many results in polyhedral theory can be generalized to higher dimensions and infinite-dimensional spaces using techniques from functional analysis and convex analysis
  • The proofs often involve extending the concepts of separation, duality, and polarity to more abstract settings

Related Theorems and Extensions

• The Farkas-Minkowski-Weyl theorem is a generalization of Farkas' lemma and the Minkowski-Weyl theorem to convex cones
  • It states that a convex cone is polyhedral if and only if it is finitely generated and can be expressed as the intersection of a finite number of halfspaces
• Carathéodory's theorem is a fundamental result in convex geometry that relates the convex hull of a set to its subsets
  • It states that if a point lies in the convex hull of a set, then it can be expressed as a convex combination of at most $d+1$ points from the set, where $d$ is the dimension of the space
• Helly's theorem is another important result in convex geometry that deals with the intersection of convex sets
  • It states that if a collection of convex sets in $\mathbb{R}^d$ has the property that any $d+1$ of them have a common point, then all the sets in the collection have a common point
• The Krein-Milman theorem is a fundamental result in functional analysis that relates a compact convex set to its extreme points
  • It states that a compact convex set in a locally convex topological vector space is the closed convex hull of its extreme points
• The Choquet-Meyer theorem is an extension of the Krein-Milman theorem to non-compact convex sets
  • It states that every point in a convex set can be represented as an integral of extreme points with respect to a probability measure
• The Lovász-Schrijver hierarchy and the Sherali-Adams hierarchy are methods for approximating the convex hull of the integer feasible solutions in integer programming
  • These hierarchies generate a sequence of increasingly tighter polyhedral relaxations of the integer hull, providing a systematic approach to solving integer programs
• The cutting plane method and the branch-and-bound method are algorithmic techniques in integer programming that rely on polyhedral theory
  • Cutting plane methods iteratively refine the feasible region by adding valid inequalities, while branch-and-bound methods recursively partition the feasible region into smaller subproblems