|
#REDIRECT [[Mathematical optimization]]
{{orphan}}
In [[mathematical optimization]], '''ordinal optimization''' is the maximization of functions taking values in a [[partially ordered set]] ("poset"). Ordinal optimization has applications in the theory of [[queuing theory|queuing]] [[flow network|networks]].
{{Rcat shell|
== Mathematical foundations ==
{{R to related topic}}
{{See also|Mathematical optimization|Partially ordered set|Lattice|Greedoid|Antimatroid|Combinatorial optimization|Duality (mathematics)#Order-reversing dualities}}
{{R without mention}}
}}
Ordinal optimization is the maximization of function taking values in a [[partially ordered set]] ("poset") — or, [[duality (mathematics)#Order-reversing dualities|dually]], the minimization of functions taking values in a poset.</ref><ref>Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. ''IBM J. Res. Develop.'' 47 (2003), no. 1, 25–30. <!-- MR1957350 (2003k:90102) --></ref><ref>Topkis, Donald M. ''Supermodularity and complementarity''. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN: 0-691-03244-0 <!-- MR1614637 (99i:90024) --></ref><ref>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 <!-- MR1461544 --></ref><ref>Björner, Anders; Ziegler, Günter M. Introduction to greedoids. ''Matroid applications'', 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,<!-- MR1165545 (94a:05038) --></ref>
=== Definitions ===
A '''partial order''' is a [[binary relation]] "≤" over a [[Set (mathematics)|set]] ''P'' which is [[reflexive relation|reflexive]], [[antisymmetric relation|antisymmetric]], and [[transitive relation|transitive]], i.e., for all ''a'', ''b'', and ''c'' in ''P'', we have that:
*''a ≤ a'' (reflexivity);
*if ''a ≤ b'' and ''b ≤ a'' then ''a'' = ''b'' (antisymmetry);
*if ''a ≤ b'' and ''b ≤ c'' then ''a ≤ c'' (transitivity).
In other words, a partial order is an antisymmetric [[preorder]].
A set with a partial order is called a '''partially ordered set''' (also called a '''poset'''). The term ''ordered set'' is sometimes also used for posets, as long as it is clear from the context that no other kinds of orders are meant. In particular, totally ordered sets can also be referred to as "ordered sets", especially in areas where these structures are more common than posets.
For ''a, b'' distinct elements of a partially ordered set ''P'', if ''a ≤ b'' or ''b ≤ a'', then ''a'' and ''b'' are '''comparable'''. Otherwise they are '''incomparable'''. If every two elements of a poset are comparable, the poset is called a [[totally ordered set]] or '''chain''' (e.g. the natural numbers under order). A poset in which every two elements are incomparable is called an [[antichain]].
=== Examples ===
Standard examples of posets arising in mathematics include:
* The [[real number]]s ordered by the standard ''less-than-or-equal'' relation ≤ (a totally ordered set as well).
* The set of [[natural number]]s equipped with the relation of [[divisor#Divisibility of numbers|divisibility]].
* The set of [[subset]]s of a given set (its [[power set]]) ordered by [[subset|inclusion]] (see the figure on top-right).
* The set of subspaces of a [[vector space]] ordered by inclusion.
* For a partially ordered set ''P'', the [[sequence space]] containing all [[sequence]]s of elements from ''P'', where sequence ''a'' precedes sequence ''b'' if every item in ''a'' precedes the corresponding item in ''b''. Formally, <big>(''a''<sub>''n''</sub>)<sub>''n''∈ℕ</sub> ≤ (''b''<sub>''n''</sub>)<sub>''n''∈ℕ</sub></big> if and only if <big>''a''<sub>''n''</sub> ≤ ''b''<sub>''n''</sub></big> for all ''n'' in ℕ.
* For a set ''X'' and a partially ordered set ''P'', the [[function space]] containing all functions from ''X'' to ''P'', where ''f'' ≤ ''g'' if and only if ''f''(''x'') ≤ ''g''(''x'') for all ''x'' in ''X''.
* The vertex set of a [[directed acyclic graph]] ordered by [[reachability]].
* A [[Fence (mathematics)|fence]], a partially ordered set defined by an alternating sequence of order relations ''a'' < ''b'' > ''c'' < ''d'' ...
=== Extrema ===
There are several notions of "greatest" and "least" element in a poset ''P'', notably:
* [[Greatest element]] and least element: An element ''g'' in ''P'' is a greatest element if for every element ''a'' in ''P'', ''a'' ≤ ''g''. An element ''m'' in ''P'' is a least element if for every element ''a'' in ''P'', ''a'' ≥ ''m''. A poset can only have one greatest or least element.
* [[Maximal element]]s and minimal elements: An element ''g'' in P is a maximal element if there is no element ''a'' in ''P'' such that ''a'' > ''g''. Similarly, an element ''m'' in ''P'' is a minimal element if there is no element ''a'' in P such that ''a'' < ''m''. If a poset has a greatest element, it must be the unique maximal element, but otherwise there can be more than one maximal element, and similarly for least elements and minimal elements.
* [[Upper and lower bounds]]: For a subset ''A'' of ''P'', an element ''x'' in ''P'' is an upper bound of ''A'' if ''a'' ≤ ''x'', for each element ''a'' in ''A''. In particular, ''x'' need not be in ''A'' to be an upper bound of ''A''. Similarly, an element ''x'' in ''P'' is a lower bound of ''A'' if ''a'' ≥ ''x'', for each element ''a'' in ''A''. A greatest element of ''P'' is an upper bound of ''P'' itself, and a least element is a lower bound of ''P''.
For example, consider the natural numbers, ordered by divisibility: 1 is a least element, as it divides all other elements, but this set does not have a greatest element nor does it have any maximal elements: any ''g'' divides 2''g'', so 2''g'' is greater than ''g'' and ''g'' cannot be maximal. If instead we consider only the natural numbers that are greater than 1, then the resulting poset does not have a least element, but any [[prime number]] is a minimal element. In this poset, 60 is an upper bound (though not the least upper bound) of {2,3,5} and 2 is a lower bound of {4,6,8,12}.
=== Additional structure ===
In many such cases, the poset has additional structure: For example, the poset can be a [[semilattice]] or [[lattice (order)|lattice]] or the poset can be a [[Ordered semigroup|partially ordered algebraic structure]].<ref>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 <!-- MR2171629 (2006d:90098) --></ref><ref>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 <!-- MR2389137 (2009g:16066) --></ref><ref>Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. ''IBM J. Res. Develop.'' 47 (2003), no. 1, 25–30. <!-- MR1957350 (2003k:90102) --></ref><ref>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 <!-- MR1997998 (2004f:90007) --></ref><ref>Topkis, Donald M. ''Supermodularity and complementarity''. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN: 0-691-03244-0 <!-- MR1614637 (99i:90024) --></ref><ref>Zimmermann, U. ''Linear and combinatorial optimization in ordered algebraic structures''. Ann. Discrete Math. 10 (1981), viii+380 pp. <!-- MR0609751 --></ref><ref>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 <!-- MR0580321 --></ref>
== Ordinal optimization in the mathematical sciences ==
{{See also|Selection algorithm}}
Problems of ordinal optimization arise in many disciplines. [[Computer science|Computer scientists]] study [[selection algorithm]]s, which are simpler than [[sorting algorithm]]s.<ref>[[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.</ref><ref>[[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.</ref>
[[Statistical decision theory]] studies "selection problems" that require the identification of a "best" subpopulation or of identifying a "near best" subpopulation.<ref>Gibbons, Jean Dickinson; [[Ingram Olkin|Olkin, Ingram]], and Sobel, Milton, ''Selecting and Ordering of Populations'', Wiley, (1977). (Republished as a Classic in Applied Mathematics by SIAM.)</ref><ref>Santner, Thomas J., and Tamhane, A. C., ''Design of Experiments: Ranking and Selection'', M. Dekker, (1984). </ref><ref>Robert E. Bechhofer, Thomas J. Santner, David M. Goldsman. ''Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons''. John Wiley & Sons, 1995.</ref><ref>Friedrich Liese, Klaus-J. Miescke. 2008. ''Statistical Decision Theory: Estimation, Testing, and Selection''. Springer Verlag.</ref>
== Applications ==
{{See also|Antimatroid|Max-plus algebra|Flow network|Queuing theory|Discrete event simulation}}
Since the 1960s, the field of ordinal optimization has expanded in theory and in applications. In particular, [[antimatroid]]s and the "[[max-plus algebra]]" have found application in [[flow network|network analysis]] and [[queuing theory]], particularly in queuing networks and [[discrete event simulation|discrete-event systems]].<ref>{{ cite book| last1=Glasserman|first1=Paul|last2=Yao|first2=David D.|title=Monotone structure in discrete-event systems|series=Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics|publisher=John Wiley & Sons, Inc.|___location=New York|1994|pages=xiv+297|isbn=0-471-58041-4|id={{MR|1266839}} }}</ref><ref>{{ cite book|author=Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre|title=Synchronization and linearity: An algebra for discrete event systems|series=Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics|publisher=John Wiley & Sons, Ltd.|___location=Chichester|year=1992|pages=xx+489|isbn=0-471-93609-X |id={{MR|1204266}} }}</ref><ref>{{ cite book|author=Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob|title=Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications|series=Princeton Series in Applied Mathematics|publisher=Princeton University Press|___location=Princeton, NJ|year=2006|pages=xii+213|isbn=978-0-691-11763-8, 0-691-11763-2, 0-691-11763-2|id={{MR|2188299}} }}</ref>
== See also ==
* [[Stochastic optimization]]
* [[Computational complexity theory]]
* [[Heuristic (computer science)|Heuristics]]
* [[Operations research]]
* [[Discrete event simulation]]
* [[Queuing theory]]
== References ==
{{refs|colwidth=30em}}
== Further reading ==
* 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 <!-- MR2171629 (2006d:90098) -->
* 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 <!-- MR2389137 (2009g:16066) -->
* Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. ''IBM J. Res. Develop.'' 47 (2003), no. 1, 25–30. <!-- MR1957350 (2003k:90102) -->
* 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 <!-- MR1997998 (2004f:90007) -->
* Topkis, Donald M. ''Supermodularity and complementarity''. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN: 0-691-03244-0 <!-- MR1614637 (99i:90024) -->
* 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 <!-- MR1461544 -->
* Björner, Anders; Ziegler, Günter M. Introduction to greedoids. ''Matroid applications'', 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,<!-- MR1165545 (94a:05038) -->
* Zimmermann, U. ''Linear and combinatorial optimization in ordered algebraic structures''. Ann. Discrete Math. 10 (1981), viii+380 pp. <!-- MR0609751 -->
* 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 <!-- MR0580321 -->
* {{ cite book|author=Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre|title=Synchronization and linearity: An algebra for discrete event systems|series=Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics|publisher=John Wiley & Sons, Ltd.|___location=Chichester|year=1992|pages=xx+489|isbn=0-471-93609-X
|id={{MR|1204266}}|}}
* {{ cite book| last1=Glasserman|first1=Paul|last2=Yao|first2=David D.|title=Monotone structure in discrete-event systems|series=Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics|publisher=John Wiley & Sons, Inc.|___location=New York|1994|pages=xiv+297|isbn=0-471-58041-4|id={{MR|1266839}}|}}
* {{ cite book|author=Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob|title=Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications|series=Princeton Series in Applied Mathematics|publisher=Princeton University Press|___location=Princeton, NJ|year=2006|pages=xii+213|isbn=978-0-691-11763-8, 0-691-11763-2, 0-691-11763-2|id={{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. Ilic. Price-Based Commitment Decisions in the Electricity Market. Advances in industrial control. London: Springer, 1999. ISBN 9781852330699
== External links ==
* [http://people.deas.harvard.edu/~ho/DEDS/OO/Reference/OOReference.html Annotated bibliography on ordinal optimization]
[[Category:Mathematical optimization]]
[[Category:Control theory]]
[[Category:Order theory]]
[[Category:Selection algorithms]]
|
