A Comprehensive Review of Theoretical Foundations and Algorithmic Advances in Linear Semi-Infinite Programming (LSIP): Classical Theory and Recent Developments
TL;DR
Simplex-like methods remain theoretically important and practically useful under appropriate regularity and separation assumptions and provide a foundation for modern hybrid approaches such as interior-point/simplex methods, smoothing techniques, and learning-based strategies.
Abstract
Linear Semi-Infinite Programming (LSIP) problems constitute an important and challenging class of constrained optimization problems in which, unlike classical linear programming, the number of constraints may be infinite while the number of decision variables remains finite. This distinctive structure has found extensive applications in approximation theory, filter design, optimal control, production planning with continuous demand, location problems, and, more recently, robust optimization and machine learning. This paper aims to provide a systematic, comprehensive, and up-to-date review of two fundamental aspects of LSIP: the theoretical foundations - including the geometric analysis of feasible sets, the classification of semi-infinite systems, and the duality-gap phenomenon - and simplex-like methods as a major family of algorithms for the numerical solution of these problems. In the theoretical part, basic concepts including the cone of feasible directions D(F,x), the active-constraints cone A(x), extreme points, and faces are introduced. The classification of semi-infinite systems based on the LOP (Locally Polyhedral) and LFM (Locally Farkas-Minkowski) properties is then discussed in detail. Under the LOP condition, the feasible set behaves locally as a polyhedral set and the active-constraints cone has the corresponding closed polyhedral structure. Global finiteness of the entire extreme-point set is not inferred from LOP alone; finite-termination results require the additional hypotheses stated in the relevant theorem. Furthermore, the phenomenon of a positive duality gap, v(P) > v(D), which is one of the principal distinctions between LSIP and classical finite linear programming, is analyzed through a standard example, together with conditions guaranteeing strong duality. In the algorithmic part, three principal methods are presented hierarchically: (1) a Purification Algorithm for transforming an arbitrary feasible dual point into an initial extreme point; (2) a Dual Simplex-Like Algorithm, a direct extension of Dantzig's revised simplex method to LSIP, which moves through the dual space using a deepest-cut strategy; and (3) a Multiple Exchange Algorithm, which solves an auxiliary linear programming problem so that several constraints can be exchanged simultaneously, thereby mitigating the slow convergence of single-exchange methods. For each algorithm, convergence conditions, including LOP and analyticity assumptions, are discussed, and standard numerical examples are used to illustrate performance and challenges. A comparative table summarizes computational cost, convergence behavior, and complexity. The review concludes that simplex-like methods, supported by the geometric theory of LSIP, remain theoretically important and practically useful under appropriate regularity and separation assumptions and provide a foundation for modern hybrid approaches such as interior-point/simplex methods, smoothing techniques, and learning-based strategies. Their links with distributionally robust optimization and stochastic programming also open promising directions for future research.