American Institute of Mathematical Sciences

Advanced
2015, 5(2): 169-184. doi: 10.3934/naco.2015.5.169

A wedge trust region method with self-correcting geometry for derivative-free optimization

Liang Zhang 1, , Wenyu Sun 1, , Raimundo J. B. de Sampaio 2, and  Jinyun Yuan 3,

1. 

School of Mathematical Sciences, Jiangsu Key Labratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China, China
2. 

PPGEPS, Pontifical Catholic University of Parana (PUCPR), Curitiba, Parana, Brazil
3. 

Department of Mathematics, Universidade Federal do Parana (UFPR), Curitiba, Parana, Brazil

Received  December 2014 Revised  April 2015 Published  June 2015

Recently, some methods for solving optimization problems without derivatives have been proposed. The main part of these methods is to form a suitable model function that can be minimized for obtaining a new iterative point. An important strategy is geometry-improving iteration for a good model, which needs a lot of calculations. Besides, Marazzi and Nocedal (2002) proposed a wedge trust region method for derivative free optimization. In this paper, we propose a new self-correcting geometry procedure with less computational efforts, and combine it with the wedge trust region method. The global convergence of new algorithm is established. The limited numerical experiments show that the new algorithm is efficient and competitive.
Keywords: Derivative-free optimization, self-correcting geometry., model-based method, unconstrained optimization, trust region method.
Mathematics Subject Classification: Primary: 65K05; Secondary: 90C3.
Citation: 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
References:
[1]

P. G. Ciarlet and P. A. Raviart, General Lagrange and Hermite interpolation in Rn with applications to finite element methods,, Archive for Rational Mechanics and Analysis, 46 (1972), 178.   Google Scholar

[2]

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

[3]

A. R. Conn, K. Scheinberg and Ph. L. Toint, A derivative free optimization algorithm in practice,, In the proceeding of the 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, (1998).   Google Scholar

[4]

A. R. Conn, K. Scheinberg and L. N. Vicente, Introduction to Derivative-Free Optimization,, MPS-SIAM Series on Optimization, (2008).  doi: 10.1137/1.9780898718768.  Google Scholar

[5]

Y. H. Dai, W. W. Hager, K. Schittkowski and H. C. Zhang, The cyclic Barzilai-Borwein method for unconstrained optimization,, IMA J. Numerical Analysis, 26 (2006), 604.  doi: 10.1093/imanum/drl006.  Google Scholar

[6]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar

[7]

K. R. Fowler, J. P. Reese, C. E. Kees, J. E. Dennis, C. T. Kelley, C. T. Miller, C. Audet, A. J. Booker, G. Couture, R. W. Darwin, M. W. Farthing, D. E. Finkel, J. M. Gablonsky, G. Gray and T. G. Kolda, Comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems,, Advances in Water Resources, 31 (2008), 743.   Google Scholar

[8]

S. Gratton, Ph. L. Toint and A. Tröltzsch, An active-set trust-region method for derivative-free nonlinear bound-constrained optimization,, Optimization Methods and Software, 26 (2011), 873.  doi: 10.1080/10556788.2010.549231.  Google Scholar

[9]

G. Gray, T. Kolda, K. Sale and M. Young, Optimizing an empirical scoring function for transmembrane protein structure determination,, INFORMS Journal on Computing, 16 (2004), 406.  doi: 10.1287/ijoc.1040.0102.  Google Scholar

[10]

R. Hooke and T. A. Jeeves, Direct search solution of numerical and statistical problems,, Journal of the Association for Computing Machinery, 8 (1961), 212.   Google Scholar

[11]

X. W. Liu and Y. Yuan, A robust algorithm for optimization with general equality and inequality constraints,, SIAM J. Scientific Computing, 22 (2000), 517.  doi: 10.1137/S1064827598334861.  Google Scholar

[12]

M. Marazzi, Nonlinear Optimization with and without Derivatives,, PhD thesis, (2001).   Google Scholar

[13]

M. Marazzi and J. Nocedal, Wedge trust region methods for derivative free optimization,, Mathematical Programming, 91 (2002), 289.  doi: 10.1007/s101070100264.  Google Scholar

[14]

J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software,, ACM Transactions on Mathematical Software, 4 (1981), 136.  doi: 10.1145/355934.355936.  Google Scholar

[15]

J. J. Moré and D. C. Sorensen, Computing a trust region step,, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553.  doi: 10.1137/0904038.  Google Scholar

[16]

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

[17]

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

[18]

R. Oeuvray, Trust-Region Methods Based on Radial Basis Functions with Application to Biomedical Imaging,, PhD thesis, (2005).   Google Scholar

[19]

M. J. D. Powell, A new algorithm for unconstrained optimization,, In Nonlinear Programming (eds. J. B. Rosen, (1970), 31.   Google Scholar

[20]

M. J. D. Powell, On the global convergence of trust region algorithms for unconstrained optimization,, Mathematical Programming, 29 (1984), 297.  doi: 10.1007/BF02591998.  Google Scholar

[21]

M. J. D. Powell, A direct search optimization method that models the objective by quadratic interpolation,, In presentation at the 5th Stockholm Optimization Days, (1994).   Google Scholar

[22]

M. J. D. Powell, A quadratic model trust region method for unconstained minimization without derivatives,, presentation at the International Conference on Nonlinear Programming and Variational Inequalities, (1998).   Google Scholar

[23]

M. J. D. Powell, On the Lagrange functions of quadratic models that are defined by interpolation,, Optimization Methods and Software, 16 (2001), 289.  doi: 10.1080/10556780108805839.  Google Scholar

[24]

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

[25]

M. J. D. Powell, Least Frobenius norm updating of quadratic models that satisfy interpolation conditions,, Mathematical Programming, 100 (2004), 183.  doi: 10.1007/s10107-003-0490-7.  Google Scholar

[26]

M. J .D. Powell, The NEWUOA software for unconstrained optimization without derivatives,, In Large-Scale Nonlinear Optimization (eds. P. Pardalos, (2006), 255.  doi: 10.1007/0-387-30065-1_16.  Google Scholar

[27]

M. J. D. Powell, On nonlinear optimization since 1959,, In The Birth of Numerical Analysis (eds. A. Bultheel and R. Cools), (2010), 141.   Google Scholar

[28]

M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization,, Mathematical Programming, 49 (1991), 189.  doi: 10.1007/BF01588787.  Google Scholar

[29]

K. Scheinberg and Ph. L. Toint, Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization,, SIAM Journal on Optimization, 20 (2010), 3512.  doi: 10.1137/090748536.  Google Scholar

[30]

W. Sun, Q. K. Du and J. R. Chen, Computational Methods,, Science Press, (2007).   Google Scholar

[31]

W. Sun, J. Yuan and Y. Yuan, Conic trust region method for linearly constrained optimization,, Journal of Computational Mathematics, 21 (2003), 295.   Google Scholar

[32]

W. Sun and Y. Yuan, A conic trust-region method for nonlinearly constrained optimization,, Anals of Operations Research, 103 (2001), 175.  doi: 10.1023/A:1012955122229.  Google Scholar

[33]

W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming,, Springer Optimization and Its Applications, (2006).   Google Scholar

[34]

S. M. Wild, R. G. Regis and C. A. Shoemaker, ORBIT: optimization by radial basis function interpolation in trust-regions,, SIAM Journal on Scientific Computing, 30 (2008), 3197.  doi: 10.1137/070691814.  Google Scholar

[35]

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

[36]

D. Winfield, Function minimization by interpolation in a data table,, J. Inst. Math. Appl., 12 (1973), 339.   Google Scholar

[37]

D. Xue and W. Sun, On convergence analysis of a derivative-free trust region algorithm for constrained optimization with separable structure,, Science China Mathematics, 57 (2014), 1287.  doi: 10.1007/s11425-013-4677-y.  Google Scholar

[38]

Y. Yuan, On a subproblem of trust region algorithms for constrained optimization,, Mathematical Programming, 47 (1990), 53.  doi: 10.1007/BF01580852.  Google Scholar

[39]

H. C. Zhang, A. R. Conn and K. Scheinberg, A derivative-free algorithm for least-squares minimization,, SIAM J. Optimization, 20 (2010), 3555.  doi: 10.1137/09075531X.  Google Scholar

[40]

L. Zhao and W. Sun, Nonmonotone retrospective conic trust region method for unconstrained optimization,, Numerical Algebra, 3 (2013), 309.  doi: 10.3934/naco.2013.3.309.  Google Scholar

show all references

References:
[1]

P. G. Ciarlet and P. A. Raviart, General Lagrange and Hermite interpolation in Rn with applications to finite element methods,, Archive for Rational Mechanics and Analysis, 46 (1972), 178.   Google Scholar

[2]

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

[3]

A. R. Conn, K. Scheinberg and Ph. L. Toint, A derivative free optimization algorithm in practice,, In the proceeding of the 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, (1998).   Google Scholar

[4]

A. R. Conn, K. Scheinberg and L. N. Vicente, Introduction to Derivative-Free Optimization,, MPS-SIAM Series on Optimization, (2008).  doi: 10.1137/1.9780898718768.  Google Scholar

[5]

Y. H. Dai, W. W. Hager, K. Schittkowski and H. C. Zhang, The cyclic Barzilai-Borwein method for unconstrained optimization,, IMA J. Numerical Analysis, 26 (2006), 604.  doi: 10.1093/imanum/drl006.  Google Scholar

[6]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar

[7]

K. R. Fowler, J. P. Reese, C. E. Kees, J. E. Dennis, C. T. Kelley, C. T. Miller, C. Audet, A. J. Booker, G. Couture, R. W. Darwin, M. W. Farthing, D. E. Finkel, J. M. Gablonsky, G. Gray and T. G. Kolda, Comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems,, Advances in Water Resources, 31 (2008), 743.   Google Scholar

[8]

S. Gratton, Ph. L. Toint and A. Tröltzsch, An active-set trust-region method for derivative-free nonlinear bound-constrained optimization,, Optimization Methods and Software, 26 (2011), 873.  doi: 10.1080/10556788.2010.549231.  Google Scholar

[9]

G. Gray, T. Kolda, K. Sale and M. Young, Optimizing an empirical scoring function for transmembrane protein structure determination,, INFORMS Journal on Computing, 16 (2004), 406.  doi: 10.1287/ijoc.1040.0102.  Google Scholar

[10]

R. Hooke and T. A. Jeeves, Direct search solution of numerical and statistical problems,, Journal of the Association for Computing Machinery, 8 (1961), 212.   Google Scholar

[11]

X. W. Liu and Y. Yuan, A robust algorithm for optimization with general equality and inequality constraints,, SIAM J. Scientific Computing, 22 (2000), 517.  doi: 10.1137/S1064827598334861.  Google Scholar

[12]

M. Marazzi, Nonlinear Optimization with and without Derivatives,, PhD thesis, (2001).   Google Scholar

[13]

M. Marazzi and J. Nocedal, Wedge trust region methods for derivative free optimization,, Mathematical Programming, 91 (2002), 289.  doi: 10.1007/s101070100264.  Google Scholar

[14]

J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software,, ACM Transactions on Mathematical Software, 4 (1981), 136.  doi: 10.1145/355934.355936.  Google Scholar

[15]

J. J. Moré and D. C. Sorensen, Computing a trust region step,, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553.  doi: 10.1137/0904038.  Google Scholar

[16]

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

[17]

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

[18]

R. Oeuvray, Trust-Region Methods Based on Radial Basis Functions with Application to Biomedical Imaging,, PhD thesis, (2005).   Google Scholar

[19]

M. J. D. Powell, A new algorithm for unconstrained optimization,, In Nonlinear Programming (eds. J. B. Rosen, (1970), 31.   Google Scholar

[20]

M. J. D. Powell, On the global convergence of trust region algorithms for unconstrained optimization,, Mathematical Programming, 29 (1984), 297.  doi: 10.1007/BF02591998.  Google Scholar

[21]

M. J. D. Powell, A direct search optimization method that models the objective by quadratic interpolation,, In presentation at the 5th Stockholm Optimization Days, (1994).   Google Scholar

[22]

M. J. D. Powell, A quadratic model trust region method for unconstained minimization without derivatives,, presentation at the International Conference on Nonlinear Programming and Variational Inequalities, (1998).   Google Scholar

[23]

M. J. D. Powell, On the Lagrange functions of quadratic models that are defined by interpolation,, Optimization Methods and Software, 16 (2001), 289.  doi: 10.1080/10556780108805839.  Google Scholar

[24]

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

[25]

M. J. D. Powell, Least Frobenius norm updating of quadratic models that satisfy interpolation conditions,, Mathematical Programming, 100 (2004), 183.  doi: 10.1007/s10107-003-0490-7.  Google Scholar

[26]

M. J .D. Powell, The NEWUOA software for unconstrained optimization without derivatives,, In Large-Scale Nonlinear Optimization (eds. P. Pardalos, (2006), 255.  doi: 10.1007/0-387-30065-1_16.  Google Scholar

[27]

M. J. D. Powell, On nonlinear optimization since 1959,, In The Birth of Numerical Analysis (eds. A. Bultheel and R. Cools), (2010), 141.   Google Scholar

[28]

M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization,, Mathematical Programming, 49 (1991), 189.  doi: 10.1007/BF01588787.  Google Scholar

[29]

K. Scheinberg and Ph. L. Toint, Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization,, SIAM Journal on Optimization, 20 (2010), 3512.  doi: 10.1137/090748536.  Google Scholar

[30]

W. Sun, Q. K. Du and J. R. Chen, Computational Methods,, Science Press, (2007).   Google Scholar

[31]

W. Sun, J. Yuan and Y. Yuan, Conic trust region method for linearly constrained optimization,, Journal of Computational Mathematics, 21 (2003), 295.   Google Scholar

[32]

W. Sun and Y. Yuan, A conic trust-region method for nonlinearly constrained optimization,, Anals of Operations Research, 103 (2001), 175.  doi: 10.1023/A:1012955122229.  Google Scholar

[33]

W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming,, Springer Optimization and Its Applications, (2006).   Google Scholar

[34]

S. M. Wild, R. G. Regis and C. A. Shoemaker, ORBIT: optimization by radial basis function interpolation in trust-regions,, SIAM Journal on Scientific Computing, 30 (2008), 3197.  doi: 10.1137/070691814.  Google Scholar

[35]

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

[36]

D. Winfield, Function minimization by interpolation in a data table,, J. Inst. Math. Appl., 12 (1973), 339.   Google Scholar

[37]

D. Xue and W. Sun, On convergence analysis of a derivative-free trust region algorithm for constrained optimization with separable structure,, Science China Mathematics, 57 (2014), 1287.  doi: 10.1007/s11425-013-4677-y.  Google Scholar

[38]

Y. Yuan, On a subproblem of trust region algorithms for constrained optimization,, Mathematical Programming, 47 (1990), 53.  doi: 10.1007/BF01580852.  Google Scholar

[39]

H. C. Zhang, A. R. Conn and K. Scheinberg, A derivative-free algorithm for least-squares minimization,, SIAM J. Optimization, 20 (2010), 3555.  doi: 10.1137/09075531X.  Google Scholar

[40]

L. Zhao and W. Sun, Nonmonotone retrospective conic trust region method for unconstrained optimization,, Numerical Algebra, 3 (2013), 309.  doi: 10.3934/naco.2013.3.309.  Google Scholar

[1]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050
[2]

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, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[3]

Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139
[4]

C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020058
[5]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135
[6]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006
[7]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014
[8]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[9]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[10]

Yi An, Bo Li, Lei Wang, Chao Zhang, Xiaoli Zhou. Calibration of a 3D laser rangefinder and a camera based on optimization solution. Journal of Industrial & Management Optimization, 2021, 17 (1) : 427-445. doi: 10.3934/jimo.2019119
[11]

Hongfei Yang, Xiaofeng Ding, Raymond Chan, Hui Hu, Yaxin Peng, Tieyong Zeng. A new initialization method based on normed statistical spaces in deep networks. Inverse Problems & Imaging, 2021, 15 (1) : 147-158. doi: 10.3934/ipi.2020045
[12]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018
[13]

Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, 2021, 17 (2) : 669-686. doi: 10.3934/jimo.2019128
[14]

Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020178
[15]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[16]

Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089
[17]

Editorial Office. Retraction: Xiao-Qian Jiang and Lun-Chuan Zhang, Stock price fluctuation prediction method based on time series analysis. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 915-915. doi: 10.3934/dcdss.2019061
[18]

Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134
[19]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[20]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098

 Impact Factor: 

Tools

Metrics

  • PDF downloads (47)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences