3 Presentations

• 
  11:30 AM - 11:55 AM

  A fresh CP look at mixed-binary QPs: new formulations and relaxations

  • Jianqiang Cheng, presenter, University of Arizona
  • Immanuel Bomze, University of Vienna
  • Peter Dickinson, University of Twente
  • Abdel Lisser, University of Paris-Sud

  Triggered by Burer’s seminal characterization from 2009, many copositive
  reformulations of mixed-binary QPs have been discussed by now.Most of them can be
  used as proper relaxations, if the intractable co(mpletely)positive cones are replaced
  by tractable approximations. While the widely used approximation hierarchies have
  the disadvantage to use positive-semidefinite (psd) matrices of orders which rapidly
  increase with the level of approximation, alternatives focus on the problem of keeping
  psd matrix orders small, with the aim to avoid memory problems in the interior
  point algorithms. This work continues this approach, proposing new reformulations
  and relaxations. Moreover, we provide a thorough comparison of the respective duals
  and establish a monotonicity relation among their duality gaps. We also identify sufficient conditions for strong duality/zero duality gap in some of these formulations and
  generalize some of our observations to general conic problems.

• 
  11:55 AM - 12:20 PM

  Min-Max fractional quadratic over linear problems

  • Paula Amaral, presenter, Dep. Mathematics FCT UNL
  • Immanuel Bomze, University of Vienna

  Fractional programs are in general non-convex programs and exact methods require the existence of good lower bounds. An important feature of completely positive (CP) formulations is that its relaxations give tight lower bounds. In this talk we present completely positive formulations for min-max fractional quadratic over linear problems, with linear and quadratic constraints and study the properties of the doubly positive (DP) relaxations. The fractional min-max problem occurs, among others, in the study of worst-case analysis when different scenarios are under evaluation. Computational experience compare the lower bound obtained by the DP relaxation with the one provided by Baron, and show that for instances that Baron could not solve, if these lower bounds were initially used optimality could be achieved.

• 
  12:20 PM - 12:45 PM

  Trust your data or not - Standard remains Standard (QP)

  • Immanuel Bomze, presenter, University of Vienna
  • Michael Kahr, University of Vienna
  • Markus Leitner, University of Vienna
  • Werner Schachinger, University of Vienna
  • Reinhard Ullrich, University of Vienna

  In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite of its simplicity, this model is quite versatile. Applications are numerous, ranging from the famous Markowitz portfolio problem in Finance, Economics (evolutionary game theory) through Machine Learning (background-foreground clustering in image analysis), biological and social network analysis to other life science applications, e.g. in Population Genetics (selection models) and Ecology (replicator dynamics).

  If the problem data (i.e., the form) are uncertain, most of the usual uncertainty sets do not add complexity to the robust counterpart. On the other hand, it is well known that most probably within this problem class, a generic StQP instance is not too hard to solve as the worst cases are hidden in relatively thin manifolds of the class. These hard instances allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally, which question in turn is closely related to copositive optimization.

  In this study, we improve on existing worst-case lower bounds for the number of strict local solutions by a new technique to construct instances with a rich solution structure, studying the influence of perturbations of a matrix on its pattern. The results obtained along this line may be of independent interest and also may serve to construct test instances for nonlinear solvers.

  To gain insight on typical hard cases and their distribution, we conducted extensive experimental results on potentially hard instance matrices.