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:

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 distinct elements a, b 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 numbers ordered by the standard less-than-or-equal relation ≤ (a totally ordered set as well).
The set of subsets of a given set (its power set) ordered by inclusion
The set of subspaces of a vector space ordered by inclusion.
For a partially ordered set P, the sequence space containing all sequences of elements from P, where sequence a precedes sequence b if every item in a precedes the corresponding item in b. Formally, $(an)n∈[math]\displaystyle{ \mathbb{N} }[/math] ≤ (bn)n∈[math]\displaystyle{ \mathbb{N} }[/math]$ if and only if $a n \leq b n$ for all n in [math]\displaystyle{ \mathbb{N} }[/math].
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.
The set of natural numbers equipped with the relation of divisibility.

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 elements 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 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 page: 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: [math]\displaystyle{ 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: [math]\displaystyle{ a \land b }[/math] (also known as the greatest lower bound, or the infimum).

The join and meet of a and b are denoted by [math]\displaystyle{ a \lor b }[/math] and [math]\displaystyle{ a \land b }[/math], respectively. This definition makes [math]\displaystyle{ \lor }[/math] and [math]\displaystyle{ \land }[/math] 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: a₁ ≤ a₂ and b₁ ≤ b₂ implies that a₁[math]\displaystyle{ \lor }[/math] b₁ ≤ a₂ [math]\displaystyle{ \lor }[/math] b₂ and a₁[math]\displaystyle{ \land }[/math]b₁ ≤ a₂[math]\displaystyle{ \land }[/math]b₂.

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 [math]\displaystyle{ \bigvee A=a_1\lor\cdots\lor a_n }[/math] (resp.[math]\displaystyle{ \bigwedge A=a_1\land\cdots\land a_n }[/math]) where [math]\displaystyle{ A=\{a_1,\ldots,a_n\} }[/math].

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 [math]\displaystyle{ \bigvee\varnothing=0 }[/math], and the meet of the empty set is defined to be the greatest element [math]\displaystyle{ \bigwedge\varnothing=1 }[/math]. 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,

[math]\displaystyle{ \bigvee \left( A \cup B \right)= \left( \bigvee A \right) \vee \left( \bigvee B \right) }[/math]

and

[math]\displaystyle{ \bigwedge \left( A \cup B \right)= \left(\bigwedge A \right) \wedge \left( \bigwedge B \right) }[/math]

hold. Taking B to be the empty set,

[math]\displaystyle{ \bigvee \left( A \cup \emptyset \right) = \left( \bigvee A \right) \vee \left( \bigvee \emptyset \right) = \left( \bigvee A \right) \vee 0 = \bigvee A }[/math]

and

[math]\displaystyle{ \bigwedge \left( A \cup \emptyset \right) = \left( \bigwedge A \right) \wedge \left( \bigwedge \emptyset \right) = \left( \bigwedge A \right) \wedge 1 = \bigwedge A }[/math]

which is consistent with the fact that [math]\displaystyle{ A \cup \emptyset = A }[/math].

Ordered algebraic structure

Main page: Ordered semigroup

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

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 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.^[11]