Supremum and infimum
Sometimes when reading math books, like Convex Optimization, I stumble upon the infimum ($\inf$) and supremum ($\sup$) operators. For example, let $L(x,\lambda,\nu)$ denote the Lagrangian associated with an optimization problem. The Lagrange dual function is defined as
$$ g(\lambda,\nu) = \inf_{x \in \mathcal{D}} L(x,\lambda,\nu), $$
where $\mathcal{D}$ stands for the domain of $x$. But what exactly is the infimum? And the supremum? What are their relation to the minimum ($\min$) and the maximum ($\max$) operators?
To better understand these operators, I read the great Wikipedia article Infimum and supremum. Therein, we have the following definitions. Let $P$ be a partially ordered set and $S$ a subset, $S \subseteq P$.
Infimum
- A lower bound of $S$ is any element $l \in P$ such that $l \leq x$ for all $x \in S$.
- $l^* \in P$ is the infimum of $S$ if it is larger than any other lower bound, i.e., $l^* \geq l$.
Supremum
- An upper bound of $S$ is any element $u \in P$ such that $u \geq x$ for all $x \in S$.
- $u^* \in P$ is the supremum of $S$ if it is larger than any other upper bound, i.e., $u^* \leq u$.
Consider the following examples to illustrate these definitions:
- Let $P = \mathbb{R}$ and $S = { x \in P \mid 0 < x < 1}$. Then $\inf{P} = 0$ and $\sup{P} = 1$.
- Let $P = \mathbb{Z}$ and $S = {1,2,3}$. Then $\inf{P} = 1$ and $\sup{P}=3$.
In the first example, $P$ does not have minimum and maximum values: for any $x \in S$, we can always define a $y > x$, and a $z < x$. So, infimum and supremum may be useful to describe sets which may not have minimum and maximum. In the second example, the infimum and supremum coincide with minimum and maximum: we have that $\max{S} = \sup{S}=3$ and $\min{S} = \inf{S} = 1$.