Mathematics

A Generalization of Convex Sets and Convex Functions

  1. Introduction
  2. The setting: a vector space over a field with a partial order
  3. A Convex set is the same as an order-convex set
  4. A convex function defined in terms of a convex set
  5. A convex function in terms of order-convexity
  6. Convex sets and convex functions in machine learning
    1. Convex Optimization
    2. Software Libraries

Introduction

Convex sets are thought of as subsets of $\mathbb{R}^{n}$, with $n$ a nonnegative integer, and convex functions as real-valued functions on convex subsets of $\mathbb{R}^{n}$. For instance, see this paper, p. 11 and this one. We’ll show you that convex sets and convex functions can be seen in a more general framework.

The setting: a vector space over a field with a partial order

To give you a hint of where we’re going, we’ll start by defining an $\textbf{order-convex}$ subset $S$ of any set $X$ with a reflexive and transitive order $\leq$ as a set such that for all $x,y$ in $S$ and any $z$ in $X$, $x\leq z\leq y$ implies $z$ is in $S$, and let $V$ be any vector space over a field $\mathbb{F}$ with a partial order $\leq$, satisfying these rules:
1. $0\leq1$;
2. for all $s,t\in\mathbb{F}$, if $s,t\geq0$ then $st\geq0$;
3. for all $r,s,t$ in $\mathbb{F}$, $r\le s$ implies $r+t\leq s+t$.

Then a $\textbf{convex}$ $\textbf{set}$ $C$ is a subset of $V$ such that for all $x,y$ in $C$ and for any $t$ in the interval $\left[0,1\right]$ in $\mathbb{F}$, the element $\left(1-t\right)x+ty$ is in $C$, and a $\textbf{convex function}$ $f$ is a function from a convex set $C$ to $\mathbb{F}$ such that for all $x,y$ in $C$ and any $t$ in the interval $\left[0,1\right]$, it follows $f\left(tx+\left(1-t\right)y\right)\leq tf\left(x\right)+\left(1-t\right)f\left(y\right)$. The relationship between order-convexity and convexity is as follows. For any $x,y$ in $C$, define the function $\phi_{x,y}$ from $\left[0,1\right]$ to $V$ as $\phi_{x,y}\left(t\right)=\left(1-t\right)x+ty$. Then we can define an order on the vector space $V$ as $x\leq y$ if there is a function $\phi_{x,y}$. For any $x,y$ in $V$ and any $t$ in $\left[0,1\right]$, the element $\left(1-t\right)x+ty$ always exists since $V$ is a vector space, so for all $x,y$ in $V$ we have $x\leq y$. It follows that this order on $V$ is reflexive and transitive, which we reiterate with this lemma:
Lemma 1: For all $x,y,z$ in $V$,
1. $x\leq x$;
2. $x\leq y\leq z$ $\textrm{implies}$ $x\leq z$.

A Convex set is the same as an order-convex set

When a vector space has this reflexive and transitive order, as defined above, order-convexity coincides with convexity. We show this with the following:
Theorem 2: Let $V$ be any vector space over a field with a partial order; also, let $V$ have the order $x\leq y$ if there is $\phi_{x,y}$. Then, for any subset $C$ of $V$, we have $C$ is convex if and only if $C$ is order-convex. 

Proof: Assume $C$ is convex. Let $x,z$ be in $C$ and $y$ in $V$, and suppose $x\leq y\leq z$, so there is $\phi_{x,y}$. Hence, $y=\phi_{x,y}\left(1\right)=\left(1-1\right)x+1y$, so $y$ is in $C$. Now, assume $C$ is order-convex. Let $x,y$ be in $C$, and for any $t$ in $\left[0,1\right]$, let $u=\left(1-t\right)x+ty$. Since $u$ is in $V$, $x\leq u\leq y$, so $u$ is in $C$. 

A convex function defined in terms of a convex set

A convex function can be defined in terms of a convex set. For any function $f$ from a convex subset $C$ of $V$ to the field $\mathbb{F}$ with a partial order, let $A\left(C,f\right)$ be the set of pairs $\left\langle c,y\right\rangle $ such that $f\left(c\right)\leq y$. Note that $A\left(C,f\right)$ is a subset of $V\times\mathbb{F}$, which is a vector space over $\mathbb{F}$ with operations defined as follows: $\left\langle v_{1},t_{1}\right\rangle +\left\langle v_{2},t_{2}\right\rangle :=\left\langle v_{1}+v_{2},t_{1}+t_{2}\right\rangle $ and $k\left\langle v_{1},t_{1}\right\rangle :=\left\langle kv_{1},kt_{1}\right\rangle $ with $k$ in $\mathbb{F}$. Then define $f$ to be convex if $A\left(C,f\right)$ is convex, as a subset of $V\times\mathbb{F}$. These two definitions of a convex function are equivalent. Before showing this equivalence, we prove this technical lemma:

Lemma 3: For any $t,a,b$ in a field with a partial order, if $0\le t$ and $a\leq b$, then $ta\leq tb$. 

