-
作者：Scieur, Damien; d'Aspremont, Alexandre; Bach, Francis
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：We describe a convergence acceleration technique for unconstrained optimization problems. Our scheme computes estimates of the optimum from a nonlinear average of the iterates produced by any optimization method. The weights in this average are computed via a simple linear system, whose solution can be updated online. This acceleration scheme runs in parallel to the base algorithm, providing improved estimates of the solution on the fly, while the original optimization method is running. Numer...
-
作者：Berczi, Kristof; Chandrasekaran, Karthekeyan; Kiraly, Tamas; Madan, Vivek
作者单位：Eotvos Lorand University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We investigate the approximability of the linear 3-cut problem in directed graphs. The input here is a directed graph D = (V, E) with node weights and three specified terminal nodes s, r, t. V, and the goal is to find a minimum weight subset of nonterminal nodes whose removal ensures that s cannot reach r and t, and r cannot reach t. The precise approximability of linear 3-cut has been wide open until now: the best known lower bound under the unique games conjecture (UGC) was 4/3, while the be...
-
作者：Bertsimas, Dimitris; Lamperski, Jourdain; Pauphilet, Jean
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider the maximum likelihood estimation of sparse inverse covariance matrices. We demonstrate that current heuristic approaches primarily encourage robustness, instead of the desired sparsity. We give a novel approach that solves the cardinality constrained likelihood problem to certifiable optimality. The approach uses techniques from mixed-integer optimization and convex optimization, and provides a high-quality solution with a guarantee on its suboptimality, even if the algorithm is t...
-
作者：Conforti, Michele; Di Summa, Marco; Faenza, Yuri
作者单位：University of Padua; Columbia University
摘要：A celebrated theorem of Balas gives a linear mixed-integer formulation for the union of two nonempty polytopes whose relaxation gives the convex hull of this union. The number of inequalities in Balas formulation is linear in the number of inequalities that describe the two polytopes and the number of variables is doubled. In this paper we show that this is best possible: in every dimension there exist two nonempty polytopes such that if a formulation for the convex hull of their union has a n...
