-
作者：Del Pia, Alberto; Khajavirad, Aida
作者单位：University of Wisconsin System; University of Wisconsin Madison; Lehigh University
摘要：With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the set of binary points z is an element of {0, 1}(V boolean OR S) satisfying a collection of equalities of the form z(s) = Pi(v is an element of s) sigma(s)(z(v)), for all s is an element of S, where sigma(s) (z(v)) is an element of {z(v), 1 - z(v)}, and where S is a multiset of subsets of V. By representing the pseudo-Boolean polytope via a signed hyp...
-
作者：Scott, James R.; Geunes, Joseph
作者单位：Texas A&M University System; Texas A&M University College Station; Duke University
摘要：We devise a method for minimizing a low-rank quasiconcave objective function over a polytope by first projecting the polytope's normal fan, then using the projected fan to obtain candidate solutions. When the polytope's maximal number of nonparallel edges is bounded by a polynomial in its dimension, our method solves the problem in time that is polynomial in the number of variables and exponential in the rank of the objective function. We discuss several problems from previous literature that ...
-
作者：Qiu, Yuzhou; Yildirim, E. Alper
作者单位：University of Edinburgh
摘要：We study linear programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT), referred to as RLT relaxations. We investigate the relations between the polyhedral properties of the feasible regions of a quadratic program and its RLT relaxation. We establish various connections between recession directions, boundedness, and vertices of the two feasible regions. Using these properties, we present a complete description of the set of instances th...
-
作者：Bestuzheva, Ksenia; Gleixner, Ambros; Achterberg, Tobias
作者单位：Zuse Institute Berlin
摘要：The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, we present a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs, which is based on analyzing linear constraints with binary variables, thus ...
-
作者：van Ee, Martijn; Oosterwijk, Tim; Sitters, Rene; Wiese, Andreas
作者单位：Vrije Universiteit Amsterdam; Technical University of Munich
摘要：We study routing problems of a convoy in a graph, generalizing the shortest path problem (SPP), the travelling salesperson problem (TSP), and the Chinese postman problem (CPP) which are all well-studied in the classical (non-convoy) setting. We assume that each edge in the graph has a length and a speed at which it can be traversed and that our convoy has a given length. While the convoy moves through the graph, parts of it can be located on different edges. For safety requirements, at all tim...
-
作者：Rebjock, Quentin; Boumal, Nicolas
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：Optimization algorithms can see their local convergence rates deteriorate when the Hessian at the optimum is singular. These singularities are inescapable when the optima are non-isolated. Yet, under the right circumstances, several algorithms preserve their favorable rates even when optima form a continuum (e.g., due to over-parameterization). This has been explained under various structural assumptions, including the Polyak-& Lstrok;ojasiewicz condition, Quadratic Growth and the Error Bound....
-
作者：Fischer, Frank
作者单位：Johannes Gutenberg University of Mainz
摘要：We develop a fully asynchronous proximal bundle method for solving non-smooth, convex optimization problems. The algorithm can be used as a drop-in replacement for classic bundle methods, i.e., the function must be given by a first-order oracle for computing function values and subgradients. The algorithm allows for an arbitrary number of master problem processes computing new candidate points and oracle processes evaluating functions at those candidate points. These processes share informatio...
-
作者：Wang, Irina; Becker, Cole; Van Parys, Bart; Stellato, Bartolomeo
作者单位：Princeton University; Massachusetts Institute of Technology (MIT)
摘要：Robust optimization is a tractable and expressive technique for decision-making under uncertainty, but it can lead to overly conservative decisions when pessimistic assumptions are made on the uncertain parameters. Wasserstein distributionally robust optimization can reduce conservatism by being data-driven, but it often leads to very large problems with prohibitive solution times. We introduce mean robust optimization, a general framework that combines the best of both worlds by providing a t...
-
作者：Sen, Buse; Akkaya, Deniz; Pinar, Mustafa c.
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Ihsan Dogramaci Bilkent University
摘要：We consider the problem of mean-variance portfolio selection regularized with an & ell;0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _0$$\end{document}-penalty term to control the sparsity of the portfolio. We analyze the structure of local and global minimizers and use our results in the design of a Branch...
-
作者：Alcantara, Jan Harold; Nguyen, Chieu Thanh; Okuno, Takayuki; Takeda, Akiko; Chen, Jein-Shan
作者单位：RIKEN; Vietnam National University of Agriculture (VNUA); Seikei University; University of Tokyo; National Taiwan Normal University
摘要：Strongly motivated from applications in various fields including machine learning, the methodology of sparse optimization has been developed intensively so far. Especially, the advancement of algorithms for solving problems with nonsmooth regularizers has been remarkable. However, those algorithms suppose that weight parameters of regularizers, called hyperparameters hereafter, are pre-fixed, but it is a crucial matter how the best hyperparameter should be selected. In this paper, we focus on ...
