Linear, Cone and Semidefinite 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

    Copositive programming motivated bounds on the stability and the chromatic number

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

    The Lovasz 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 Lovasz theta number toward the … 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

    An inexact primal-dual path following algorithm for convex quadratic SDP

  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose primal-dual path-following Mehrotra-type predictor-corrector methods for solving convex quadratic semidefinite programming (QSDP) problems of the form: $\min_{X} \{ \frac{1}{2} X\bullet {\cal Q}(X) + C\bullet X : {\cal A} (X) = b, X\succeq 0\}$, where ${\cal Q}$ is a self-adjoint positive semidefinite linear operator on ${\cal S}^n$, $b\in R^m$, and ${\cal A}$ is a … Read more

    Robust Semidefinite Programming Approaches for Sensor Network Localization with Anchors

  • Nathan Krislock
  • Veronica Piccialli
  • Henry Wolkowicz
    • Categories Applications - OR and Management Sciences, Civil and Environmental Engineering, Linear, Cone and Semidefinite Programming Tags , , , , ,

    We derive a robust primal-dual interior-point algorithm for a semidefinite programming, SDP, relaxation for sensor localization with anchors and with noisy distance information. The relaxation is based on finding a Euclidean Distance Matrix, EDM, that is nearest in the Frobenius norm for the known noisy distances and that satisfies given upper and lower bounds on … 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

    Exploiting Equalities in Polynomial Programming

  • Javier F. Peña
  • Juan Vera
  • Luis F. Zuluaga
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    We propose a novel solution approach for polynomial programming problems with equality constraints. By means of a generic transformation, we show that solution schemes for the (typically simpler) problem without equalities can be used to address the problem with equalities. In particular, we propose new solution schemes for mixed binary programs, pure 0-1 quadratic programs, … Read more

    Implementation of Warm-Start Strategies in Interior-Point Methods for Linear Programming in Fixed Dimension

  • Elizabeth John
  • E. Alper Yildirim
    • Categories Linear Programming Tags , , ,

    We implement several warm-start strategies in interior-point methods for linear programming (LP). We study the situation in which both the original LP instance and the perturbed one have exactly the same dimensions. We consider different types of perturbations of data components of the original instance and different sizes of each type of perturbation. We modify … 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