nach oben

Journal of Applied Mathematics and Computing

Erschienen in:

01.06.2016 | Original Research

A modified PRP conjugate gradient algorithm with nonmonotone line search for nonsmooth convex optimization problems

verfasst von: Gonglin Yuan, Zengxin Wei

Erschienen in: Journal of Applied Mathematics and Computing | Ausgabe 1-2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

It is well-known that nonlinear conjugate gradient (CG) methods are preferred to solve large-scale smooth optimization problems due to their simplicity and low storage. However, the CG methods for nonsmooth optimization have not been studied. In this paper, a modified Polak–Ribière–Polyak CG algorithm which combines with a nonmonotone line search technique is proposed for nonsmooth convex minimization. The search direction of the given method not only possesses the sufficiently descent property but also belongs to a trust region. Moreover, the search direction has not only the gradients information but also the functions information. The global convergence of the presented algorithm is established under suitable conditions. Numerical results show that the given method is competitive to other three methods.

Vorheriger Artikel The Laplacian and signless Laplacian spectrum of semi-Cayley graphs over abelian groups

Nächster Artikel A note on “Quotient structures of intuitionistic fuzzy finite state machines”

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ahmed, T., Storey, D.: Efficient hybrid conjugate gradient techniques. Journal of Optimization Theory and Applications 64, 379–394 (1990)MathSciNetCrossRefMATH

Al-Baali, A.: Descent property and global convergence of the Flecher–Reeves method with inexact line search. IMA Journal of Numerical Analysis 5, 121–124 (1985)MathSciNetCrossRefMATH

Birge, J.R., Qi, L., Wei, Z.: A general approach to convergence properties of some methods for nonsmooth convex optimization. Applied Mathematics & Optimization 38, 141–158 (1998)MathSciNetCrossRefMATH

Birgin, E.G., Martinez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM Journal on Optimization 10, 1196–1121 (2000)MathSciNetCrossRefMATH

Bonnans, J.F., Gilbert, J.C., Lemaréchal, C., Sagastizábal, C.A.: A family of veriable metric proximal methods. Mathematical Programming 68, 15–47 (1995)MathSciNetMATH

Calamai, P.H., Moré, J.J.: Projected gradient methods for linear constrained problems. Mathematical Programming 39, 93–116 (1987)MathSciNetCrossRefMATH

Correa, R., Lemaréchal, C.: Convergence of some algorithms for convex minization. Mathematical Programming 62, 261–273 (1993)MathSciNetCrossRefMATH

Dai, Y., Yuan, Y.: Nonlinear Conjugate Gradient Methods. Shanghai Scientific and Technical Publishers, Shanghai (1998)

Fukushima, M., Qi, L.: A global and superlinearly convergent algorithm for nonsmooth convex minimization. SIAM Journal on Optimization 6, 1106–1120 (1996)MathSciNetCrossRefMATH

10.

Gilbert, J.C., Nocedal, J.: Global convergence properties of conjugate gradient methods for optimization. SIAM Journal on Optimization 2, 21–42 (1992)MathSciNetCrossRefMATH

11.

Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for newton’s method. SIAM Journal on Numerical Analysis 23, 707–716 (1986)MathSciNetCrossRefMATH

12.

Grippo, L., Lucidi, S.: A globally convergent version of the Polak–Ribière gradient method. Mathematical Programming 78, 375–391 (1997)MathSciNetMATH

13.

Haarala, M., Miettinen, K., Mäkelä, M.M.: New limited memory bundle method for large-scale nonsmooth optimization. Optimization Methods and Software 19, 673–692 (2004)MathSciNetCrossRefMATH

14.

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

15.

Hager, W.W., Zhang, H.: Algorithm 851: CGDESCENT, a conjugate gradient method with guaranteed descent. ACM Transactions on Mathematical Software 32, 113–137 (2006)MathSciNetCrossRef

16.

Han, J.Y., Liu, G.H.: Global convergence analysis of a new nonmonotone BFGS algorithm on convex objective functions. Computational Optimization and Applications 7, 277–289 (1997)MathSciNetCrossRefMATH

17.

Hiriart-Urruty, J.B., Lemmaréchal, C.: Convex Analysis and Minimization Algorithms II. Springer, Berlin (1983)

18.

Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization. Springer, Berlin (1985)MATH

19.

Kiwiel, K.C.: Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. Mathematical Programming 69, 89–109 (1995)MathSciNetMATH

20.

Kiwiel, K.C.: Proximity control in bundle methods for convex nondifferentiable optimization. Mathematical Programming 46, 105–122 (1990)MathSciNetCrossRefMATH

21.

Lemaréchal, C.: Extensions Diverses des Médthodes de Gradient et Applications. Thèse d’Etat, Paris (1980)

22.

Lemaréchal, C.: Nondifferentiable optimization. In: Nemhauser, G.L., Rinnooy Kan, A.H.G., Todd, M.J. (eds.) Handbooks in Operations Research and Management Science, Vol. 1, Optimization. North-Holland, Amsterdam (1989)

23.

Lemaréchal, C., Sagastizábal, C.: Practical aspects of the Moreau-Yosida regularization: Theoretical preliminaries. SIAM Journal on Optimization 7, 367–385 (1997)MathSciNetCrossRefMATH

24.

Liu, G.H., Peng, J.M.: The convergence properties of a nonmonotonic algorithm. Journal of Computational Mathematics 1, 65–71 (1992)MathSciNet

