Invited Session Tue.1.H 2038

Tuesday, 10:30 - 12:00 h, Room: H 2038

Cluster 4: Conic programming [...]

New advances in conic programming


Chair: Cristian Dobre



Tuesday, 10:30 - 10:55 h, Room: H 2038, Talk 1

Julia Sponsel
On standard quadratic optimization problems


Many NP-hard problems can be reformulated as copositive programs, i.e., linear optimization problems over the copositive cone. The difficulty then lies in the cone constraint.
Testing copositivity of a given matrix~Q is a co-NP-complete problem which can be stated as a standard quadratic optimization problem of the following form
min & xT Q x \
s.t. & eT x = 1 \
& x ≥ 0  .
The matrix~Q is copositive if and only if the optimal value of~(StQP) is nonnegative.
We consider relaxations of this problem and the case where~Q is a 5× 5-matrix which is of special interest, since there are copositive 5×5-matrices which cannot be decomposed into the sum of a positive semidefinite and a nonnegative matrix whereas this is possible for every copositive n× n-matrix with n ≤ 4.



Tuesday, 11:00 - 11:25 h, Room: H 2038, Talk 2

Cristian Dobre
Infinite dimensional semidefinite programming

Coauthors: Mirjam Dür, Frank Vallentin


In this talk we investigate the infinite dimensional analogue of the primal and dual semidefinite matrix cones. Whereas in the finite case the cone of positive semidefinite matrices is self-dual this is no longer true in infinite dimensions. We introduce the suitable infinite dimensional objects, formulate the pair of primal-dual semidefinite programs and characterize the extremal rays of the dual infinite semidefinite cone. The technique we use employs the theory of reproducing kernels. Applying the same technique to the finite case gives a new proof and interesting new insights on the extremal semidefinite matrices.



Tuesday, 11:30 - 11:55 h, Room: H 2038, Talk 3

Juan C. Vera
Exploiting symmetry in copositive programs

Coauthor: Cristian Dobre


We study the solution of copositive programs using a sequence of improving relaxations, as the ones used by Gaddar-Vera-Anjos for polynomial programs. This method consists of using interactively a master-subproblem scheme; the master solves a conic-relaxation of the original problem, while the subproblem improves the cone used in the relaxation using dual information from the master.
We show how symmetry of the original copositive formulation can be used to reduce both the master and subproblem. To reduce the master, techniques to exploit symmetry in semidefinite programming - which are becoming standard nowadays - are used; reducing the subproblem requires exploding the symmetry of Polya-like representations for copositive polynomials in a novel manner.


  Payday Loans In Michigan. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.