Immanuel M. Bomze

Think co(mpletely )positive ! Matrix properties, examples and a clustered bibliography on copositive optimization

  • Immanuel M. Bomze
  • Werner Schachinger
  • Gabriele Uchida
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Linear, Cone and Semidefinite Programming

    Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing a linear functional over a convex cone subject to linear constraints), namely the cone of all completely positive symmetric nxn matrices, and its … Read more

    Copositivity and constrained fractional quadratic problems

  • Paula Alexandra Amaral
  • Immanuel M. Bomze
  • Joaquim J. Júdice
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Linear, Cone and Semidefinite Programming

    We provide Completely Positive and Copositive Programming formulations for the Constrained Fractional Quadratic Problem (CFQP) and Standard Fractional Quadratic Problem (StFQP). Based on these formulations, Semidefinite Programming (SDP) relaxations are derived for finding good lower bounds to these fractional programs, which are used in a global optimization branch-and-bound approach. Applications of the CFQP and StFQP, … Read more

    Fast population game dynamics for dominant sets and other quadratic optimization problems

  • Immanuel M. Bomze
  • Marcello Pelillo
  • Samuel Rota-Bulo
    • Categories Data-Mining, Game Theory, Quadratic Programming Tags ,

    We propose a fast population game dynamics, motivated by the analogy with infection and immunization processes within a population of “players,” for finding dominant sets, a powerful graph-theoretical notion of a cluster. Each step of the proposed dynamics is shown to have a linear time/space complexity and we show that, under the assumption of symmetric … Read more

    Copositivity detection by difference-of-convex decomposition and omega-subdivision

  • Immanuel M. Bomze
  • Gabriele Eichfelder
    • Categories Linear, Cone and Semidefinite Programming Tags

    We present three new copositivity tests based upon difference-of-convex (d.c.) decompositions, and combine them to a branch-and-bound algorithm of $\omega$-subdivision type. The tests employ LP or convex QP techniques, but also can be used heuristically using appropriate test points. We also discuss the selection of efficient d.c.~decompositions and propose some preprocessing ideas based on the … Read more

    Quadratic factorization heuristics for copositive programming

  • Immanuel M. Bomze
  • Florian Jarre
  • Franz Rendl
    • Categories (Mixed) Integer Linear Programming, Global Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Copositive optimization problems are particular conic programs: extremize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone … Read more

    Building a completely positive factorization

  • Immanuel M. Bomze
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    Using a bordering approach, and building upon an already known factorization of a principal block, we establish sufficient conditions under which we can extend this factorization to the full matrix. Simulations show that the approach is promising also in higher dimensions. Citation Preprint, Univ.of Vienna (2017), submitted Article Download View Building a completely positive factorization

    A note on Burer’s copositive representation of mixed-binary QPs

  • Immanuel M. Bomze
  • Florian Jarre
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming Tags

    In an important paper, Burer recently showed how to reformulate general mixed-binary quadratic optimization problems (QPs) into copositive programs where a linear functional is minimized over a linearly constrained subset of the cone of completely positive matrices. In this note we interpret the implication from a topological point of view, showing that the Minkowski sum … Read more

    Standard Bi-Quadratic Optimization Problems and Unconstrained Polynomial Reformulations

  • Immanuel M. Bomze
  • Liqun Qi
  • Chen Ling
  • Xinzhen Zhang
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory Tags , , , ,

    A so-called Standard Bi-Quadratic Optimization Problem (StBQP) consists in minimizing a bi-quadratic form over the Cartesian product of two simplices (so this is different from a Bi-Standard QP where a quadratic function is minimized over the same set). An application example arises in portfolio selection. In this paper we present a bi-quartic formulation of StBQP, … Read more

    Necessary conditions for local optimality in d.c. programming

  • Immanuel M. Bomze
  • Claude Lemaréchal
    • Categories Constrained Nonlinear Optimization, Unconstrained Optimization

    Using $\eps$-subdifferential calculus for difference-of-convex (d.c.) programming, D\”ur proposed a condition sufficient for local optimality, and showed that this condition is not necessary in general. Here it is proved that whenever the convex part is strongly convex, this condition is also necessary. Strong convexity can always be ensured by changing the given d.c. decomposition slightly. … Read more

    Multi-Standard Quadratic Optimization Problems

  • Immanuel M. Bomze
  • Werner Schachinger
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming

    A Standard Quadratic Optimization Problem (StQP) consists of maximizing a (possibly indefinite) quadratic form over the standard simplex. Likewise, in a multi-StQP we have to maximize a (possibly indefinite) quadratic form over the cartesian product of several standard simplices (of possibly different dimensions). Two converging monotone interior point methods are established. Further, we prove an … Read more