Main — algopt

The Research Group in Algorithms and Optimization focuses on developing new approaches in mathematical optimization and algorithm design to tackle computational questions arising in a wide range of areas, with a particular focus on problems at the interface of economics and computation. We combine methods from discrete and continuous optimization, computer science, game theory, and economics to develop efficient and exact approximation algorithms, and to understand the limits of computability.

Our group was established in August 2024 as part of the Transdisciplinary Research Area (TRA) Modelling at the University of Bonn, and is lead by the Hertz Professor László Végh.

We are connected to the Research Institute for Discrete Mathematics, the Institute of Computer Science, and the Department of Economics.

People

Events

Teaching

Events

25.04: "Optimization and Algorithmic Game Theory", Inaugural Symposium for Prof. László Végh, Hertz Chair for Algorithms and Optimization

Date: 25.04.2025

Location: Endenicher Allee 60, Center for Mathematics, Lipschitz-Hall

Program and Registration: https://www.uni-bonn.de/en/research-and-teaching/research-profile/transdisciplinary-research-areas/tra-1-modelling/symposium25

24.02: Group Seminar: "Near-Optimality and Strong Polynomiality of the Trust Region Predictor-Corrector Interior Point Method" (Haoyuan Ma)

Date: 24.02.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Haoyuan Ma

We investigate a variant of the trust region interior point method (TR-IPM) which was originally given by Lan, Monteiro and Tsuchiya (SIAM J. Optim. 2009). We show that the iteration complexity of this algorithm is essentially optimal in the L2-neighbourhood of the central path. Namely, the iteration complexity of the TR-IPM is upper bounded by the minimum number of segments of any piecewise linear curve traversing in a close L2-neighbourhood of the central path. This strengthens the previous bounds that were in terms of the Dikin-Todd-Stewart conditional number of the constraint matrix.

Lan, Monteiro and Tsuchiya only gave a weakly polynomial algorithm for solving the trust region problem, and left it as an open question to develop a strongly polynomial algorithm. We resolve this question by presenting a new strongly polynomial algorithm that solves a parametric minimum norm problem to a very high accuracy. As a result, each iteration of our TR-IPM can be implemented in strongly polynomial time. Our algorithm for the parametric problem relies on approximately computing the singular value decomposition of an associated matrix. These singular values enable us to locate the optimal parameter value in a narrow interval, where Newton's method exhibits quadratic convergence.

This is based on joint work with Daniel Dadush, Bento Natura, and László Végh.

27.01: Group Seminar: "Characterizing and testing principal minor equivalence" (Roshan Raj)

Date: 27.01.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Roshan Raj

Two matrices are said to be principal minor equivalent if they have equal corresponding principal minors of all orders. We give a characterization of principal minor equivalence and a deterministic polynomial time algorithm to check if two given matrices are principal minor equivalent. Earlier such results were known for certain special cases like symmetric matrices, skew-symmetric matrices with {0, 1, -1}-entries, and matrices with no cuts (i.e., for any non-trivial partition of the indices, the top right block or the bottom left block must have rank more than 1). As an immediate application, we get an algorithm to check if the determinantal point processes corresponding to two given kernel matrices (not necessarily symmetric) are the same. As another application, we give a deterministic polynomial-time test to check equality of two multivariate polynomials, each computed by a symbolic determinant with a rank 1 constraint on coefficient matrices.