Online Semi-Infinite Linear Programming via Nonnegative Function Approximation

We study online semi-infinite linear programming, a sequential resource-allocation problem in which the decision space is finite dimensional but the constraints are indexed by a large, possibly infinite, set. This setting captures online allocation problems with continuously indexed safety, robustness, coverage, or moment constraints. Classical online linear-programming algorithms maintain one dual variable per constraint, and their regret guarantees typically scale with the number of constraints; this dependence becomes prohibitive in semi-infinite regimes. We propose a nonnegative function-approximation approach that represents the dual measure using \(q\) nonnegative basis functions. This yields a tractable projected problem whose regret bounds depend on the basis dimension \(q\), rather than on the number of original constraints. We develop first-order primal–dual algorithms for stochastic and random-permutation input models. Under stochastic arrivals, our algorithms achieve \(O(qT)\) regret, together with sublinear projected constraint violation. Under random permutation arrivals, we obtain a \(\widetilde O(qT)\)-type regret bound. We further give an accelerate-then-refine algorithm that improves the stochastic regret to \(O(q\log T)\) under additional conditions. Experiments on large-scale instances show that the proposed basis-based methods remain stable as the number of constraints grows, while standard online LP methods degrade substantially.