Generalized Inequalities
Contents
9.7. Generalized Inequalities#
A proper cone \(K\) can be used to define a generalized inequality, which is a partial ordering on \(\RR^n\).
Definition 9.38
Let \(K \subseteq \RR^n\) be a proper cone. A partial ordering on \(\RR^n\) associated with the proper cone \(K\) is defined as
We also write \(x \succeq_K y\) if \(y \preceq_K x\). This is also known as a generalized inequality.
A strict partial ordering on \(\RR^n\) associated with the proper cone \(K\) is defined as
where \(\Interior{K}\) is the interior of \(K\). We also write \(x \succ_K y\) if \(y \prec_K x\). This is also known as a strict generalized inequality.
When \(K = \RR_+\), then \(\preceq_K\) is same as usual \(\leq\) and \(\prec_K\) is same as usual \(<\) operators on \(\RR_+\).
Example 9.20 (Nonnegative orthant and component-wise inequality)
The nonnegative orthant \(K=\RR_+^n\) is a proper cone. Then the associated generalized inequality \(\preceq_{K}\) means that
This is usually known as component-wise inequality and usually denoted as \(x \preceq y\).
Example 9.21 (Positive semidefinite cone and matrix inequality)
The positive semidefinite cone \(S_+^n \subseteq S^n\) is a proper cone in the vector space \(S^n\).
The associated generalized inequality means
i.e. \(Y - X\) is positive semidefinite. This is also usually denoted as \(X \preceq Y\).
9.7.1. Minima and maxima#
The generalized inequalities (\(\preceq_K, \prec_K\)) w.r.t. the proper cone \(K \subset \RR^n\) define a partial ordering over any arbitrary set \(S \subseteq \RR^n\).
But since they may not enforce a total ordering on \(S\), not every pair of elements \(x, y\in S\) may be related by \(\preceq_K\) or \(\prec_K\).
Example 9.22 (Partial ordering with nonnegative orthant cone)
Let \(K = \RR^2_+ \subset \RR^2\). Let \(x_1 = (2,3), x_2 = (4, 5), x_3=(-3, 5)\). Then we have
\(x_1 \prec x_2\), \(x_2 \succ x_1\) and \(x_3 \preceq x_2\).
But neither \(x_1 \preceq x_3\) nor \(x_1 \succeq x_3\) holds.
In general For any \(x , y \in \RR^2\), \(x \preceq y\) if and only if \(y\) is to the right and above of \(x\) in the \(\RR^2\) plane.
If \(y\) is to the right but below or \(y\) is above but to the left of \(x\), then no ordering holds.
Definition 9.39
We say that \(x \in S \subseteq \RR^n\) is the minimum element of \(S\) w.r.t. the generalized inequality \(\preceq_K\) if for every \( y \in S\) we have \(x \preceq y\).
\(x\) must belong to \(S\).
It is highly possible that there is no minimum element in \(S\).
If a set \(S\) has a minimum element, then by definition it is unique (Prove it!).
Definition 9.40
We say that \(x \in S \subseteq \RR^n\) is the maximum element of \(S\) w.r.t. the generalized inequality \(\preceq_K\) if for every \( y \in S\) we have \(y \preceq x\).
\(x\) must belong to \(S\).
It is highly possible that there is no maximum element in \(S\).
If a set \(S\) has a maximum element, then by definition it is unique.
Example 9.23 (Minimum element)
Consider \(K = \RR^n_+\) and \(S = \RR^n_+\). Then \(0 \in S\) is the minimum element since \(0 \preceq x \Forall x \in \RR^n_+\).
Example 9.24 (Maximum element)
Consider \(K = \RR^n_+\) and \(S = \{x | x_i \leq 0 \Forall i=1,\dots,n\}\). Then \(0 \in S\) is the maximum element since \(x \preceq 0 \Forall x \in S\).
There are many sets for which no minimum element exists. In this context we can define a slightly weaker concept known as minimal element.
Definition 9.41
An element \(x\in S\) is called a minimal element of \(S\) w.r.t. the generalized inequality \(\preceq_K\) if there is no element \(y \in S\) distinct from \(x\) such that \(y \preceq_K x\). In other words \(y \preceq_K x \implies y = x\).
Definition 9.42
An element \(x\in S\) is called a maximal element of \(S\) w.r.t. the generalized inequality \(\preceq_K\) if there is no element \(y \in S\) distinct from \(x\) such that \(x \preceq_K y\). In other words \(x \preceq_K y \implies y = x\).
The minimal or maximal element \(x\) must belong to \(S\).
It is highly possible that there is no minimal or maximal element in \(S\).
Minimal or maximal element need not be unique. A set may have many minimal or maximal elements.
Lemma 9.1
A point \(x \in S\) is the minimum element of \(S\) if and only if
Proof. Let \(x \in S\) be the minimum element. Then by definition \(x \preceq_K y \Forall y \in S\). Thus
Note that \(k \in K\) would be distinct for each \( y \in S\).
Now let us prove the converse.
Let \(S \subseteq x + K\) where \(x \in S\). Thus
Thus \(x\) is the minimum element of \(S\) since there can be only one minimum element of S.
\(x + K \) denotes all the points that are comparable to \(x\) and greater than or equal to \(x\) according to \(\preceq_K\).
Lemma 9.2
A point \(x \in S\) is a minimal point if and only if
Proof. Let \(x \in S\) be a minimal element of \(S\). Thus there is no element \(y \in S\) distinct from \(x\) such that \(y \preceq_K x\).
Consider the set \(R = x - K = \{x - k | k \in K \}\).
Thus \(x - K\) consists of all points \(r \in \RR^n\) which satisfy \( r \preceq_K x\). But there is only one such point in \(S\) namely \(x\) which satisfies this. Hence
Now let us assume that \(\{ x - K \} \cap S = \{ x \}\). Thus the only point \(y \in S\) which satisfies \(y \preceq_K x\) is \(x\) itself. Hence \(x\) is a minimal element of \(S\).
\(x - K\) represents the set of points that are comparable to \(x\) and are less than or equal to \(x\) according to \(\preceq_K\).