-
作者：Bardakci, I. E.; Jalilzadeh, A.; Lagoa, C.; Shanbhag, U., V
作者单位：Bartin University; University of Arizona; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：In this paper, we consider the maximizing of the probability P { zeta vertical bar zeta is an element of K(x) } over a closed and convex set chi, a special case of the chance-constrained optimization problem. Suppose K(x) (sic) { zeta is an element of K vertical bar c(x, zeta) >= 0}, and zeta is uniformly distributed on a convex and compact set K and c(x, zeta) is defined as either c(x, zeta) (sic) 1 - vertical bar zeta(T)x vertical bar(m) where m >= 0 (Setting A) or c(x, zeta) (sic) Tx - zeta...
-
作者：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...
-
作者：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...
-
作者：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 ...
-
作者：Lee, Ching-pei
作者单位：Academia Sinica - Taiwan
摘要：For regularized optimization that minimizes the sum of a smooth term and a regularizer that promotes structured solutions, inexact proximal-Newton-type methods, or successive quadratic approximation (SQA) methods, are widely used for their superlinear convergence in terms of iterations. However, unlike the counter parts in smooth optimization, they suffer from lengthy running time in solving regularized subproblems because even approximate solutions cannot be computed easily, so their empirica...
-
作者：Jia, Xiaoxi; Kanzow, Christian; Mehlitz, Patrick; Wachsmuth, Gerd
作者单位：University of Wurzburg; Brandenburg University of Technology Cottbus; University of Mannheim
摘要：This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality ...
-
作者：Weber, Melanie; Sra, Suvrit
作者单位：University of Oxford; Princeton University; Massachusetts Institute of Technology (MIT)
摘要：We study projection-free methods for constrained Riemannian optimization. In particular, we propose a Riemannian Frank-Wolfe (RFW) method that handles constraints directly, in contrast to prior methods that rely on (potentially costly) projections. We analyze non-asymptotic convergence rates of RFW to an optimum for geodesically convex problems, and to a critical point for nonconvex objectives. We also present a practical setting under which RFW can attain a linear convergence rate. As a concr...
-
作者：Leygonie, Jacob; Carriere, Mathieu; Lacombe, Theo; Oudot, Steve
作者单位：University of Oxford; Universite Cote d'Azur; Inria; Universite Gustave-Eiffel; ESIEE Paris; Institut Polytechnique de Paris; Ecole des Ponts ParisTech; Inria; Institut Polytechnique de Paris
摘要：We introduce a novel gradient descent algorithm refining the well-known Gradient Sampling algorithm on the class of stratifiably smooth objective functions, which are defined as locally Lipschitz functions that are smooth on some regular pieces-called the strata-of the ambient Euclidean space. On this class of functions, our algorithm achieves a sub-linear convergence rate. We then apply our method to objective functions based on the (extended) persistent homology map computed over lower-star ...
