15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

Horaire Auteurs Mon horaire

Copositivity and (fractional) polynomial optimization

12 juil. 2017 11h30 – 12h45

Salle: Nancy et Michel-Gaucher

Présidée par Immanuel Bomze

3 présentations

  • 11h30 - 11h55

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

    • Jianqiang Cheng, prés., 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.

  • 11h55 - 12h20

    Min-Max fractional quadratic over linear problems

    • Paula Amaral, prés., 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.

  • 12h20 - 12h45

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

    • Immanuel Bomze, prés., 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.