sparsity

BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints

  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Akiko Takeda
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity (BBC) constraints. Given a POP in the class and a relaxation order, BBCPOP constructs a simple conic optimization problem (COP), which serves as a … Read more

    On the Size of Integer Programs with Bounded Coefficients or Sparse Constraints

  • Christopher Hojny
  • Marc E. Pfetsch
  • Hendrik Lüthen
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Integer programming formulations describe optimization problems over a set of integer points. A fundamental problem is to determine the minimal size of such formulations, in particular, if the size of the coefficients or sparsity of the constraints is bounded. This article considers lower and upper bounds on these sizes both in the original and in … Read more

    Preconditioning PDE-constrained optimization with L^1-sparsity and control constraints

  • Margherita Porcelli
  • Valeria Simoncini
  • Martin Stoll
    • Categories Control Applications, Systems governed by Differential Equations Optimization Tags , , , , ,

    PDE-constrained optimization aims at finding optimal setups for partial differential equations so that relevant quantities are minimized. Including sparsity promoting terms in the formulation of such problems results in more practically relevant computed controls but adds more challenges to the numerical solution of these problems. The needed L^1-terms as well as additional inclusion of box … Read more

    Piecewise Parametric Structure in the Pooling Problem – from Sparse Strongly-Polynomial Solutions to NP-Hardness

  • Radu Baltean-Lugojan
  • Ruth Misener
    • Categories Combinatorial Optimization, Quadratic Programming Tags , , , , , ,

    The standard pooling problem is a NP-hard sub-class of non-convex quadratically-constrained optimization problems that commonly arises in process systems engineering applications. We take a parametric approach to uncovering topological structure and sparsity of the standard pooling problem in its p-formulation. The structure uncovered in this approach validates Professor Christodoulos A. Floudas’ intuition that pooling problems … Read more

    Worst-Case Hardness of Approximation for Sparse Optimization with L0 Norm

  • Yichen Chen
  • Mengdi Wang
    • Categories Combinatorial Optimization, Nonlinear Optimization Tags , , , ,

    In this paper, we consider sparse optimization problems with L0 norm penalty or constraint. We prove that it is strongly NP-hard to find an approximate optimal solution within certain error bound, unless P = NP. This provides a lower bound for the approximation error of any deterministic polynomial-time algorithm. Applying the complexity result to sparse … Read more

    A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation

  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , , , , , , , ,

    Stochastic approximation techniques play an important role in solving many problems encountered in machine learning or adaptive signal processing. In these contexts, the statistics of the data are often unknown a priori or their direct computation is too intensive, and they have thus to be estimated online from the observed signals. For batch optimization of … Read more

    Analysis of Sparse Cutting-plane for Sparse MILPs with Applications to Stochastic MILPs

  • Santanu S. Dey
  • Marco Molinaro
  • Qianyi Wang
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags ,

    In this paper, we present an analysis of the strength of sparse cutting-planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. Given a MILP instance of one of these three … Read more

    How Good Are Sparse Cutting-Planes?

  • Santanu S. Dey
  • Marco Molinaro
  • Qianyi Wang
    • Categories Integer Programming Tags ,

    Sparse cutting-planes are often the ones used in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-\&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope $P$ (e.g. the integer hull of … Read more

    Extreme point inequalities and geometry of the rank sparsity ball

  • Dmitriy Drusvyatskiy
  • Stephen A. Vavasis
  • Henry Wolkowicz
    • Categories Convex Optimization Tags , , , , ,

    We investigate geometric features of the unit ball corresponding to the sum of the nuclear norm of a matrix and the l_1 norm of its entries — a common penalty function encouraging joint low rank and high sparsity. As a byproduct of this effort, we develop a calculus (or algebra) of faces for general convex … Read more

    Compressed Sensing Off the Grid

  • Badri Narayan Bhaskar
  • Benjamin Recht
  • Parikshit Shah
  • Gongguo Tang
    • Categories Convex Optimization, Data-Mining, Semi-definite Programming Tags , , , , , , ,

    We consider the problem of estimating the frequency components of a mixture of s complex sinusoids from a random subset of n regularly spaced samples. Unlike previous work in compressed sensing, the frequencies are not assumed to lie on a grid, but can assume any values in the normalized frequency domain [0, 1]. We propose … Read more