-
作者：Aliev, Iskander; Celaya, Marcel; Henk, Martin
作者单位：Cardiff University; Technical University of Berlin
摘要：We obtain new transference bounds that connect the additive integrality gap and sparsity of solutions for integer linear programs. Specifically, we consider the integer programs min{cx:x is an element of P boolean AND Zn}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \{{\varvec{c}}\cdot {\varvec{x}}: {\varvec...
-
作者：Arakcheev, Aleksandr; Bauschke, Heinz H.
作者单位：University of British Columbia
摘要：Opial's Lemma is a fundamental result in the convergence analysis of sequences generated by optimization algorithms in real Hilbert spaces. We introduce the concept of Opial sequences-sequences for which the limit of the distance to each point in a given set exists. We systematically derive properties of Opial sequences, contrasting them with the well-studied Fej & eacute;r monotone sequences, and establish conditions for weak and strong convergence. Key results include characterizations of we...
-
作者：Yang, Yan; Gao, Bin; Yuan, Ya-xiang
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
摘要：Imposing additional constraints on low-rank optimization has garnered growing interest. However, the geometry of coupled constraints hampers the well-developed low-rank structure and makes the problem intricate. To this end, we propose a space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraints. The space-decoupling is reflected in several ways. We show that the tangent cone of coupled constraints is the intersection of tangent cones of each c...
-
作者：Cartis, Coralia; Zhu, Wenqi
作者单位：University of Oxford
摘要：There has been growing interest in high-order tensor methods for nonconvex optimization, with adaptive regularization, as they possess better/optimal worst-case evaluation complexity globally and faster convergence asymptotically. These algorithms crucially rely on repeatedly minimizing nonconvex multivariate Taylor-based polynomial sub-problems, at least locally. Finding efficient techniques for the solution of these sub-problems, beyond the second-order case, has been an open question. This ...
-
作者：Ghorbal, Khalil; Kozaily, Christelle
作者单位：Universite de Rennes; Inria
摘要：This paper is concerned with a covering problem of Euclidean space by a particular arrangement of cones that are not necessarily full and are allowed to overlap. The problem provides an equivalent geometric reformulation of the solvability of the linear complementarity problem defining the class of Q-matrices. Assuming feasibility, we rely on standard tools from convex geometry to study maximal connected uncovered regions, we term holes. We then use our approach to fully characterize the probl...
-
作者：Grimmer, Benjamin; Li, Danlin
作者单位：Johns Hopkins University
摘要：We consider (stochastic) subgradient methods for strongly convex but potentially nonsmooth non-Lipschitz optimization. We provide new equivalent dual descriptions (in the style of dual averaging) for the classic subgradient method, the proximal subgradient method, and the switching subgradient method. These equivalences enable O(1/T) convergence guarantees in terms of both their classic primal gap and a not previously analyzed dual gap for strongly convex optimization. Consequently, our theory...
-
作者：Benedek, Marton; Biro, Peter; Kern, Walter; Palvolgyi, Domotor; Paulusma, Daniel
作者单位：Corvinus University Budapest; University of Twente; Eotvos Lorand University; Durham University
摘要：We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a fair way. A partitioned matching game (N, v) is defined on a graph G = (V, E) with an edge weighting w and a partition V = V-1 boolean OR center dot center dot center dot boolean OR V-n. The player set is N = {1,..., n}, and player p is an element of N owns ...
-
作者：Santiago, Richard; Sergeev, Ivan; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an O(1)-competitive algorithm for the Matroid Secretary Problem (MSP). Here, the elements of a weighted matroid appear one-by-one, revealing their weight at appearance, and the task is to select elements online with the goal to get an independent set of largest possible weight. O(1)-competitive MSP algorithms have so far only been obtained for restricted matroid classes and for MSP v...
-
作者：Kim, Do Sang; Nguyen, Minh Tung; Pham, Tien-Son
作者单位：Pukyong National University; Ho Chi Minh University of Banking (HUB); Dalat University
摘要：In this work, the notions of normal cones at infinity to unbounded sets and limiting and singular subdifferentials at infinity for extended real value functions are introduced. Various calculus rules for these notions are established. A complete characterization of the Lipschitz continuity at infinity for lower semicontinuous functions is given. The obtained results are aimed ultimately at applications to diverse problems of optimization, such as optimality conditions, coercive properties, wea...
-
作者：Abdi, Ahmad; Silina, Olha
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University
摘要：Let G=(V,E) be a matching-covered graph, denote by P its perfect matching polytope, and by L the integer lattice generated by the integral points in P. In this paper, we give short, polyhedral proofs for two difficult results established by Lov & aacute;sz (1987), and by Carvalho, Lucchesi, and Murty (2002) in a series of three papers totaling over 120 pages. More specifically, we prove that (a) L has a lattice basis consisting solely of incidence vectors of some perfect matchings of G, (b) 2x...
