Link: : https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
Speaker: Harold Nieuwboer (UvA & Ruhr University Bochum)
Title: Interior-point methods on manifolds
Date: Thursday 30 March, 4pm CET
Abstract:
Interior-point methods offer a highly versatile framework for convex optimization that is effective in theory and practice. A key notion in their theory is that of a self-concordant barrier. We give a suitable generalization of self-concordance to Riemannian manifolds and show that it gives the same structural results and guarantees as in the Euclidean setting, in particular local quadratic convergence of Newton's method.
We then analyze a short-step path-following method for optimizing compatible objectives over a convex domain for which one has a self-concordant barrier, and obtain the standard complexity guarantees
as in the Euclidean setting. We show that on the positive-definite matrices and other symmetric spaces, the squared distance to a point is a self-concordant function. Our work is motivated by recent progress on
scaling problems and non-commutative optimization, and we show that these fit into our framework, yielding algorithms with state-of-the-art complexity guarantees. Furthermore, we show how to apply our methods to
computing geometric medians on spaces with constant negative curvature.
Joint work with Michael Walter. Based on https://arxiv.org/abs/2303.04771.
Speaker: Lucy Verberk (TU/e)
Title: Stabilization of capacitated matching games
Date: Thursday 30 March, 4:30pm CET
Abstract:
An edge-weighted, vertex-capacitated graph G is called stable if the value of a maximum-weight capacity-matching equals the value of a maximum-weight fractional capacity-matching. Stable graphs play a key
role in characterizing the existence of stable solutions for popular combinatorial games that involve the structure of matchings in graphs, such as network bargaining games and cooperative matching games.
The vertex-stabilizer problem asks to compute a minimum number of players to block (i.e., vertices of G to remove) in order to ensure stability for such games. The problem has been shown to be solvable in
polynomial-time, for unit-capacity graphs. This stays true also if we impose the restriction that the set of players to block must not intersect with a given specified maximum matching of G.
We investigate these algorithmic problems in the more general setting of arbitrary capacities. We show that the vertex-stabilizer problem with the additional restriction of avoiding a given maximum matching remains
polynomial-time solvable. Differently, without this restriction, the vertex-stabilizer problem becomes NP-hard and even hard to approximate, in contrast to the unit-capacity case.
Finally, in unit-capacity graphs there is an equivalence between the stability of a graph, existence of a stable solution for network bargaining games, and existence of a stable solution for cooperative matching games. We show that this equivalence does not extend to the capacitated case.
Joint work with Matthew Gerstbrein and Laura Sanità . Based on
https://arxiv.org/abs/2211.12179.
The meeting will take place here:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
