Strong duality and sensitivity analysis in semi-infinite linear programming
From MaRDI portal
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.
Recommendations
- Strong duality and dual pricing properties in semi-infinite linear programming: a non-Fourier-Motzkin elimination approach
- Duality for inexact semi-infinite linear programming
- On duality theory of convex semi-infinite programming
- On duality in semi-infinite programming and existence theorems for linear inequalities
- Robust linear semi-infinite programming duality under uncertainty
Cites work
- scientific article; zbMATH DE number 3650305 (Why is no real title available?)
- scientific article; zbMATH DE number 4029251 (Why is no real title available?)
- scientific article; zbMATH DE number 3525695 (Why is no real title available?)
- scientific article; zbMATH DE number 1070896 (Why is no real title available?)
- A pathological semi-infinite program verifying Karlovitz's conjecture
- An Infinite Linear Program with a Duality Gap
- Duality gaps in semi-infinite linear programming—an approximation problem
- Duality in semi-infinite programs and some works of Haar and Carathéodory
- Extending the mixed algebraic-analysis Fourier-Motzkin elimination method for classifying linear semi-infinite programmes
- In a semi-infinite program only a countable subset of the constraints is essential
- Infinite dimensional analysis. A hitchhiker's guide.
- Linear optimization and approximation. An introduction to the theoretical analysis and numerical treatment of semi-infinite programs. Transl. from the German
- Motzkin decomposition of closed convex sets
- On Representations of Semi-Infinite Programs which Have No Duality Gaps
- On the sufficiency of finite support duals in semi-infinite linear programming
- On the use of purely finitely additive multipliers in mathematical programming
- Post-Optimal Analysis in Linear Semi-Infinite Optimization
- Projection: A unified approach to semi-infinite linear programs and duality in convex programming
- Semi-Infinite Programming: Theory, Methods, and Applications
- Semi-infinite programming, duality, discretization and optimality conditions†
- Sensitivity analysis in linear semi-infinite programming via partitions
- Sensitivity analysis in linear semi-infinite programming: perturbing cost and right-hand-side coefficients
- The Slater Conundrum: Duality and Pricing in Infinite-Dimensional Optimization
Cited in
(8)- scientific article; zbMATH DE number 5036103 (Why is no real title available?)
- Projection: A unified approach to semi-infinite linear programs and duality in convex programming
- scientific article; zbMATH DE number 4030685 (Why is no real title available?)
- On the sufficiency of finite support duals in semi-infinite linear programming
- Recent contributions to linear semi-infinite optimization
- Strong duality for standard convex programs
- Strong duality and dual pricing properties in semi-infinite linear programming: a non-Fourier-Motzkin elimination approach
- Recent contributions to linear semi-infinite optimization: an update
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)
