Invited Session Tue.3.MA 005

Tuesday, 15:15 - 16:45 h, Room: MA 005

Cluster 14: Mixed-integer nonlinear programming [...]

Convex relaxations for nonconvex optimization problems


Chair: Jeff Linderoth



Tuesday, 15:15 - 15:40 h, Room: MA 005, Talk 1

Kurt Anstreicher
Second-order-cone constraints for extended trust-region subproblems

Coauthor: Sam Burer


The classical trust-region subproblem (TRS) minimizes a nonconvex quadratic objective over the unit ball. We consider extensions of TRS having additional constraints. It is known that TRS, and the extension of TRS that adds a single linear inequality, both admit convex programming representations. We show that when two parallel linear inequalities are added to
TRS, the resulting nonconvex problem has an exact convex representation as a semidefinite programming (SDP) problem with additional linear and second-order-cone constraints. For the case where an additional ellipsoidal constraint is added to TRS, resulting in the well-known "two trust-region
subproblem'' (TTRS), we describe a new relaxation including second-order-cone constraints that significantly strengthens the usual SDP relaxation. Numerical experiments show that the strengthened relaxation provides an exact solution of TTRS in most instances, although the theoretical complexity of TTRS
remains an open problem.



Tuesday, 15:45 - 16:10 h, Room: MA 005, Talk 2

Jeff Linderoth
Solving mixed integer polynomial optimization problems with MINOTAUR

Coauthors: Jim Luedtke, Ashutosh Mahajan, Mahdi Namazifar


We study methods for building polyhedral relaxations of multilinear
terms that arise in nonconvex mixed integer optimization problems.
The goal is to obtain a formulation that is more compact than the
convex hull formulation, but yields tighter relaxations than the
standard McCormick relaxation. We present computational results for an
approach based on grouping the variables into subsets that cover all
multilinear terms in the problem. The approach is combined with
additional reformulation techniques and spatial branching in the
software framework MINOTAUR to produce a solver for mixed integer
polynomial optimization problems.



Tuesday, 16:15 - 16:40 h, Room: MA 005, Talk 3

Jon Lee
Global optimization of indefinite quadratics


I will talk on some methodology for global optimization of indefinite quadratics.


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Buy Cialis is the one that definitely differs from all other products.