Jump to content

Ordinal optimization

Edit links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Mark viking (talk | contribs) at 12:17, 29 August 2022 (cut out unneeded expository copypasta and some refs of unclear relevance). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In mathematical optimization, ordinal optimization is the maximization of functions taking values in a partially ordered set ("poset").[1][2][3][4]

Problems of ordinal optimization arise in many disciplines. Ordinal optimization has applications in the theory of queuing networks. In particular, antimatroids and the "max-plus algebra" have found application in network analysis and queuing theory, particularly in queuing networks and discrete-event systems.[5][6][7] Computer scientists study selection algorithms, which are simpler than sorting algorithms.[8][9] Statistical decision theory studies "selection problems" that require the identification of a "best" subpopulation or of identifying a "near best" subpopulation.[10][11][12] Partially ordered vector spaces and vector lattices are important in optimization with multiple objectives.[13]

See also

References

  1. ^ Dietrich & Hoffman 2003.
  2. ^ Topkis 1998.
  3. ^ Singer 1997.
  4. ^ Björner & Ziegler 1992.
  5. ^ Glasserman & Yao 1994.
  6. ^ Baccelli et al. 1992.
  7. ^ Heidergott, Oldser & van der Woude 2006.
  8. ^ Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp.207–219.
  9. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp.183–196. Section 14.1: Dynamic order statistics, pp.302–308.
  10. ^ Gibbons, Jean Dickinson; Olkin, Ingram, and Sobel, Milton, Selecting and Ordering of Populations, Wiley, (1977). (Republished as a Classic in Applied Mathematics by SIAM.)
  11. ^ Gupta, Shanti S.; Panchapakesan, S. (1979). Multiple decision procedures: Theory and methodology of selecting and ranking populations. Wiley Series in Probability and Mathematical Statistics. New York: John Wiley & Sons. pp. xxv+573. ISBN 0-471-05177-2. MR 0555416. (Republished as a Classic in Applied Mathematics by SIAM.)
  12. ^ Santner, Thomas J., and Tamhane, A. C., Design of Experiments: Ranking and Selection, M. Dekker, (1984).
  13. ^ Zălinescu, C. (2002). Convex analysis in general vector spaces. River Edge, NJ: World Scientific Publishing  Co., Inc. pp. xx+367. ISBN 981-238-067-1. MR 1921556.

Further reading

  • ‹See TfM›Fujishige, Satoru Submodular functions and optimization. Second edition. Annals of Discrete Mathematics, 58. Elsevier B. V., Amsterdam, 2005. xiv+395 pp. ISBN 0-444-52086-4
  • ‹See TfM›Gondran, Michel; Minoux, Michel Graphs, dioids and semirings. New models and algorithms. Operations Research/Computer Science Interfaces Series, 41. Springer, New York, 2008. xx+383 pp. ISBN 978-0-387-75449-9
  • ‹See TfM›Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. IBM J. Res. Dev. 47 (2003), no. 1, 25–30.
  • ‹See TfM›Murota, Kazuo Discrete convex analysis. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003. xxii+389 pp. ISBN 0-89871-540-7
  • ‹See TfM›Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
  • ‹See TfM›Singer, Ivan Abstract convex analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp. ISBN 0-471-16015-6
  • ‹See TfM›Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
  • ‹See TfM›Zimmermann, U. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. 10 (1981), viii+380 pp.
  • ‹See TfM›Cuninghame-Green, Raymond Minimax algebra. Lecture Notes in Economics and Mathematical Systems, 166. Springer-Verlag, Berlin-New York, 1979. xi+258 pp. ISBN 3-540-09113-0
  • Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre (1992). Synchronization and linearity: An algebra for discrete event systems. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: John Wiley & Sons, Ltd. pp. xx+489. ISBN 0-471-93609-X. MR 1204266.
  • Glasserman, Paul; Yao, David D. (1994). Monotone structure in discrete-event systems. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. New York: John Wiley & Sons, Inc. pp. xiv+297. ISBN 0-471-58041-4. MR 1266839.
  • Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob (2006). Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. pp. xii+213. ISBN 978-0-691-11763-8. MR 2188299.
  • Ho, Y.C., Sreenivas, R., Vakili, P.,"Ordinal Optimization of Discrete Event Dynamic Systems", J. of DEDS 2(2), 61-88, (1992).
  • Allen, Eric, and Marija D. Ilić. Price-Based Commitment Decisions in the Electricity Market. Advances in industrial control. London: Springer, 1999. ISBN 978-1-85233-069-9
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ordinal_optimization&oldid=1107329511"