(132b) Deterministic Global Optimization of Semi-Infinite Programs

A deterministic algorithm is proposed for the global solution of SIPs without any convexity/concavity assumptions. The algorithm employs an upper bound based on a restriction of the right-hand-side of the constraint and a discretization of the parameter set and a lower bound based on discretization of the parameter set. Finite termination is proved and the advantages of the proposed algorithm over existing algorithms are demonstrated by numerical examples.

Semi-infinite programs are optimization problems with a finite number of variables and an infinite number of constraints. More precisely, a finite number of constraints is parameterized via continuous parameters and the constraints must be satisfied for all values of these parameters. Many problems in engineering and the sciences can be cast as SIPs, e.g., concerning design centering [1] or model reduction [2]. SIPs are very challenging to solve, even in relatively restrictive cases, such as linear SIPs. In the case that the constraint is nonconcave in the parameters, it is particularly difficult to solve SIPs. It is even challenging to find a feasible point or establish the feasibility of a point, because, at least in principle, these operations involve global optimization of the nonconvex lower-level program, i.e., maximization of the constraint with respect to the parameters. The first algorithms for SIPs with nonconvex lower-level programs have been recently proposed. The first idea was based on an interval extension reformulation [2,3]. Subsequently, ideas based on convex relaxation were proposed [1,5].

Herein, we propose a much simpler alternative via restriction of the right-hand side and discretization of the parameter set. The proposed algorithm consists of an upper and a lower bounding problem. The overall strategy is similar to the strategy by Blankenship and Falk [6], i.e., a successively finer discretization of the parameter set based on the solutions to the lower level program. However, unlike [6], the finite termination with a truly feasible point is guaranteed with the proposed algorithm. A proof of convergence is given along with a prototype implementation in GAMS. 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. Moreover, the algorithm naturally allows the global optimization of SIPs with algorithms embedded via the development in [7].

[1] C. A. Floudas and O. Stein, The adaptive convexification algorithm: A feasible point method for semi-infinite programming, SIAM Journal on Optimization, 18 (2007), p 1187-1208.

[2] B. Bhattacharjee, D. A. Schwer, P. I. Barton and W. H. Green Jr, Optimally-reduced kinetic models: Reaction elimination in large-scale kinetic mechanisms, Combustion and Flame, 135 (2003), p 191-208.

[3] B. Bhattacharjee, W. H. Green Jr. and P. I. Barton, Interval methods for semi-infinite programs, Computational Optimization and Applications, 30 (2005), p 63-93.

[4] B. Bhattacharjee, P. Lemonidis, W. H. Green Jr. and P. I. Barton, Global solution of semi-infinite programs, Mathematical Programming, Series B, 103 (2005), p 283-307.

[5] A. Mitsos, P. Lemonidis and P. I. Barton, Global solution of bilevel programs with a nonconvex inner program, Journal of Global Optimization, 42 (2008), p 475-513.

[6] J. W. Blankenship and J. E. Falk, Infinitely constrained optimization problems, Journal of Optimization Theory and Applications, 19 (1976), p. 261-281.

[7] A. Mitsos, B. Chachuat, and P. I. Barton, McCormick-based relaxations of algorithms, SIAM Journal on Optimization, 20 (2009), p. 573-601.