Mathematisches Kolloquium am 11.07.2023
EINLADUNG
Es spricht
Herr Dr. Markus Gabl
(Karlsruher Institut für Technologie, Stochastische Optimierung am IOR)
Zum Thema: „Concave Tents: A new tool for optimizing nonlinear convex functions over nonconvex sets“
Abstract:
Optimizing a nonlinear, convex function over nonconvex sets is challenging since solving convex relaxations where the nonconvex set is approximated by its convex hull my produce substantial relaxation gaps and infeasible solutions, which have to be "rounded" to a feasible solution, often with uncontrollable losses in performance. For this reason the aforementio-ned convex hulls are especially useful if the objective function is linear or even concave. We propose the notion of concave tents, which are concave overestimators of the convex objec-tive function that agree with the objective function on the feasible set. We derive ways to construct these concave tents under very mild assumptions as the optimal value function of conic optimization problems. Hence, evaluating our concave tents requires solving a conic problem. Interestingly, we can find super-derivatives by solving the conic dual problem, so that differentiation is of the same complexity as evaluation. For feasible sets over the boolean vectors we construct these concave tents in the original space of variables. For general feasible sets we propose a double lifting strategy, where the original optimization problem is lifted into a higher dimensional space in which the concave tent can be constructed just as easily as in the boolean case. The construction of the concave tents as well as the double lifting strategy exploit copositive optimization techniques so that our exposition establishes a connection between copositive optimization and nonlinear convex optimization and expands the applicability of the copo-sitive optimization paradigm substantially. Preliminary numerical experiments show that these concave tents can be useful e.g. in global optimization where an infeasible solution is to be "rounded" to a feasible one.
Dienstag, 11.07.2023, 15:00 Uhr, Curie-Hörsaal
(Kaffee 16:30 Uhr im Raum C 325)
Alle Interessierten sind herzlich eingeladen!