181 citations · 620 across the 171 of their papers we have counts for
12 papers · 2 filters
The exact worst-case asymptotic rate of Nesterov acceleration for strongly convex optimization
Sebastian Pokutta, Bartolomeo Stellato
We study Nesterov's accelerated gradient method with its standard constant parameters for smooth strongly convex optimization. We characterize the exact worst-case asymptotic facto…
Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
Nico Pelleriti, Maryam Shiran, David Martínez-Rubio +2
Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate sta…
Discrete eigenvalue optimization from entropic smoothing and first-order methods
Deborah Hendrych, Mathieu Besançon, Sebastian Pokutta
We study the maximization of the minimum eigenvalue under combinatorial and integrality constraints. We propose a new approach based on branch-and-bound combines entropic smoothing…
Joint-Range Inequalities for Nonconvex QCQPs
Liding Xu, Sebastian Pokutta
We study cutting planes for nonconvex quadratically constrained quadratic programs (QCQPs) through a project-then-lift approach inspired by mixed-integer rounding (MIR) inequalitie…
Random-Subspace Frank--Wolfe over Strongly Convex Sets
Pierre-Louis Poirion, Sebastian Pokutta, Akiko Takeda
Frank--Wolfe methods avoid projections, but over curved feasible regions the full-space linear minimization oracle (LMO) can itself become the computational bottleneck. We introduc…
Abs-Smooth Frank-Wolfe Method: Primal-Dual Analysis, Heavy Ball Momentum, and Inexact Oracles
Sri Harshitha Tadinada, Sebastian Pokutta, Andrea Walther
We study projection-free optimization for convex objectives that satisfy abs-smoothness, a structural property that captures many non-smooth yet piecewise smooth functions arising,…
Curvature-Dependent Lower Bounds for Frank-Wolfe
Jannis Halbey, Christophe Roux, Sebastian Pokutta
The Frank-Wolfe algorithm achieves a convergence rate of for smooth convex optimization over compact convex domains, accelerating to when bo…
CHAP: A Hybrid GPU-CPU Heuristic for MIP
Gennesaret Kharistio Tjusila, Alexander Hoen, Nils-Christian Kempke +5
We present CHAP (Coordinating Heuristics Across Platforms) a GPU-CPU-hybrid primal heuristic framework for mixed-integer programming. CHAP adopts a portfolio approach where it coor…
Out-of-the-Box Global Optimization for Packing Problems: New Models and Improved Solutions
Timo Berthold, Dominik Kamp, Gioni Mexi +2
Recent LLM-driven discoveries have renewed interest in geometric packing problems. In this paper, we study several classes of such packing problems through the lens of modern globa…
Frank-Wolfe Beyond 1/t Convergence
Sebastian Pokutta
We consider smooth convex minimization over compact convex sets, i.e., with the (vanilla) Frank-Wolfe algorithm. Well-known lower bounds establish a worst-cas…
Lower Bounds for Frank-Wolfe on Strongly Convex Sets
Jannis Halbey, Daniel Deza, Max Zimmer +3
We present a constructive lower bound of for Frank-Wolfe (FW) when both the objective and the constraint set are smooth and strongly convex, showing that…
Global Optimization for Combinatorial Geometry Problems Revisited in the Era of LLMs
Timo Berthold, Dominik Kamp, Gioni Mexi +2
Recent progress in LLM-driven algorithm discovery, exemplified by DeepMind's AlphaEvolve, has produced new best-known solutions for a range of hard geometric and combinatorial prob…