We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We … Read more
For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher’s augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that … Read more
Block-coordinate algorithms are recognized to furnish efficient iterative schemes for addressing large-scale problems, especially when the computation of full derivatives entails substantial memory requirements and computational efforts. In this paper, we propose a randomized block proximal gradient algorithm for minimizing the sum of a smooth function and a separable proper lower semicontinuous function, both possibly … Read more
Many operational decisions reshape the populations they act on: routing policies alter traffic, care interventions affect health outcomes, and public programs change participation. We study online control of such decision-dependent populations when the primitive state is a distribution, actions determine both current reward and the next distribution, and the reward and transition laws are unknown. … Read more
Decision diagrams (DDs) have become a powerful tool for discrete optimization, supporting a wide range of algorithms that span cut-generation procedures, decomposition methods, and specialized branch-and-bound searches. Despite this growth, their adoption remains limited, partly because most existing DD code is tailored to a specific algorithm or application and is therefore hard to reuse. We … Read more
The cosine measure of a set of vectors in \(\mathbb{R}^n\) measures how well the set covers all directions in \(\mathbb{R}^n\). It identifies the direction furthest, in angle, from the set. It is used in the convergence theory of various optimization algorithms, but also highlights interesting geometric properties of sets. For example, the cosine measure of … Read more
We propose a minimal-gradient subspace method for unconstrained optimization. For strictly convex quadratics, conjugate gradient can be interpreted as exact minimization over a two-dimensional affine subspace. We use the same reduced subspace in the nonlinear case, but compute a trial step by minimizing a local model of the next gradient norm. For SPD quadratics, every … Read more
Many operational decisions require solving a linear program whose cost vector is unknown at decision time and must be predicted from contextual information. Because prediction and decision are only weakly aligned, the emerging integrated learning and optimization (ILO) paradigm trains the predictor through the downstream problem, judging a prediction by the decision it induces. However, … Read more
We present AutoOPT, a domain-specific harness for end-to-end automation of optimization research. AutoOPT organizes the discovery of optimal first-order methods into four stages: numerical design through the BnB-PEP methodology; symbolic discovery of the analytic description and a convergence proof through frontier large language models (LLMs); formal verification in the Lean 4 proof assistant; and human … Read more