# 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

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

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

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

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

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