9.7. Generalized Inequalities

A proper cone $K$ can be used to define a generalized inequality, which is a partial ordering on ${\mathbb{R}}^n$.

Definition 9.38

Let $K\subseteq {\mathbb{R}}^n$ be a proper cone. A partial ordering on ${\mathbb{R}}^n$ associated with the proper cone $K$ is defined as

$$x{⪯}_{K}y⟺y-x\in K.$$

We also write $x{⪰}_{K}y$ if $y{⪯}_{K}x$. This is also known as a generalized inequality.

A strict partial ordering on ${\mathbb{R}}^n$ associated with the proper cone $K$ is defined as

$$x{\prec }_{K}y⟺y-x\in \mathring{K}.$$

where $\mathring{K}$ is the interior of $K$. We also write $x{\mathrm{succ}}_{K}y$ if $y{\prec }_{K}x$. This is also known as a strict generalized inequality.

When $K={\mathbb{R}}_{+}$, then ${⪯}_K$ is same as usual $\le$ and ${\prec }_K$ is same as usual $<$ operators on ${\mathbb{R}}_{+}$.

Example 9.20 (Nonnegative orthant and component-wise inequality)

The nonnegative orthant $K={\mathbb{R}}_{+}^n$ is a proper cone. Then the associated generalized inequality ${⪯}_K$ means that

$$x{⪯}_{K}y⟹(y-x)\in {\mathbb{R}}_{+}^n⟹x_i\le y_i\mathrm{\forall }i=1,\dots ,n.$$

This is usually known as component-wise inequality and usually denoted as $x⪯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{⪯}_{S_{+}^n}Y⟹Y-X\in S_{+}^n$$

i.e. $Y-X$ is positive semidefinite. This is also usually denoted as $X⪯Y$.

9.7.1. Minima and maxima

The generalized inequalities (${⪯}_K,{\prec }_K$) w.r.t. the proper cone $K\subset {\mathbb{R}}^n$ define a partial ordering over any arbitrary set $S\subseteq {\mathbb{R}}^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 ${⪯}_K$ or ${\prec }_K$.

Example 9.22 (Partial ordering with nonnegative orthant cone)

Let $K={\mathbb{R}}_{+}^2\subset {\mathbb{R}}^2$. Let $x_1=(2,3),x_2=(4,5),x_3=(-3,5)$. Then we have

• $x_1\prec x_2$, $x_2\mathrm{succ}{x}_1$ and $x_3⪯x_2$.

• But neither $x_1⪯x_3$ nor $x_1⪰x_3$ holds.

• In general For any $x,y\in {\mathbb{R}}^2$, $x⪯y$ if and only if $y$ is to the right and above of $x$ in the ${\mathbb{R}}^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 {\mathbb{R}}^n$ is the minimum element of $S$ w.r.t. the generalized inequality ${⪯}_K$ if for every $y\in S$ we have $x⪯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 {\mathbb{R}}^n$ is the maximum element of $S$ w.r.t. the generalized inequality ${⪯}_K$ if for every $y\in S$ we have $y⪯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={\mathbb{R}}_{+}^n$ and $S={\mathbb{R}}_{+}^n$. Then $0\in S$ is the minimum element since $0⪯x\mathrm{\forall }x\in {\mathbb{R}}_{+}^n$.

Example 9.24 (Maximum element)

Consider $K={\mathbb{R}}_{+}^n$ and $S=\{x|x_i\le 0\mathrm{\forall }i=1,\dots ,n\}$. Then $0\in S$ is the maximum element since $x⪯0\mathrm{\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 ${⪯}_K$ if there is no element $y\in S$ distinct from $x$ such that $y{⪯}_{K}x$. In other words $y{⪯}_{K}x⟹y=x$.

Definition 9.42

An element $x\in S$ is called a maximal element of $S$ w.r.t. the generalized inequality ${⪯}_K$ if there is no element $y\in S$ distinct from $x$ such that $x{⪯}_{K}y$. In other words $x{⪯}_{K}y⟹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{⪯}_{K}y\mathrm{\forall }y\in S$. Thus

$$\begin{array}{rl}& y-x\in K\mathrm{\forall }y\in S\\ ⟹& \text{ there exists some }k\in K\mathrm{\forall }y\in S\text{ such that }y=x+k\\ ⟹& y\in x+K\mathrm{\forall }y\in S\\ ⟹& S\subseteq x+K.\end{array}$$

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{array}{rl}& \mathrm{\exists }k\in K\text{ such that }y=x+k\mathrm{\forall }y\in S\\ ⟹& y-x=k\in K\mathrm{\forall }y\in S\\ ⟹& x{⪯}_{K}y\mathrm{\forall }y\in S.\end{array}$$

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 ${⪯}_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{⪯}_{K}x$.

Consider the set $R=x-K=\{x-k|k\in K\}$.

$$r\in R⟺r=x-k\text{ for some }k\in K⟺x-r\in K⟺r{⪯}_{K}x.$$

Thus $x-K$ consists of all points $r\in {\mathbb{R}}^n$ which satisfy $r{⪯}_{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{⪯}_{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 ${⪯}_K$.