Invited Session Tue.1.H 2053

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

Cluster 9: Global optimization [...]

Convex optimization approaches to polynomial optimization problems


Chair: Miguel F. Anjos



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

Amélie Lambert
Convex reformulations of integer quadratically constrained problems

Coauthors: Alain Billionnet, Sourour Elloumi


We consider a general integer program (QQP) where both the objective function and the constraints are quadratic. We show that the quadratic convex reformulation approach can be extended to that case. This approach consists in designing a program, equivalent to QQP, with a quadratic convex objective function and linear or quadratic convex constraints. The resulting program is then solved by a standard solver. We start by dealing with the objective function. For this, we solve a semi-definite program from which we deduce a reformulation of (QQP) as an equivalent problem (P) having a convex quadratic objective function. We then handle the quadratic constraints of (P). We propose and compare linear and quadratic convex reformulations of these constraints. Finally, we give some numerical results comparing our different approaches.



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

Franz Rendl
Active set methods for convex quadratic optimization with simple bounds

Coauthor: Philipp Hungerländer


A primal-dual active set method for quadratic problems with bound constraints is
presented which extends the infeasible active set approach of Kunisch and Rendl (SIOPT 2003). Based on a guess on the active set, a primal-dual pair is computed that satisfies the first order optimality condition and the complementary condition.
Primal variables outside their bounds are added to the active set until a primal feasible solution is reached.
Then a new active set is generated based on the feasibility information of the dual variables. Strict convexity of the quadratic problem is sufficient for the algorithm to stop after a finite number of steps with an optimal solution. Computational experience indicates that this approach also performs well in practice.


  There are three major facts that should be watched out for in all payday loans in the United States. 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 Without Prescription influence on blood clots.