Interval Methods for Semi-Infinite Programs

A new approach for the numerical solution of smooth, nonlinear semi-infinite programs whose feasible set contains a nonempty interior is presented. Interval analysis methods are used to construct finite nonlinear, or mixed-integer nonlinear, reformulations of the original semi-infinite program under relatively mild assumptions on the problem structure. In certain cases the finite reformulation is exact and can be solved directly for the global minimum of the semi-infinite program (SIP). In the general case, this reformulation is over-constrained relative to the SIP, such that solving it yields a guaranteed feasible upper bound to the SIP solution. This upper bound can then be refined using a subdivision procedure which is shown to converge to the true SIP solution with finite ε-optimality. In particular, the method is shown to converge for SIPs which do not satisfy regularity assumptions required by reduction-based methods, and for which certain points in the feasible set are subject to an infinite number of active constraints. Numerical results are presented for a number of problems in the SIP literature. The solutions obtained are compared to those identified by reduction-based methods, the relative performances of the nonlinear and mixed-integer nonlinear formulations are studied, and the use of different inclusion functions in the finite reformulation is investigated.

Authors and Affiliations

1. Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA, 02139, USA

   Binita Bhattacharjee, William H. Green (Jr.) & Paul I. Barton

Corresponding author

Correspondence to Paul I. Barton.

Reprints and permissions