Semi-definite Programming

Approximating semidefinite packing problems

  • Garud Iyengar
  • Cliff Stein
  • David Phillips
    • Categories Approximation Algorithms, Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    In this paper we define semidefinite packing programs and describe an algorithm to approximately solve these problems. Semidefinite packing programs arise in many applications such as semidefinite programming relaxations for combinatorial optimization problems, sparse principal component analysis, and sparse variance unfolding technique for dimension reduction. Our algorithm exploits the structural similarity between semidefinite packing programs … Read more

    Covariance regularization in inverse space

  • Takashi Tsuchiya
  • Genta Ueno
    • Categories Data-Mining, Semi-definite Programming Tags , ,

    This paper proposes to apply Gaussian graphical models to estimate the large-scale normal distribution in the context of data assimilation from a relatively small number of data from the satellite. Data assimilation is a field which fits simulation models to observation data developed mainly in meteorology and oceanography. The optimization problem tends to be huge … Read more

    Graph Realizations Associated with Minimizing the Maximum Eigenvalue of the Laplacian

  • Frank Göring
  • Christoph Helmberg
  • Susanna Reiss
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , , ,

    In analogy to the absolute algebraic connectivity of Fiedler, we study the problem of minimizing the maximum eigenvalue of the Laplacian of a graph by redistributing the edge weights. Via semidefinite duality this leads to a graph realization problem in which nodes should be placed as close as possible to the origin while adjacent nodes … Read more

    Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions

  • Nathan Krislock
  • Henry Wolkowicz
    • Categories Semi-definite Programming Tags , , ,

    The sensor network localization, SNL, problem in embedding dimension r, consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming, SDP, completion … Read more

    A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part II: General Algorithm

  • Takanori Maehara
  • Kazuo Murota
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    An algorithm is proposed for finding the finest simultaneous block-diagonalization of a finite number of square matrices, or equivalently the irreducible decomposition of a matrix *-algebra given in terms of its generators. This extends the approach initiated in Part I by Murota-Kanno-Kojima-Kojima. The algorithm, composed of numerical-linear algebraic computations, does not require any algebraic structure … Read more

    An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems

  • Kim-Chuan Toh
  • Sangwoon Yun
    • Categories Convex Optimization, Data-Mining, Semi-definite Programming Tags , , ,

    The affine rank minimization problem, which consists of finding a matrix of minimum rank subject to linear equality constraints, has been proposed in many areas of engineering and science. A specific rank minimization problem is the matrix completion problem, in which we wish to recover a (low-rank) data matrix from incomplete samples of its entries. … Read more

    Provably Near-Optimal Solutions for Very Large Single-Row Facility Layout Problems

  • Miguel F. Anjos
  • Ginger Yen
    • Categories Applications - Science and Engineering, Global Optimization, Semi-definite Programming Tags , , , ,

    The facility layout problem is a global optimization problem that seeks to arrange a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. This paper is concerned with the single-row facility layout problem (SRFLP), the one-dimensional version of facility layout that is also … Read more

    Classification with Guaranteed Probability of Error

  • Marco C. Campi
    • Categories Data-Mining, Semi-definite Programming, Statistics Tags , , , ,

    We introduce a general-purpose learning machine that we call the “Guaranteed Error Machine”, or GEM, and two learning algorithms, a “real GEM algorithm” and an “ideal GEM algorithm”. The real GEM algorithm is for use in real applications, while the ideal GEM algorithm is introduced as a theoretical tool; however, these two algorithms have identical … Read more

    A convex polynomial that is not sos-convex

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    A multivariate polynomial $p(x)=p(x_1,…,x_n)$ is sos-convex if its Hessian $H(x)$ can be factored as $H(x)= M^T(x) M(x)$ with a possibly nonsquare polynomial matrix $M(x)$. It is easy to see that sos-convexity is a sufficient condition for convexity of $p(x)$. Moreover, the problem of deciding sos-convexity of a polynomial can be cast as the feasibility of … Read more

    Numerical block diagonalization of matrix hBcalgebras with application to semidefinite programming

  • Etienne de Klerk
  • Cristian Dobre
  • Dmitrii V. Pasechnik
    • Categories Semi-definite Programming Tags , , ,

    Semidefinite programming (SDP) is one of the most active areas in mathematical programming, due to varied applications and the availability of interior point algorithms. In this paper we propose a new pre-processing technique for SDP instances that exhibit algebraic symmetry. We present computational results to show that the solution times of certain SDP instances may … Read more