Vortrag: On the dualization of the inner problems of Semi-Infinite programs (Martina Cerulli, ESSEC Business School of Paris)

Im Rahmen des Kolloquiums des Graduiertenkollegs Algorithmic Optimization findet am

Montag, dem 28. November 2022
16:00 Uhr c.t.
Hörsaal 9

folgender Vortrag statt:

On the dualization of the inner problems of Semi-Infinite programs

Martina Cerulli, ESSEC Business School of Paris

In this talk, we will discuss a solution approach for Semi-Infinite programs (SIPs) based on the dualization of the inner problem, i.e., the problem of finding the constraint that is the most violated by a given point. After a brief introduction to SIPs and the classical solution techniques for these optimization programs, we will consider two practical problems that can be modeled as SIPs: the aircraft conflict resolution and the collapsed k-core problem. Then, we will present the results of the paper “Convergent algorithms for a class of convex semi-infinite programs” by M. Cerulli, A. Oustry, C. D’Ambrosio, L. Liberti, accepted for publication on SIAM Journal on Optimization. In this paper, we focus on convex SIPs with an infinite number of quadratically parametrized constraints, not necessarily convex w.r.t. the parameter. A new convergent approach to solve these SIPs is proposed, leveraging the dualization technique. Based on the Lagrangian dual of the inner problem, a convex and tractable restriction of the considered SIP is derived. 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 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.