Optimization Online


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

Immanuel Bomze(immanuel.bomze***at***univie.ac.at)
Werner Schachinger(werner.schachinger***at***univie.ac,at)
Reinhard Ullrich(reinhard.ullrich***at***univie.ac.at)

Abstract: 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. In this study, we improve on existing lower bounds for the number of strict local solutions by a new technique to construct instances with a rich solution structure. Furthermore we provide extensive case studies where the system of supports (the so-called pattern) of solutions are analyzed in detail. Note that by naive simulation, in accordance to theory, most of the interesting patterns would not be encountered, since random instances have, with a high probability, quite sparse solutions (with singleton or doubleton supports), and likewise their expected numbers are considerably lower than in the worst case. Hence instances with a rich solution pattern are rather rare. On the other hand, by concentrating on (thin) subsets of promising instances, we are able to give an empirical answer on the size distribution of supports of strict local solutions to the StQP and their patterns, complementing average-case analysis of this NP-hard problem class.

Keywords: Local Solutions; Quadratic Optimization; Evolutionary Stability; Global Optimization; Replicator Dynamics; Selection Stability

Category 1: Global Optimization (Theory )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Other Topics (Game Theory )

Citation: Preprint, ISOR, University of Vienna, submitted

Download: [PDF]

Entry Submitted: 05/18/2016
Entry Accepted: 05/19/2016
Entry Last Modified: 05/18/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society