15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

Horaire Auteurs Mon horaire

Copositive and completely positive problems

12 juil. 2017 09h45 – 11h00

Salle: Nancy et Michel-Gaucher

Présidée par Immanuel Bomze

3 présentations

  • 09h45 - 10h10

    New upper bounds on the kissing number via copositive programming

    • Olga Kuryatnikova, prés., Tilburg University
    • Juan C. Vera, Tilburg University

    This paper introduces a hierarchy of upper bounds on the kissing number using copositive programming. Recently, it has been shown that the kissing number can be obtained from an infinite dimensional optimization problem over copositive kernels on a sphere. To construct a new semidefinite hierarchy for the kissing number, we extend an existing sdp-based hierarchy for the finite dimensional copositive cone to the infinite dimensional case and exploit symmetry of the sphere. Also, an alternative proof is given to characterize positive definite kernels invariant under automorphisms of the sphere with a given set of fixed points via Jacobi polynomials.

  • 10h10 - 10h35

    SPN completable graphs

    • Naomi Shaked-Monderer, prés., The Max Stern Yezreel Valley College
    • Abraham Berman, Technion - IIT
    • Mirjam Duer, University of Trier
    • Rajesh M Kannan, IIT Kharagpur

    An SPN matrix is a matrix which is the Sum of a Positive semidefinite and a symmetric Nonnegative one.
    We consider the SPN completion problem: Given a partial matrix all of whose fully specified principal submatrices are SPN, can it be completed to an SPN matrix?
    We characterize all the patterns of specified entries (given by a graph) which guarantee existence of such a completion.
    Our result complements known characterizations of PSD-, DNN-, CP- and COP-completable graphs.
    We also show how the characterization of completely positive graphs can be derived from our SPN completion result.

  • 10h35 - 11h00

    The structure of completely positive matrices according to their CP-rank and CP-plus-rank

    • Peter Dickinson, prés., University of Twente
    • Immanuel Bomze, University of Vienna
    • Georg Still, University of Twente

    Important in the study of completely positive matrices is the cp-rank, and here we introduce the closely related cp-plus-rank. Due to the subtle similarities and differences between the cp-plus-rank and the cp-rank, the analysis of the cp-plus-rank is highly useful in the investigation of the completely postive cone. We show numerous topological properties related to the cp-rank and cp-plus-rank, including that generically the cp-plus-rank is equal the cp-rank, and that in the interior of the completely positive cone the set of matrices whose cp-rank and cp-plus-rank both equal a fixed number is an open set.