On computing the minima of quadratic forms (Preliminary Report)

ABSTRACT

The following problem was recently raised by C. William Gear [1]: Let F(x₁,x₂,...,x_n) = Σ_i≤j a'_ijx_ix_j + Σ_i b_ix_i +c be a quadratic form in n variables. We wish to compute the point x^→(0) = (x₁⁽⁰⁾,...,x_n⁽⁰⁾), at which F achieves its minimum, by a series of adaptive functional evaluations. It is clear that, by evaluating F(x^→) at 1/2(n+1)(n+2)+1 points, we can determine the coefficients a'_ij,b_i,c and thereby find the point x^→(0). Gear's question is, “How many evaluations are necessary?” In this paper, we shall prove that O(n²) evaluations are necessary in the worst case for any such algorithm.

References

1. 1.C. William Gear, private communication.
2. 2.M. O. Rabin, Solving Linear Equations by Means of Scalar Products, in Complexity of Computer Computations, edited by R. E. Miller and J. W. Thatcher, Plenum Press, 1972.
3. 3.I. R. Shafarevich, Basic Algebraic Geometry, Springer Verlag (1974), p. 71.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

      • Theorem proving algorithms

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Numerical differentiation

    • Quadrature