2023-07-11
$$ p*=min_x f_0(x) \\ \text{subject to}: f_{i}(x) \leq 0,i=1,\dots,m, \\ $$
where
Given matrix $A$, find $x$ that $Ax \approx b$.
$$ minimize_{x} ||Ax-b||^2 $$
$y=mx+c$
Data: $(x_n,y_n)$
$$ \begin{bmatrix} x_1 & 1 \\ x_2 & 1 \\ \vdots & \vdots \\ x_n & 1 \end{bmatrix} \begin{bmatrix} m \\ c \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} $$
Find $m, c$ to minimize a quadratic function(a convex function)
$$ minimize_{m,c}\sum_{i=1}^n(y_i-(mx_i+c))^2. $$
Find $Ax \in Col(A)$ that is closed to $b$.
Because $col(A)$ is a subspace, it contains zero vector. If we place $b$ starting at zero vector in $col(A)$ and we do a orthogonal projection of $b$ onto $col(A)$. Let's say the projected point on $col(A)$ is P. $BP$ is orthogonal to any vector in $col(A)$.
Let's prove vector $OP$ is the closest to $OB$. For any point in $Col(A)$ denoted as Q(other than P), is it possible $BQ$ shorter than $BP$?
Triangle BPQ is a right triangle. BQ is the hypotenuse. $BQ$ is strictly bigger than $BP$.
Want: $(Ax-b)=e$ must be orthogonal to all of the columns of A.
Dot product of every column of A and e is zero.
$$ A^T(Ax-b)=0\\ A^TAx=A^Tb\\ $$
If $A$ is invertible, $x=(A^TA)^{-1}A^Tb$. This is the vecotr $x$ that solves $min_{x}||Ax-b||^2$.