A derivative-free trust-region algorithm for unconstrained optimization with controlled error
Jun Takaki - Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto, 606-8501,, Japan (email)
Abstract: In this paper, we consider the unconstrained optimization problem under the following conditions: (S1) The objective function is evaluated with a certain bounded error, (S2) the error is controllable, that is, the objective function can be evaluated to any desired accuracy, and (S3) more accurate evaluation requires a greater computation time. This situation arises in many fields such as engineering and financial problems, where objective function values are obtained from considerable numerical calculation or a simulation. Under (S2) and (S3), it seems reasonable to set the accuracy of the evaluation to be low at points far from a solution, and high at points in the neighborhood of a solution. In this paper, we propose a derivative-free trust-region algorithm based on this idea. For this purpose, we consider (i) how to construct a quadratic model function by exploiting pointwise errors and (ii) how to control the accuracy of function evaluations to reduce the total computation time of the algorithm. For (i), we propose a method based on support vector regression. For (ii), we present an updating formula of the accuracy of which is related to the trust-region radius. We present numerical results for several test problems taken from CUTEr and a financial problem of estimating implied volatilities from option prices.
Keywords: Derivative-free method, trust region algorithm, controlled error.
Received: September 2010; Revised: December 2010; Available Online: February 2011.