Strong duality and sensitivity analysis in semi-infinite linear programming (Q507336)

This article is a valuable contribution to linear programing at its interface with both (i) semi-infinite programming, and its relations to (ii) bi-level programming, game theory and numerical analysis. This work is both theoretically rigorous and practically relevant, and based on it, more future investigations can be raised and real-word applications conducted, e.g., via robust optimization and optimal control, in engineering, economics, earth and human sciences. Linear programs in finite-dimensions fulfill strong duality (SD) and enjoy the ``dual pricing'' (DP) property. Provided a sufficiently small perturbation of the vector at the right-hand-side, this DP secures that there is a dual solution which is correctly ``pricing'' the perturbation by a computation of the precise change of the value of the optimal objective function. Those properties can fail in semi-infinite linear programming (SILP), where the space of constraint vectors is infinite dimensional. Unlike the case of finite-dimensions, in SILP the space of constraint vectors permits a modeling choice. For a sufficiently restricted vector space the authors show that both SD and DP always hold, however, restricting the perturbations to this space. The main purpose of the paper is to augment this restricted space to the largest possible space of constraints where SD and DP are satisfied. Once for a given constraint space SD or DP fail, then these conditions default for all constraint spaces which are larger. The authors give sufficient conditions for when SD and DP are fulfilled in an augmented space of constraints. Their results necessitate the usage of linear functionals which are singular or purely finitely additive and, therefore, cannot be representable through finite support vectors. The authors employ the extension of the Fourier-Motzkin elimination procedure to SILP programs to understand those linear functionals. This excellent paper is well-structured, deep, well exemplified, and well written. The seven sections of this work are these: 1. Introduction, 2. Preliminaries, 3. Fourier-Motzkin elimination and its connection to duality, 4. Strong duality and dual pricing for a restricted constraint space, 5. Extending strong duality and dual pricing to larger constraint spaces, 6. Conclusion, and 7. Appendix. Future refinements and generalizations in analytic theory and numerical methods may be expected in the scientific community, prepared and inspired by this paper on SILP. These might be made in terms of generalized semi-infinite (linear) optimization, nonlinear semi-infinite programming, robust optimization, infinite programming, optimal control and game theory. Such future advances could foster progress in science and engineering, economics and finance, bio- and neuroscience, medicine, environmental, geo- and earth-sciences, social as well as developmental sciences.