Lower level duality and the global solution of generalized semi-infinite programs

Abstract

The reformulation of generalized semi-infinite programs (GSIP) to simpler problems is considered. These reformulations are achieved under the assumption that a duality property holds for the lower level program (LLP). Lagrangian duality is used in the general case to establish the relationship between the GSIP and a related semi-infinite program (SIP). Practical aspects of this reformulation, including how to bound the duality multipliers, are also considered. This SIP reformulation result is then combined with recent advances for the global, feasible solution of SIP to develop a global, feasible point method for the solution of GSIP. Reformulations to finite nonlinear programs, and the practical aspects of solving these reformulations globally, are also discussed. When the LLP is a linear program or second-order cone program, specific duality results can be used that lead to stronger results. Numerical examples demonstrate that the global solution of GSIP is computationally practical via the solution of these duality-based reformulations.

Keywords:

• Semi-infinite programs
• global optimization
• duality

AMS Subject Classifications:

• 90C26
• 90C34
• 90C46
• 65K05

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was funded by Novartis Pharmaceuticals as part of the Novartis-MIT Center for Continuous Manufacturing.