A parsimonious way of constructing quadratic models from values of the objective function in derivative-free optimization

Abstract:

Let the minimum of F(x−−)F(x_), x−−∈Rnx_∈Rn, be required when first derivatives of FF are not available. We consider iterative methods that employ (n+1)(n+1) values of FF on each iteration, at points in RnRn that allow the values to be interpolated uniquely by a linear polynomial. Let kk be the iteration number, let F(x−−k)F(x_k) be the least of the (n+1)(n+1) function values, let Qk(x−−)Qk(x_), x−−∈Rnx_∈Rn, be the linear polynomial, and let ρkρk be a trust region radius. The basic trust region step from x−−kx_k, say d−−kd_k, is the vector d−−d_ that minimizes Qk(x−−k+d−−)Qk(x_k+d_) subject to ∥d−−∥≤ρk‖d_‖≤ρk. A trust region iteration calculates the new value F(x−−k+d−−k)F(x_k+d_k) of the objective function, the point x−−k+d−−kx_k+d_k replaces one of the current interpolation points, x−−k+1x_k+1 is set to x−−kx_k or x−−k+d−−kx_k+d_k in the case F(x−−k+d−−k)≥F(x−−k)F(x_k+d_k)≥F(x_k) or $F ( \underline{x}_k \!+\! \underline{d}_k ) \!

It may be more efficient, however, to let QkQk be a quadratic polynomial instead of a linear one, but we wish to preserve the advantages in practice and in theory of retaining only n+1n+1 interpolation points. Our theory remains valid if the second derivative matrix ∇2Qk∇2Qk is symmetric, bounded, and otherwise arbitrary for every kk. Then, after choosing ∇2Qk∇2Qk, the current interpolation conditions supply the value Qk(x−−k)Qk(x_k) and the gradient ∇−−Qk(x−−k)∇_Qk(x_k). We consider the following automatic way of obtaining some second derivative information. When an interpolation point is replaced, n+2n+2 values of FF are available. We require the new quadratic to interpolate these values, and the remaining freedom in the new quadratic model is taken up by minimizing the Frobenius norm of the change to ∇2Qk∇2Qk. Also we set ∇2Q1∇2Q1 to the zero matrix. Experiments show that this technique for constructing quadratic models provides major improvements over the use of linear models, both in the total number of function evaluations and in the final accuracy of the optimization calculation.