-
作者：Huang, Lei; Nie, Jiawang; Yuan, Ya-Xiang
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; University of California System; University of California San Diego
摘要：This paper considers polynomial optimization with unbounded sets. We give a homogenization formulation and propose a hierarchy of Moment-SOS relaxations to solve it. Under the assumptions that the feasible set is closed at infinity and the ideal of homogenized equality constraining polynomials is real radical, we show that this hierarchy of Moment-SOS relaxations has finite convergence, if some optimality conditions (i.e., the linear independence constraint qualification, strict complementarit...
-
作者：Mazumder, Rahul; Wang, Haoyue
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Linear regression is a fundamental modeling tool in statistics and related fields. In this paper, we study an important variant of linear regression in which the predictor-response pairs are partially mismatched. We use an optimization formulation to simultaneously learn the underlying regression coefficients and the permutation corresponding to the mismatches. The combinatorial structure of the problem leads to computational challenges. We propose and study a simple greedy local search algori...
-
作者：Taskesen, Bahar; Shafieezadeh-Abadeh, Soroosh; Kuhn, Daniel
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Carnegie Mellon University
摘要：Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard. Even though such problems are ubiquitous in statistics, machine learning and computer vision, however, this perception has not yet received a theoretical justification. To fill this gap, we prove that computing the Wasserstein distance between a discrete probability measure supported on two point...
-
作者：Chandrasekaran, Karthekeyan; Wang, Weihang
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider the graph k-partitioning problem under the min-max objective, termed as Minmax k-cut. The input here is a graph G = (V, E) with non-negative integral edge weights w : E -> Z(+) and an integer k >= 2 and the goal is to partition the vertices into k non-empty parts V-1, ..., V-k so as to minimize max(i=1)(k) w(delta(V-i)). Although minimizing the sum objective Sigma(k)(i=1) w(delta(V-i)), termed as Minsum k-cut, has been studied extensively in the literature, very little is known abo...
-
作者：Gu, Xiaoyi; Dey, Santanu S.; Richard, Jean-Philippe P.
作者单位：University System of Georgia; Georgia Institute of Technology; University of Minnesota System; University of Minnesota Twin Cities
摘要：The goal of this paper is to derive new classes of valid convex inequalities for quadratically constrained quadratic programs (QCQPs) through the technique of lifting. Our first main result shows that, for sets described by one bipartite bilinear constraint together with bounds, it is always possible to sequentially lift a seed inequality that is valid for a restriction obtained by fixing variables to their bounds, when the lifting is accomplished using affine functions of the fixed variables....
-
作者：Josz, Cedric
作者单位：Columbia University
-
作者：Tang, Yujie; Zheng, Yang; Li, Na
作者单位：Peking University; University of California System; University of California San Diego; Harvard University
摘要：This paper revisits the classical Linear Quadratic Gaussian (LQG) control from a mod-ern optimization perspective. We analyze two aspects of the optimization landscape of the LQG problem: (1) Connectivity of the set of stabilizing controllers C-n; and (2) Structure of stationary points. It is known that similarity transformations do not change the input-output behavior of a dynamic controller or LQG cost. This inherent symmetry by similarity transformations makes the landscape of LQG very rich...
-
作者：Han, Shaoning; Gomez, Andres; Atamturk, Alper
作者单位：University of Southern California; University of California System; University of California Berkeley
摘要：In this paper, we study the convex quadratic optimization problem with indicator variables. For the 2 x 2 case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the 2 x 2 case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including...
-
作者：Li, Xiaocheng; Sun, Chunlin; Ye, Yinyu
作者单位：Imperial College London; Stanford University; Stanford University
摘要：In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in general resource allocation problem. The algorithm requires only one single pass through the input data and is free of matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it ess...
-
作者：Altschuler, Jason M.; Boix-Adsera, Enric
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k and their support sizes n. This paper develops a general theory about what structure makes MOT solvable in poly(n, k) time. We develop a unified algorithmic framework for ...
