Semi-definite Programming

Identifying Redundant Linear Constraints in Systems of Linear Matrix Inequality Constraints

  • Shafiu Jibrin
  • Daniel Stover
    • Categories Semi-definite Programming Tags , , ,

    Semidefinite programming has been an interesting and active area of research for several years. In semidefinite programming one optimizes a convex (often linear) objective function subject to a system of linear matrix inequality constraints. Despite its numerous applications, algorithms for solving semidefinite programming problems are restricted to problems of moderate size because the computation time … Read more

    Improved bounds for the symmetric rendezvous search problem on the line

  • Donglei Du
  • Q. Han
  • Juan Vera
  • Luis F. Zuluaga
    • Categories Combinatorial Optimization, Game Theory, Semi-definite Programming Tags , , ,

    A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance apart between the two players is 2. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best … Read more

    Target following algorithms for semidefinite programming

  • Chek Beng Chua
    • Categories Convex Optimization, Semi-definite Programming

    We present a target-following framework for semidefinite programming, which generalizes the target-following framework for linear programming. We use this framework to build weighted path-following interior-point algorithms of three distinct flavors: short-step, predictor-corrector, and large-update. These algorithms have worse-case iteration bounds that parallel their counterparts in linear programming. We further consider the problem of finding analytic … Read more

    Recognizing Underlying Sparsity in Optimization

  • Sunyoung Kim
  • Masakazu Kojima
  • Philippe L. Toint
    • Categories Combinatorial Optimization, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem’s functions can be improved by performing a nonsingular linear transformation in the space corresponding … Read more

    New Korkin-Zolotarev Inequalities

  • R. A. Pendavingh
  • S. H. M. van Zwam
    • Categories Applications - Science and Engineering, Other Topics, Semi-definite Programming Tags , , , ,

    Korkin and Zolotarev showed that if $$\sum_i A_i(x_i-\sum_{j>i} \alpha_{ij}x_j)^2$$ is the Lagrange expansion of a Korkin–Zolotarev reduced positive definite quadratic form, then $A_{i+1}\geq \frac{3}{4} A_i$ and $A_{i+2}\geq \frac{2}{3}A_i$. They showed that the implied bound $A_{5}\geq \frac{4}{9}A_1$ is not attained by any KZ-reduced form. We propose a method to optimize numerically over the set of Lagrange … Read more

    Optimization of univariate functions on bounded intervals by interpolation and semidefinite programming

  • Etienne de Klerk
  • Dick den Hertog
  • Gamal Elabwabi
    • Categories Global Optimization, Nonlinear Optimization, Semi-definite Programming Tags , ,

    We consider the problem of minimizing a univariate, real-valued function f on an interval [a,b]. When f is a polynomial, we review how this problem may be reformulated as a semidefinite programming (SDP) problem, and review how to extract all global minimizers from the solution of the SDP problem. For general f, we approximate the … Read more

    Convergent SDP-relaxations in polynomial optimization with sparsity

  • Jean-Bernard Lasserre
    • Categories Global Optimization Theory, Semi-definite Programming

    We consider a polynomial programming problem P on a compact basic semi-algebraic set K described by m polynomial inequalities $g_j(X)\geq0$, and with polynomial criterion $f$. We propose a hierarchy of semidefinite relaxations in the spirit those of Waki et al. [9]. In particular, the SDP-relaxation of order $r$ has the following two features: (a) The … Read more

    On the Quality of a Semidefinite Programming Bound for Sparse Principal Component Analysis

  • Laurent El Ghaoui
    • Categories Robust Optimization, Semi-definite Programming, Statistics Tags , , ,

    We examine the problem of approximating a positive, semidefinite matrix $\Sigma$ by a dyad $xx^T$, with a penalty on the cardinality of the vector $x$. This problem arises in sparse principal component analysis, where a decomposition of $\Sigma$ involving sparse factors is sought. We express this hard, combinatorial problem as a maximum eigenvalue problem, in … Read more

    Generating and Measuring Instances of Hard Semidefinite Programs, SDP

  • Hua Wei
  • Henry Wolkowicz
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal-dual strictly complementary optimal solution pair. On the other hand, there exists Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if … Read more

    A Note on Sparse SOS and SDP Relaxations for Polynomial Optimization Problems over Symmetric Cones

  • Masakazu Kojima
  • Masakazu Muramatsu
    • Categories Constrained Nonlinear Optimization, Global Optimization, Semi-definite Programming Tags , , , , , ,

    This short note extends the sparse SOS (sum of squares) and SDP (semidefinite programming) relaxation proposed by Waki, Kim, Kojima and Muramatsu for normal POPs (polynomial optimization problems) to POPs over symmetric cones, and establishes its theoretical convergence based on the recent convergence result by Lasserre on the sparse SOS and SDP relaxation for normal … Read more