Linear, Cone and Semidefinite Programming

On Handling Free Variables in Interior-Point Methods for Conic Linear Optimization

  • Miguel F. Anjos
  • Samuel Burer
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We revisit a regularization technique of Meszaros for handling free variables within interior-point methods for conic linear optimization. We propose a simple computational strategy, supported by a global convergence analysis, for handling the regularization. Using test problems from benchmark suites and recent applications, we demonstrate that the modern code SDPT3 modified to incorporate the proposed … Read more

    Central path curvature and iteration-complexity for redundant Klee-Minty cubes

  • Antoine Deza
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We consider a family of linear optimization problems over the n-dimensional Klee-Minty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n-2 … Read more

    New upper bounds for kissing numbers from semidefinite programming

  • Christine Bachoc
  • Frank Vallentin
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases n = 3, 4, 8, … Read more

    Copositivity cuts for improving SDP bounds on the clique number

  • Immanuel M. Bomze
  • Marco Locatelli
  • Florian Frommlet
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , ,

    Adding cuts based on copositive matrices, we propose to improve Lovász’ bound on the clique number and its tightening introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies rapidly increases … Read more

    Polytopes and Arrangements : Diameter and Curvature

  • Antoine Deza
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Linear Programming, Polyhedra Tags , , ,

    We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature. Citation AdvOL-Report #2006/09 Advanced Optimization … Read more

    Semidefinite Programming Based Algorithms for Sensor Network Localization

  • Pratik Biswas
  • Yinyu Ye
  • Tzu-Chen Liang
  • Ta-Chung Wang
    • Categories Applications - Science and Engineering, Multidisciplinary Design Optimization, Semi-definite Programming Tags

    An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite … Read more

    Theory of Semidefinite Programming for Sensor Network Localization

  • Anthony Man-Cho So
  • Yinyu Ye
    • Categories Applications - Science and Engineering, Facility Planning and Design, Semi-definite Programming Tags ,

    We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior–point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we … Read more

    A Path to the Arrow-Debreu Competitive Market Equilibrium

  • Yinyu Ye
    • Categories Complementarity and Variational Inequalities, Game Theory, Linear Programming Tags , ,

    We present polynomial-time interior-point algorithms for solving the Fisher and Arrow-Debreu competitive market equilibrium problems with linear utilities and $n$ players. Both of them have the arithmetic operation complexity bound of $O(n^4\log(1/\epsilon))$ for computing an $\epsilon$-equilibrium solution. If the problem data are rational numbers and their bit-length is $L$, then the bound to generate an … Read more

    Approximating the Radii of Point Sets

  • Kasturi Varadarajan
  • S Venkatesh
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Data-Mining, Semi-definite Programming Tags ,

    We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers $n, d, k$ where $k \le d$, and a set $P$ of $n$ points in $R^d$. The goal is to compute the {\em outer $k$-radius} of $P$, denoted by $\kflatr(P)$, which is the minimum, over all $(d-k)$-dimensional … Read more

    Static-arbitrage bounds on the prices of basket options via linear programming

  • Javier F. Peña
  • Juan Vera
  • Luis F. Zuluaga
    • Categories Applications - OR and Management Sciences, Linear Programming, Semi-infinite Programming Tags , ,

    We show that the problem of computing sharp upper and lower static-arbitrage bounds on the price of a European basket option, given the prices of other similar options, can be cast as a linear program (LP). The LP formulations readily yield super-replicating (sub-replicating) strategies for the upper (lower) bound problem. The dual counterparts of the … Read more