A geometric simplex method in infinite-dimensional spaces

Robert L. Smith Christopher Thomas Ryan · 2026

Read A geometric simplex method in infinite-dimensional spaces by Robert L. Smith Christopher Thomas Ryan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-06948.txt.

Introduction

Smith and Ryan extend the shape-based simplex method over linear programs in locally convex vector spaces, with rules for reaching best value. Work stayed in Hilbert spaces or special cases. Their breadth comes from skipping algebra pivot by column steps, which needed stronger space rules to link basic feasible answers with extreme point structure. They show their meaning of shapes captures tuning over the Hilbert cube, an object in endless spaces known for traits. All shapes under their meaning have exposed extreme points joined by edge paths.

Catalog record

CREATORRobert L. Smith Christopher Thomas Ryan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76442
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.06948

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A geometric simplex method in infinite-dimensional spaces Robert L. Smith Christopher Thomas Ryan Abstract We expand the basic geometric elements of the simplex method to linear programs in locally convex topological vector spaces and provide conditions under which the method converges in value to optimality. This setting generalizes many previous investigations of the simplex method, which are restricted to Hilbert spaces or otherwise specially structured instances. Our generality is obtained by avoiding the “algebraic” machinery of pivoting via column operations, which has required stronger topological conditions in establishing a connection between basic feasible solutions and extreme point structure. We show that our definition of polytopes captures optimization over the Hilbert cube, a quintessential object in infinite-dimensional spaces known for its surprisingly complicated properties. Moreover, all polytopes (under our definition) have exposed extreme points connected by edge paths. 1 Introduction Infinite-dimensional linear programming is both classical and cutting-edge. Some of the very first linear programs studied were stated over infinite-dimensional spaces [ 33 , 27 ] , and there has been recent growing interest in several applied areas of mathematics that concern infinite-dimensional linear programs [ 15 , 29 , 24 , 19 , 38 , 25 , 12 , 30 ] . Since at least [ 6 ] , researchers have been interested in extensions of the simplex method to understand the structure and optimality of linear programs in topological vector spaces. Anderson and Nash [ 6 ] were interested in generalizing the algebraic structure underlying the simplex method, including notions of column bases, basic feasible solutions, and reduced costs. This program was championed over the years by several research groups (for example, [ 35 , 16 , 42 , 22 , 40 , 41 , 44 , 4 , 5 ] ), including recent advancements [ 19 , 41 ] . In this literature, the focus is largely on finding special types of linear programs where these algebraic concepts prove meaningful and amenable to analysis. In general, the dictionary between extreme points and basic feasible solutions that is foundational to the simplex method in finite dimensions (see Chapter 2 of [ 9 ] ) breaks down in topological vector spaces (as detailed at length in [ 6 ] ). This paper pursues a different program. We are interested in generalizing the classical geometric understanding of the simplex method: start with an extreme point and iteratively follow the edges to adjacent extreme points until you reach an extreme point from which no adjacent edge direction improves the objective. We do not concern ourselves with finding an underlying algebraic description of extreme points. Despite alleviating ourselves of this concern, this new path is still fraught with complexities. It is not immediately obvious how to (i) define “edges”, (ii) ensure that moving along the edges yields another extreme point, and (iii) that the process makes guaranteed progress toward optimality. We tackle these and other issues in this paper. Our main result is to produce a geometric simplex algorithm with the following properties. Starting with an extreme point, it can identify a set of adjacent extreme points and define edges on which to reach them. We show ( theorem 4 ) that this algorithm converges to optimal value (that is, the objective values of successive iterates converge to the optimal value of the program). When a unique optimal solution exists, the iterates of the algorithm converge to the optimal solution ( corollary 1 ). Though the goal seems simple, a carefully constructed set of assumptions was required (see 1 – 9 throughout the paper). These assumptions will be motivated and justified as they are presented and we will not attempt to recapitulate that careful development here. A summarizing discussion of the assumptions can be found in section 6 . Our algorithm has important limitations. We do not guarantee that each iteration can be executed in finite time, let alone that an optimal solution can be found in finite time. However, it ensures that the simplex method has the necessary geometric structure of extreme points, edges, and improving directions so that the algorithm does not get “caught” in locally optimal solutions or be unable to determine where to go next. The assumptions all drive toward validating the basic mechanism of “moving from extreme point to extreme point while improving the objective” under minimal restrictiveness. Our goal is more conceptual than providing an implementable algorithm. We are interested in the general geometric structure of a compact convex set described by linear inequalities that make it amenable to a simplex method. Our assumptions are broad enough to capture most of the well-known examples of when a simplex method ‘‘works’’ in the sense we put forward here, including the (corrected) 1 1 1 We say “corrected” conditions because we found an error in the development of [ 19 ] . We propose a fix to recover the results of that paper in appendix B . conditions of [ 19 ] that define a broad class of countably-infinite linear programs (including many instances of previous investigations). Our approach allows us to move beyond the sequence space setting of [ 19 ] and related papers, opening the door to problems defined over non-sequence spaces, including function and measure spaces. However, we show that a very classical object — the Hilbert cube — fails the conditions of [ 19 ] but nonetheless satisfies our assumptions (see examples 2 , 8 , 7 , 4 , 5 , 6 and 3 ). This demonstrates that our simplex method is broader than that explored in the previous literature. The fact that the Hilbert cube is problematic for previous methods is not too surprising, despite its simplicity, as it is a notoriously challenging example to understand and analyze [ 7 ] . Our assumptions provide a novel definition of what we will call a polytope for general topological vector spaces: a polytope is an object where a geometric simplex method can be used to optimize a linear functional over it, potentially requiring infinitely many iterations, under our assumptions. Why might there be interest in such a definition? The familiar definitions of a polytope do not extend to general topological spaces as we might hope. In finite-dimensional space, there are two alternative definitions of a polytope: (i) the convex hull of finitely many points or (ii) the bounded intersection of finitely many halfspaces. Both of these conceptions are flawed in infinite-dimensional space. For (i), the convex hull of finitely many points is only finite-dimensional, a trivial restriction in infinite-dimensional spaces. Indeed, several papers have successively executed simplex-like algorithms on infinite-dimensional objects [ 40 , 22 , 38 , 19 ] . The problem with (ii) is arguably even more severe: in infinite-dimensional space, the intersection of finitely many halfspaces is never bounded. Other authors have proposed alternative definitions for polytopes, while there is generally no consensus on how they should be defined. In our search of the literature, we found at least twelve alternative definitions of “polytope” in general spaces (and make no claims of exhaustion) [ 8 , 28 , 32 , 1 , 34 , 3 , 23 , 36 , 31 , 11 , 13 ] . For a comprehensive overview

Read the complete text