-
作者：Ghadiri, Mehrdad; Santiago, Richard; Shepherd, Bruce
作者单位：Massachusetts Institute of Technology (MIT); Swiss Federal Institutes of Technology Domain; ETH Zurich; University of British Columbia
摘要：The multilinear framework for submodular maximization was developed to achieve a tight 1-1/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-1/e$$\end{document} approximation for maximizing a monotone submodular function subject to a matroid constraint, including as special case the submodular welfare problem. The...
-
作者：Goujaud, Baptiste; Taylor, Adrien; Dieuleveut, Aymeric
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Inria; Ecole Normale Superieure (ENS)
摘要：In this work, we show that the heavy-ball (HB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\operatorname {HB}$$\end{document}) method provably does not reach an accelerated convergence rate on smooth strongly convex problems. More specifically, we show that for any condition number and any choice of algorithmic p...
-
作者：Van Dyk, Madison; Klause, Kim; Koenemann, Jochen; Megow, Nicole
作者单位：University of Bremen; University of Waterloo
摘要：Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes in typical hub-and-spoke fashion. In practice, such consolidation requires parcel sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that it is NP-hard to determine whether a feasible sort...
-
作者：Borodin, Allan; Macrury, Calum
作者单位：University of Toronto; Columbia University
摘要：We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they exist, based on known edge probabilities. A probing algorithm must respect commitment, meaning that if a probed edge exists, it must be used in the matching. Additionally, each online vertex has a patience constraint which limits the number of probes that can be made to its adjacent edges. We introduce a new configu...
-
作者：Yoon, TaeHo; Ryu, Ernest K.; Grimmer, Benjamin
作者单位：Johns Hopkins University; University of California System; University of California Los Angeles
摘要：For nonexpansive fixed-point problems, Halpern's method with optimal parameters, its so-called H-dual algorithm, and in fact, an infinite family of algorithms containing them, all exhibit the exact minimax optimal convergence rate. In this work, we provide a characterization of the complete, exhaustive family of distinct algorithms using predetermined step-sizes, represented as lower triangular H-matrices, which attain the same optimal convergence rate. The characterization is based on polynom...
-
作者：Lee, Jisun; Gomez, Andres; Atamturk, Alper
作者单位：University System of Georgia; Georgia Institute of Technology; University of Southern California; University of California System; University of California Berkeley
摘要：We study a multi-period mixed-integer convex quadratic optimization problem, where the state evolves dynamically as an affine function of the state and action (control) variables in each period. We begin by projecting out the state variables using linear dynamics, resulting in a mixed-integer quadratic optimization problem with a positive-definite (block-)factorizable cost matrix. Employing this expression, we construct a closed convex hull representation of the epigraph of the quadratic cost ...
-
作者：O'Leary-Roseberry, Thomas; Bollapragada, Raghu
作者单位：University System of Ohio; Ohio State University; University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin
摘要：We consider minimizing finite-sum objective functions via Hessian-averaging based subsampled Newton methods. These methods allow for gradient inexactness and have fixed per-iteration Hessian approximation costs. The recent work (Na et al. 2023) demonstrated that Hessian averaging can be utilized to achieve fast Ologkk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \...
-
作者：Tawarmalani, Mohit
作者单位：Purdue University System; Purdue University
摘要：This paper introduces novel relaxation hierarchies for concavo-convex programs (CXP), a class of problems that includes disjoint bilinear programming (DBP) and concave minimization (CM) as special cases. At the core of these hierarchies is an algorithm based on double-description (DD) that computes the barycentric coordinates of a polyhedral cone as rational, non-negative functions representing multipliers associated with the cone's rays. These hierarchies combine geometric structure derived f...
-
作者：Lu, Zhaosong; Wang, Xiangyuan
作者单位：University of Minnesota System; University of Minnesota Twin Cities
摘要：We study a class of constrained nonconvex-nonconcave minimax optimization problems in which the inner maximization involves potentially complex constraints. Under the assumption that the inner problem of a novel lifted minimax reformulation satisfies a local Kurdyka-& Lstrok;ojasiewicz (KL) condition, we show that the maximal function of the original problem enjoys a local generalized H & ouml;lder smoothness property. We also propose a sequential convex programming (SCP) method for solving co...
-
作者：Hou, Di; Tang, Tianyun; Toh, Kim-Chuan
作者单位：National University of Singapore; University of Chicago; National University of Singapore
摘要：Polynomial optimization problems (POPs) can be reformulated as geometric convex conic programs, as shown by Kim, Kojima, and Toh (SIOPT 30:1251-1273, 2020), though such formulations remain NP-hard. In this work, we prove that several well-known relaxations can be unified under a common polyhedral-SDP framework, which arises by approximating the intractable cone by tractable intersections of polyhedral cones with the positive semidefinite matrix cone. Although effective in providing tight lower...
