Quadratic functions with exponential number of local maxima (Q1079496): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0167-6377(86)90100-8 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2001988454 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some simplified NP-complete graph problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Roof duality, complementation and persistency in quadratic 0–1 optimization / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic Functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Technical Note—Construction of Difficult Linearly Constrained Concave Minimization Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimization by Simulated Annealing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Minimum cuts and related problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5613011 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5342287 / rank
 
Normal rank

Latest revision as of 14:18, 17 June 2024

scientific article
Language Label Description Also known as
English
Quadratic functions with exponential number of local maxima
scientific article

    Statements

    Quadratic functions with exponential number of local maxima (English)
    0 references
    0 references
    1986
    0 references
    The global maximization of a quadratic function \[ f(x)=\sum^{n}_{i=1}\sum^{n}_{j=i}q_{ij}x_ ix_ j \] over \(B^ n_ 2=\{x:\) \(x_ i\in \{0,1\}\) for \(i=1,...,n\}\) and over \(\bar B^ n_ 2=\{x:\) \(0\leq x_ i\leq 1\) for \(i=1,...,n\}\) is considered. The maximization over \(\bar B^ n_ 2\) is an NP-hard problem. For f convex, the maximization over \(\bar B^ n_ 2\) is equivalent to that over \(B^ n_ 2\). A measure of complexity of algorithms obtaining and analyzing local solutions that these problems possess is proposed. A quadratic function with an exponential \((2^ n)\) number of distinct local maxima is constructed. So, local algorithms for quadratic programming have an exponential worst case time complexity.
    0 references
    global maximization
    0 references
    quadratic function
    0 references
    exponential worst case time complexity
    0 references

    Identifiers