Numerical Algebra, Control and Optimization (NACO)

A derivative-free trust-region algorithm for unconstrained optimization with controlled error

Pages: 117 - 145, Volume 1, Issue 1, March 2011      doi:10.3934/naco.2011.1.117

       Abstract        References        Full Text (559.7K)       Related Articles       

Jun Takaki - Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto, 606-8501,, Japan (email)
Nobuo Yamashita - 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.
Mathematics Subject Classification:  Primary: 90C56; Secondary: 90C30.

Received: September 2010;      Revised: December 2010;      Available Online: February 2011.