Content deleted Content added
→See also: * Level of measurement ("Ordinal data"), removed stuff discussed and linked in the article |
m WP:CHECKWIKI error fixes + genfixes using AWB (7408) |
||
Line 1:
{{orphan|date=November 2010}}
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]].
Line 6:
{{See also|Mathematical optimization|Partially ordered set|Lattice|Greedoid|Antimatroid|Combinatorial optimization|Duality (mathematics)#Order-reversing dualities}}
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>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
=== Definitions ===
Line 27:
* The [[real number]]s ordered by the standard ''less-than-or-equal'' relation ≤ (a totally ordered set as well).
* The set of [[subset]]s of a given set (its [[power set]]) ordered by [[subset|inclusion]]
* 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 ℕ.
Line 48:
In many such cases, the poset has additional structure: For example, the poset can be a [[lattice (order)|lattice]] or a [[ordered semigroup|partially ordered algebraic structure]].
====Lattices====
{{Main|Lattice (order)}}
A [[Partially ordered set|poset]] (''L'', ≤) is a '''lattice''' if it satisfies the following two axioms.
;Existence of binary joins:
: For any two elements ''a'' and ''b'' of ''L'', the set {''a, b''} has a '''[[Join (mathematics)|join]]''': <math>a \lor b</math> (also known as the least upper bound, or the supremum).
;Existence of binary meets:
: For any two elements ''a'' and ''b'' of ''L'', the set {''a, b''} has a '''[[meet (mathematics)|meet]]''': <math>a \land b</math> (also known as the greatest lower bound, or the infimum).
Line 90:
{{Main|Ordered semigroup}}
{{See also|Ordered vector space|Riesz space}}
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
In [[algebra]], an ''ordered semigroup'' is a [[semigroup]] (''S'',•) together with a [[partial order]] ≤ that is ''compatible'' with the semigroup operation, meaning that ''x'' ≤ ''y'' implies z•x ≤ z•y and x•z ≤ y•z for all ''x'', ''y'', ''z'' in ''S''. If S is a [[
== Ordinal optimization in computer science and statistics ==
Line 99:
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>{{cite book|last1=Gupta|first1=Shanti S.|last2=Panchapakesan|first2=S.|title=Multiple decision procedures: Theory and methodology of selecting and ranking populations|series=Wiley Series in Probability and Mathematical Statistics|publisher=John Wiley & Sons|___location=New York|year=1979|pages=xxv+573|isbn=0-471-05177-2|id={{MR|555416}}|}} (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).
== Applications ==
Line 115:
== References ==
{{
== Further reading ==
* Fujishige, Satoru ''Submodular functions and optimization''. Second edition. Annals of Discrete Mathematics, 58. Elsevier B. V., Amsterdam, 2005. xiv+395 pp.
* 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.
* 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.
* Topkis, Donald M. ''Supermodularity and complementarity''. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp.
* 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.
* 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.
* {{ 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}}|}}
Line 136:
== External links ==
* [http://people.deas.harvard.edu/~ho/DEDS/OO/Reference/OOReference.html Annotated bibliography on ordinal optimization] by [[Yu-Chi Ho]]
{{DEFAULTSORT:Ordinal Optimization}}
[[Category:Mathematical optimization]]
[[Category:Control theory]]
| |||