Back to Search
Start Over
CONVERGENT ALGORITHMS FOR A CLASS OF CONVEX SEMI-INFINITE PROGRAMS.
- Source :
-
SIAM Journal on Optimization . 2022, Vol. 32 Issue 4, p2493-2526. 34p. - Publication Year :
- 2022
-
Abstract
- We focus on convex semi-infinite programs with an infinite number of quadratically parametrized constraints. In our setting, the lower-level problem, i.e., the problem of finding the constraint that is the most violated by a given point, is not necessarily convex. We propose a new convergent approach to solve these semi-infinite programs. Based on the Lagrangian dual of the lower-level problem, we derive a convex and tractable restriction of the considered semi-infinite programming problem. We state sufficient conditions for the optimality of this restriction. If these conditions are not met, the restriction is enlarged through an inner-outer approximation algorithm, and its value converges to the value of the original semi-infinite problem. This new algorithmic approach is compared with the classical cutting plane algorithm. We also propose a new rate of convergence of the cutting plane algorithm, directly related to the iteration index, derived when the objective function is strongly convex, and under a strict feasibility assumption. We successfully test the two methods on two applications: the constrained quadratic regression and a zero-sum game with cubic payoff. Our results are compared to those obtained using the approach proposed in [A. Mitsos, Optimization, 60 (2011), pp. 1291-1308], as well as using the classical relaxation approach based on the KKT conditions of the lower-level problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 32
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 161593484
- Full Text :
- https://doi.org/10.1137/21M1431047