Convex Sets

A line segment between $x_1$ and $x_2$ is all points $x=t{x}_1+(1-t)x^2$ with $0\le t\le 1$.

Convex Set

A convex set contains line segment between any two points in the set, that is, if $x,y\in C$, then $tx+(1-t)y\in C$ for all $t\in [0,1]$.

Link to original

Example of Convex Sets

• Line Segments: $C=\{tx+(1-t)y:t\in [0,1]\}$ for some $x,y\in {\mathbb{R}}^n$
• Line: $C=\{tx+(1-t)y:t\in \mathbb{R}\}$ for some $x,y\in {\mathbb{R}}^n$
• Halfspaces: $C=\{x\in {\mathbb{R}}^n:w^{T}x+b\le 0\}$ for some $w\in {\mathbb{R}}^n$ and $b\in \mathbb{R}$.
• Balls of Radius $ϵ$: $C=\{x\in {\mathbb{R}}^n:||x|{|}_2\le ϵ\}\text{ for some }ϵ\ge 0\in \mathbb{R}$ $||x|{|}_2=\sqrt{x^{T}x}=\sqrt{{\sum }_{i=1}^n{x}_i^2}$ We use the Euclidean norm / distance as $||x-y|{|}_2$ is equal to the length of the line segment between points $x$ and $y$.

Convex combination of the points $S=\{x^{(1)},\dots ,x^{(k)}\in {\mathbb{R}}^n\}$: Any point of the form $x=t_1{x}^{(1)}+\dots +t_k{x}^{(k)}$ with $t_1+\dots +t_k=1,t_i\ge 0$

Convex hull is a set $C$ which is a convex set of all points $y$ that can be obtained as convex combinations of the $x\in S$.

Proof

Convex Functions

A function $f:C\to {\mathbb{R}}^n$ is convex if:

• $C$ is a convex set
• $f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$ for all $x,y\in C$ and $t\in [0,1]$

We call a function $f$ concave if $-f$ is convex.

A function $f$ is strictly convex if $C$ is convex and $f(tx+(1-t)y)<tf(x)+(1-t)f(y)$ for all $x,y\in C$, $x\ne y$ and $t\in [0,1]$.

Example Functions

Given $R++$ is the set of positive reals.

Convex

• affine: $ax+b$ on $R$, for any $a,b\in R$
• exponential: $e^{ax}$, for any $a\in R$
• powers: $x^{\alpha }$ on $R++$, for any $\alpha \ge 1$ or $\alpha \le 0$
• powers of absolute value: $|x{|}^p$ on $R$, for $p\ge 1$
• …

First-order condition

$f$ is differentiable if $C$ is open and the gradient $\nabla f(x)=\left(\begin{array}{c}\frac{\partial f(x)}{\partial x_1}\end{array}\right),\dots ,\frac{\partial f(x)}{\partial x_n}$ exist at each $x\in C$.

1st-order condition: differentiable $f$ with convex domain is convex iff $f(y)\ge f(x)+\nabla f(x)(y-x)$ for all $x,y\in C$, i.e. first-order approximation of $f$ is a global under-estimator

Second-order condition

$f$ is twice differentiable if $C$ is open and the Hessian ${\nabla }^{2}f(x)$, ${\nabla }^{2}f(x{)}_{ij}=\frac{{\partial }^{2}f(x)}{\partial x_i\partial x_j},i,j=1,\dots ,n$ exist at each $x\in C$.

2nd-order conditions: for twice differentiable $f$ with convex domain $f$ is convex iff ${\nabla }^{2}f(x)\succcurlyeq 0$ for all $x\in C$ i.e. the Hessian is positive semi-definite (all of the eigenvalues are non-negative)

There is a special case when $C\subseteq \mathbb{R}$:

• A twice continuously differentiable function $f:C\to \mathbb{R}$ with $C\subseteq \mathbb{R}$ is convex if $C$ is a convex set and $\frac{d^{2}f}{d{x}^2}(x^{\prime })\ge 0$ for all $x^{\prime }\in C$.

Operations Preserving Convexity

Methods for establishing convexity of a function

• Verify the definition.
• For twice differentiable functions, show $\frac{d^{2}y}{d{x}^2}f(x)\ge 0$.
• Show that $f$ is obtained from simple convex functions by operations that preserve convexity.

Nonnegative weighted sums of convex functions are convex, i.e. if $f_1:{\mathbb{R}}^n\to \mathbb{R}$ and $f_2:{\mathbb{R}}^n\to \mathbb{R}$ are convex functions and $c_1,c_2\ge 0$, then $g(x)=c_1{f}_1(x)+c_2{f}_2(x)$ is a convex function.

Composition with an affine function, i.e. if $f:{\mathbb{R}}^n\to \mathbb{R}$ is a convex function and $M\in {\mathbb{R}}^{n\times m}$, $b\in {\mathbb{R}}^n$, then $g:{\mathbb{R}}^m\to \mathbb{R}$ given by: $g(x)=f(Mx+b)$ is a convex function.

Pointwise maximum of convex functions are convex, i.e. if $f_1:{\mathbb{R}}^n\to \mathbb{R}$ and $f_2:{\mathbb{R}}^n\to \mathbb{R}$ are convex functions, then $g(x)=\max (f_1(x),f_2(x))$ is a convex function.

Pointwise supremum, i.e. if $f(x,y)$ is convex in $x\in {\mathbb{R}}^n$ for each fixed $y\in Y$ then $g(x)={\sup }_{y\in Y}f(x,y)$ is a convex function.

Note: a maximum of a set must be an element of the set, a supremum need not be.

Convex optimisation

Only in Typst!

slide 24 general optimisation

slide 25 optimal / locally optimal points

slides 26-27 implicit constraints

slides 28-29 convex optimisation

slides 30-32 local and global optima

slides 33 linear programming problems

slides 34 quad

slides 35-36 least squares regression