Recursive Outer Projection for Linear Programming

We present the Recursive Outer Projection (PER) algorithm for linear programming, based on recursive dimensionality reduction with deterministic constraint selection guided by the objective function. Unlike Seidel's algorithm (1991), which selects constraints randomly and has an expected complexity of O(d!·m), PER utilizes the gradient direction of the objective function to identify the optimal face of the polyhedron. We prove the Cone Lemma, which establishes a necessary condition for non-redundant inactive constraints to compete with active ones. We construct a minimal counterexample in R³ refuting the conjecture that the most violated face is always optimal, and we demonstrate a probabilistic result guaranteeing that greedy selection works with probability tending to 1 for random LPs. A C implementation with __float128 and OpenMP achieves 100% accuracy in dimensions 3–10 with sub-second execution times. Author Note: The foundational geometric intuition for this algorithmic approach was conceived independently by J.V.G.O. This repository serves as the official timestamped record and supplementary material for the theoretical formalization.