-
作者：Lan, Guanghui; Ouyang, Yuyuan; Zhang, Zhe
作者单位：University System of Georgia; Georgia Institute of Technology; Clemson University; Purdue University System; Purdue University
摘要：We propose novel optimal and parameter-free algorithms for computing an approximate solution with small (projected) gradient norm. Specifically, for computing an approximate solution such that the norm of its (projected) gradient does not exceed epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\...
-
作者：Hunkenschroder, Christoph; Koutecky, Martin; Levin, Asaf; Vu, Tung Anh
作者单位：Technical University of Berlin; Technion Israel Institute of Technology; Charles University Prague
摘要：We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: min{ f (x) | Ax = b, 1 <= x <= u, x is an element of Z(n)}. The number of variables n is a variable part of the input, and we consider the regime where the constraint matrix A has small coefficients IIAIIcand small primal or dual treedepth td(P) (A) or td(D)(A), respectively. Equivalently, we consider block-structured matrices, in particular n-fold, tree-fold, ...
-
作者：Hunkenschroder, Christoph; Klein, Kim-Manuel; Koutecky, Martin; Lassota, Alexandra; Levin, Asaf
作者单位：Technical University of Berlin; University of Lubeck; Charles University Prague; Eindhoven University of Technology; Technion Israel Institute of Technology
摘要：We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs have a constraint matrix with independent blocks linked together by few constraints in a recursive pattern. Transposing this constraint matrix yields the constraint matrix of multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to ask whether this gap is inherent. We answer this question in the affirmative. A...
-
作者：Cole, Richard; Hertrich, Christoph; Tao, Yixin; Vegh, Laszlo A.
作者单位：New York University; Shanghai University of Finance & Economics; University of Bonn; University of London; London School Economics & Political Science; Corvinus University Budapest
摘要：Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. From a theoretical perspective, linear convergence rates have been established for first order LP algorithms, despite the fact that the underlying formulations are not strongly convex. However, the convergence rate typically depends on the Hoffman constant of a large matrix that contains the constraint matrix, as w...
-
作者：Kong, Siyu; Lewis, A. S.
作者单位：Cornell University
摘要：Goldstein's 1977 idealized iteration for minimizing a Lipschitz objective fixes a distance - the step size - and relies on a certain approximate subgradient. That Goldstein subgradient is the shortest convex combination of objective subgradients at points within that distance of the current iterate. A recent implementable Goldstein-style algorithm allows a remarkable complexity analysis (Zhang et al. 2020), and a more sophisticated variant (Davis and Jiang, 2022) leverages typical objective ge...
-
作者：Gupta, Anupam; Hu, Jinqiao; Kehne, Gregory; Levin, Roie
作者单位：New York University; University of Warwick; Washington University (WUSTL); Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：We study online contention resolution schemes (OCRSes) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-ok(1))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1-o_k(1))$$\end{document}-selectable ...
-
作者：De Loera, Jesus A.; Marsters, Brittney; Xu, Luze; Zhang, Shixuan
作者单位：University of California System; University of California Davis; Texas A&M University System; Texas A&M University College Station
摘要：We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set with the help of a group action. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbe...
-
作者：Cartis, Coralia; Zhu, Wenqi
作者单位：University of Oxford
摘要：High-order tensor methods for solving both convex and nonconvex optimization problems have recently generated significant research interest, due in part to the natural way in which higher derivatives can be incorporated into adaptive regularization frameworks, leading to algorithms with optimal global rates of convergence and local rates that are faster than Newton's method. On each iteration, to find the next solution approximation, these methods require the unconstrained local minimization o...
-
作者：Grimmer, Benjamin; Shu, Kevin; Wang, Alex L.
作者单位：Johns Hopkins University; California Institute of Technology; Purdue University System; Purdue University
摘要：The study of convex optimization has historically been concerned with worst-case convergence rates. The development of the Optimized Gradient Method (OGM), due to Drori and Teboulle [1] and Kim and Fessler [2], marked a major milestone in this study, as OGM achieves the optimal worst-case convergence rate among all first-order methods for unconstrained smooth convex optimization. In order to examine the possibility of obtaining stronger convergence guarantees, we will consider algorithms with ...
-
作者：Chervet, Patrick; Grappe, Roland; Vallee, Mathieu
作者单位：Universite PSL; Universite Paris-Dauphine; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：Totally equimodular matrices generalize totally unimodular matrices and arise in the context of box-totally dual integral polyhedra. This work further explores the parallels between these two classes and introduces foundational building blocks for constructing totally equimodular matrices. Consequently, we present a decomposition theorem for totally equimodular matrices of full row rank. Building on this decomposition theorem, we prove that simplicial cones whose generators form the rows of a ...
