We study decentralized minimization of an average of strongly convex, smooth local objectives over an intersection of agent-private closed convex sets, where each agent knows only its own objective and its own set and agents communicate over a gossip network. We show that the complexity is controlled by a single geometric scalar, which we call … Read more
Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\bar{\chi}_A^*$. Their work builds on Vavasis and Ye’s (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\bar{\chi}_A$. Monteiro-Tsuchiya (2003) defined the optimal condition number … Read more
This work considers the design of first-order convex optimization algorithms and convergence proofs. In particular, we consider nonsmooth Lipschitz and smooth problems accessed through a subgradient or gradient oracle, respectively. For the general class of fixed-step first-order methods, prior work on Performance Estimation Problems (PEPs) has shown that structured, tight convergence proofs typically exist. Under … Read more
One goal of multiobjective optimization is to approximate the nondominated set in the image space. One widely used approximation concept is that of enclosures. These are unions of closed boxes that cover the nondominated set. The bounds of these boxes form the lower and upper bound sets of the enclosure. The quality of an enclosure … Read more
We systematically investigate the potentials of improving the lower bound obtained with a linear relaxation of the Quadratic Unconstrained Binary Optimization problem by integrating curvature information from an accompanying quadratic convex underestimator via gradient inequalities. On the one hand, we exemplify to which extent this hybrid approach may provide a lower bound that is strictly … Read more
We study mixed-integer quadratic optimization (MIQO) problems with indicator variables. We propose a unified framework, based on decision diagrams, that serves both to solve the associated optimization problems and to construct ideal conic quadratic extended formulations of the closure of the convex hull of the underlying mixed-integer set. The construction applies to arbitrary quadratics and … Read more
Georeferenced synthetic populations are essential inputs for agent-based simulations in epidemiology, transportation, and urban planning, yet existing methods for spatial allocation of households to residences lack formal optimality guarantees. We present a two-stage mathematical framework for generating such populations from publicly available census data. The first stage combines Iterative Proportional Fitting (IPF) with a mixed-integer … Read more
We consider optimization applications with unknown parameters where the decision maker believes that the optimal value of the nominal problem—the optimization problem they would have solved if the true parameters were known—is unlikely to be large. This belief derives from information that humans have that is not captured in datasets, obtained from domain knowledge and … Read more
Path planning in environments containing obstacles has numerous practical applications. The problem is challenging because it is inherently nonlinear and nonconvex. Consequently, a variety of techniques have been developed to address this problem, among which machine learning and optimal control (or optimization) have emerged as two prominent approaches. In general, machine learning methods do not … Read more
This paper studies the Sinkhorn distributionally robust hypothesis testing (SDRHT) problem, seeking a robust detector against least-favorable distributions in Sinkhorn discrepancy-based ambiguity sets centered at the empirical distributions. Existing approaches solve this problem by solving large-scale conic programs, which are not scalable. To overcome this, we propose a generative framework that learns least-favorable distributions and … Read more