Extending the mixed algebraic-analysis Fourier–Motzkin elimination method for classifying linear semi-infinite programmes

Abstract

Motivated by a recent Basu–Martin–Ryan paper, we obtain a reduced primal-dual pair of a linear semi-infinite programming problem by applying an amended Fourier–Motzkin elimination method to the linear semi-infinite inequality system. The reduced primal-dual pair is equivalent to the original one in terms of consistency, optimal values and asymptotic consistency. Working with this reduced pair and reformulating a linear semi-infinite programme as a linear programme over a convex cone, we reproduce all the theorems that lead to the full eleven possible duality state classification theory. Establishing classification results with the Fourier–Motzkin method means that the two classification theorems for linear semi-infinite programming, 1969 and 1974, have been proved by new and exciting methods. We also show in this paper that the approach to study linear semi-infinite programming using Fourier–Motzkin elimination is not purely algebraic, it is mixed algebraic-analysis.

Keywords:

• semi-infinite and conic programming
• duality results and classification theory
• extended Fourier–Motzkin method

Notes

No potential conflict of interest was reported by the authors.

1 A paper that enhances a quick and efficient overview of the topic and its history for a finite number of linear inequalities is Williams [13]. However, quoting Williams for the finite case, circa 1986, ‘no efficient method has yet been devised for removing all the redundant inequalities generated’.

2 The strong duality defined here is different from the one in [1]. However, we believe that the definition given here is widely accepted in the related literature.

3 Quoting [13] for the finite case, ‘Fourier’s method (and its dual) is computationally impractical for anything but small models.’