Semi-definite Programming

SFSDP: a Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Hayato Waki
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , ,

    SFSDP is a Matlab package for solving a sensor network localization problem. These types of problems arise in monitoring and controlling applications using wireless sensor networks. SFSDP implements the semidefinite programming (SDP) relaxation proposed in Kim et al. [2009] for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) … Read more

    Semidefinite programming and sums of hermitian squares of noncommutative polynomials

  • Igor Klep
  • Janez Povh
    • Categories Optimization Software Design Principles, Semi-definite Programming Tags , , ,

    An algorithm for finding sums of hermitian squares decompositions for polynomials in noncommuting variables is presented. The algorithm is based on the “Newton chip method”, a noncommutative analog of the classical Newton polytope method, and semide finite programming. Citation I. Klep and J. Povh. Semide nite programming and sums of hermitian squares of noncommutative polynomials. J. Pure … Read more

    Band Gap Optimization of Two-Dimensional Photonic Crystals Using Semidefinite Programming and Subspace Methods

  • Robert M. Freund
  • Han Men
  • Ngoc-Cuong Nguyen
  • Pablo A. Parrilo
  • Jaime Peraire
    • Categories Optimization of Systems modeled by PDEs, Semi-definite Programming Tags , ,

    In this paper, we consider the optimal design of photonic crystal band structures for two-dimensional square lattices. The mathematical formulation of the band gap optimization problem leads to an infinite-dimensional Hermitian eigenvalue optimization problem parametrized by the dielectric material and the wave vector. To make the problem tractable, the original eigenvalue problem is discretized using … Read more

    Trace Norm Regularization: Reformulations, Algorithms, and Multi-task Learning

  • Shuiwang Ji
  • Ting Kei Pong
  • Paul Tseng
  • Jieping Ye
    • Categories Convex Optimization, Data-Mining, Semi-definite Programming Tags , , , , , ,

    We consider a recently proposed optimization formulation of multi-task learning based on trace norm regularized least squares. While this problem may be formulated as a semidefinite program (SDP), its size is beyond general SDP solvers. Previous solution approaches apply proximal gradient methods to solve the primal problem. We derive new primal and dual reformulations of … Read more

    A Hierarchy of Near-Optimal Policies for Multi-stage Adaptive Optimization

  • Dimitris Bertsimas
  • Dan Iancu
  • Pablo A. Parrilo
    • Categories Robust Optimization, Semi-definite Programming, Supply Chain Management Tags , , ,

    In this paper, we propose a new tractable framework for dealing with multi-stage decision problems affected by uncertainty, applicable to robust optimization and stochastic programming. We introduce a hierarchy of polynomial disturbance-feedback control policies, and show how these can be computed by solving a single semidefinite programming problem. The approach yields a hierarchy parameterized by … Read more

    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