01. Mathematical Notation — The Minimum Grammar of Optimization

// BACKGROUND 1/6 — read sets, intervals, vectors, functions, mappings, summations, and norms in a consistent way

Optimization documents look difficult because they contain many symbols. But most of them are shorthand for "a collection of possible values," "a rule that maps inputs to outputs," "a way of adding several terms," or "a way of measuring magnitude."

Sets and intervals

A set is a collection of elements. For example, $x \in S$ means that "$x$ is an element of the set $S$." Optimization expresses all possible candidates as a set.

An interval is a contiguous portion of the real numbers.

Notation	Meaning	Endpoints included?
$[a,b]$	At least $a$ and at most $b$	Both
$(a,b)$	Greater than $a$ and less than $b$	Neither
$[a,b)$	At least $a$ and less than $b$	Left only
$(a,b]$	Greater than $a$ and at most $b$	Right only

The feasible region of an optimization problem is usually written in set notation:

$$\mathcal{F}=\{x\in\mathbb{R}^n \mid g_i(x)\le 0,\ h_j(x)=0\}.$$

Here $\mathcal{F}$ is "the set of candidates satisfying every constraint."

Vectors

A vector bundles several numbers into one decision:

$$x = (x_1,x_2,\dots,x_n)^\top \in \mathbb{R}^n.$$

In optimization, $x$ is usually the decision variable. In a factory design, for example, $x_1$ might be length, $x_2$ thickness, and $x_3$ flow rate.

:::tip Sentence to remember Choosing one scalar is searching on a line; choosing a vector is searching for a point in a space. :::

Functions and mappings

A function is a rule that maps inputs to outputs.

$$f:\mathbb{R}^n\to\mathbb{R}$$

maps an $n$-dimensional vector to one number. An objective function usually has this form:

$$\min_{x\in\mathbb{R}^n} f(x).$$

In contrast, $F:\mathbb{R}^n\to\mathbb{R}^m$ maps an input vector to an output vector. It is natural to view several constraints or simulation outputs as a vector-valued function.

Summation

Summation notation compresses repeated addition.

$$\sum_{i=1}^{n} x_i = x_1+x_2+\cdots+x_n.$$

The mean squared error of a regression problem is usually written as

$$\frac{1}{n}\sum_{i=1}^{n}(y_i-\hat{y}_i)^2.$$

It is simple to read: substitute values from $i=1$ through $n$ and add everything.

Norms

A norm is a function that measures the magnitude of a vector. The Euclidean norm is used most often:

$$\|x\|_2=\sqrt{x_1^2+x_2^2+\cdots+x_n^2}.$$

Optimization uses norms to decide "how far did we move?", "how large is the error?", and "has the gradient become small enough?"

Norm	Definition	Intuition
$\|x\|_1$	$\sum_i	x_i
$\|x\|_2$	$\sqrt{\sum_i x_i^2}$	Straight-line distance
$\|x\|_\infty$	$\max_i	x_i

How to read an optimization statement

Consider

$$\min_{x\in\mathbb{R}^n} f(x)\quad\text{subject to}\quad Ax\le b.$$

It reads as follows:

1. Choose a vector called $x$.
2. We want to make $f(x)$ small.
3. But the constraint $Ax\le b$ must be respected.
4. Find the best point among the possible values of $x$.

Next: Calculus for Optimization