(433d) Tighter Lower Bounds for Semi-Infinite Programming Using Parametric Sensitivity Theory

Semi-infinite programs (SIPs) are mathematical optimization problems with finitely many decision variables and infinitely many constraints (typically parametrized using a finite-dimensional parameter). They can be used to model several problems in science and engineering such as Chebyshev approximation, design centering, and robust optimization [1-3]. Most numerical methods for SIPs either make restrictive assumptions on the formulation, or only guarantee convergence to local solutions [1, 2]. Global optimization of SIPs can be challenging even when all of the functions are linear in the decision variables because verifying feasibility of a candidate solution may itself require the global solution (over the parameters) of a lower-level problem [3].

Several papers in the last two decades address the global minimization of SIPs [3-8]. Most of these approaches rely on the adaptive discretization method of Blankenship and Falk [9] to guarantee convergence of lower bounds. While this approach can determine good lower bounds in relatively few iterations, it may require an excessive number of discretization points in the parameter space before the lower bounds converge. Furthermore, the Blankenship and Falk approach does not make use of sensitivities of the solution to the lower-level problem [3]. State-of-the-art approaches for determining guaranteed feasible solutions to SIPs [6-8] also rely on the adaptive discretization method in [9].

We propose a new discretization-based lower bounding method for SIPs that can mitigate slow convergence of the Blankenship and Falk algorithm. The main idea is to populate the discretization of the parameter space with parameter values that yield the highest lower bound rather than with values that correspond to the largest violation of the semi-infinite constraint at incumbent solutions. This problem of choosing the optimal discretization points can be formulated as a max-min problem, where the outer-maximization chooses the discretization points and the inner minimization solves the lower bounding problem for a fixed discretization. Crucially, we do not need to solve this max-min problem to global optimality to obtain a valid discretization. This is important because solving this max-min problem may be as hard as solving the original SIP. We argue that local solutions to this max-min problem may be sufficient to obtain good-quality discretizations of the parameter space. We use results from parametric sensitivity theory [10] within first-order methods to efficiently solve this max-min problem to local optimality. We also demonstrate how our lower bounding method can be adapted to consider sensitivities of the solution to the lower-level problem and explore extensions to generalized semi-infinite programs. Numerical experiments on the SIP test set in [11] demonstrate that our new lower bounding approach can significantly reduce the number of iterations for the lower bound to converge compared to the approach in [9]. Finally, we also explore efficient local optimization-based upper bounding methods for SIP that do not explicitly discretize the parameter space and illustrate their potential on test instances.

1. Hettich, R., and Kortanek, K. O. (1993). Semi-infinite programming: theory, methods, and applications. SIAM review, 35(3), 380-429.
2. Vázquez, F. G., Rückmann, J. J., Stein, O., and Still, G. (2008). Generalized semi-infinite programming: a tutorial. Journal of computational and applied mathematics, 217(2), 394-419.
3. Djelassi, H., Mitsos, A., and Stein, O. (2021). Recent advances in nonconvex semi-infinite programming: Applications and algorithms. EURO Journal on Computational Optimization, 9, 100006.
4. Bhattacharjee, B., Lemonidis, P., Green Jr, W. H., and Barton, P. I. (2005). Global solution of semi-infinite programs. Mathematical Programming, 103(2), 283-307.
5. Floudas, C. A., and Stein, O. (2008). The adaptive convexification algorithm: a feasible point method for semi-infinite programming. SIAM Journal on Optimization, 18(4), 1187-1208.
6. Mitsos, A. (2011). Global optimization of semi-infinite programs via restriction of the right-hand side. Optimization, 60(10-11), 1291-1308.
7. Tsoukalas, A., and Rustem, B. (2011). A feasible point adaptation of the Blankenship and Falk algorithm for semi-infinite programming. Optimization Letters, 5(4), 705-716.
8. Djelassi, H., and Mitsos, A. (2017). A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs. Journal of Global Optimization, 68(2), 227-253.
9. Blankenship, J. W., and Falk, J. E. (1976). Infinitely constrained optimization problems. Journal of Optimization Theory and Applications, 19(2), 261-281.
10. Still, G. (2018). Lectures on parametric optimization: An introduction. Optimization Online.
11. Mitsos, A. (2009). Test set of semi-infinite programs. Technical Report, Massachusetts Institute of Technology.