Mathematical Programming

最新文章

• Eventual convexity of probability constraints with elliptical distributions AI翻译
  作者：van Ackooij, Wim; Malick, Jerome
  作者单位：Electricite de France (EDF); Centre National de la Recherche Scientifique (CNRS)
  摘要：Probability constraints are often employed to intuitively define safety of given decisions in optimization problems. They simply express that a given system of inequalities depending on a decision vector and a random vector is satisfied with high enough probability. It is known that, even if this system is convex in the decision vector, the associated probability constraint is not convex in general. In this paper, we show that some degree of convexity is still preserved, for the large class of...
• An extension of Chubanov's algorithm to symmetric cones AI翻译
  作者：Lourenco, Bruno F.; Kitahara, Tomonari; Muramatsu, Masakazu; Tsuchiya, Takashi
  作者单位：Seikei University; Institute of Science Tokyo; Tokyo Institute of Technology; University of Electro-Communications - Japan; National Graduate Institute for Policy Studies
  摘要：In this work we present an extension of Chubanov's algorithm to the case of homogeneous feasibility problems over a symmetric cone K. As in Chubanov's method for linear feasibility problems, the algorithm consists of a basic procedure and a step where the solutions are confined to the intersection of a half-space and K. Following an earlier work by Kitahara and Tsuchiya on second order cone feasibility problems, progress is measured through the volumes of those intersections: when they become ...
• Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach AI翻译
  作者：Fang, Ethan X.; Liu, Han; Wang, Mengdi
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Princeton University
  摘要：We consider the problem of estimating high dimensional spatial graphical models with a total cardinality constraint (i.e., the 0-constraint). Though this problem is highly nonconvex, we show that its primal-dual gap diminishes linearly with the dimensionality and provide a convex geometry justification of this blessing of massive scale phenomenon. Motivated by this result, we propose an efficient algorithm to solve the dual problem (which is concave) and prove that the solution achieves optima...
• A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems AI翻译
  作者：Boland, Natashia; Christiansen, Jeffrey; Dandurand, Brian; Eberhard, Andrew; Oliveira, Fabricio
  作者单位：University System of Georgia; Georgia Institute of Technology; Royal Melbourne Institute of Technology (RMIT); Aalto University
  摘要：We contribute improvements to a Lagrangian dual solution approach applied to large-scale optimization problems whose objective functions are convex, continuously differentiable and possibly nonlinear, while the non-relaxed constraint set is compact but not necessarily convex. Such problems arise, for example, in the split-variable deterministic reformulation of stochastic mixed-integer optimization problems. We adapt the augmented Lagrangian method framework to address the presence of nonconve...
• A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications AI翻译
  作者：Li, Xudong; Sun, Defeng; Toh, Kim-Chuan
  作者单位：Princeton University; Hong Kong Polytechnic University; National University of Singapore; National University of Singapore; National University of Singapore
  摘要：For a symmetric positive semidefinite linear system of equations Qx=b, where x=(x1,...,xs) is partitioned into s blocks, with s2, we show that each cycle of the classical block symmetric Gauss-Seidel (sGS) method exactly solves the associated quadratic programming (QP) problem but added with an extra proximal term of the form, where T is a symmetric positive semidefinite matrix related to the sGS decomposition of Q and xk is the previous iterate. By leveraging on such a connection to optimizat...
• Level-set methods for convex optimization AI翻译
  作者：Aravkin, Aleksandr Y.; Burke, James V.; Drusvyatskiy, Dmitry; Friedlander, Michael P.; Roy, Scott
  作者单位：University of Washington; University of Washington Seattle; University of Washington; University of Washington Seattle; University of British Columbia
  摘要：Convex optimization problems arising in applications often have favorable objective functions and complicated constraints, thereby precluding first-order methods from being immediately applicable. We describe an approach that exchanges the roles of the objective with one of the constraint functions, and instead approximately solves a sequence of parametric level-set problems. Two Newton-like zero-finding procedures for nonsmooth convex functions, based on inexact evaluations and sensitivity in...
• Global optimization in Hilbert space AI翻译
  作者：Houska, Boris; Chachuat, Benoit
  作者单位：ShanghaiTech University; Imperial College London
  摘要：We propose a complete-search algorithm for solving a class of non-convex, possibly infinite-dimensional, optimization problems to global optimality. We assume that the optimization variables are in a bounded subset of a Hilbert space, and we determine worst-case run-time bounds for the algorithm under certain regularity conditions of the cost functional and the constraint set. Because these run-time bounds are independent of the number of optimization variables and, in particular, are valid fo...
• Concave regression: value-constrained estimation and likelihood ratio-based inference AI翻译
  作者：Doss, Charles R.
  作者单位：University of Minnesota System; University of Minnesota Twin Cities
  摘要：We propose a likelihood ratio statistic for forming hypothesis tests and confidence intervals for a nonparametrically estimated univariate regression function, based on the shape restriction of concavity (alternatively, convexity). Dealing with the likelihood ratio statistic requires studying an estimator satisfying a null hypothesis, that is, studying a concave least-squares estimator satisfying a further equality constraint. We study this null hypothesis least-squares estimator (NLSE) here, ...
• On variance reduction for stochastic smooth convex optimization with multiplicative noise AI翻译
  作者：Jofre, Alejandro; Thompson, Philip
  作者单位：Universidad de Chile; Universidad de Chile
  摘要：We propose dynamic sampled stochastic approximation (SA) methods for stochastic optimization with a heavy-tailed distribution (with finite 2nd moment). The objective is the sum of a smooth convex function with a convex regularizer. Typically, it is assumed an oracle with an upper bound sigma(2) on its variance (OUBV). Differently, we assume an oracle with multiplicative noise. This rarely addressed setup is more aggressive but realistic, where the variance may not be uniformly bounded. Our met...
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval AI翻译
  作者：Chen, Yuxin; Chi, Yuejie; Fan, Jianqing; Ma, Cong
  作者单位：Princeton University; Carnegie Mellon University; Princeton University
  摘要：This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest x?Rn from m quadratic equations/samples yi=(ai?x?)2,1im. This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficacy of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient descentwhen randomly initializedyields a...