The Complexity of Simple Models—A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem

DOI10.1287/moor.2017.0877zbMath1440.90042OpenAlexW2762341112MaRDI QIDQ5219559

Werner Schachinger, Immanuel M. Bomze, Reinhard Ullrich

Publication date: 12 March 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2017.0877

zbMATH Keywords

global optimizationevolutionary stabilityreplicator dynamicsquadratic optimizationlocal solutionsselection stability

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Population dynamics (general) (92D25) Evolutionary games (91A22)

Related Items (12)

Chris Cannings: a life in games ⋮ Constructing patterns of (many) ESSs under support size control ⋮ Maximization of homogeneous polynomials over the simplex and the sphere: structure, stability, and generic behavior ⋮ The smallest mono-unstable convex polyhedron with point masses has 8 faces and 11 vertices ⋮ On sparsity of the solution to a random quadratic optimization problem ⋮ On the algebraic structure of the copositive cone ⋮ Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations ⋮ A new branch-and-bound algorithm for standard quadratic programming problems ⋮ Building a completely positive factorization ⋮ Hessian Barrier Algorithms for Linearly Constrained Optimization Problems ⋮ Two-stage stochastic standard quadratic optimization ⋮ A study on sequential minimal optimization methods for standard quadratic problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse solutions to random standard quadratic optimization problems
• From seven to eleven: completely positive matrices with high cp-rank
• Infection and immunization: a new class of evolutionary game dynamics
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• Well supported approximate equilibria in bimatrix games
• On the support size of stable strategies in random games
• Quadratic programming with one negative eigenvalue is NP-hard
• Game theoretical foundations of evolutionary stability
• On standard quadratic optimization problems
• Detecting all evolutionarily stable strategies
• Sequential methods for generating patterns of ESS's
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• ESS patterns: Adding pairs to an ESS
• Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects
• New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and Extensions
• New Lower Bounds and Asymptotics for the cp-Rank
• Models of animal conflict
• On the number of local maxima of a constrained quadratic form
• Evolutionary Games and Population Dynamics
• Algorithms and Computation
• On cliques in graphs

This page was built for publication: The Complexity of Simple Models—A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem