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

Previous Article
A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions
NACO Home
This Issue
Next Article
Speeding up a memetic algorithm for the max-bisection problem

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

Abstract
Related Papers

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 and 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 Rⁿ with applications to finite element methods, Archive for Rational Mechanics and Analysis, 46 (1972), 178-199.
[2]	A. R. Conn, N. I. M. Gould and Ph. L. Toint, Trust-Region Methods, SIAM, 2000. doi: 10.1137/1.9780898719857.
[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, St. Louis, MO, USA, September 1998.
[4]	A. R. Conn, K. Scheinberg and L. N. Vicente, Introduction to Derivative-Free Optimization, MPS-SIAM Series on Optimization, SIAM, Philadelphia, PA, USA, 2008. doi: 10.1137/1.9780898718768.
[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-627. doi: 10.1093/imanum/drl006.
[6]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-203. doi: 10.1007/s101070100263.
[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-757.
[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-894. doi: 10.1080/10556788.2010.549231.
[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-418. doi: 10.1287/ijoc.1040.0102.
[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-219.
[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-534. doi: 10.1137/S1064827598334861.
[12]	M. Marazzi, Nonlinear Optimization with and without Derivatives, PhD thesis, Department of Industrial Engineering an Management Science, Norhtwestern University, Illinois, USA, 2001.
[13]	M. Marazzi and J. Nocedal, Wedge trust region methods for derivative free optimization, Mathematical Programming, 91 (2002), 289-305. doi: 10.1007/s101070100264.
[14]	J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software, ACM Transactions on Mathematical Software, 4 (1981), 136-140. doi: 10.1145/355934.355936.
[15]	J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553-572. doi: 10.1137/0904038.
[16]	J. A. Nelder and R. Mead, A simplex method for function minimization, The Computer Journal, 7 (1965), 308-313.
[17]	J. Nocedal and S. J. Wright, Numerical Optimization, Springer, New York, (1999). doi: 10.1007/b98874.
[18]	R. Oeuvray, Trust-Region Methods Based on Radial Basis Functions with Application to Biomedical Imaging, PhD thesis, Institut de Mathématiques, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, 2005.
[19]	M. J. D. Powell, A new algorithm for unconstrained optimization, In Nonlinear Programming (eds. J. B. Rosen, O. L. Mangasarian and K. Ritter), Academic Press, New York, (1970), 31-65.
[20]	M. J. D. Powell, On the global convergence of trust region algorithms for unconstrained optimization, Mathematical Programming, 29 (1984), 297-303. doi: 10.1007/BF02591998.
[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, Stockholm, Sweden, 1994.
[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, Hong Kong, 1998.
[23]	M. J. D. Powell, On the Lagrange functions of quadratic models that are defined by interpolation, Optimization Methods and Software, 16 (2001), 289-309. doi: 10.1080/10556780108805839.
[24]	M. J. D. Powell, UOBYQA: Unconstrained optimization by quadratic approximation, Mathematical Programming, 92 (2002), 555-582. doi: 10.1007/s101070100290.
[25]	M. J. D. Powell, Least Frobenius norm updating of quadratic models that satisfy interpolation conditions, Mathematical Programming, 100 (2004), 183-215. doi: 10.1007/s10107-003-0490-7.
[26]	M. J .D. Powell, The NEWUOA software for unconstrained optimization without derivatives, In Large-Scale Nonlinear Optimization (eds. P. Pardalos, G. Pillo and M. Roma), Springer, New York, (2006), 255-297. doi: 10.1007/0-387-30065-1_16.
[27]	M. J. D. Powell, On nonlinear optimization since 1959, In The Birth of Numerical Analysis (eds. A. Bultheel and R. Cools), World Scientific, (2010), 141-160.
[28]	M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization, Mathematical Programming, 49 (1991), 189-211. doi: 10.1007/BF01588787.
[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-3532. doi: 10.1137/090748536.
[30]	W. Sun, Q. K. Du and J. R. Chen, Computational Methods, Science Press, Beijing, (2007).
[31]	W. Sun, J. Yuan and Y. Yuan, Conic trust region method for linearly constrained optimization, Journal of Computational Mathematics, 21 (2003), 295-304.
[32]	W. Sun and Y. Yuan, A conic trust-region method for nonlinearly constrained optimization, Anals of Operations Research, 103 (2001), 175-191. doi: 10.1023/A:1012955122229.
[33]	W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer Optimization and Its Applications, Volume 1. Springer, New York, 2006.
[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-3219. doi: 10.1137/070691814.
[35]	D. Winfield, Function and Functional Optimization by Interpolation in Data Tables, PhD thesis, Havard University, Cambridge, USA, 1969.
[36]	D. Winfield, Function minimization by interpolation in a data table, J. Inst. Math. Appl., 12 (1973), 339-347.
[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-1302. doi: 10.1007/s11425-013-4677-y.
[38]	Y. Yuan, On a subproblem of trust region algorithms for constrained optimization, Mathematical Programming, 47 (1990), 53-63. doi: 10.1007/BF01580852.
[39]	H. C. Zhang, A. R. Conn and K. Scheinberg, A derivative-free algorithm for least-squares minimization, SIAM J. Optimization, 20 (2010), 3555-3576. doi: 10.1137/09075531X.
[40]	L. Zhao and W. Sun, Nonmonotone retrospective conic trust region method for unconstrained optimization, Numerical Algebra, Control and Optimization, 3 (2013), 309-324. doi: 10.3934/naco.2013.3.309.

show all references

References:

[1]	P. G. Ciarlet and P. A. Raviart, General Lagrange and Hermite interpolation in Rⁿ with applications to finite element methods, Archive for Rational Mechanics and Analysis, 46 (1972), 178-199.
[2]	A. R. Conn, N. I. M. Gould and Ph. L. Toint, Trust-Region Methods, SIAM, 2000. doi: 10.1137/1.9780898719857.
[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, St. Louis, MO, USA, September 1998.
[4]	A. R. Conn, K. Scheinberg and L. N. Vicente, Introduction to Derivative-Free Optimization, MPS-SIAM Series on Optimization, SIAM, Philadelphia, PA, USA, 2008. doi: 10.1137/1.9780898718768.
[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-627. doi: 10.1093/imanum/drl006.
[6]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-203. doi: 10.1007/s101070100263.
[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-757.
[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-894. doi: 10.1080/10556788.2010.549231.
[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-418. doi: 10.1287/ijoc.1040.0102.
[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-219.
[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-534. doi: 10.1137/S1064827598334861.
[12]	M. Marazzi, Nonlinear Optimization with and without Derivatives, PhD thesis, Department of Industrial Engineering an Management Science, Norhtwestern University, Illinois, USA, 2001.
[13]	M. Marazzi and J. Nocedal, Wedge trust region methods for derivative free optimization, Mathematical Programming, 91 (2002), 289-305. doi: 10.1007/s101070100264.
[14]	J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software, ACM Transactions on Mathematical Software, 4 (1981), 136-140. doi: 10.1145/355934.355936.
[15]	J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553-572. doi: 10.1137/0904038.
[16]	J. A. Nelder and R. Mead, A simplex method for function minimization, The Computer Journal, 7 (1965), 308-313.
[17]	J. Nocedal and S. J. Wright, Numerical Optimization, Springer, New York, (1999). doi: 10.1007/b98874.
[18]	R. Oeuvray, Trust-Region Methods Based on Radial Basis Functions with Application to Biomedical Imaging, PhD thesis, Institut de Mathématiques, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, 2005.
[19]	M. J. D. Powell, A new algorithm for unconstrained optimization, In Nonlinear Programming (eds. J. B. Rosen, O. L. Mangasarian and K. Ritter), Academic Press, New York, (1970), 31-65.
[20]	M. J. D. Powell, On the global convergence of trust region algorithms for unconstrained optimization, Mathematical Programming, 29 (1984), 297-303. doi: 10.1007/BF02591998.
[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, Stockholm, Sweden, 1994.
[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, Hong Kong, 1998.
[23]	M. J. D. Powell, On the Lagrange functions of quadratic models that are defined by interpolation, Optimization Methods and Software, 16 (2001), 289-309. doi: 10.1080/10556780108805839.
[24]	M. J. D. Powell, UOBYQA: Unconstrained optimization by quadratic approximation, Mathematical Programming, 92 (2002), 555-582. doi: 10.1007/s101070100290.
[25]	M. J. D. Powell, Least Frobenius norm updating of quadratic models that satisfy interpolation conditions, Mathematical Programming, 100 (2004), 183-215. doi: 10.1007/s10107-003-0490-7.
[26]	M. J .D. Powell, The NEWUOA software for unconstrained optimization without derivatives, In Large-Scale Nonlinear Optimization (eds. P. Pardalos, G. Pillo and M. Roma), Springer, New York, (2006), 255-297. doi: 10.1007/0-387-30065-1_16.
[27]	M. J. D. Powell, On nonlinear optimization since 1959, In The Birth of Numerical Analysis (eds. A. Bultheel and R. Cools), World Scientific, (2010), 141-160.
[28]	M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization, Mathematical Programming, 49 (1991), 189-211. doi: 10.1007/BF01588787.
[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-3532. doi: 10.1137/090748536.
[30]	W. Sun, Q. K. Du and J. R. Chen, Computational Methods, Science Press, Beijing, (2007).
[31]	W. Sun, J. Yuan and Y. Yuan, Conic trust region method for linearly constrained optimization, Journal of Computational Mathematics, 21 (2003), 295-304.
[32]	W. Sun and Y. Yuan, A conic trust-region method for nonlinearly constrained optimization, Anals of Operations Research, 103 (2001), 175-191. doi: 10.1023/A:1012955122229.
[33]	W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer Optimization and Its Applications, Volume 1. Springer, New York, 2006.
[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-3219. doi: 10.1137/070691814.
[35]	D. Winfield, Function and Functional Optimization by Interpolation in Data Tables, PhD thesis, Havard University, Cambridge, USA, 1969.
[36]	D. Winfield, Function minimization by interpolation in a data table, J. Inst. Math. Appl., 12 (1973), 339-347.
[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-1302. doi: 10.1007/s11425-013-4677-y.
[38]	Y. Yuan, On a subproblem of trust region algorithms for constrained optimization, Mathematical Programming, 47 (1990), 53-63. doi: 10.1007/BF01580852.
[39]	H. C. Zhang, A. R. Conn and K. Scheinberg, A derivative-free algorithm for least-squares minimization, SIAM J. Optimization, 20 (2010), 3555-3576. doi: 10.1137/09075531X.
[40]	L. Zhao and W. Sun, Nonmonotone retrospective conic trust region method for unconstrained optimization, Numerical Algebra, Control and Optimization, 3 (2013), 309-324. doi: 10.3934/naco.2013.3.309.

[1]	Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117
[2]	Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919
[3]	Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309
[4]	A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial and Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319
[5]	Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[6]	Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223
[7]	Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial and Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321
[8]	Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050
[9]	Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237
[10]	Yigui Ou, Wenjie Xu. A unified derivative-free projection method model for large-scale nonlinear equations with convex constraints. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021125
[11]	Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030
[12]	Hong Seng Sim, Chuei Yee Chen, Wah June Leong, Jiao Li. Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021143
[13]	Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034
[14]	Gaohang Yu. A derivative-free method for solving large-scale nonlinear systems of equations. Journal of Industrial and Management Optimization, 2010, 6 (1) : 149-160. doi: 10.3934/jimo.2010.6.149
[15]	Dong-Hui Li, Xiao-Lin Wang. A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 71-82. doi: 10.3934/naco.2011.1.71
[16]	Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[17]	Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391
[18]	Alexandr Golodnikov, Stan Uryasev, Grigoriy Zrazhevsky, Yevgeny Macheret, A. Alexandre Trindade. Optimization of composition and processing parameters for alloy development: a statistical model-based approach. Journal of Industrial and Management Optimization, 2007, 3 (3) : 489-501. doi: 10.3934/jimo.2007.3.489
[19]	Chen Li, Fajie Wei, Shenghan Zhou. Prediction method based on optimization theory and its application. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1213-1221. doi: 10.3934/dcdss.2015.8.1213
[20]	Chien-Wen Chao, Shu-Cherng Fang, Ching-Jong Liao. A tropical cyclone-based method for global optimization. Journal of Industrial and Management Optimization, 2012, 8 (1) : 103-115. doi: 10.3934/jimo.2012.8.103

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Liang Zhang Wenyu Sun Raimundo J. B. de Sampaio Jinyun Yuan
on Google Scholar
Liang Zhang Wenyu Sun Raimundo J. B. de Sampaio Jinyun Yuan

[Back to Top]