Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A New Adaptive Conjugate Gradient Algorithm for Large-Scale Unconstrained Optimization Read chapter Read first chapter

2016 | OriginalPaper | Chapter

The Legendre Transformation in Modern Optimization

Author : Roman A. Polyak

Published in: Optimization and Its Applications in Control and Data Sciences

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The Legendre transform (LET) is a product of a general duality principle: any smooth curve is, on the one hand, a locus of pairs, which satisfy the given equation and, on the other hand, an envelope of a family of its tangent lines.
An application of the LET to a strictly convex and smooth function leads to the Legendre identity (LEID). For strictly convex and three times differentiable function the LET leads to the Legendre invariant (LEINV).
Although the LET has been known for more then 200 years both the LEID and the LEINV are critical in modern optimization theory and methods.
The purpose of the paper is to show the role of the LEID and the LEINV play in both constrained and unconstrained optimization.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Algorithmic Principle of Least Revenue for Finding Market Equilibria
Literature
1.
Alber, M., Reemtsen, R.: Intensity modulated radiotherapy treatment planning by use of a barrier-penalty multiplier method. Optim. Methods Softw. 22 (3), 391–411 (2007)MathSciNetCrossRefMATH
2.
Antipin, A.S.: Methods of Nonlinear Programming Based on the Direct and Dual Augmentation of the Lagrangian. VNIISI, Moscow (1979)
3.
Auslender, R., Cominetti, R., Haddou, M.: Asymptotic analysis for penalty and barrier methods in convex and linear programming. Math. Oper. Res. 22 (1), 43–62 (1997)MathSciNetCrossRefMATH
4.
Bauschke, H., Matouskova, E., Reich, S.: Projection and proximal point methods, convergence results and counterexamples. Nonlinear Anal. 56 (5), 715–738 (2004)MathSciNetCrossRefMATH
5.
Ben-Tal, A., Nemirovski, A.: Optimal design of engineering structures. Optima 47, 4–9 (1995)
6.
7.
Bertsekas, D.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982)MATH
8.
Bregman, L.: The relaxation method for finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7, 200–217 (1967)MathSciNetCrossRefMATH
9.
Bregman, L., Censor, Y., Reich, S.: Dykstra algorithm as the nonlinear extension of Bregman’s optimization method. J. Convex Anal. 6 (2), 319–333 (1999)MathSciNetMATH
10.
Breitfeld, M., Shanno, D.: Computational experience with modified log-barrier methods for nonlinear programming. Ann. Oper. Res. 62, 439–464 (1996)MathSciNetCrossRefMATH
11.
Byrne, C., Censor, Y.: Proximity function minimization using multiple Bregman projections with application to split feasibility and Kullback-Leibler distance minimization. Ann. Oper. Res. 105, 77–98 (2001)MathSciNetCrossRefMATH
12.
Carroll, C.: The created response surface technique for optimizing nonlinear-restrained systems. Oper. Res. 9 (2), 169–184 (1961)MathSciNetCrossRefMATH
13.
14.
Chen, C., Mangasarian, O.L.: Smoothing methods for convex inequalities and linear complementarity problems. Math. Program. 71, 51–69 (1995)MathSciNetCrossRefMATH
15.
Chen, G., Teboulle, M.: Convergence analysis of a proximal-like minimization algorithm using Bregman functions. SIAM J. Optim. 3 (4), 538–543 (1993)MathSciNetCrossRefMATH
16.
Courant, R.: Variational methods for the solution of problems of equilibrium and vibrations. Bull. Am. Math. Soc. 49, 1–23 (1943)MathSciNetCrossRefMATH
17.
Daube-Witherspoon, M., Muehllehner, G.: An iterative space reconstruction algorithm suitable for volume ECT. IEEE Trans. Med Imaging 5, 61–66 (1986)CrossRef
18.
Dikin, I.: Iterative solutions of linear and quadratic programming problems. Sov. Math. Dokl. 8, 674–675 (1967)MATH
19.
Eckstein, J.: Nonlinear proximal point algorithms using Bregman functions with applications to convex programming. Math. Oper. Res. 18 (1), 202–226 (1993)MathSciNetCrossRefMATH
20.
21.
Ekeland, I.: Legendre duality in nonconvex optimization and calculus of variations. SIAM J. Control. Optim. 16 (6), 905–934 (1977)MathSciNetCrossRefMATH
22.
Fiacco, A., Mc Cormick, G.: Nonlinear Programming, Sequential Unconstrained Minimization Techniques. SIAM, Philadelphia (1990)CrossRef
23.
Frisch, K.: The logarithmic potential method for convex programming. Memorandum of May 13 1955, University Institute of Economics, Oslo (1955)
24.
Goldshtein, E., Tretiakov, N.: Modified Lagrangian Functions. Nauka, Moscow (1989)
25.
Griva, I., Polyak, R.: Primal-dual nonlinear rescaling method with dynamic scaling parameter update. Math. Program. Ser. A 106, 237–259 (2006)MathSciNetCrossRefMATH
26.
Griva, I., Polyak, R.: Proximal point nonlinear rescaling method for convex optimization. Numer. Algebra Control Optim. 1 (3), 283–299 (2013)MathSciNetMATH
27.
28.
29.
30.
Ioffe, A., Tichomirov, V.: Duality of convex functions and extremum problems. Uspexi Mat. Nauk 23 (6)(144), 51–116 (1968)
31.
Jensen, D., Polyak, R.: The convergence of a modify barrier method for convex programming. IBM J. Res. Dev. 38 (3), 307–321 (1999)CrossRefMATH
32.
Kocvara, M., Stingl, M.: PENNON. A code for convex nonlinear and semidefinite programming. Optim. Methods Softw. 18 (3), 317–333 (2003)MathSciNetCrossRefMATH
33.
Kocvara, M., Stingl, M.: Recent progress in the NLP-SDP code PENNON. In: Workshop Optimization and Applications, Oberwalfach (2005)
34.
Kocvara, M., Stingl, M.: On the solution of large-scale SDP problems by the modified barrier method using iterative solver. Math. Program. Ser. B 109, 413–444 (2007)MathSciNetCrossRefMATH
35.
Martinet, B.: Regularization d’inequations variationelles par approximations successive. Rev. Fr. Inf. Res. Ofer 4 (R3), 154–159 (1970)MathSciNetMATH
36.
Martinet, B.: Determination approachee d’un point fixe d’une application pseudo-contractante. C.R. Acad. Sci. Paris 274 (2), 163–165 (1972)
37.
Matioli, L., Gonzaga, C.: A new family of penalties for augmented Lagrangian methods. Numer. Linear Algebra Appl. 15, 925–944 (2008)MathSciNetCrossRefMATH
38.
39.
Moreau, J.: Proximite et dualite dans un espace Hilbertien. Bull. Soc. Math. France 93, 273–299 (1965)MathSciNetMATH
40.
Motzkin, T.: New techniques for linear inequalities and optimization. In: project SCOOP, Symposium on Linear Inequalities and Programming, Planning Research Division, Director of Management Analysis Service, U.S. Air Force, Washington, D.C., no. 10, (1952)
41.
Nash, S., Polyak, R., Sofer, A.: A numerical comparison of barrier and modified barrier method for large scale bound-constrained optimization. In: Hager, W., Hearn, D., Pardalos, P. (eds.) Large Scale Optimization, State of the Art, pp. 319–338. Kluwer Academic, Dordrecht (1994)CrossRef
42.
Nesterov, Yu., Nemirovsky, A.: Interior Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1994)CrossRef
43.
Nesterov, Yu.: Introductory Lectures on Convex Optimization. Kluwer Academic, Norwell, MA (2004)CrossRefMATH
44.
Polyak, B.: Iterative methods using lagrange multipliers for solving extremal problems with constraints of the equation type. Comput. Math. Math. Phys. 10 (5), 42–52 (1970)MathSciNetCrossRef
45.
Polyak, B.: Introduction to Optimization. Optimization Software, New York (1987)MATH
46.
47.
48.
Polyak, R.: Nonlinear rescaling vs. smoothing technique in convex optimization. Math. Program. 92, 197–235 (2002)MathSciNet
49.
Polyak, R.: Lagrangian transformation and interior ellipsoid methods in convex optimization. J. Optim. Theory Appl. 163 (3), 966–992 (2015)MathSciNetCrossRefMATH
50.
Polyak, R., Teboulle, M.: Nonlinear rescaling and proximal-like methods in convex optimization. Math. Program. 76, 265–284 (1997)MathSciNetMATH
51.
Polyak, B., Tret’yakov, N.: The method of penalty estimates for conditional extremum problems. Comput. Math. Math. Phys. 13 (1), 42–58 (1973)MathSciNetCrossRefMATH
52.
Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher (ed.) Optimization, pp. 283–298. Academic Press, London (1969)
53.
Powell, M.: Some convergence properties of the modified log barrier methods for linear programming. SIAM J. Optim. 50 (4), 695–739 (1995)CrossRefMATH
54.
Ray, A., Majumder, S.: Derivation of some new distributions in statistical mechanics using maximum entropy approach. Yugosl. J. Oper. Res. 24 (1), 145–155 (2014)MathSciNetCrossRef
55.
Reich, S., Sabach, S.: Two strong convergence theorems for a proximal method in reflexive Banach spaces. Numer. Funct. Anal. Optim. 31, 22–44 (2010)MathSciNetCrossRefMATH
56.
Rockafellar, R.T.: A dual approach to solving nonlinear programming problems by unconstrained minimization. Math. Program. 5, 354–373 (1973)MathSciNetCrossRefMATH
57.
Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal points algorithms in convex programming. Math. Oper. Res. 1, 97–116 (1976)MathSciNetCrossRefMATH
58.
59.
60.
Tikhonov, A.N.: Solution of incorrectly formulated problems and the regularization method. Sov. Math. (Translated) 4, 1035–1038 (1963)
61.
Tseng, P., Bertsekas, D.: On the convergence of the exponential multipliers method for convex programming. Math. Program. 60, 1–19 (1993)MathSciNetCrossRefMATH
62.
Metadata
Title
The Legendre Transformation in Modern Optimization
Author
Roman A. Polyak
Copyright Year
2016
Book
Optimization and Its Applications in Control and Data Sciences

Print ISBN: 978-3-319-42054-7

Electronic ISBN: 978-3-319-42056-1

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-42056-1_15