This notebook follows **Chapter 8, "Optimization and Minimum Principles,"** from [**"Computational Science and Engineering" by Gilbert Strang.**](https://www.amazon.ca/Computational-Science-Engineering-Gilbert-Strang/dp/0961408812)

# 8.1 Least Squares
Consider a matrix A of size $m x n$ with $n$ independent columns, and $m > n$. 
$A^T A$ is symmetric positive definite, as Rank(A) = $n$. 
We wish to solve $Au = b$ for some vector $b$ with $m$ components. The solution $\hat{u}$ has $n$ components. 

This gives rise to the **least squares problem**:
$$ \min \parallel Au - b \parallel ^2 $$ 

Below are the **normal equations**, which give the solution $\hat{u}$:
$$ 
\begin{align} 
Au &= b \nonumber \\
A^T A \hat{u} &= A^T b 
\end{align}
$$ 

The residual of the cost function is $e = b - Au$, and has dimensions $m \times 1$. Thus, 
$$ A^T e = A^T b - A^T A u $$
Therefore, $A^T e = 0$ when $u = \hat{u}$. 

$e$ is in the nullspace of $A^T$, and is therefore perpendicular to the columns (column space) of $A$ (equivalently, $e$ is perpendicular to the rows/rowspace of $A^T$). Recall that orthogonality means that the dot product of two vectors is 0. 

## 8.1.1 Refresher on Orthogonality
Before we start on the next section, let's review some concepts from linear algebra. Specifically, the orthogonality of vectors and vector spaces. 

### Orthogonal Vectors 
There is an analogue between geometry in Euclidean space and in $\mathcal{R}^n$. 

First, *two vectors $\mathbf{u}$ and $\mathbf{v}$ are perpendicular i.f.f. the distance between $\mathbf{u}$ and $\mathbf{-v}$ is the same as the distance between $\mathbf{u}$ and $\mathbf{+v}$.* 

First, the distance between $\mathbf{u}$ and $\mathbf{-v}$:
$$
\begin{align}
[\textrm{dist}(\mathbf{u}, \mathbf{-v})]^2 &= \parallel \mathbf{u}-(-\mathbf{v}) \parallel ^2 = \parallel \mathbf{u} +\mathbf{v} \parallel ^2 \\
&= (\mathbf{u} + \mathbf{v}) \cdot (\mathbf{u} + \mathbf{v}) \\ 
&= \parallel \mathbf{u} \parallel^2 + \parallel \mathbf{v} \parallel^2 + 2\mathbf{u} \cdot \mathbf{v}
\end{align}
$$

Next, the distance between $\mathbf{u}$ and $\mathbf{+v}$:
$$
\begin{align}
[\textrm{dist}(\mathbf{u}, \mathbf{v})]^2 &= \parallel \mathbf{u} -\mathbf{v} \parallel ^2 \\
&= (\mathbf{u} - \mathbf{v}) \cdot (\mathbf{u} - \mathbf{v}) \\ 
&= \parallel \mathbf{u} \parallel^2 + \parallel \mathbf{v} \parallel^2 - 2\mathbf{u} \cdot \mathbf{v}
\end{align}
$$

Therefore, 
$$
\begin{align}
[\textrm{dist}(\mathbf{u}, \mathbf{-v})]^2 = [\textrm{dist}(\mathbf{u}, \mathbf{v})]^2 &\iff - 2\mathbf{u} \cdot \mathbf{v} = 2\mathbf{u} \cdot \mathbf{v} \\
&\implies \quad \mathbf{u} \cdot \mathbf{v} = 0 \\
&\implies \parallel \mathbf{u} + \mathbf{v} \parallel ^2 = \parallel \mathbf{u} \parallel^2 + \parallel \mathbf{v} \parallel^2
\end{align}
$$

## 8.1.2 Orthogonal Complements in $\mathcal{R}^n$
If a vector $\mathbf{z}$ is orthogonal to every vector in a subspace $W$ of $\mathcal{R}^n$, then $\mathbf{z}$ is orthogonal to $W$. The set of all such vectors $\mathbf{z}$ is the **orthogonal complement** of $W$ and denoted by $W^\bot$.

Let's go through the relation between nullspace, orthogonal complements, and the columns and rows of a $m \times n$ matrix $A$. We have the folllowing theorem: 
$$
(\textrm{Row}(A))^\bot = \textrm{Nul}(A) \quad \textrm{and} \quad (\textrm{Col}(A))^\bot = \textrm{Nul}(A)^\bot 
$$

If $Ax = 0$ for some $n \times 1$ vector $x$, then $x \in \textrm{Nul}(A)$, which means $x$ is orthogonal to the rows of $A$. The rows of $A$ span its row space, so $x$ is orthogonal to Row($A$).

**Explanation** 
$$
\begin{align}
A &= \begin{pmatrix} a & b & c \\ d & e & f \end{pmatrix}, \quad u = \begin{vmatrix} x & y & z \end{vmatrix}. \\
Au &= 0 \\
&= \begin{pmatrix} ax + by + cz \\ dx + ey + fz \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} 
\end{align}
$$
The elements of the product $Au$ are dot products between $u$ and the row vectors of $A$. Since $Au = 0$, $u$ is in the nullspace of A, and from the above, we see that $u$ is orthogonal to the rows of $A$.

