8.7. Generalized Inequalities¶

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

Definition 8.38

Let $K \subseteq R^{n}$ be a proper cone. A partial ordering on $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 $R^{n}$ associated with the proper cone $K$ is defined as

x ≺_{K} y ⟺ y - x \in \overset{˚}{K} .

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

When $K = R_{+}$ , then $⪯_{K}$ is same as usual $\leq$ and $≺_{K}$ is same as usual $<$ operators on $R_{+}$ .

Example 8.20 (Nonnegative orthant and component-wise inequality)

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

x ⪯_{K} y ⟹ (y - x) \in R_{+}^{n} ⟹ x_{i} \leq y_{i} \forall i = 1, \dots, n .

This is usually known as component-wise inequality and usually denoted as $x ⪯ y$ .

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

8.7.1. Minima and maxima¶

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

Example 8.22 (Partial ordering with nonnegative orthant cone)

Let $K = R_{+}^{2} \subset R^{2}$ . Let $x_{1} = (2, 3), x_{2} = (4, 5), x_{3} = (- 3, 5)$ . Then we have

$x_{1} ≺ x_{2}$ , $x_{2} 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 R^{2}$ , $x ⪯ y$ if and only if $y$ is to the right and above of $x$ in the $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 8.39

We say that $x \in S \subseteq 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 8.40

We say that $x \in S \subseteq 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 8.23 (Minimum element)

Consider $K = R_{+}^{n}$ and $S = R_{+}^{n}$ . Then $0 \in S$ is the minimum element since $0 ⪯ x \forall x \in R_{+}^{n}$ .

Example 8.24 (Maximum element)

Consider $K = R_{+}^{n}$ and $S = {x | x_{i} \leq 0 \forall i = 1, \dots, n}$ . Then $0 \in S$ is the maximum element since $x ⪯ 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 8.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 8.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 8.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 \forall y \in S$ . Thus

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

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

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 8.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 for some k \in K ⟺ x - r \in K ⟺ r ⪯_{K} x .

Thus $x - K$ consists of all points $r \in 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}$ .

Topics in Signal Processing

Generalized Inequalities

Contents

8.7. Generalized Inequalities¶

8.7.1. Minima and maxima¶