Proof: Since $a\leq b$, we have $0\leq b-a$ by the third rule aforementioned, so $0\leq t\left(b-a\right)$ by the second rule. Hence, $ta\leq tb$ by distributivity and the third rule

Theorem 4: Let $V$ be any vector space over a field $\mathbb{F}$ with a partial order, and let $C$ be a convex subset of $V$ and $f$ a function from $C$ to $\mathbb{F}$. Then, $f$ is convex (as defined in here) if and only if $A\left(C,f\right)$ is convex

Proof: Suppose $f$ is convex. Let $\left\langle c_{1},y_{1}\right\rangle ,\left\langle c_{2},y_{2}\right\rangle $ be in $A\left(C,f\right)$. Note that for any $t$ in $\left[0,1\right]$, we have $f\left(\left(1-t\right)c_{1}+tc_{2}\right)\leq\left(1-t\right)f\left(c_{1}\right)+f\left(c_{2}\right)\leq\left(1-t\right)y_{1}+ty_{2}$;
the first inequality holds by definition of convexity and the second inequality by Lemma 3.
Hence, $\left(1-t\right)\left\langle c_{1},y_{1}\right\rangle +t\left\langle c_{2},y_{2}\right\rangle $ is in $A\left(C,f\right)$.

Now, suppose $A\left(C,f\right)$ is convex. For any $c_{1},c_{2}$ in $C$, note that $\left\langle c_{1},f\left(c_{1}\right)\right\rangle ,\left\langle c_{2},f\left(c_{2}\right)\right\rangle $ are in $A\left(C,f\right)$ since the order on $\mathbb{F}$ is reflexive, so for any $t$ in $\left[0,1\right]$, we have $\left(1-t\right)\left\langle c_{1},f\left(c_{1}\right)\right\rangle +t\left\langle c_{2},f\left(c_{2}\right)\right\rangle =\left\langle \left(1- t\right)c_{1}+tc_{2},\left(1-t\right)f\left(c_{1}\right)+tf\left(c_{2}\right)\right\rangle $ is in $A\left(C,f\right)$ by convexity. Thus, $f\left(\left(1-t\right)c_{1}+tc_{2}\right)\le\left(1-t\right)f\left(c_{1}\right)+tf\left(c_{2}\right)$.

A convex function in terms of order-convexity

Recall that $A\left(C,f\right)$ is a subset of the vector space $V\times\mathbb{F}$ over $\mathbb{F}$. If $V$ has any reflexive and transitive order, then we define the lexicographic order on $V\times\mathbb{F}$ as $\left(v_{1},t_{1}\right)\leq\left(v_{2},t_{2}\right):=v_{1}\leq v_{2}\textrm{, or }v_{1}=v_{2}\textrm{ and }t_{1}\leq t_{2}$. The lexicographic order is reflexive and transitive. We then can define a convex function entirely in terms of order-convexity, which would go as follows: let $V$ be any vector space over a field with a partial order, and let $V$ have a reflexive and transitive order on it; for any order-convex subset $C$ of $V$, a function from $C$ to $\mathbb{F}$ is $\textbf{convex}$ if $A\left(C,f\right)$ is order-convex.

We’ll show you how the proof of a standard theorem goes when a convex function is defined in terms of order-convexity:

Theorem 5: Let $V$ be any vector space over a field $\mathbb{F}$ with a partial order, and let $C$ be a convex subset of $V$. For any convex function $f$ from $C$ to $\mathbb{F}$, the set of points of $C$ at which $f$ attains a minimum is convex. 

Proof: Recall $V$ has a natural reflexive, transitive order (as defined here) and $V\times\mathbb{F}$ has an induced lexicographic order, which also is reflexive and transitive. Let $M$ be the set of points of $C$ at which $f$ attains a minimum, and let $x,y$ be in $M$. For any $u$ in $C$, if $x\leq u\leq y$, then we need to show that $u$ is in $M$. For any $z$ in $C$, both $\left\langle x,f\left(z\right)\right\rangle $ and $\left\langle y,f\left(z\right)\right\rangle $ are in $A\left(C,f\right)$ since $x,y$ are in $M$, so $\left\langle x,f\left(z\right)\right\rangle \leq\left\langle u,f\left(z\right)\right\rangle \leq\left\langle y,f\left(z\right)\right\rangle$ . Since $A\left(C,f\right)$ is order-convex, $\left\langle u,f\left(z\right)\right\rangle $ is in $A\left(C,f\right)$, so $f\left(u\right)\leq f\left(z\right)$. Since $z$ is arbitrary, $u$ is in $M$.

Convex sets and convex functions in machine learning

Convex Optimization

Many problems in machine learning consist in minimizing an error function of a neural network, which is considered to be a convex function on a convex set. For instance, see this paper and this one.

Software Libraries

There are couple software libraries that help solve some optimization problems with a computer. For instance, see this software package and this Matlab software.

 ———————————————————————————————————————————————-



Leave a Reply

Your email address will not be published. Required fields are marked *