semidefinite programming

Strange Behaviors of Interior-point Methods for Solving Semidefinite Programming Problems in Polynomial Optimization

  • Masakazu Muramatsu
  • Hayato Waki
  • Maho Nakata
    • Categories Optimization Software and Modeling Systems, Semi-definite Programming Tags , ,

    We observe that in a simple one-dimensional polynomial optimization problem (POP), the `optimal’ values of semidefinite programming (SDP) relaxation problems reported by the standard SDP solvers converge to the optimal value of the POP, while the true optimal values of SDP relaxation problems are strictly and significantly less than that value. Some pieces of circumstantial … Read more

    A New Full-Newton step (n)$ Infeasible Interior-Point Algorithm for Semidefinite Optimization

  • Hossein Mansouri
  • Cornelis Roos
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed an efficient primal-dual infeasible interior-point algorithm with full Newton steps for linear optimization problems. In this paper we extend the algorithm to semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence … Read more

    A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with (\sqrt{n}\log{\frac{{\rm Tr}(X^0S^0)}{\epsilon}})$ iteration complexity

  • Yang Li
  • Tamás Terlaky
    • Categories Semi-definite Programming Tags , , ,

    In this paper, we extend the Ai-Zhang direction to the class of semidefinite optimization problems. We define a new wide neighborhood $\N(\tau_1,\tau_2,\eta)$ and, as usual, we utilize symmetric directions by scaling the Newton equation with special matrices. After defining the “positive part” and the “negative part” of a symmetric matrix, we solve the Newton equation … Read more

    Lower bounds for approximate factorizations via semidefinite programming

  • Erich Kaltofen
  • Kartik Krishnan Sivaramakrishnan
  • Bin Li
  • Zhengfeng Yang
  • Lihong Zhi
    • Categories Semi-definite Programming Tags , ,

    The problem of approximately factoring a real or complex multivariate polynomial $f$ seeks minimal perturbations $\Delta f$ to the coefficients of the input polynomial $f$ so that the deformed polynomial $f + \Delta f$ has the desired factorization properties. Efficient algorithms exist that compute the nearest real or complex polynomials that has non-trivial factors. (see … Read more

    Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices based on Semidefinite Programming

  • Hans D Mittelmann
  • Jiming Peng
    • Categories Applications - OR and Management Sciences, Semi-definite Programming Tags , , ,

    Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes … Read more

    Copositive programming motivated bounds on the stability and the chromatic numbers

  • Igor Dukanovic
  • Franz Rendl
    • Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , ,

    The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the … Read more

    A Newton-CG Augmented Lagrangian Method for Semidefinite Programming

  • Defeng Sun
  • Kim-Chuan Toh
  • Xinyuan Zhao
    • Categories Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive … Read more

    Parallel implementation of a semidefinite programming solver based on CSDP on a distributed memory cluster

  • Etienne de Klerk
  • Ivan D. Ivanov
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    In this paper we present the algorithmic framework and practical aspects of implementing a parallel version of a primal-dual semidefinite programming solver on a distributed memory computer cluster. Our implementation is based on the CSDP solver and uses a message passing interface (MPI), and the ScaLAPACK library. A new feature is implemented to deal with … Read more

    Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes

  • Miguel F. Anjos
  • Anthony Vannelli
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , , ,

    This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more

    Lower Bounds for Measurable Chromatic Numbers

  • Christine Bachoc
  • Fernando Mário de Oliveira Filho
  • Frank Vallentin
  • Gabriele Nebe
    • Categories Semi-definite Programming Tags , , , ,

    The Lov\’asz theta function provides a lower bound for the chromatic number of finite graphs based on the solution of a semidefinite program. In this paper we generalize it so that it gives a lower bound for the measurable chromatic number of distance graphs on compact metric spaces. In particular we consider distance graphs on … Read more