-
作者：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...
-
作者：Xiong, Zikai; Freund, Robert M.
作者单位：Northwestern University; Massachusetts Institute of Technology (MIT)
摘要：In recent years, there has been growing interest in solving linear optimization problems - or more simply LP - using first-order methods in order to avoid the costly matrix factorizations of traditional methods for huge-scale LP instances. The restarted primal-dual hybrid gradient method (PDHG) - together with some heuristic techniques - has emerged as a powerful tool for solving huge-scale LPs. However, the theoretical understanding of the restarted PDHG and the validation of various heuristi...
-
作者：Aolaritei, Liviu; Shafiee, Soroosh; Dorfler, Florian
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Cornell University
摘要：Distributionally robust optimization (DRO) has become a powerful framework for estimation under uncertainty, offering strong out-of-sample performance and principled regularization. In this paper, we propose a DRO-based method for linear regression and address a central question: how to optimally choose the robustness radius, which controls the trade-off between robustness and accuracy. Focusing on high-dimensional settings where the dimension and the number of samples are both large and compa...
-
作者：Mulansky, Bernd; Potschka, Andreas
作者单位：TU Clausthal
摘要：We derive a mixed integer nonlinear programming formulation for the problem of finding a convex polygon with n vertices that is small (diameter at most one) and has maximum perimeter provided a stated conjecture is true. The formulation is based on a geometric construction using centrally symmetric polygons (zonogons). The resulting zonogons can be characterized by equivalence classes (under the action of the dihedral group) of 2n-vectors with entries either plus or minus one and a self-dualit...
-
作者：Gabl, Markus; Anstreicher, Kurt M.
作者单位：Helmholtz Association; Karlsruhe Institute of Technology; University of Iowa
摘要：We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with cutting planes and conic constraints. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a variety of different nonconvex quadratic problems.
-
作者：Aktas, Fatih S.; Kroer, Christian
作者单位：Columbia University
摘要：We study the convergence properties of the greedy Frank-Wolfe (GFW) algorithm with a unit step size, for a concave minimization problem (or equivalently, convex maximization) over a compact set. We assume that the function satisfies smoothness and strong concavity. These assumptions, together with the Kurdyka-& Lstrok;ojasiewicz (KL) property, allow us to derive global asymptotic convergence for the sequence generated by the algorithm. Furthermore, we also derive a convergence rate that depend...
-
作者：Cristi, Andres; Salas, David
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Universidad de O'Higgins
摘要：In 1960, B. Gr & uuml;nbaum proved that, for any convex body C subset of Rd and every halfspace H containing the centroid of C, the volume of H boolean AND C is at least a 1e -fraction of the volume of C. In 2014, Oertel conjectured that a similar result holds for mixed-integer convex sets. Concretely, he proposed that for any convex body C subset of Rn+d , there should exist a point x is an element of S=C boolean AND(Zn & times;Rd) such that every halfspace H containing x satisfies where Hd d...
-
作者：Bok, Jinho; Altschuler, Jason M.
作者单位：University of Pennsylvania
摘要：Recent advances in convex optimization have leveraged computer-assisted proofs to develop optimized first-order methods that improve over classical algorithms. However, each optimized method is specially tailored for a particular problem setting, and it is a well-documented challenge to extend optimized methods to other settings due to their highly bespoke design and analysis. We provide a framework that derives optimized methods for composite optimization directly from those for unconstrained...
-
作者：Gupta, Swati; Moondra, Jai; Singh, Mohit
作者单位：Massachusetts Institute of Technology (MIT); Carnegie Mellon University; University System of Georgia; Georgia Institute of Technology
摘要：Motivated by fairness concerns, we study the 'portfolio problem': given an optimization problem with set D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {D}$$\end{document} of feasible solutions, a class C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepac...
-
作者：Soma, Tasuku; Uschmajew, Andre
作者单位：Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; University of Augsburg; University of Augsburg
摘要：We propose accelerated versions of the operator Sinkhorn iteration for operator scaling using successive overrelaxation. We analyze the local convergence rates of these accelerated methods via linearization, which allows to determine the asymptotically optimal relaxation parameter based on Young's SOR theorem. Using the Hilbert metric on positive definite cones, we also obtain a global convergence result for a geodesic version of overrelaxation in a specific range of relaxation parameters. The...
