(282g) Restriction-Based Algorithms and Kkt-Based Bounding Procedures for Semi-Infinite Programming

Semi-infinite programs (SIPs) are mathematical programs with a finite number of variables and an infinite number of constraints. This is commonly expressed by a parameterized constraint, which has to hold for all possible values of a parameter from a set of infinite cardinality. One solution approach for SIPs is a finite discretization of this parameter set, which results in a relaxation of the original program [2]. The relaxed program is a nonlinear program (NLP) and can be solved by existing solvers to provide a lower bound to the solution of the SIP. Given an adaptive discretization scheme, a series of these lower bounding NLPs can be solved such that the lower bound converges to the solution of the SIP in the limit. This basic algorithm, however, cannot guarantee feasible iterates in finite time. Recently, several methods were proposed that solve SIPs to a feasible ε-optimal point in finite time [1,3,4,6].

In the first part of this presentation, we analyze two discretization-based bounding algorithms [4,6] that introduce (implicitly or explicitly) a restriction of the semi-infinite constraint to achieve feasible iterates. We show that for certain problems, these algorithms tend to generate an overpopulated discretization and therefore require many iterations to converge. Motivated by the comparison, we derive a hybrid method relying on modified procedures from both algorithms to generate an adaptive restriction of the semi-infinite constraint and thereby avoid overpopulation. The new method performs better on problems where overpopulation would be a problem while remaining competitive on established SIP benchmark problems [7].

In the second part of this presentation, we present numerical experiments concerning the efficacy of alternative bounding problems proposed in [5]. The bounding problems used in [4] are augmented with the KKT conditions of the lower-level problem of the SIP to achieve tighter bounds. The resulting problems are mathematical programs with equilibrium constraints (MPECs). A direct solution approach and a mixed integer reformulation are compared to the original bounding problems. Especially for upper bounding, the KKT-based approach promises tighter bounds, resulting in fewer iterations and reduced overall computational effort.

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

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

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

[4] A. Mitsos. Global optimization of semi-infinite programs via restriction of the right-hand side. Optimization, 60(10-11):1291–1308, 2011.

[5] A. Mitsos, P. Lemonidis, C. K. Lee, and P. I. Barton. Relaxation-based bounds for semi-infinite programs. SIAM Journal on Optimization, 19(1):77–113, 2008.

[6] A. Tsoukalas and B. Rustem. A feasible point adaptation of the Blankenship and Falk algorithm for semi-infinite programming. Optimization Letters, 5(1):705-716, 2011.

[7] G. A. Watson. Numerical experiments with globally convergent methods for semi-infinite programming problems. Lecture Notes in Economics and Mathematical Systems, 215(1):193-205, 1983.