Global optimization of semi-infinite programs via restriction of the right-hand side

An algorithm is proposed for the global solution of semi-infinite programs (SIPs) without convexity assumptions. It terminates finitely with a guaranteed feasible point, and a certificate of ϵ f -optimality. The only assumptions are continuity of the functions and existence of an ϵ f -optimal SIP-Slater point. The lower and upper bounds are obtained by the solution of two nonconvex nonlinear programs (NLP) each, thus shifting the nonconvexity to the global NLP solver. The main contribution of this article is a new procedure for the generation of feasible points. These are obtained by a restriction of the constraints right-hand side by ϵ g > 0 and a successively finer discretization of the parameter set. A suitable decreasing sequence of ϵ g → 0 leads to convergence of the generated upper bound. The converging lower bound is obtained by successively tighter discretization, following the principle of Blankenship and Falk [Infinitely constrained optimization problems, J. Optim. Theory Appl. 19 (1976), pp. 261–281]. A proof of convergence is given along with a prototype implementation in general algebraic modelling system. The algorithm is extended to problems with multiple constraints as well as mixed-integer problems. Literature and new problems are solved numerically. The algorithm is extremely simple to implement, but nevertheless very efficient compared to existing methods for nonconvex lower level programs.