Ordinal optimization

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

Mathematical foundations

Definitions

A partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., for all a, b, and c in P, we have that:

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:

Extrema

There are several notions of "greatest" and "least" element in a poset P, notably:

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 2g, so 2g 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 lattice or a partially ordered algebraic structure.

Lattices

Main article: Lattice (order)

A 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: (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: (also known as the greatest lower bound, or the infimum).

The join and meet of a and b are denoted by and , respectively. This definition makes and binary operations. The first axiom says that L is a join-semilattice; the second says that L is a meet-semilattice. Both operations are monotone with respect to the order: a1  a2 and b1  b2 implies that a1 b1 ≤ a2 b2 and a1b1 ≤ a2b2.

It follows by an induction argument that every non-empty finite subset of a lattice has a join (supremum) and a meet (infimum). With additional assumptions, further conclusions may be possible; see Completeness (order theory) for more discussion of this subject.

A bounded lattice has a greatest (or maximum) and least (or minimum) element, denoted 1 and 0 by convention (also called top and bottom). Any lattice can be converted into a bounded lattice by adding a greatest and least element, and every non-empty finite lattice is bounded, by taking the join (resp., meet) of all elements, denoted by (resp.) where .

A poset is a bounded lattice if and only if every finite set of elements (including the empty set) has a join and a meet. Here, the join of an empty set of elements is defined to be the least element , and the meet of the empty set is defined to be the greatest element . This convention is consistent with the associativity and commutativity of meet and join: the join of a union of finite sets is equal to the join of the joins of the sets, and dually, the meet of a union of finite sets is equal to the meet of the meets of the sets, i.e., for finite subsets A and B of a poset L,

and

hold. Taking B to be the empty set,

and

which is consistent with the fact that .

Ordered algebraic structure

Main article: Ordered semigroup

The poset can be a partially ordered algebraic structure.[5][6][7][8][9][10][11]

In algebra, an ordered semigroup is a semigroup (S,•) together with a partial order ≤ that is compatible with the semigroup operation, meaning that xy implies z•x ≤ z•y and x•z ≤ y•z for all x, y, z in S. If S is a 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. Partially ordered vector spaces and vector lattices are important in optimization with multiple objectives.[12]

Ordinal optimization in computer science and statistics

Problems of ordinal optimization arise in many disciplines. Computer scientists study selection algorithms, which are simpler than sorting algorithms.[13][14]

Statistical decision theory studies "selection problems" that require the identification of a "best" subpopulation or of identifying a "near best" subpopulation.[15][16][17][18][19]

Applications

Since the 1960s, the field of ordinal optimization has expanded in theory and in applications. 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.[20][21][22]

See also

References

  1. 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.
  2. Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
  3. 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
  4. Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
  5. 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
  6. 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
  7. 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.
  8. 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
  9. Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
  10. Zimmermann, U. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. 10 (1981), viii+380 pp.
  11. 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
  12. 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.
  13. 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.207219.
  14. 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.183196. Section 14.1: Dynamic order statistics, pp.302308.
  15. Gibbons, Jean Dickinson; Olkin, Ingram, and Sobel, Milton, Selecting and Ordering of Populations, Wiley, (1977). (Republished as a Classic in Applied Mathematics by SIAM.)
  16. 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 555416. (Republished as a Classic in Applied Mathematics by SIAM.)
  17. Santner, Thomas J., and Tamhane, A. C., Design of Experiments: Ranking and Selection, M. Dekker, (1984).
  18. 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.
  19. Friedrich Liese, Klaus-J. Miescke. 2008. Statistical Decision Theory: Estimation, Testing, and Selection. Springer Verlag.
  20. 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.
  21. 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.
  22. 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. ISBN 0-691-11763-2. ISBN 0-691-11763-2.

Further reading

External links

This article is issued from Wikipedia - version of the 6/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.