American Institute of Mathematical Sciences

Advanced
April  2017, 13(2): 595-608. doi: 10.3934/jimo.2016034

A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems

Guanghui Zhou 1,2, , Qin Ni 1, and  Meilan Zeng 1,3,

1. 

Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu Province, 211106, China
2. 

Huaibei Normal University, Huaibei, Anhui Province, 235000, China
3. 

Hubei Engineering University, Xiaogan, Hubei Pvovince, 432000, China

Received  January 2015 Revised  December 2015 Published  May 2016

Fund Project: The authors are supported by the Natural Science Foundation of China (11471159,11571169), the Natural Science Foundation of Jiangsu Province (BK20141409), the Education Department Foundation of Anhui Province(KJ2016A651,2014jyxm161), and the Science and Technology Foundation of the Department of Education of Hubei Province (D20152701).

In this paper, a scaled method that combines the conjugate gradient with moving asymptotes is presented for solving the large-scaled nonlinear unconstrained optimization problem. A diagonal matrix is obtained by the moving asymptote technique, and a scaled gradient is determined by multiplying the gradient with the diagonal matrix. The search direction is either a scaled conjugate gradient direction or a negative scaled gradient direction under different conditions. This direction is sufficient descent if the step size satisfies the strong Wolfe condition. A global convergence analysis of this method is also provided. The numerical results show that the scaled method is efficient for solving some large-scaled nonlinear problems.

Keywords: Scaling, conjugate gradient, moving asymptotes, the Wolfe condition, unconstrained optimization.
Mathematics Subject Classification: Primary: 65K05; Secondary: 90C30, 49M37.
Citation: 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
References:
[1]

M. Al-Baali, Y. Narushima and H. Yabe, A family of three-term conjugate gradient methods with sufficient descent property for unconstrained optimization, Computational Optimization and Applications, 60 (2015), 89-110.  doi: 10.1007/s10589-014-9662-z.

[2]

N. Andrei, An unconstrained optimization test functions collection, Advanced Modeling and Optimization, 10 (2008), 147-161. 

[3]

Y. Dai and Y. Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal on Optimization, 10 (1999), 177-182.  doi: 10.1137/S1052623497318992.

[4]

Y. Dai and C. Kou, A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search, SIAM Journal on Optimization, 23 (2013), 296-320.  doi: 10.1137/100813026.

[5]

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

[6]

R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, The Computer Journal, 7 (1964), 149-154.  doi: 10.1093/comjnl/7.2.149.

[7]

N. I. M. Gould, D. Orban and P. L. Toint, CUTEr and SifDec: A constrained and unconstrained testing environment, revisited, ACM Transactions on Mathematical Software, 29 (2003), 353-372.  doi: 10.1145/962437.962438.

[8]

W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 16 (2005), 170-192.  doi: 10.1137/030601880.

[9]

W. Hager and H. Zhang, The limited memory conjugate gradient method, SIAM Journal on Optimization, 23 (2013), 2150-2168.  doi: 10.1137/120898097.

[10]

M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49 (1952), 409-436.  doi: 10.6028/jres.049.044.

[11]

D. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd edition, Springer-Verlag, New York, 2008.

[12]

W. Nakamura, Y. Narushima and H. Yabe, Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization, Journal of Industrial and Management Optimization, 9 (2013), 595-619.  doi: 10.3934/jimo.2013.9.595.

[13]

Y. Narushima, H. Yabe and J. A. Ford, A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM Journal on Optimization, 21 (2011), 212-230.  doi: 10.1137/080743573.

[14]

Q. Ni, A globally convergent method of moving asymptotes with trust region technique, Optimization methods and software, 18 (2003), 283-297.  doi: 10.1080/1055678031000118491.

[15]

E. Polak and G. Ribiere, Note sur la convergence de méthodes de directions conjuguées, Revue française d'informatique et de recherche opérationnelle, série rouge, 3 (1969), 35-43. 

[16]

B. T. Polyak, The conjugate gradient method in extremal problems, USSR Computational Mathematics and Mathematical Physics, 9 (1969), 94-112.  doi: 10.1016/0041-5553(69)90035-4.

[17]

K. Svanberg, The method of moving asymptotes—a new method for structural optimization, International Journal for Numerical Methods in Engineering, 24 (2987), 359-373.  doi: 10.1002/nme.1620240207.

[18]

H. Wang and Q. Ni, A new method of moving asymptotes for large-scale unconstrained optimization, Applied Mathematics and Computaiton, 203 (2008), 62-71.  doi: 10.1016/j.amc.2008.03.035.

[19]

W. Zhou and Y. Zhou, On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization, Journal of Industrial and Management Optimization, 9 (2013), 893-899.  doi: 10.3934/jimo.2013.9.893.

show all references

References:
[1]

M. Al-Baali, Y. Narushima and H. Yabe, A family of three-term conjugate gradient methods with sufficient descent property for unconstrained optimization, Computational Optimization and Applications, 60 (2015), 89-110.  doi: 10.1007/s10589-014-9662-z.

[2]

N. Andrei, An unconstrained optimization test functions collection, Advanced Modeling and Optimization, 10 (2008), 147-161. 

[3]

Y. Dai and Y. Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal on Optimization, 10 (1999), 177-182.  doi: 10.1137/S1052623497318992.

[4]

Y. Dai and C. Kou, A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search, SIAM Journal on Optimization, 23 (2013), 296-320.  doi: 10.1137/100813026.

[5]

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

[6]

R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, The Computer Journal, 7 (1964), 149-154.  doi: 10.1093/comjnl/7.2.149.

[7]

