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

 

Abstract:
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
\begin{equation}
\begin{array}{cl}
min & xT Q x \
s.t. & eT x = 1 \
& x ≥ 0  .
\end{array}
\tag{StQP}
\end{equation}
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

 

Abstract:
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

 

Abstract:
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.

 

  Today, Ohio Loans Online are legitimate, but there are illegal transactions that are still on the rise. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.