25.

Lukšan, L., Vlček, J.: A bundle-Newton method for nonsmooth unconstrained minimization. Mathematical Programming 83, 373–391 (1998)MathSciNetMATH

26.

Lukšan, L., Vlček, J. (2000). Test Problems for Nonsmooth Unconstrained and Linearly Constrained Optimization, Technical Report No. 798, Institute of Computer Science, Academy of Sciences of the Czech Republic

27.

Polak, E., Ribière, G.: Note sur la convergence de directions conjugées. Revue Francaise informat Recherche Opératinelle 3, 35–43 (1969)MATH

28.

Polyak, B.T.: The conjugate gradient method in extreme problems. USSR Computational Mathematics and Mathematical Physics 9, 94–112 (1969)CrossRefMATH

29.

Powell, M.J.D.: Nonconvex Minimization Calculations and the Conjugate Gradient Method, Vol. 1066 of Lecture Notes in Mathematics. Spinger, Berlin (1984)

30.

Powell, M.J.D.: Convergence properties of algorithm for nonlinear optimization. SIAM Review 28, 487–500 (1986)MathSciNetCrossRefMATH

31.

Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Mathematics of Operations Research 18, 227–245 (1993)MathSciNetCrossRefMATH

32.

Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Mathematical Programming 58, 353–367 (1993)MathSciNetCrossRefMATH

33.

Schramm, H.: Eine kombination yon bundle-und trust-region-verfahren zur Lösung nicht- differenzierbare optimierungsprobleme, Bayreuther Mathematische Schriften, Heft 30. University of Bayreuth, Bayreuth (1989)

34.

Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results. SIAM Journal on Optimization 2, 121–152 (1992)MathSciNetCrossRefMATH

35.

Toint, P.L.: An assessment of non-monotone line search techniques for unconstrained minimization problem. SIAM Journal on Computing 17, 725–739 (1996)MathSciNetCrossRefMATH

36.

Wei, Z., Li, G., Qi, L.: Global convergence of the Polak–Ribiere–Polyak conjugate gradient methods with inexact line search for nonconvex unconstrained optimization problems. Mathematics of Computation 77, 2173–2193 (2008)MathSciNetCrossRefMATH

37.

Wei, Z., Li, G., Qi, L.: New quasi-Newton methods for unconstrained optimization problems. Applied Mathematics and Computation 175, 1156–1188 (2006)MathSciNetCrossRefMATH

38.

Wei, Z., Yu, G., Yuan, G., Lian, Z.: The superlinear convergence of a modified BFGS-type method for unconstrained optimization. Computational Optimization and Application 29, 315–332 (2004)MathSciNetCrossRefMATH

39.

Wolfe, P.: A method of conjugate subgradients for minimizing nondifferentiable convex functions. Mathematical Programming Study 3, 145–173 (1975)MathSciNetCrossRefMATH

40.

Xiao, Y., Wei, Z., Wang, Z.: A limited memory BFGS-type method for large-scale unconstrained optimization. Computational Mathematics Applications 56, 1001–1009 (2008)MathSciNetCrossRefMATH

41.

Yuan, G.: Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems. Optimization Letters 3, 11–21 (2009)MathSciNetCrossRefMATH

42.

Yuan, G., Wei, Z.: Convergence analysis of a modified BFGS method on convex minimizations. Computational Optimization and Applications 47, 237–255 (2010)MathSciNetCrossRefMATH

43.

Yuan, G., Wei, Z., Li, G.: A modified PolakCRibièreCPolyak conjugate gradient algorithm for nonsmooth convex programs. Journal of Computational and Applied Mathematics 255, 86–96 (2014)MathSciNetCrossRefMATH

44.

Zhang, J., Deng, N., Chen, L.: New quasi-Newton equation and related methods for unconstrained optimization. Journal of Optimization Theory and Application 102, 147–167 (1999)MathSciNetCrossRefMATH

45.

Zhang, H., Hager, W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM Journal on Optimization 14, 1043–1056 (2004)MathSciNetCrossRefMATH

46.

Zhang, L., Zhou, W., Li, D.: A descent modified Polak–Ribière–Polyak conjugate method and its global convergence. IMA Journal on Numerical Analysis 26, 629–649 (2006)MathSciNetCrossRefMATH

47.

Zhou, J., Tits, A.: Nonmonotone line search for minimax problem. Journal Optimization Theory and Applications 76, 455–476 (1993)MathSciNetCrossRefMATH

48.

Zowe, J.: Computational mathematical programming. In: Schittkowski, K. (ed.) Nondifferentiable optimization, pp. 323–356. Springer, Berlin (1985)

Titel: A modified PRP conjugate gradient algorithm with nonmonotone line search for nonsmooth convex optimization problems
verfasst von: Gonglin Yuan
Zengxin Wei
Publikationsdatum: 01.06.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Applied Mathematics and Computing / Ausgabe 1-2/2016
Print ISSN: 1598-5865
Elektronische ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-015-0912-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1-2/2016

On fuzzy multiset automata

Study on a giant panda reintroduction state feedback control pulse model with diffusion between two patches

Modeling sheep brucellosis transmission with a multi-stage model in Changling County of Jilin Province, China

Generalized Peaceman-Rachford splitting method for separable convex programming with applications to image processing

Douglas–Rachford splitting method for semidefinite programming

A note on “Quotient structures of intuitionistic fuzzy finite state machines”

Premium Partner