Key Sequence

Notation

New Concepts

• Euclidian Geometry Crash Course
  • perspective function
  • linear-fractional function
  • generalized inequality
• convex function
• extended-value extension

Important Results / Claims

• operations that preserve convexity
• seperating hyperplane theorem
• supporting hyperplane theorem
• some convex functions
• some concave fuctions
• convexity preserve line restriction

Questions

Interesting Factoids

• SU-SOC175 JAN052025
• SU-SOC175 JAN072025

a function for which, given any two points, the function between those points sits at (lines are convex!) or below the plane given those points

constituents

For \(f: \mathbb{R}^{n} \to \mathbb{R}\)

requirements

\begin{equation} f\qty(\theta x + \qty(1-\theta) y) \leq \theta f\qty(x) + \qty(1-\theta) f\qty(y) \end{equation}

strictly convex is the strict inequality

additional information

some convex functions

• affine: \(ax + b\)
• exponential: \(e^{ax}\)
• powers: \(x^{\alpha}\) for \(\alpha \geq 1\) or \(\alpha \leq 0\)
• \(|x|^{p}\) for \(p > 1\)
• relu
• any norm
• sum of squares: \(\qty {x}^{2}_{2} = x_1^{2} + … + x_{n}^{2}\)
• max function: \(\max \qty(x) = \max \qty {x_1 \dots x_{n}}\)
• softmax: \(\log \qty(\exp x_1 + \dots + \exp x_{n})\)

some concave fuctions

• affine
• powers
• logs: \(\log x\)
• entropy: \(- x \log x\)
• negative part (opposite relu)

constituents

• set \(C\)
• \(\theta \in \mathbb{R}\)

requirements

A set \(C\) is a convex set if:

\begin{equation} x_1, x_2 \in C, 0 \leq \theta \leq 1 \implies \theta x_{1} + \qty(1-\theta) x_{2} \in C \end{equation}

definitions

standard definitions

additional information

operations that preserve convexity

Convex sets is a calculus! Methods to showing complexity:

1. apply definition: show \(x_1, x_2 \in C, 0 \leq \theta \leq 1 \implies \theta x_1 + \qty(1-\theta) x_2 \in C\)
2. use convex functions
3. show that \(C\) is obtained from convex sets via the following operations

intersection

Intersections of any number of convex sets, include infinite, are convex.

\(f: \mathbb{R}^{n} \to \mathbb{R}\) is convex IFF the function \(g: \mathbb{R} \to \mathbb{R}\) is convex:

\begin{equation} g\qty(t) = f\qty(x + tv), \text{dom } g = \qty {t \mid x + tv \in \text{dom }f} \end{equation}

is convex in \(t \in \mathbb{R}\) for any \(x \in \text{dom } f\), \(v \in \mathbb{R}^{n}\).