Abstracts: Michael Powell
How many function values are sufficient to estimate the least value of a quadratic function
Let the least value of a strictly convex quadratic function of n variables be required, the function being specified by a "black box" that returns its value for any vector of variables. It is elementary to solve the problem using (n+1)(n+2)/2 function values, because then there are enough data to define the function completely. Numerical experiments with the NEWUOA software of the author, however, suggest that the position of the minimum in the space of the variables can be estimated to high accuracy using only of magnitude n function values when n is large. Some numerical results that give this conclusion will be presented.
On each iteration of NEWUOA, an approximation to the second derivative matrix of the "black box" objective function is updated, using a version of the "symmetric Broyden formula", which has the property that the Frobenius norms of the errors of these approximations decrease monotonically as the iterations proceed. The numerical experiments with large n show, however, that the Frobenius norm of the error at the end of the calculation is not much less than its initial value. Therefore another updating procedure is going to be investigated during the 4 months between the writing of this abstract and the conference. It gives attention not only to changes in second derivatives but also to changes in first derivatives. The findings of this new work will be reported too.