<center></center>

## 8.1.3 Primal and Dual Problems 
In the *primal* problem, we find the solution $\hat{u}$ by projecting $b$ onto the column space of $A$, i.e. $A\hat{u}$ is the closest point to $b$ in the column space of $A$. In general, the product $Au$ yields a linear combination of the columns of $A$. The column space of $A$ contains all such products. 

$$ Au = y \quad \implies \quad y \in \textrm{Col}(A), \quad \forall \quad u $$
Where, Col($A$) refers to the column space of $A$. 

The *dual* problem solves $A^T e = 0$ for $e$, which is the projection of $b$ onto the nullspace of $A^T$. Recall from above: 
$$ \textrm{Nul}(A^T) = (\textrm{Row}(A^T))^\bot = (\textrm{Col}(A))^\bot $$
Thus, $e$ is contained in (Col($A$))$^\bot$, which contains *all vectors perpendicular to the columns of $A$*. The dimension of (Col($A$))$^\bot$ is given by the Rank-Nullity Theorem: 
$$
\begin{align}
&\textrm{Rank}(A) + \textrm{Nullity}(A) = n, \quad \textrm{ where } n \textrm{ is the number of columns in } A. \\
&\textrm{Rank}(A^T) + \textrm{Nullity}(A^T) = m \\ 
&\textrm{Rank}(A) = \textrm{Rank}(A^T) \quad \implies \quad \textrm{Nullity}(A^T) = m - n \\
&\textrm{Nullity}(A^T) = \textrm{dim(Row(}A^T))^\bot = \textrm{dim(Col(}A)^\bot) = m - n
\end{align}
$$

<center></center>
<center><b>Ordinary least squares</b></center>

$e$ and $\hat{u}$ solve the two linear equations shown by the figure above:
$$
\begin{align}
e + A \hat{u} &= b \rightarrow m \textrm{ equations} \\
A^T e &= 0 \rightarrow n \textrm{ equations}
\end{align}
$$

These are called the "Primal-Dual", "Saddle Point", and "Kuhn-Tucker (KKT)" equations. We discussed the meaning of "Primal" and "Dual" above, but let's go over the other names. The third comes from somebody who worked on these equations.

## 8.1.4 "Saddle Point" Equations
The Saddle Point, or KKT, matrix is a block matrix that represents the Primal-Dual equations:
$$ S = \begin{bmatrix} I & A \\ A^T & 0 \end{bmatrix} \quad \implies \quad S \begin{bmatrix} e \\ \hat{u} \end{bmatrix} = \begin{bmatrix} Ie + A\hat{u} \\ A^T e + 0 \end{bmatrix} $$ 
Where, $I$ is an $m \times m$ identity matrix. Thus, $I$ constitutes the first $m$ pivot columns of $S$. Thus, to reduce $S$, we need to make the lower left hand corner of $S$ a $n \times n$ matrix of zeroes. To do this, let's review elimination on block matrices: 

**Elimination of block matrices**
$$
\begin{align}
\begin{bmatrix} I & 0 \\ -CA^{-1} & I \end{bmatrix} \begin{bmatrix} A & B \\ C & D \end{bmatrix} &= \begin{bmatrix} A + 0 & B + 0 \\ -CA^{-1}A + C & -CA^{-1}B + D \end{bmatrix} \\
&= \begin{bmatrix} A & B \\ 0 & D - CA^{-1}B \end{bmatrix} 
\end{align}
$$

The first matrix, $\begin{bmatrix} I & 0 \\ -CA^{-1} & I \end{bmatrix}$, is also known as the Gaussian elimination matrix $E$. If we also wanted to reduce $A$ into a matrix of pivots: 
$$
\begin{align}
\begin{bmatrix} A^{-1} & 0 \\ -CA^{-1} & I \end{bmatrix} \begin{bmatrix} A & B \\ C & D \end{bmatrix} &= \begin{bmatrix} AA^{-1} + 0 & BA^{-1} + 0 \\ -CA^{-1}A + C & -CA^{-1}B + D \end{bmatrix} \\
&= \begin{bmatrix} I & BA^{-1} \\ 0 & D - CA^{-1}B \end{bmatrix} 
\end{align}
$$

We now reduce our Primal-Dual matrix $S$ with $E = \begin{bmatrix} I & 0 \\ -A^T & I \end{bmatrix}$:
$$
\begin{align}
ES &= \begin{bmatrix} I & 0 \\ -A^T & I \end{bmatrix} \begin{bmatrix} I & A \\ A^T & 0 \end{bmatrix} \\
&= \begin{bmatrix} I + 0 & A + 0 \\ -A^T + A^T & -AA^T + 0 \end{bmatrix} \\
&= \begin{bmatrix} I & A \\ 0 & -AA^T \end{bmatrix}
\end{align}
$$

By convention, the lower right-hand block remaining after elimination is known as the **Schur complement**. More importantly, the first $m$ pivots are positive (=1), but **the final $n$ pivots, determined by $-AA^T$ are negative.** When a matrix has pivots of both signs, it is known as **indefinite**. For such matrices, there is **no maximum or minimum**, positive or negative definite. Instead, there is a **saddle point**, $(\hat{u}, e)$.

## 8.1.5 "Primal-Dual" Equations
The primal problem is to minimize $\frac{1}{2} \parallel Au - b \parallel^2$.

The dual problem is to minimize $\frac{1}{2} \parallel e - b \parallel^2$ with the constraint $A^T e = 0$. Here, $u$ acts a Lagrange multiplier to enforce the constraint $A^T e = 0$. 

Solutions to the primal and dual problems are found simultaneously, and add to $b$. 

Let's do an example!

Let
$$
A = \begin{bmatrix}2 \\ 1 \end{bmatrix} \quad b = \begin{bmatrix}3 \\ 4\end{bmatrix} \quad A^T A = 5 \quad A^T b = 10 \\

\begin{align}
&\textrm{Projection: } A\hat{u} = \begin{bmatrix}4 \\ 2\end{bmatrix} \\ 
&\textrm{Error: } e = b - A\hat{u} = \begin{bmatrix}3 \\ 4 \end{bmatrix} - \begin{bmatrix}4 \\ 2\end{bmatrix} = \begin{bmatrix}-1 \\ 2\end{bmatrix} 
\end{align}

$$

Let's verify that $A\hat{u}$ and $e$ are perpendicular. First, $A\hat{u}$ and $e$ sum to $b$:
$$
A\hat{u} + e = A\hat{u} + (b - A\hat{u}) = b \\

\begin{align}
\parallel b \parallel^2 &= \parallel A\hat{u} \parallel^2 + \parallel e \parallel^2 \\
&= 20 + 5 = 25 \\
A \hat{u} \cdot e &= \parallel A \hat{u} \parallel \parallel e \parallel \cos \theta \\
0 &= \sqrt{20} \sqrt{5} \cos \theta \\
\therefore \cos \theta &= 0 \quad \implies \quad \theta = \frac{\pi}{2} 
\end{align}
$$

**Primal** 

The normal equation is: $A^T A \hat{u} = A^T b$, so $\hat{u} = 2$. 

**Dual**

The dual minimizes $\frac{1}{2}\parallel e-b \parallel^2$ under the constraint $A^T e = 0$. The solution to the dual problem gives $e$ and $\hat{u}$:

The Lagrange function is:
$$ 
\begin{align}
L &= \frac{1}{2}\parallel e-b \parallel^2 + u(A^T e) \\
L(e_1, e_2, u) &= \frac{1}{2}(e_1 - b_1 )^2 + \frac{1}{2}(e_2 - b_2 )^2 + u(A^{T}_{1} e_1 + A^{T}_{2} e_2) \\

\frac{\partial L}{\partial (e_1, e_2, u)} &= 
\begin{bmatrix}
    e_1 - b_1 + 2\hat{u} = 0 \\
    e_2 - b_2 + \hat{u} = 0 \\
    2e_1 + e_2 = 0 
\end{bmatrix} \\
&= \begin{bmatrix}
        e_1 & e_2 & \hat{u} \\
        1 & 0 & 2 \\
        0 & 1 & 1 \\
        2 & 1 & 0 
    \end{bmatrix} \begin{bmatrix}
        e_1 \\ e_2 \\ \hat{u} 
    \end{bmatrix} = 
    \begin{bmatrix} b_1 \\ b_2 \\ 0 \end{bmatrix}
\end{align}
$$

The matrix $
    \begin{bmatrix}
        e_1 & e_2 & \hat{u} \\
        1 & 0 & 2 \\
        0 & 1 & 1 \\
        2 & 1 & 0 
    \end{bmatrix} $
is the saddle point matrix $S$. 


```python

```

14a67bdac77c1cd8eab0773ddf02bd919905b24f
ipynb
Jupyter Notebook
_posts/Strang_Ch8.ipynb
haganenoneko/website.github.io
fcb72e2ba797f22f262d54d82a0b0b4b4d9b4a69
MIT
_posts/Strang_Ch8.ipynb
haganenoneko/website.github.io
fcb72e2ba797f22f262d54d82a0b0b4b4d9b4a69
MIT
_posts/Strang_Ch8.ipynb
haganenoneko/website.github.io
fcb72e2ba797f22f262d54d82a0b0b4b4d9b4a69
MIT
Qwen/Qwen-72B
1. YES
2. YES