American Institute of Mathematical Sciences

Advanced
2011, 1(1): 117-145. doi: 10.3934/naco.2011.1.117

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

Jun Takaki 1, and  Nobuo Yamashita 2,

1. 

Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto, 606-8501,, Japan
2. 

Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto, 606-8501

Received  September 2010 Revised  December 2010 Published  February 2011

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: controlled error., trust region algorithm, Derivative-free method.
Mathematics Subject Classification: Primary: 90C56; Secondary: 90C3.
Citation: Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117
References:
[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.  doi: 10.1145/200979.201043.  Google Scholar

[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.   Google Scholar

[3]

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

[4]

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

[5]

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

[6]

A. R. Conn and Ph. L. Toint, An algorithm using quadratic interpolation for unconstrained derivative free optimization,, in, (1996), 27.   Google Scholar

[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, (1998).   Google Scholar

[8]

A. R. Conn, K. Scheinberg and Ph. L. Toint, A derivative free optimization method via support vector machines,, 1999. Available from: , ().   Google Scholar

[9]

A. R. Conn, K. Scheinberg and Ph. L. Toint, On the convergence of derivative-free methods for unconstrained optimization,, in, (1997), 83.   Google Scholar

[10]

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

[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.  doi: 10.1093/imanum/drn046.  Google Scholar

[12]

C. Cox and M. Rubinstein, "Option Markets,'', Prentice-Hall, (1985).   Google Scholar

[13]

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

[14]

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

[15]

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

[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.  doi: 10.1137/0805015.  Google Scholar

[17]

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

[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.  doi: 10.1137/S003614450242889.  Google Scholar

[19]

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

[20]

J. Nocedal and S. J. Wright, "Numerical Optimization,'', Springer-Verlag, (1999).  doi: 10.1007/b98874.  Google Scholar

[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).   Google Scholar

[22]

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

[23]

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

[24]

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

[25]

D. Winfield, "Function and Functional Optimization by Interpolation in Data Tables,'', PhD thesis, (1969).   Google Scholar

[26]

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

show all references

References:
[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.  doi: 10.1145/200979.201043.  Google Scholar

[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.   Google Scholar

[3]

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

[4]

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

[5]

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

[6]

A. R. Conn and Ph. L. Toint, An algorithm using quadratic interpolation for unconstrained derivative free optimization,, in, (1996), 27.   Google Scholar

[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, (1998).   Google Scholar

[8]

A. R. Conn, K. Scheinberg and Ph. L. Toint, A derivative free optimization method via support vector machines,, 1999. Available from: , ().   Google Scholar

[9]

A. R. Conn, K. Scheinberg and Ph. L. Toint, On the convergence of derivative-free methods for unconstrained optimization,, in, (1997), 83.   Google Scholar

[10]

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

[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.  doi: 10.1093/imanum/drn046.  Google Scholar

[12]

C. Cox and M. Rubinstein, "Option Markets,'', Prentice-Hall, (1985).   Google Scholar

[13]

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

[14]

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

[15]

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

[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.  doi: 10.1137/0805015.  Google Scholar

[17]

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

[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.  doi: 10.1137/S003614450242889.  Google Scholar

[19]

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

[20]

J. Nocedal and S. J. Wright, "Numerical Optimization,'', Springer-Verlag, (1999).  doi: 10.1007/b98874.  Google Scholar

[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).   Google Scholar

[22]

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

[23]

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

[24]

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

[25]

D. Winfield, "Function and Functional Optimization by Interpolation in Data Tables,'', PhD thesis, (1969).   Google Scholar

[26]

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

[1]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169
[2]

Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial & Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321
[3]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial & Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319
[4]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030
[5]

Gaohang Yu. A derivative-free method for solving large-scale nonlinear systems of equations. Journal of Industrial & Management Optimization, 2010, 6 (1) : 149-160. doi: 10.3934/jimo.2010.6.149
[6]

Dong-Hui Li, Xiao-Lin Wang. A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 71-82. doi: 10.3934/naco.2011.1.71
[7]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[8]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223
[9]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237
[10]

Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919
[11]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309
[12]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
[13]

Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070
[14]

Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041
[15]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A socp relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019104
[16]

Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117
[17]

Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143
[18]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[19]

Orazio Muscato, Wolfgang Wagner. A stochastic algorithm without time discretization error for the Wigner equation. Kinetic & Related Models, 2019, 12 (1) : 59-77. doi: 10.3934/krm.2019003
[20]

Wolf-Jürgen Beyn, Raphael Kruse. Two-sided error estimates for the stochastic theta method. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 389-407. doi: 10.3934/dcdsb.2010.14.389

 Impact Factor: 

Tools

Metrics

  • PDF downloads (16)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences