-
作者：Wang, Alex L.; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：We consider the generalized trust region subproblem (GTRS) ofminimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. Alifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this nonconvex set in terms of the generalized eigenvalues of an associated matrix pencil. This result may be of interest in building r...
-
作者：Johnstone, Patrick R.; Eckstein, Jonathan
作者单位：Rutgers University System; Rutgers University New Brunswick
摘要：This work is concerned with the classical problem of finding a zero of a sum of maximal monotone operators. For the projective splitting framework recently proposed by Combettes and Eckstein, we show how to replace the fundamental subproblem calculation using a backward step with one based on two forward steps. The resulting algorithms have the same kind of coordination procedure and can be implemented in the same block-iterative and highly flexible manner, but may perform backward steps on so...
-
作者：Zhang, Junyu; Xiao, Lin
作者单位：Princeton University; Facebook Inc
摘要：We consider the problem of minimizing composite functions of the form f(g(x))+h(x), where f and h are convex functions (which can be nonsmooth) and g is a smooth vector mapping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an epsilon-stationary poin...
-
作者：Jansen, Klaus; Klein, Kim-Manuel; Maack, Marten; Rau, Malin
作者单位：University of Kiel; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
摘要：Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems where a set of items has to be placed in multiple target locations. Herein, a configuration describes a possible placement on one of the target locations, and the IP is used to choose suitable configurations covering the items. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework...
-
作者：Yue, Man-Chung; Kuhn, Daniel; Wiesemann, Wolfram
作者单位：Hong Kong Polytechnic University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
摘要：Wasserstein balls, which contain all probability measures within a pre-specified Wasserstein distance to a reference measure, have recently enjoyed wide popularity in the distributionally robust optimization and machine learning communities to formulate and solve data-driven optimization problems with rigorous statistical guarantees. In this technical note we prove that the Wasserstein ball is weakly compact under mild conditions, and we offer necessary and sufficient conditions for the existe...
-
作者：Xie, Weijun; Zhang, Jie; Ahmed, Shabbir
作者单位：Virginia Polytechnic Institute & State University; University System of Georgia; Georgia Institute of Technology
摘要：In a bottleneck combinatorial problem, the objective is to minimize the highest cost of elements of a subset selected from the combinatorial solution space. This paper studies data-driven distributionally robust bottleneck combinatorial problems (DRBCP) with stochastic costs, where the probability distribution of the cost vector is contained in a ball of distributions centered at the empirical distribution specified by the Wasserstein distance. We study two distinct versions of DRBCP from diff...
-
作者：Iwamasa, Yuni; Takazawa, Kenjiro
作者单位：Kyoto University; Hosei University
摘要：For two matroids M-1 and M-2 with the same ground set V and two cost functions w(1) and w(2) on 2(V), we consider the problem of finding bases X-1 of M-1 and X-2 of M-2 minimizing w(1)(X-1) + w(2)(X-2) subject to a certain cardinality constraint on their intersection X-1 boolean AND X-2. For this problem, Lendl et al. (Matroid bases with cardinality constraints on the intersection, arXiv:1907.04741v2, 2019) discussed modular cost functions: they reduced the problem to weighted matroid intersec...
-
作者：Kim, Sunyoung; Kojima, Masakazu; Toh, Kim-Chuan
作者单位：Ewha Womans University; Chuo University; National University of Singapore; National University of Singapore
摘要：We propose a doubly nonnegative (DNN) relaxation for polynomial optimization problems (POPs) with binary and box constraints. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems to POPs. The dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to which an accelerated bisection and projection (BP) algorithm is applied. The COP involves a single equality constraint in a matrix variable which is restricted ...
-
作者：Bernstein, Aaron; Disser, Yann; Gross, Martin; Himburg, Sandra
作者单位：Rutgers University System; Rutgers University New Brunswick; Technical University of Darmstadt; University of Waterloo
摘要：We propose a theoretical framework to capture incremental solutions to cardinality constrained maximization problems. The defining characteristic of our framework is that the cardinality/support of the solution is bounded by a value k is an element of N that grows over time, and we allow the solution to be extended one element at a time. We investigate the best-possible competitive ratio of such an incremental solution, i.e., the worst ratio over all kbetween the incremental solution after kst...
-
作者：Lodi, Andrea; Malaguti, Enrico; Nannicini, Giacomo; Thomopulos, Dimitri
作者单位：Universite de Montreal; Polytechnique Montreal; University of Bologna; International Business Machines (IBM); IBM USA; University of Pisa
摘要：We present a Branch-and-Cut algorithm for a class of nonlinear chance-constrained mathematical optimization problems with a finite number of scenarios. Unsatisfied scenarios can enter a recovery mode. This class corresponds to problems that can be reformulated as deterministic convex mixed-integer nonlinear programming problems with indicator variables and continuous scenario variables, but the size of the reformulation is large and quickly becomes impractical as the number of scenarios grows....
