Reinhard Ullrich

The complexity of simple models – a study of worst and typical hard cases for the Standard Quadratic Optimization Problem

  • Immanuel M. Bomze
  • Werner Schachinger
  • Reinhard Ullrich
    • Categories Game Theory, Global Optimization Theory, Quadratic Programming

    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 this simplicity, the nonconvex instances of this problem class allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally. … Read more

    New lower bounds and asymptotics for the cp-rank

  • Immanuel M. Bomze
  • Werner Schachinger
  • Reinhard Ullrich
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    Let $p_n$ denote the largest possible cp-rank of an $n\times n$ completely positive matrix. This matrix parameter has its significance both in theory and applications, as it sheds light on the geometry and structure of the solution set of hard optimization problems in their completely positive formulation. Known bounds for $p_n$ are $s_n=\binom{n+1}2-4$, the current … Read more

    From seven to eleven: completely positive matrices with high cp-rank

  • Immanuel M. Bomze
  • Werner Schachinger
  • Reinhard Ullrich
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We study $n\times n$ completely positive matrices $M$ on the boundary of the completely positive cone, namely those orthogonal to a copositive matrix $S$ which generates a quadratic form with finitely many zeroes in the standard simplex. Constructing particular instances of $S$, we are able to construct counterexamples to the famous Drew-Johnson-Loewy conjecture (1994) for … Read more