Ordinal optimization: Difference between revisions

Revision as of 15:13, 9 February 2018

Revision as of 05:25, 28 August 2018

Line 1:

In [[mathematical optimization]], '''ordinal optimization''' is the maximization of functions taking values in a [[partially ordered set]] ("poset").<ref>Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. ''IBM J. Res. DevelopDev.'' 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> Ordinal optimization has applications in the theory of [[queuing theory|queuing]] [[flow network|networks]].

== Mathematical foundations ==

Line 86:

{{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|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. DevelopDev.'' 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>

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 [[Group (mathematics)|group]] and it is ordered as a semigroup, one obtains the notion of [[ordered group]], and similarly if S is a [[monoid]] it may be called ''ordered monoid''. [[Ordered vector space|Partially ordered vector space]]s and [[Riesz space|vector lattice]]s are important in [[multiobjective optimization|optimization with multiple objectives]].<ref>{{cite book|last=Zălinescu|first=C.|title=Convex analysis in general vector spaces|publisher=World Scientific Publishing&nbsp; Co.,&nbsp;Inc|___location = River Edge,&nbsp;NJ|year= 2002|pages=xx+367|isbn=981-238-067-1|mr=1921556}}</ref>

Line 117:

* 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. DevelopDev.'' 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) -->