# Convexity

*Definition* **Convex Function**

> A function $f:X \to R$ is convex if for any $a,b$ in $X$ and $t \in [0,1]$, $$f(ta+(1-t)b) \le tf(a) + (1-t)f(b) $$

> A function $f:X \to R$ is **strictly** convex if for any $a,b$ in $X$, $a \neq b$, and $t \in [0,1]$, $$f(ta+(1-t)b) < tf(a) + (1-t)f(b) $$

*Definition* **Quasiconvex Function**

> A function $f:X \to R$ is quasiconvex if for any $a,b$ in $X$ and $t \in [0,1]$, $$f(ta+(1-t)b) \le \max \{f(a),f(b)\} $$

> A function $f:X \to R$ is **strictly** quasiconvex if for any $a,b$ in $X$, $a \neq b$, and $t \in [0,1]$, $$f(ta+(1-t)b) < \max \{f(a),f(b)\} $$

*Definition* **Lower Contour Set of a Function**

> A lower contour set of a function $f:X \to R$ with $c \in R$ is, $$S(c)=\{x \in X| f(x) \le c\}$$

Clearly, a convex function must be quasiconvex.

*Claim* **Quasiconvex Function $\iff$ Convex Lower Contour Sets**

> A function is quasiconvex if and only if all of its lower contour sets are convex.

>Proof:

>Define $f:X \to R$.

>If part:
>>Suppose $f$ is quasiconvex, given $c \in X$, $t \in [0.1]$, and any $a, b \in S(c)$, we know that $f(a) \le c$ and $f(b) \le c$. Following the property of quasiconvexity, $$f(ta+(1-t)b) \le \max \{f(a),f(b)\} \le c $$ Hence, $S(c)$ is convex.

>Only if part:
>>Suppose for all $c \in R$, the lower contour set $S(c)$ of $f$ is convex. Given $t \in [0.1]$, and any $a, b \in X$, WLOG, we assume $f(a) \le f(b) = d$. $$ f(a) \le f(b) = d \implies a, b \in S(d) \\ S(d) \text{ is convex } \implies t(a) + (1-t)b \in S(d) \\ t(a) + (1-t)b \in S(d) \implies f(t(a) + (1-t)b) \le d = \max \{f(a),f(b)\}$$ Hence, $f$ is quasiconvex.

*Note*

Given $f:X \to R$, the contour set of $f$ refers to the subset of $X$.

*Definition* **Supper-additive**

> A function $f:R \to R$ is super-additive if
$$f(x+y) \ge f(x) + f(y), \text{ for } x\ge 0 , y \ge 0$$

**Convexity and Supper-additive**
**Claim** For a function goes through the origin, i.e., $f:R \to R, f(0)=0$, convexity implies supper-additive.
**Proof:**
>Because $f(x)$ is convex and passing the origin, we have
$$f(\lambda x) = f(\lambda x + (1-\lambda)0) \le \lambda f(x) + (1-\lambda) f(0) = \lambda f(x), \forall \lambda \in [0,1]$$
With $xy>0$, we have,
$$f(x) = f(\frac{x}{x+y}(x+y)) \le \frac{x}{x+y}f(x+y)$$
Simarly,
$$f(y) \le \frac{y}{x+y}f(x+y)$$
Hence,
$$f(x+y) = \frac{x}{x+y}f(x+y) + \frac{y}{x+y}f(x+y) \ge f(x) + f(y) $$