Invited Session Mon.2.H 2038

Monday, 13:15 - 14:45 h, Room: H 2038

Cluster 4: Conic programming [...]

Nonlinear semidefinite programs and copositive programs


Chair: Florian Jarre



Monday, 13:15 - 13:40 h, Room: H 2038, Talk 1

Michal Kocvara
Introducing PENLAB, a Matlab code for nonlinear conic optimization

Coauthors: Jan Fiala, Michael Stingl


We will introduce a new code PENLAB, an open Matlab implementation and extension of our older PENNON. PENLAB can solve problems of nonconvex nonlinear optimization with standard (vector) variables and constraints, as well as matrix variables and constraints. We will demonstrate its functionality using several nonlinear semidefinite examples.



Monday, 13:45 - 14:10 h, Room: H 2038, Talk 2

Mirjam Dür
Remarks on copositive plus matrices and the copositive plus completion problem

Coauthor: Willemieke van Vliet


A matrix A is called copositive plus if it is copositive and if for x ≥ 0, xT Ax = 0 implies Ax = 0. These matrices play a role in linear complementarity problems (LCPs), since it is well known that Lemke's algorithm can solve LCPs when the matrix involved is copositive plus.
In this talk, we study two issues: first, we discuss properties of the cone of copositive plus matrices. In particular, we formulate an analogous result to the well-known fact that any copositive matrix of order up to four can be represented as a sum of a positive semidefinite and an entrywise nonnegative matrix.
The second problem we are interested in is the copositive plus completion problem: Given a partial matrix, i.e., a matrix where some entries are unspecified, can this partial matrix be completed to a copositive plus matrix by assigning values to the unspecified entries? We answer this question both for the setting where diagonal entries are unspecified, and for the case of unspecified non-diagonal entries.



Monday, 14:15 - 14:40 h, Room: H 2038, Talk 3

Peter James Clair Dickinson
Considering the complexity of complete positivity using the Ellipsoid method

Coauthors: Kurt M. Anstreicher, Samuel Burer, Luuk Gijben


Copositive programming has become a useful tool in dealing with all sorts of optimisation problems. It has however been shown by Murty and Kabadi [Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39, no.2:117-129, 1987] that the strong membership problem for the copositive cone, that is deciding whether or not a given matrix is in the copositive cone, is a co-NP-complete problem. The dual cone to the copositive cone is called the completely positive cone, and, because of this result on the copositive cone, it has widely been assumed that the strong membership problem for this cone would be an NP-complete problem. The proof to this has however been lacking. In order to show that this is indeed true we would need to show that the problem is both an NP-hard problem and a problem in NP. In this talk we use the Ellipsoid Method to show that this is indeed an NP-hard problem and that the weak membership problem for the completely positive cone is in NP (where we use a natural extension of the definition of NP for weak membership problems). It is left as an open question as to whether the strong membership problem itself is in NP.


  Do you need Payday Loans Missouri as soon as possible? But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.