15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, July 12 — 14, 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, July 12 — 14, 2017

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

Copositive and completely positive problems

Jul 12, 2017 09:45 AM – 11:00 AM

Location: Nancy et Michel-Gaucher

Chaired by Immanuel Bomze

3 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    09:45 AM - 10:10 AM

    New upper bounds on the kissing number via copositive programming

    • Olga Kuryatnikova, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:10 AM - 10:35 AM

    SPN completable graphs

    • Naomi Shaked-Monderer, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:35 AM - 11:00 AM

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

    • Peter Dickinson, presenter, 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.