Seminar More@DIAG
When: Friday, May 25th, 2012, 10:30 - 12:30
Where: Aula Magna - DIAG - Via Ariosto 25, Roma
Speaker: Christoph Buchheim - TU Dortmund (10:30-11:15)
Title: Dual Bounds from Nonconvex Relaxations of Discrete Quadratic Optimization Problems
Speaker: Francisco Facchinei - Sapienza Universita` di Roma (11:30-12:15)
Title: Distributed algorithms for the solution of (generalized) Nash equilibrium problems
Serie: DIAG Lunch Seminars on Management , Operations Research, and Economics of S&T (Science and Technology) - more@DIAG
Abstract (Christoph Buchheim):
Minimizing a quadratic function over integer variables is an NP-hard problem in general. This remains true even if the objective function is convex and all variables are unbounded or binary. In our talk, we present a branch-and-bound approach that turns out to be particularly effective for problems with small variable domains. Both for convex and non-convex subproblems, dual bounds are computed by minimizing the objective function over the boundary of certain axis-parallel ellipsoids. After a suitable preprocessing, these dual bounds can be computed very efficiently, yielding a fast algorithm for ternary quadratic optimization. A similar approach can be used to address combinatorial optimization problems with quadratic objective functions.
Abstract (Francisco Facchinei):
The talk is divided into two parts. In the first, introductory part the (generalized) Nash equilibrium problem is presented and an overview of recent results related to their numerical solution is discussed. The second part is devoted to study of (distributed) algorithms for the solution of the "Nash selection problem", extending and unifying several cases considered in the first part. Applications will be presented.
Serie: DIAG Lunch Seminars on Management, Operations Research, and Economics of Science&Technology