-
作者：Johnstone, Patrick R.; Moulin, Pierre
作者单位：Rutgers University System; Rutgers University New Brunswick; University of Illinois System; University of Illinois Urbana-Champaign
摘要：The purpose of this manuscript is to derive new convergence results for several subgradient methods applied to minimizing nonsmooth convex functions with Holderian growth. The growth condition is satisfied in many applications and includes functions with quadratic growth and weakly sharp minima as special cases. To this end there are three main contributions. First, for a constant and sufficiently small stepsize, we show that the subgradient method achieves linear convergence up to a certain r...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco
作者单位：Johns Hopkins University; University of Padua
摘要：We consider Gomory and Johnson's infinite group model with a single row. Valid inequalities for this model are expressed by valid functions and it has been recently shown that any valid function is dominated by some nonnegative valid function, modulo the affine hull of the model. Within the set of nonnegative valid functions, extreme functions are the ones that cannot be expressed as convex combinations of two distinct valid functions. In this paper we construct an extreme function pi:R ->[0,1...
-
作者：Klatte, Diethard; Kummer, Bernd
作者单位：University of Zurich; Humboldt University of Berlin
-
作者：Ahmadi, Amir Ali; Zhang, Jeffrey
作者单位：Princeton University
摘要：We prove that unlessP=NP there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known Frank-Wolfe type theorems imply that exactly one of two cases can occur: either the optimal value is attained on every instance, or it is strongly NP-...
-
作者：D'Ambrosio, Claudia; Liberti, Leo; Poirion, Pierre-Louis; Vu, Ky
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; RIKEN; FPT University
摘要：Random projections map a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Although random projections are usually applied to numerical data, we show in this paper that they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving the higher-dimensional original problem, we solve the projected problem more efficiently. This yields a feasib...
-
作者：Graf, Lukas; Harks, Tobias; Sering, Leon
作者单位：Technical University of Berlin
摘要：We study dynamic network flows and introduce a notion of instantaneous dynamic equilibrium (IDE) requiring that for any positive inflow into an edge, this edge must lie on a currently shortest path towards the respective sink. We measure current shortest path length by current waiting times in queues plus physical travel times. As our main results, we show: existence and constructive computation of IDE flows for multi-source single-sink networks assuming constant network inflow rates, finite t...
-
作者：Menickelly, Matt; Wild, Stefan M.
作者单位：United States Department of Energy (DOE); Argonne National Laboratory
摘要：We develop an algorithm for minimax problems that arise in robust optimization in the absence of objective function derivatives. The algorithm utilizes an extension of methods for inexact outer approximation in sampling a potentially infinite-cardinality uncertainty set. Clarke stationarity of the algorithm output is established alongside desirable features of the model-based trust-region subproblems encountered. We demonstrate the practical benefits of the algorithm on a new class of test pro...
-
作者：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...
