Semi-definite Programming

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

    Convexity in semi-algebraic geometry and polynomial optimization

  • Jean-Bernard Lasserre
    • Categories Convex and Nonsmooth Optimization, Semi-definite Programming

    We review several (and provide new) results on the theory of moments, sums of squares and basic semi-algebraic sets when convexity is present. In particular, we show that under convexity, the hierarchy of semidefinite relaxations for polynomial optimization simplifies and has finite convergence, a highly desirable feature as convex problems are in principle easier to … 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

    The Difference Between 5×5 Doubly Nonnegative and Completely Positive Matrices

  • Kurt M. Anstreicher
  • Samuel Burer
  • Mirjam Duer
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , ,

    The convex cone of $n \times n$ completely positive (CPP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CPP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for $n \le 4$ only, every DNN matrix is CPP. … 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

    Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion

  • Dimitris Bertsimas
  • Xuan Vinh Doan
  • Karthik Natarajan
  • Chung-Piaw Teo
    • Categories Semi-definite Programming, Stochastic Programming

    In this paper, we propose a semidefinite optimization (SDP) based model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of the second-stage random variables is assumed to be chosen from a set of multivariate distributions with known mean and second moment matrix. For the minimax stochastic problem with … 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