Invited Session Tue.2.H 2053

Tuesday, 13:15 - 14:45 h, Room: H 2053

Cluster 9: Global optimization [...]

Rigorous global optimization


Chair: Arnold Neumaier



Tuesday, 13:15 - 13:40 h, Room: H 2053, Talk 1

Hermann Schichl
Balanced rigorous relaxation methods in global optimization

Coauthors: Mihaly Cs Markot, Arnold Neumaier


Relaxations are an important tool for solving global optimization problems. Linear and more general convex relaxations are most commonly employed in global optimization algorithms. We present a new relaxation scheme for mixed integer nonlinear programs which balances the dimension of the relaxed problem with its enclosure properties and apply it to generate LP and MIP relaxations of a factorable global optimization problem as well as convex QP and QCQP relaxations.
We generate these relaxations by analyzing the structure of the operational directed acyclic graph of the problem and use a combination of local relaxation at a node of the graph and slope based relaxation methods working on subgraphs. This allows to limit the size of the relaxation, hereby reducing the computational effort for the solution of the relaxations during the branch and bound process.



Tuesday, 13:45 - 14:10 h, Room: H 2053, Talk 2

Ferenc Domes
Finding global robust solutions of robust quadratic optimization problems

Coauthor: Alexandre Goldsztejn


In our talk we discuss finding global robust solutions of robust optimization problems having a quadratic cost function and quadratic inequality constraints. The uncertainties in the constraint coefficients are represented using either universal or existential quantified parameters and interval parameter domains. This approach allows to model non-controlled uncertainties by using universally quantified parameters and controlled uncertainties by using existentially quantified parameters. While existentially quantified parameters could be equivalently considered as additional variables, keeping them as parameters allows maintaining the quadratic problem structure, which is essential for our algorithm.
The branch and bound algorithm we present handles both universally and existentially quantified parameters in a homogeneous way without branching on their domains, and uses some dedicated numerical constraint programming techniques for finding the robust, global solution. The algorithm’s worst-case complexity is exponential with respect to the
number of variables only, even in the case of many and/or large parameters uncertainties.



Tuesday, 14:15 - 14:40 h, Room: H 2053, Talk 3

Arnold Neumaier
Projective methods for constraint satisfaction and global optimization

Coauthors: Ferenc Domes, Mihaly Markot, Hermann Schichl


Many constraint satisfaction problems and global optimization problems
contain some unbounded variables. Their solution by branch and bound
methods poses special challenges as the search region is infinitely
extended. Most branch and bound solvers add artificial bounds to make
the problem bounded, or require the user to add these. However, if
these bounds are too small, they may exclude a solution, while when
they are too large, the search in the resulting huge but bounded region
may be very inefficient. Moreover, global solvers that provide a
rigorous guarantee cannot accept such artificial bounds.
We present methods based on compactification and projective geometry
to cope with the unboundedness in a rigorous manner. Two different
versions of the basic idea, namely (i) projective constraint
propagation and (ii) projective transformation of the variables,
are implemented in the rigorous global solvers COCONUT and GloptLab.
Numerical tests demonstrate the capability of the new technique,
combined with standard pruning methods, to rigorously solve unbounded
global problems.


  In particular, Texas Payday Loans can cater to the needs of its residents. If you have already decided to take Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.