Strong duality and sensitivity analysis in semi-infinite linear programming

DOI10.1007/S10107-016-1018-2MaRDI QIDQ507336zbMATH OpenOpenAlexFDO

Authors Amitabh Basu, Christopher Thomas Ryan, Kipp Martin

Publication date 3 February 2017

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.07531

duality semi-infinite linear programming sensitivity analysis

Sensitivity, stability, parametric optimization (90C31) Semi-infinite programming (90C34) Optimality conditions and duality in mathematical programming (90C46)

Abstract: Finite-dimensional linear programs satisfy strong duality (SD) and have the "dual pricing" (DP) property. The (DP) property ensures that, given a sufficiently small perturbation of the right-hand-side vector, there exists a dual solution that correctly "prices" the perturbation by computing the exact change in the optimal objective function value. These properties may fail in semi-infinite linear programming where the constraint vector space is infinite dimensional. Unlike the finite-dimensional case, in semi-infinite linear programs the constraint vector space is a modeling choice. We show that, for a sufficiently restricted vector space, both (SD) and (DP) always hold, at the cost of restricting the perturbations to that space. The main goal of the paper is to extend this restricted space to the largest possible constraint space where (SD) and (DP) hold. Once (SD) or (DP) fail for a given constraint space, then these conditions fail for all larger constraint spaces. We give sufficient conditions for when (SD) and (DP) hold in an extended constraint space. Our results require the use of linear functionals that are singular or purely finitely additive and thus not representable as finite support vectors. The key to understanding these linear functionals is the extension of the Fourier-Motzkin elimination procedure to semi-infinite linear programs.

Review text

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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Strong duality and sensitivity analysis in semi-infinite linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507336)