Strong duality and sensitivity analysis in semi-infinite linear programming

• 成果类型: Article
• 署名作者: Basu, Amitabh; Martin, Kipp; Ryan, Christopher Thomas
• 署名单位: Johns Hopkins University; University of Chicago
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1018-2
• 发表日期: 2017
• 页码: 451-485
• 关键词: semi-infinite programs; gaps

摘要

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. We use the extension of the Fourier-Motzkin elimination procedure to semi-infinite linear systems to understand these linear functionals.