Kolokoltsov, V. N. (Vasiliĭ Nikitich). (2001) Idempotent structures in optimization. Journal of Mathematical Sciences, Vol.104 (No.1). pp. 847-880. ISSN 10723374

Preview

PDF WRAP_Kolokoltsov_pontr.pdf - Submitted Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (404Kb)

Abstract

Consider the set A = R ∪ {+∞} with the binary operations o1 = max and o2 = + and denote by An the set of vectors v = (v1,...,vn) with entries in A. Let the generalised sum u o1 v of two vectors denote the vector with entries uj o1 vj , and the product a o2 v of an element a ∈ A and a vector v ∈ An denote the vector with the entries a o2 vj . With these operations, the set An provides the simplest example of an idempotent semimodule. The study of idempotent semimodules and their morphisms is the subject of idempotent linear algebra, which has been developing for about 40 years already as a useful tool in a number of problems of discrete optimisation. Idempotent analysis studies infinite dimensional idempotent semimodules and is aimed at the applications to the optimisations problems with general (not necessarily finite) state spaces. We review here the main facts of idempotent analysis and its major areas of applications in optimisation theory, namely in multicriteria optimisation, in turnpike theory and mathematical economics, in the theory of generalised solutions of the Hamilton-Jacobi Bellman (HJB) equation, in the theory of games and controlled Marcov processes, in financial mathematics.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Statistics
Library of Congress Subject Headings (LCSH):	Mathematical optimization, Idempotents
Journal or Publication Title:	Journal of Mathematical Sciences
Publisher:	Springer
ISSN:	10723374
Date:	2001
Volume:	Vol.104
Number:	No.1
Page Range:	pp. 847-880
Identification Number:	10.1023/A:1009514904187
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
References:	[1] M. Akian. Densities of idempotent measures and large deviations. INRIA Report 2534, 1995. [2] M. Akian, R. Bapat, S. Gaubert. Asymptotics of the Perron eigenvalue and eigenvector using max-algebra. C.R. Acad. Sci. Paris, 327 (1): 927- 932, 1998. [3] M. Akian, J.-P. Quadrat and M. Viot. Duality between Probability and OPtimisation. In: “Idempotency” [21], 331-353. [4] S. M. Avdoshin, V. V. Belov, and V. P. Maslov. Mathematical Issues of Computing Media Synthesis [in Russian]. MIEM Publishers, Moscow, 1984. Engl. transl. in [43]. [5] F. Baccelli. Ergodic theory of stochastic Petri networks. Annals of Prob., 20(1):375–396, 1992. [6] F. Baccelli, G. Cohen, G. Olsder, and J.-P. Quadrat. Synchronization and Linearity: an Algebra for Discrete Event Systems. John Wiley Publ., N.Y., 1992. [7] R. Bellman. Dynamic Programming. 1960. [8] W. A. Brock and A. Haurie. On existence of overtaking optimal trajectories over an infinite time horizon. Math. Oper. Res., 1:337–346, 1976. [9] M. D. Bronstein and S. N. Samborskii. A multicriterion variational method for systems of nonlinear partial differential equations. Dokl. Akad. Nauk SSSR, 320(6):1289–1293, 1991. Engl. transl. in Sov. Math. Dokl., 44(2):603–607, 1992. [10] P. Butkovic. Strong regularity of matrices - a survey of results. Discrete Applied Mathematics 48: 45-68, 1994. [11] M. G. Crandall, L. C. Evans, and P. L. Lions. Some properties of viscosity solutions of Hamilton–Jacobi equations. Trans. Amer. Math. Soc., 282:487–502, 1984. [12] M. G. Crandall and P. L. Lions. Viscosity solutions of Hamilton–Jacobi equations. Trans. Amer. Math. Soc., 277:1–42, 1983. [13] M. G. Crandall and P. L. Lions. Hamilton–Jacobi equations in infinite dimension. Part I: Uniqueness of viscosity solutions. J. Funct. Anal., 62:379–396, 1985. [14] M.G. Crandall and L. Tartar. Some relations between nonexpansive and order-preserving mappings. Proc. Amer. Math. Soc., 78: 385-390, 1980. [15] J.C. Cox, S.A. Ross, M. Rubinstein. Option Pricing: A Simplified Approach. J. Financial Economics, 7: 229-263, 1979. [16] R. A. Cuninghame-Green. Minimax algebra. Lect. Notes in Economics and Mathematical Systems, 166, 1979. [17] P. I. Dudnikov and S. N. Samborskii. Endomorphisms of semimodules over semirings with an idempotent operation. Math. USSR Izvestiya, 38(1):91– 105, 1991. [18] M. Gondran, M. Minoux. Graphs and Algorithms. John Wiley, 1984. [19] J. Gunawardena. Min-max functions. Discrete Event Dynamic Systems, 4:377-406, 1994. [20] J. Gunawardena. An introduction to Idempotency. In “Idempotency” [21], 1-49. [21] J. Gunawardena, editor. Proc. Intern. Workshop “Idempotency”, Bristol, October 1994. Cambridge Univ. Press, 1998. [22] S. C. Kleene. Representation of events in nerve nets and finite automata. In J. McCarthy and C. Shannon, editors, Automata Studies, pages 3–40. Princeton University Press, Princeton, 1956. [23] V. N. Kolokoltsov. On linear, additive, and homogeneous operators in idempotent analysis. In Idempotent Analysis [41], pages 87–102. [24] V. N. Kolokoltsov. The stochastic Bellman equation as a nonlinear equation in Maslov spaces. Perturbation theory. Dokl. Akad. Nauk SSSR, 323:223–228, 1992. Engl. transl. in Russian Acad. Sci. Dokl. Math., 45(2):294–300, 1992. [25] V. N. Kolokoltsov. Long time behavior of continuously observed and controlled quantum systems (a study of the Belavkin quantum filtering equation). In Quantum Probability Communications (Eds. R.L. Hudson, J.M. Lindsay), World Scientific, Singapore (1998), 229-243. [26] V. N. Kolokoltsov. Introduction of new currency (coupons) according to Maslov’s idea for solving the market game at inequilibrium prices. Dokl. Akad. Nauk SSSR, 320(6):1310–1314, 1994. Engl. transl. in Russian Acad. Sci. Dokl. Math. [27] V. N. Kolokoltsov. Stochastic Hamilton–Jacobi–Bellman equation and stochastic WKB method. In [21], 285-302. [28] V.N. Kolokoltsov. Nonexpansive maps and option pricing theory. Kibernetika, 34(6): 713-724, 1998. [29] V.N. Kolokoltsov. Semiclassical Approximation for Diffusion and Stochastic Processes. Monograph. Submitted for publication. [30] V. N. Kolokoltsov and O. A. Malafeev. Turnpikes in conflict-controlled processes with infinite time horizon. In International Seminar NODPOC’ 91, Vladivostok, September, pages 58–59, Minsk, 1991. [31] V. N. Kolokoltsov and V. P. Maslov. Bellman’s differential equation and Pontryagin’s maximum principle for multicriteria optimization problem. Dokl. Akad. Nauk SSSR, 324(1):29–34, 1992. Engl. transl. in Sov. Math Dokl. [32] V. N. Kolokoltsov and V. P. Maslov. Idempotent Analysis and Its Application to the Optimal Control [in Russian]. Nauka, Moscow, 1994. [33] V.N. Kolokoltsov, V.P. Maslov. Idempotent Analysis and its Applications Kluwer Academic Publ. 1998. [34] V.N. Kolokoltsov, V.P. Maslov. A new differential equation for the dynamics of the Pareto sets. In “Idempotency” [21], 322-330. [35] A.A. Korbut. Extremal Spaces. Dokl. Akad. Nauk SSSR 164 (6): 1229- 1231, 1965. [36] S. N. Kruzhkov. Generalized solutions of nonlinear equations of first order with several variables. Mat. Sbornik, 70(3):394–415, 1966. Engl. transl. in Math. USSR Sbornik. [37] G. L. Litvinov and V. P. Maslov. Correspondence principle for idempotent calculus and some computer applications. In [21], 420-443. [38] T. Lions. Uncertain volatility and the risk-free synthesis of derivatives. Applied Mathematical Finance, 2: 117-133, 1995. [39] V. P. Maslov. Asymptotic Methods for Solving Pseudodifferential Equations [in Russian]. Nauka, Moscow, 1987. [40] V. P. Maslov. M´ethodes op´eratorielles. ´Editions MIR, Moscow, 1987. [41] V. P. Maslov and S. N. Samborskii. Editors Idempotent Analysis. Number 13 in Advances in Soviet Mathematics. AMS, Providence, RI, 1992 [42] V. P. Maslov and S. N. Samborskii. Stationary Hamilton–Jacobi and Bellman equations (existence and uniqueness of solutions). In Idempotent Analysis [41], pages 87–101. [43] V. P. Maslov and K. A. Volosov, editors. Mathematical Aspects of Computer Engineering. Mir, Moscow, 1988. [44] Gr.C. Moisil. Asupra unor representari ale grafurilor ce intervin in probleme de economia transportirilor. Communicarile Akademie RPR 10 (8): 647-652, 1960. [45] P. Del Moral. Maslov optimization theoryle. Appendix In Idempotent Analysis [33], 243-302. [46] R. O. Nussbaum. Convergence of iterates of a nonlinear operator arising in statistical mechanics. Nonlinearity, 4:1223–1240, 1991. [47] S.N. Pandit. A new matrix calculus. J. Soc. Industr. Appl. Math. 9 (4): 632-639, 1961. [48] I.V. Romanovski. Asymptotical behavior of the processes of dynamic programming with continuous state space. Dokl. Akad. Nauk SSSR 159 (6): 1224-1227, 1964. [49] S. N. Samborskii and A. L. Tarashchan. Semirings occurring in multicriteria optimization problems and in analysis of computing media. Sov. Math. Dokl., 40:441–445, 1990. [50] L. E. Stern. Criteria of optimality in the infinite-time optimal control problem. J. Optimiz. Theory Appl., 44(3):497–508, 1984. [51] A. I. Subbotin. Min-Max solutions and Hamilton–Jacobi Equation [in Russian]. Nauka, Moscow, 1991. [52] A. Truman and H. Z. Zhao. The stochastic Hamilton–Jacobi equation, stochastic heat equations, and Schr¨odinger equations. In: A.Truman, I.M.Davies, K.D. Elworthy (Eds), Stochastic Analysis and Application. World Scientific Press (1996), 441-464. [53] S.R.S. Varadhan. Large Deviations and Applications. CBMS-NSF Regional Conference Series in Applied Mathematics, 46. SIAM Philadelphia, Penn., 1984 [54] N.N. Vorobjev. Extremal Algebra of Matrices. Dokl. Akad. Nauk SSSR 152 (1): 24-27, 1963. [55] N.N. Vorobjev. Extremal Algebra of Positive Matrices. Electron. Informationsverarbeitung und Kybernetik 3: 39-71, 1967 (in Russian). [56] M. Weitzman. Duality theory for infinite horizon convex models. Management Sci., 19(7):783–789, 1973. [57] S. Y. Yakovenko. On the notion of infinite extremal in stationary problems of dynamic optimization. Dokl. Akad. Nauk SSSR., 308(4):758–802, 1989. [58] S. Y. Yakovenko and L. A. Kontorer. Nonlinear semigroups and infinite horizon optimization. In Idempotent Analysis [41], pages 167–210. [59] U. Zimmermann. Linear and Combinatorial Optimization in Ordered Algebraic Structures. Annals of Discrete Mathematics 10. North-Holland, Amsterdam, 1981
URI:	http://wrap.warwick.ac.uk/id/eprint/39365

Request changes to a record

Actions (login required)

View Item