> For the complete documentation index, see [llms.txt](https://muhans-notebook.gitbook.io/computational-optimization/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://muhans-notebook.gitbook.io/computational-optimization/convex-functions.md).
# Convex Functions
* definition
* relationship to convex sets
* operations preserve convexity
* global optimality (necessary $$\equiv$$ sufficient)
### Simplex
$$
\Delta\_n = {x\in \R^n \mid \sum x\_i\le1, x\ge0}
$$
### 
### “Probability” Simplex
$$
\bar{\Delta}\_n={x\in\R^n\mid\sum x\_j=1, x\ge0}
$$
$$\text{Conv}(S)= {\sum\_{i=1}^k\lambda\_ix\_i\mid\lambda \in\bar{\Delta}\_k,x\_i\in S,k\in \N }$$, where $$\N$$ denotes non-negative
$$
\Delta\_2=H^-*{\begin{pmatrix}0\\-1\end{pmatrix},0}\cap H^-*{\begin{pmatrix}-1\0\end{pmatrix},0}\cap H^-\_{\begin{pmatrix}1\1\end{pmatrix},1}
$$
[Caratheodory’s Theorem](https://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_\(convex_hull\)) (Chp6, Beck)
Hyperplane: $$H\_{a,\beta}= {x\in \R^n\mid a^Tx=\beta }$$
Halfspace: $$H^{-1}\_{a,\beta}$$
$$
H^-\_{a,\beta}={x\in\R^n\mid a^Tx\le\beta}, (a\ne 0)
$$
***Definition.*** A function $$f:C\to \R$$, $$C\subseteq \R^n$$ (convex set), is *convex* if
$$
f(\lambda x+(1-\lambda)y)\le\lambda f(x)+(1-\lambda)f(y)
$$
for any $$x,y\in C$$, and $$\lambda\in \[0,1]$$
→ Difference between strict convex and convex?
***Definition.*** $$f$$ is concave if $$-f$$ is convex
*Consequence*: A function $$f$$ is concave and convex if and only if $$f$$ is affine
*Example*: Norm $$\lVert \cdot \rVert: \R^n\to\R\_+$$
All norms satisfy the
1. $$\Delta\text{-inequality}$$
$$
\lVert x+y\rVert\le \lVert x\rVert+\lVert y\rVert
$$
2. $$\lVert \alpha x\rVert=\lvert \alpha\rvert \cdot\lVert x\rVert$$
Take any $$x,y\in \R^n$$ and any $$\lambda \in \[0,1]$$
$$
Z:=\lambda x+(1-\lambda)y
$$
$$\begin{aligned}\lVert Z\rVert &= \lVert \lambda x+(1-\lambda)y\rVert \ &\le \lVert \lambda x\rVert+\lVert (1-\lambda)y\rVert \ &=\lvert \lambda\rvert \cdot\lVert x\rVert+\lvert 1-\lambda\lvert\cdot \lVert y\rVert \ &=\lambda\lVert x\rVert+(1-\lambda)\lVert y\rVert\end{aligned}$$
***Example***: Affine functions
$$
f(x)=a^Tx+\beta
$$
Ex: $$f(x)=-log(x), f:\R\to\R$$
Ex: $$f(x)=e^x f:\R\to\R$$
### Operations that preserve the convexity of functions
1. **Non-negative multiples**
$$\alpha f(x)$$ is convex if $$f(x)$$ is convex and $$\alpha \ge 0$$
2. **Sums**
$$f\_1+f\_2+\ldots+f\_m$$ is convex if $$f\_1,\ldots,f\_m$$ are convex
3. **Composition** of a convex function with affine function is convex, i.e.,
if $$f$$ convex then $$f(Ax+b)$$ convex for ***any*** matrix $$A$$ and vector $$b$$
Proof:
Take any point $$x,y\in \R^n$$ and $$\lambda \in \[0,1]$$:
$$f(A(\lambda x+(1-\lambda)y)+b)=f(\lambda(Ax+b)+(1-\lambda)(Ay+b))\le \lambda f(Ax+b)+(1-\lambda)f(Ay+b)$$
*Example* $$f(x\_1,x\_2,x\_3)=e^{x\_1-x\_2+x\_3}+e^{2x\_2}+x\_1$$
*Example* For any matrix $$A$$ and vector $$b$$, LS objective: $$\frac{1}{2}\lVert Ax-b\rVert\_2^2$$
$$\frac{1}{2}\lVert Ax-b\rVert\_2^2=\frac{1}{2}\sum(a\_i^Tx-b\_i)^2=\frac{1}{2}\sum f(a\_i^Tx-b\_i)$$, where $$f(\cdot)=(\cdot)^2$$
### GLOBAL Optimality
(P) $$\underset{x\in\R^n}{\min}f(x)$$ subject to $$x\in C$$
where $$f:\R^n\to\R$$ convex and $$C\subseteq \R^n$$ convex set
If $$x^*$$ *is a local minimizer of (P), i.e.,* $$f(x^*)\le f(x), \forall x\in \mathbb{B}\_{\varepsilon}\cap C$$ for all $$\varepsilon \gt 0$$ small enough, then $$x^*$$ is a global minimizer of (P), *i.e.*, $$f(x^*)\le f(x), \forall x\in C$$.
**Proof** Suppose $$x^\* \in C$$ is a local minimizer of (P), but not a global minimizer.
$$\exists y\in C$$ s.t. $$f(y)\lt f(x^\*)$$
By convexity of $$C$$, $$\lambda x^\* +(1-\lambda)y\in C$$ for any $$\lambda \in \[0,1]$$ and by convexity of $$f$$;
$$\begin{aligned} f(\lambda x^*+(1-\lambda)y)&\le \lambda f(x^*)+(1-\lambda)f(y) \ &\lt \lambda f(x^*)+(1-\lambda)f(x^*) \ &=f(x^\*)\end{aligned}$$
