In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We present a formulation of the QMSTP as a mixed-integer semidefinite program exploiting the algebraic connectivity of a graph. Based on this formulation, we derive a doubly nonnegative relaxation … Read more
We introduce a novel time-varying step-size for the classical projected subgradient method, offering optimal ergodic convergence. Importantly, this approach does not depend on the Lipschitz assumption of the objective function, thereby broadening the convergence result of projected subgradient method to non-Lipschitz case. ArticleDownload View PDF
Follow-The-Regularized-Leader (FTRL) algorithms often enjoy optimal regret for adversarial as well as stochastic bandit problems and allow for a streamlined analysis. However, FTRL algorithms require the solution of an optimization problem in every iteration and are thus computationally challenging. In contrast, Follow-The-Perturbed-Leader (FTPL) algorithms achieve computational efficiency by perturbing the estimates of the rewards of … Read more
Convexification techniques have gained increasing interest over the past decades. In this work, we apply a recently developed convexification technique for fractional programs by He, Liu and Tawarmalani (2024) to the problem of determining the edge expansion of a graph. Computing the edge expansion of a graph is a well-known, difficult combinatorial problem that seeks … Read more
This paper develops a new parameter-free restarted method, namely RPF-SFISTA, and a new parameter-free aggressive regularization method, namely A-REG, for solving strongly convex and convex composite optimization problems, respectively. RPF-SFISTA has the major advantage that it requires no knowledge of both the strong convexity parameter of the entire composite objective and the Lipschitz constant of … Read more
The restarted primal-dual hybrid gradient method (rPDHG) has recently emerged as an important tool for solving large-scale linear programs (LPs). For LPs with unique optima, we present an iteration bound of \(O\left(\kappa\Phi\cdot\ln\left(\frac{\kappa\Phi\|w^*\|}{\varepsilon}\right)\right)\), where \(\varepsilon\) is the target tolerance, \(\kappa\) is the standard matrix condition number, \(\|w^*\|\) is the norm of the optimal solution, and \(\Phi\) … Read more
In recent years, the transition to clean bus fleets has accelerated. Although this transition might bring environmental and economic benefits, it requires a long-term strategic plan due to the large investment costs involved. This paper proposes a multi-stage stochastic program to optimize strategic plans for the clean bus fleet transition that explicitly considers the uncertainty … Read more
Log-det semidefinite programming (SDP) problems are optimization problems that often arise from Gaussian graphic models. A log-det SDP problem with an l1-norm term has been examined in many methods, and the dual spectral projected gradient (DSPG) method by Nakagaki et al.~in 2020 is designed to efficiently solve the dual problem of the log-det SDP by … Read more
Abstract Nonprofit Organizations (NPOs) rely on volunteers to support community needs but struggle with making strategic volunteer-to-task assignments to enable volunteer satisfaction, and completion of complex tasks. Creation of volunteer groups and their assignment to NPO tasks can help achieve these goals by providing volunteers with opportunity for networking, collaboration, and peer learning. However, strategically … Read more
We study an auction design problem where a seller aims to sell a single item to multiple bidders with independent private values. The seller knows only an upper bound on these values and does not know their distribution. The objective is to devise a deterministic auction mechanism effective across a broad set of distributions. We … Read more