Ordinal optimization: Difference between revisions

Revision as of 18:19, 8 September 2013

Revision as of 11:58, 30 September 2013

Line 90:

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>

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>

== Ordinal optimization in computer science and statistics ==