N. I. M. Gould, D. Orban and P. L. Toint, CUTEr and SifDec: A constrained and unconstrained testing environment, revisited, ACM Transactions on Mathematical Software, 29 (2003), 353-372.  doi: 10.1145/962437.962438.

[8]

W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 16 (2005), 170-192.  doi: 10.1137/030601880.

[9]

W. Hager and H. Zhang, The limited memory conjugate gradient method, SIAM Journal on Optimization, 23 (2013), 2150-2168.  doi: 10.1137/120898097.

[10]

M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49 (1952), 409-436.  doi: 10.6028/jres.049.044.

[11]

D. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd edition, Springer-Verlag, New York, 2008.

[12]

W. Nakamura, Y. Narushima and H. Yabe, Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization, Journal of Industrial and Management Optimization, 9 (2013), 595-619.  doi: 10.3934/jimo.2013.9.595.

[13]

Y. Narushima, H. Yabe and J. A. Ford, A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM Journal on Optimization, 21 (2011), 212-230.  doi: 10.1137/080743573.

[14]

Q. Ni, A globally convergent method of moving asymptotes with trust region technique, Optimization methods and software, 18 (2003), 283-297.  doi: 10.1080/1055678031000118491.

[15]

E. Polak and G. Ribiere, Note sur la convergence de méthodes de directions conjuguées, Revue française d'informatique et de recherche opérationnelle, série rouge, 3 (1969), 35-43. 

[16]

B. T. Polyak, The conjugate gradient method in extremal problems, USSR Computational Mathematics and Mathematical Physics, 9 (1969), 94-112.  doi: 10.1016/0041-5553(69)90035-4.

[17]

K. Svanberg, The method of moving asymptotes—a new method for structural optimization, International Journal for Numerical Methods in Engineering, 24 (2987), 359-373.  doi: 10.1002/nme.1620240207.

[18]

H. Wang and Q. Ni, A new method of moving asymptotes for large-scale unconstrained optimization, Applied Mathematics and Computaiton, 203 (2008), 62-71.  doi: 10.1016/j.amc.2008.03.035.

[19]

W. Zhou and Y. Zhou, On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization, Journal of Industrial and Management Optimization, 9 (2013), 893-899.  doi: 10.3934/jimo.2013.9.893.

Figure 1.  CPU time performance profiles in a log2 scale (n = 102)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Iterations performance profiles in a log2 scale (n = 102)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  CPU time performance profiles in a log2 scale (n = 103)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Iterations performance profiles in a log2 scale (n = 103)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  CPU time performance profiles in a log2 scale (n = 104)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Iterations performance profiles in a log2 scale (n = 104)
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Test functions
No. Function Name No. Function Name
1 ARWHEAD 17 Ext quadratic penalty QP2
2 COSINE 18 Ext quadratic exponential EP1
3 EDENSCH 19 Ext Tridiagonal 2
4 EG2 20 Ext DENSCHNF
5 ENGVAL1 21 HIMMELBG
6 GENROSE 22 HIMMELH
7 Ext Freudenstein & Roth 23 TOINTGSS
8 Raydan 2 24 Extended DENSCHNB
9 Ext Tridiagonal 1 25 LIARWHD
10 Ext TET 26 Extended Trigonometric
11 Diagonal 5 27 Extended Penalty
12 Diagonal 2 28 Extended BD1
13 Ext Maratos 29 Perturbed Quadratic
14 Ext Cliff 30 Raydan 1
15 Perturbed quadratic diagonal 31 Diagonal 4
16 Ext quadratic penalty QP1 32 QUARTC
Table Options

Download as excel

No. Function Name No. Function Name
1 ARWHEAD 17 Ext quadratic penalty QP2
2 COSINE 18 Ext quadratic exponential EP1
3 EDENSCH 19 Ext Tridiagonal 2
4 EG2 20 Ext DENSCHNF
5 ENGVAL1 21 HIMMELBG
6 GENROSE 22 HIMMELH
7 Ext Freudenstein & Roth 23 TOINTGSS
8 Raydan 2 24 Extended DENSCHNB
9 Ext Tridiagonal 1 25 LIARWHD
10 Ext TET 26 Extended Trigonometric
11 Diagonal 5 27 Extended Penalty
12 Diagonal 2 28 Extended BD1
13 Ext Maratos 29 Perturbed Quadratic
14 Ext Cliff 30 Raydan 1
15 Perturbed quadratic diagonal 31 Diagonal 4
16 Ext quadratic penalty QP1 32 QUARTC
[1]

Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595
[2]

Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial and Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739
[3]

Shummin Nakayama, Yasushi Narushima, Hiroshi Yabe. Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1773-1793. doi: 10.3934/jimo.2018122
[4]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883
[5]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control and Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[6]

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
[7]

Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[8]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[9]

Mohamed Aly Tawhid. Nonsmooth generalized complementarity as unconstrained optimization. Journal of Industrial and Management Optimization, 2010, 6 (2) : 411-423. doi: 10.3934/jimo.2010.6.411
[10]

Sarra Delladji, Mohammed Belloufi, Badreddine Sellami. Behavior of the combination of PRP and HZ methods for unconstrained optimization. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 377-389. doi: 10.3934/naco.2020032
[11]

Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial and Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415
[12]

Manxue You, Shengjie Li. Perturbation of Image and conjugate duality for vector optimization. Journal of Industrial and Management Optimization, 2022, 18 (2) : 731-745. doi: 10.3934/jimo.2020176
[13]

C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial and Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193
[14]

Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems and Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195
[15]

Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025
[16]

ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021150
[17]

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
[18]

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
[19]

Lixing Han. An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 583-599. doi: 10.3934/naco.2013.3.583
[20]

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

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (2640)
  • HTML views (409)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy