Discrete eigenvalue optimization from entropic smoothing and first-order methods
Abstract
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 of the minimum eigenvalue function and Frank-Wolfe methods over concave relaxations of the constraints, thereby exploiting combinatorial structure through linear optimization oracles. We establish approximation and convergence guarantees, including for truncated gradients computed from partial eigendecompositions, and introduce rank- and eigenvalue-based pruning and duality-based variable fixing. We evaluate the method on E-optimal experimental design and maximum algebraic connectivity problems and compare it with SCIP-SDP. The results show that our approach is particularly effective for large-dimensional instances and problems with additional combinatorial structure, whereas SCIP-SDP performs better on moderately sized instances with simpler constraints.
Related
- Computing Multi-Slot First-Price Pacing Equilibria at Scale via Entropic Smoothing
- Inertial Primal-Dual Dynamics Methods Featuring Implicit Hessian-Driven Damping for Convex Optimization Problems in Continuous and Discrete Time
- Inverse eigenvalue problem for discrete three-diagonal Schroedinger operator and the continuum limit in Tikhonov regularization approach
- Statistical Rates for Entropic Optimal Transport in the Discrete to SubGaussian Regime
- An entropic barrier to equilibration in the discrete nonlinear Schrödinger equation: Rigorous bounds for the microcanonical Brownian motion
BibTeX
@misc{hendrych2026discrete,
title = {{Discrete eigenvalue optimization from entropic smoothing and first-order methods}},
author = {Deborah Hendrych and Mathieu Besançon and Sebastian Pokutta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.27024},
eprint = {2608.27024},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27024},
}
RIS
TY - UNPB
TI - Discrete eigenvalue optimization from entropic smoothing and first-order methods
AU - Deborah Hendrych
AU - Mathieu Besançon
AU - Sebastian Pokutta
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2608.27024
UR - https://arxiv.org/abs/2608.27024
AB - 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 of the minimum eigenvalue function and Frank-Wolfe methods over concave relaxations of the constraints, thereby exploiting combinatorial structure through linear optimization oracles. We establish approximation and convergence guarantees, including for truncated gradients computed from partial eigendecompositions, and introduce rank- and eigenvalue-based pruning and duality-based variable fixing. We evaluate the method on E-optimal experimental design and maximum algebraic connectivity problems and compare it with SCIP-SDP. The results show that our approach is particularly effective for large-dimensional instances and problems with additional combinatorial structure, whereas SCIP-SDP performs better on moderately sized instances with simpler constraints.
ER -