semidefinite programming

A Constraint-Reduced Algorithm for Semidefinite Optimization Problems with Superlinear Convergence

  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , ,

    Constraint reduction is an essential method because the computational cost of the interior point methods can be effectively saved. Park and O’Leary proposed a constraint-reduced predictor-corrector algorithm for semidefinite programming with polynomial global convergence, but they did not show its superlinear convergence. We first develop a constraint-reduced algorithm for semidefinite programming having both polynomial global … Read more

    Strong SOCP Relaxations for the Optimal Power Flow Problem

  • Santanu S. Dey
  • Burak Kocuk
  • Xu Andy Sun
    • Categories Applications - Science and Engineering, Global Optimization, Nonlinear Optimization Tags , , ,

    This paper proposes three strong second order cone programming (SOCP) relaxations for the AC optimal power flow (OPF) problem. These three relaxations are incomparable to each other and two of them are incomparable to the standard SDP relaxation of OPF. Extensive computational experiments show that these relaxations have numerous advantages over existing convex relaxations in … Read more

    Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … Read more

    Quantum and classical coin-flipping protocols based on bit-commitment and their point games

  • Ashwin Nayak
  • Jamie Sikora
  • Levent Tunçel
    • Categories Linear Programming, Second-Order Cone Programming, Semi-definite Programming Tags , , , ,

    We focus on a family of quantum coin-flipping protocols based on quantum bit-commitment. We discuss how the semidefinite programming formulations of cheating strategies can be reduced to optimizing a linear combination of fidelity functions over a polytope. These turn out to be much simpler semidefinite programs which can be modelled using second-order cone programming problems. … Read more

    New bounds for the max-hBccut and chromatic number of a graph

  • Renata Sotirov
  • Edwin van Dam
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , , , , ,

    We consider several semidefinite programming relaxations for the max-$k$-cut problem, with increasing complexity. The optimal solution of the weakest presented semidefinite programming relaxation has a closed form expression that includes the largest Laplacian eigenvalue of the graph under consideration. This is the first known eigenvalue bound for the max-$k$-cut when $k>2$ that is applicable to … Read more

    Constrained trace-optimization of polynomials in freely noncommuting variables

  • Igor Klep
  • Janez Povh
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , , , , , ,

    The study of matrix inequalities in a dimension-free setting is in the realm of free real algebraic geometry (RAG). In this paper we investigate constrained trace and eigenvalue optimization of noncommutative polynomials. We present Lasserre’s relaxation scheme for trace optimization based on semidefinite programming (SDP) and demonstrate its convergence properties. Finite convergence of this relaxation … Read more

    An Axiomatic Duality Framework for the Theta Body and Related Convex Corners

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are … Read more

    Mathematical Programming Models Based on Hub Covers in Graph Query Processing

  • Ş. İlker Birbil
  • Kerem Bülbül
  • Belma Yelbay
    • Categories 0-1 Programming, Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    The use of graph databases for social networks, images, web links, pathways and so on, has been increasing at a fast pace and promotes the need for efficient graph query processing on such databases. In this study, we discuss graph query processing — referred to as graph matching — and an inherent optimization problem known … Read more

    On globally solving the maximum weighted clique problem

  • Nam Nguyen Canh
    • Categories Applications - OR and Management Sciences Tags , , , ,

    In this paper, we consider a combinatorial optimization problem, the Maximum Weighted Clique Problem (MWCP), a NP-hard problem. The considered problem is first formulated in the form of binary constrained quadratic program and then reformulated as a Difference Convex (DC) program. A global optimal solution is found by applying DC Algorithm (DCA) in combining with … Read more

    Lov\'{a}sz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

  • S. Bianchi
  • Mariana Escalante
  • Levent Tunçel
  • G. Nasini
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We study the Lov\'{a}sz-Schrijver lift-and-project operator ($\LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $\LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs … Read more