7.7. Generalized Inequalities#

A proper cone \(K\) can be used to define a generalized inequality, which is a partial ordering on \(\RR^n\).

Definition 7.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

\[ x \preceq_{K} y \iff y - x \in K. \]

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

\[ x \prec_{K} y \iff y - x \in \Interior{K}. \]

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 7.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

\[ x \preceq_K y \implies (y-x) \in \RR_+^n \implies x_i \leq y_i \Forall i= 1,\dots,n. \]

This is usually known as component-wise inequality and usually denoted as \(x \preceq y\).

Example 7.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

\[ X \preceq_{S_+^n} Y \implies Y - X \in S_+^n \]

i.e. \(Y - X\) is positive semidefinite. This is also usually denoted as \(X \preceq Y\).

7.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 7.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 7.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 7.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 7.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 7.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 7.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 7.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 7.1

A point \(x \in S\) is the minimum element of \(S\) if and only if

\[ S \subseteq x + K \]

Proof. Let \(x \in S\) be the minimum element. Then by definition \(x \preceq_K y \Forall y \in S\). Thus

\[\begin{split} & y - x \in K \Forall y \in S \\ \implies & \text{ there exists some } k \in K \Forall y \in S \text{ such that } y = x + k\\ \implies & y \in x + K \Forall y \in S\\ \implies & S \subseteq x + K. \end{split}\]

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

\[\begin{split} & \exists k \in K \text{ such that } y = x + k \Forall y \in S\\ \implies & y - x = k \in K \Forall y \in S\\ \implies & x \preceq_K y \Forall y \in S. \end{split}\]

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 7.2

A point \(x \in S\) is a minimal point if and only if

\[ \{ x - K \} \cap S = \{ x \}. \]

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 \}\).

\[ r \in R \iff r = x - k \text { for some } k \in K \iff x - r \in K \iff r \preceq_K x. \]

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

\[ \{ x - K \} \cap S = \{ x \}. \]

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\).