2001/01/01 by Alexandre Megretski · 42 citations
Mathematics · #Advanced Optimization Algorithms Research #Mathematical Approximation and Integration #Point processes and geometric inequalities #Operator (biology) #Quadratic programming #Quadratic equation #Relaxation (psychology) #Mathematics #Intersection (aeronautics) #Counterexample #Mathematical optimization #Duality (order theory) #Conjecture #Applied mathematics #Discrete mathematics
paper · doi:10.1007/978-3-0348-8362-7_15
published in Birkhäuser Basel eBooks, 365-392
openalex publication_date 2001/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
The paper describes a class of mathematical problems at an intersection of operator theory and combinatorics, and discusses their application in complex system analysis. The main object of study is duality gap bounds in quadratic programming which deals with problems of maximizing quadratic functionals subject to quadratic constraints Such optimization is known to be universal, in the sense that many computationally hard questions can be reduced to quadratic programming On the other hand, it is conjectured that an efficient algorithm of solving general non-convex quadratic programs exactly does not exist. A specific technique of ”relaxation”, which essentially replaces deterministic decision parameters by random variables, is known experimentally to yield high quality approximate solutions in some non-convex quadratic programs arising in engineering applications. However, proving good error bounds for a particular relaxation scheme is usually a challenging mathematical problem. In this paper relaxation techniques of dynamical system analysis will be described. It will be shown how operator theoretic methods can be used to give error bounds for these techniques or to provide counterexamples. On the other hand, it will be demonstrated that some difficult problems of operator theory have equivalent formulations in terms of relaxation bounds in quadratic programming, and can be approached using the insights from combinatorics and system theory. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.