$x^*$ solves $\min \frac{1}{2} \lVert Ax-b\rVert^2$

check if $x^$ solves $A^TAx^=A^Tb$

$A^T(Ax^*-b)=0$

$\lVert A^Tr^*\rVert\le \varepsilon$

$\underset{x\in \mathbb{R}^n}{\min}f(x)$, $f:\mathbb{R}^n \to \mathbb{R}$ smooth

(later: $x\in C \le \mathbb{R}^n$)

Optimality

$\bar{x}$ is a …

1. local min of $f$ if $f(\bar{x}) \le f(x)$ $\forall x \in B_\varepsilon(\bar{x})$, for some $\varepsilon>0$ small,

   where $B_\varepsilon(\bar{x})=\{x \mid \lVert x-\bar{x}\rVert_2 \le \varepsilon\}$

2. global min of $f$ if $f(\bar{x})≤f(x)$ $\forall x \in \mathbb{R}^n$

$\bar{x}$ is a maximizer of $f$

↔

$\bar{x}$ is a minimizer of $-f$

Ex: lack of attainment

$\underset{x \to \infty}{\lim} e^{-x}=0$

$\underset{x}{\inf}e^{-x}=0$

$e^{-x}$ is not coercive

Definition: A function f is coercive if $\underset{\lVert x\rVert \to \infty}{\lim} f(x) = \infty$

Equivalently The level sets $\{x \mid f(x) \le \tau\}$ for any $\tau \in \mathbb{R}$ are all compact (closer & bond)

First-order necessary condition

$\bar{x}$ is a local min of $f:\mathbb{R}^n \to \mathbb{R}$ only if $\nabla f(\bar{x})=0$

[$\overset{\bar{x}}{\text{local min}} \to \nabla f(\bar{x})=0$]