Optimisation

Tip: Vectorial product rule Let $F, G \colon \mathbb{R}^n \to \mathbb{R}^n$. Then, $$ \nabla (F(X)^\top G(X)) = \nabla F(X)^\top G(X) + \nabla G(X)^\top F(X) $$ $$ \DeclareMathOperator*{\argmax}{arg \,max \,} \DeclareMathOperator*{\argmin}{arg \,min \,} $$ Without constraints We are interested in minimizing an arbitrary function $f \colon \mathbb{R}^n \to \mathbb{R}$. To do so, we will use the gradient descent method. Let $\mathbf{x}^{(0)} \in \mathbb{R}^n$ be a random starting point. Then, for $k \in \mathbb{N}$, $$ \mathbf{x}^{(k + 1)} = \mathbf{x}^{(k)} - s^{(k)} \nabla f(\mathbf{x}^{(k)})....

Simplex We want to solve the following problem: $$ \max{z} = \sum_{j = 1}^n c_j x_j $$ where $$ \begin{cases} \sum_{j = 1}^n a_{ij} x_j &\leq b_i, \qquad i \in \{1, \dots, m\} \\ x_j &\geq 0, \qquad j \in \{1, \dots, n\} \end{cases} $$ Then, we find a tuple $x^\ast = (x_1^\ast, \dots, x_n^\ast)$ that is the solution of the optimization problem. To this end, we build dictionaries such that...

Let $A \in \mathbb{R}^{m \times n}$ and $\mathbf{b} \in \mathbb{R}^m$. Our goal is to solve the linear system $A\mathbf{x} = \mathbf{b}$ where $\mathbf{x} \in \mathbb{R}^n$. Info Some facts about matrices: If $A A^\top = A^\top A$, then $A$ is normal; If $A = A^\top$, then $A$ is symmetric; If $A A^\top = A^\top A = I_n$, then $A$ is orthogonal. Norms The following norms are used often: $L_1$ norm: $\Vert \mathbf{x} \Vert_1 = \sum_{i=1}^n |x_i|$; $L_2$ norm: $\Vert \mathbf{x} \Vert_2 = \sqrt{\sum_{i=1}^n x_i^2}$; Frobenius norm: $\Vert A \Vert_F = \sqrt{\mathrm{tr}(A^\top A)}$; $L_1$ norm: $\Vert A \Vert_1 = \max_{1 \leq j \leq n} \sum_{i=1}^n |a_{ij}|$, which is the maximum absolute column sum of $A$; $L_\infty$ norm: $\Vert A \Vert_\infty = \max_{1 \leq i \leq n} \sum_{j=1}^n |a_{ij}|$, which is the maximum absolute row sum of $A$; $L_2$ norm: $\Vert A \Vert_2 = \rho(A) = \max\{\vert \lambda(A) \vert \}$, which is the spectral radius of $A$, i....