\documentclass{article}
\usepackage{amsmath}
\begin{document}
\chapter{Motivation of a nonlinear multigrid method for optimization problems}
\section{Basic Multigrid}
To calculate numerical solutions of partial differential equation (PDE) one has
to solve big linear equation systems $Ax=b$ with a thin layered matrix A. The
size of $x$ depends on the discritization. A small example illustrates how big the
matrix $A$ becomes: If we want to solve a 2-D problem with a grid with $100\times
100$ nodes, the vector $x$ has 10.000 entries and the matrix has the dimension
$10.000\times 10.000$. So even this small problem is far to big to solve it with
direct solvers, e.g. LU-decomposition. Instead of using direct methods one needs
iterative solvers. Standard linear iterative solvers like Gauss-Seidel
converge very slowly, therefore it is not practical to use them.
There are two main ideas behind the basic multigrid algorithm. The first one is
the observation, that if you have an approximative solution $\tilde{x}$ with
$A\tilde{x}\approx b$ you can calculate a defect solution $u$
\begin{equation}\label{defect eq}
Au=d,\text{ with } d=A\tilde{x}-b
\end{equation}
to obtain $x=\tilde{x}-u$ with
$$Ax = A\tilde{x}-Au =A\tilde{x}-d = b.$$
The second idea is to restrict the defect and solve the defect equation
(\ref{defect eq}) on a coarser grid. Then we prolongate this solution to our
origin grid and calculate $x$. If we use this as step in an iterative process it is
called \emph{Two-Grid algorithm}\index{Two-Grid algorithm}. Instead of solving
the defect equation exact on the coarser grid one can also recursivly use the
Two-Grid algorithm.
\begin{enumerate}
\item If $l=0$, find x with $Ax=b$ and return x. If $l \neq 0$, find
$\tilde{x}$ which approximately solves $A\tilde{x}=b$.
\item Set $u = R_l (A\tilde{x}-b)$.
\item v = Multigrid (u, l-1)
\item Return $x :=P_{l-1}v+\tilde{x}$
\end{enumerate}
\section{Non-linear Multigrid}
We try to develop a multigrid method for nonlinear optimization problems. To
motivate the method we use the standard multigrid method for the minimization
of a quadratic function
\begin{equation}
q:\mathbb{R}^n\to \mathbb{R},\ q(x):=c + \langle g,
x\rangle + \frac{1}{2}\langle W x,x\rangle,
\end{equation}
whereas $W$ is a symmetric positive definite matrix. From optimization theory we
know, that for a convex function (like q) every stationary point is a global
minimizer. So we need to solve the system
\begin{equation}
\nabla q(x) = 0\ \Leftrightarrow Wx=-g.
\end{equation}
To use multigrid methods we need a grid hierarchy $H_l,\ l=0,\ldots, r$, where
$H_0$
is the coarsest an $H_r$ the finest grid. The grid size (the distance between
two grid points) is $h_l$. Furthermore we need restriction operators
\begin{equation}
R_i:H_i\to H_{i-1},\ i=1,\ldots,r
\end{equation}
and related prolongation operators ($P_i^*=R_i$)
\begin{equation}
P_i:H_{i-1}\to H_{i},\ i=1,\ldots,r.
\end{equation}
At last we need on every grid a representation of our quadratic function,
whereas $q_r:=q$ and $q_l$ adequate\footnote{e.g. $q_l$ should be consistent
with $q_{l+1}$ in such a way, that from $\nabla q_{l+1}(x)=$ follows $\nabla
q_l(R_l(x))=0$}.
In every iteration of the classical multigrid algorithm we solve or smooth a
system $W_lx=-b$ with a given right side b.\footnote{On the finest grid we have
$b=g_r$} To convey this to our quadratic problem, we have to solve the system
$\nabla q_l(x) - g_l + b = 0.$
Now we have all requisites to formulate the simple multigrid algorithm:
\begin{enumerate}
\item If $l>0$, use a smoother to obtain a solution $\hat{x}$ so that $\nabla
q_l(\hat{x})-g_l+b$ is smoother than $\nabla q_l(x)-g_l+b$, else solve the
system $\nabla q_0(\hat{x})-g_l+b = 0$.
\item Set $u=R_l (\nabla q_l(\hat{x})-g_l+b)$
\item If $l>0$: $v=$Multigrid ($l-1, 0, u$)
\item Set $x'=\hat{x}+Pv$ and return $x'$
\end{enumerate}
Instead of solving $\nabla q_l(\hat{x})-g_l+b=0$ we can also rewrite this in an
equivalent form $\nabla h_l(s) := \nabla q_l(x+s) - \nabla q_l(x) +b =0$. It
follows $h_l(s) = q_l(x+s)- \langle \nabla q_l(x)-b, s\rangle$ and our
multigrid algorithm becomes
\begin{enumerate}
\item If $l>0$, use a smoother to obtain a solution $s$ so that $\nabla h_l(s)$ is
smoother than $\nabla h_l(0)$, else solve the problem $\min_s h_0(s)$
and return $s$.
\item Set $u=R_l (\nabla h_l(s))$
\item If $l>0$: $v=$Multigrid ($l-1, 0, u$)
\item Set $x'=x + s+Pv$ and return $x'$
\end{enumerate}
\end{document}