\`x^2+y_1+z_12^34\`
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.

    Citation:

    \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.

    [2]

    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.

    [3]

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

    [4]

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

    [5]

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

    [6]

    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.

    [7]

    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.

    [8]

    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

    [9]

    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.

    [10]

    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.

    [11]

    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.

    [12]

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

    [13]

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

    [14]

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

    [15]

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

    [16]

    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.

    [17]

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

    [18]

    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.

    [19]

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

    [20]

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

    [21]

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

    [22]

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

    [23]

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

    [24]

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

    [25]

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

    [26]

    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.

  • 加载中
SHARE

Article Metrics

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

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return