Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C56; Secondary: 90C30.


    \begin{equation} \\ \end{equation}
  • [1]

    I. Bongartz, A. R. Conn, N. I. M. Gould and Ph. L. Toint, CUTE: Constrained and unconstrained testing environment, ACM Transactions on Mathematical Software, 21 (1995), 123-160.doi: 10.1145/200979.201043.


    A. J. Booker, J. E. Dennis, P. D. Frank, D. B. Serafini, V. Torczon and M. W. Trosset, A rigorous framework for optimization of expensive functions by surrogates, Structural and Multidisciplinary Optimization, 17 (1999), 1-13.


    T. D. Choi and C. T. Kelley, Superlinear Convergence and Implicit Filtering, SIAM Journal on Optimization, 10 (2000), 1149-1162.doi: 10.1137/S1052623499354096.


    B. Colson, P. Marcotte and G. Savard, Bilevel programming: A survey, 4OR: A Quarterly Journal of Operations Research, 3 (2005), 87-107.


    A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods,'' SIAM, Philadelphia, 2000.doi: 10.1137/1.9780898719857.


    A. R. Conn and Ph. L. Toint, An algorithm using quadratic interpolation for unconstrained derivative free optimization, in "Nonlinear Optimization and Applications,'' Plenum Publishing, (1996), 27-47.


    A. R. Conn, K. Scheinberg and Ph. L. Toint, A derivative free optimization algorithm in practice, the American Institute of Aeronautics and Astronautics Conference, St Louis, 1998.


    A. R. Conn, K. Scheinberg and Ph. L. TointA derivative free optimization method via support vector machines, 1999. Available from: www.cas.mcmaster.ca/ oplab/seminar/conn/conn_deriv_free.ps


    A. R. Conn, K. Scheinberg and Ph. L. Toint, On the convergence of derivative-free methods for unconstrained optimization, in "Approximation Theory and Optimization,'' Cambridge University Press, (1997), 83-108.


    A. R. Conn, K. Scheinberg and L. N. Vicente, Geometry of interpolation sets in derivative free optimization, Mathematical Programming, 111 (2008), 141-172.doi: 10.1007/s10107-006-0073-5.


    A. R. Conn, K. Scheinberg and L. N. Vicente, Geometry of sample sets in derivative free optimization: Polynomial regression and underdetermined interpolation, IMA Journal of Numerical Analysis, 28 (2008), 721-748.doi: 10.1093/imanum/drn046.


    C. Cox and M. Rubinstein, "Option Markets,'' Prentice-Hall, 1985.


    N. Cristianini and J. Shawe-Taylor, "An Introduction to Support Vector Machines and Other Kernel-based Methods,'' Cambridge University Press, Cambridge, UK, 2000.


    J. E. Dennis and V. Torczon, Direct search methods on parallel machines, SIAM Journal on Optimization, 1 (1991), 448-474.doi: 10.1137/0801027.


    R. A. Fisher, "The Design of Experiments,'' Oliver and Boyd Ltd., 1951.


    P. Gilmore and C. T. Kelley, An implicit filtering algorithm for optimization of functions with many local minima, SIAM Journal on Optimization, 5 (1995), 269-285.doi: 10.1137/0805015.


    B. Karasözen, Survey of trust-region derivative free optimization methods, Journal of Industrial and Management Optimization, 3 (2007), 321-334.


    T. G. Kolda, R. M. Lewis and V. Torzcon, Optimization by direct search: new perspectives of some classical and modern methods, SIAM Review, 45 (2003), 385-482.doi: 10.1137/S003614450242889.


    J. A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, 7 (1965), 308-313.


    J. Nocedal and S. J. Wright, "Numerical Optimization,'' Springer-Verlag, New York, 1999.doi: 10.1007/b98874.


    M. J. D. Powell, Trust region methods that employ quadratic interpolation to the objective function, Presentation at the 5th SIAM Conference on Optimization, 1996.


    M. J. D. Powell, UOBYQA: unconstrained optimization by quadratic approximation, Mathematical Programming, 92 (2002), 555-582.doi: 10.1007/s101070100290.


    J. A. Tilley, Valuing American options in a path simulation model, Transactions of the Society of Actuaries, 45 (1993), 83-104.


    V. Torczon, On the convergence of the multidirectional search algorithm, SIAM Journal on Optimization, 1 (1991), 123-145.doi: 10.1137/0801010.


    D. Winfield, "Function and Functional Optimization by Interpolation in Data Tables,'' PhD thesis, Harvard University in Cambridge, 1969.


    D. Winfield, Functional minimization by interpolation in a data table, Journal of the Institute of Mathematics and its Applications, 12 (1973), 339-347.doi: 10.1093/imamat/12.3.339.

  • 加载中

Article Metrics

HTML views() PDF downloads(89) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint