text:
\documentclass[conference]{IEEEtran}
\IEEEoverridecommandlockouts
\usepackage{cite}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{algorithmic}
\usepackage{graphicx}
\usepackage{textcomp}
\usepackage{xcolor}
\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
\begin{document}

\title{Genetic Algorithm for a Self-Driving Car*\\
{\footnotesize \textsuperscript{*}Note: For this particular case, the algorithm evolved in a 2D complex environment.}
}

\author{\IEEEauthorblockN{Fabio Oliveira}
    \IEEEauthorblockA{\textit{Msc. Applied Artificial Intelligence} \\
        \textit{Polytechnic Institute of Cavado and Ave}\\
        Barcelos, Portugal \\
        fabiodiogo29@gmail.com}
}

\maketitle

\begin{abstract}
    The challenge with self-driving cars is to create a model that converts sensors data (such as cameras or proximity sensors) into actions.
    This way the car can react to its changing environment and make the right decisions. Games oﬀer a suitable testbed where new methodologies
    and algorithms can be tested in a near-real life environment. For example, in a car driving game, using transfer learning or other techniques
    results can be generalized to autonomous driving environments. In this paper, we propose a agent based on a genetic algorithm that learns to
    drive autonomously in a complex environment given real time data from the car sensors. In the literature \cite{neelarghya_2021,mandav_2018,patel_2021}, Neural Networks is the most
    promising technique used to parse these sensors data. For this particular case we'll use a 2nd order polynomial function to convert the data
    from three sensors into one action (degree of turn). To simulate the car and the environment we've put together a car game simulator with Pygame.
    The code is available at \textbf{\textit{github.com/fabioo29}}.
\end{abstract}

\begin{IEEEkeywords}
    Artificial Intelligence, Neural Networks, Genetic Algorithm, Pygame
\end{IEEEkeywords}

\begin{figure}[b]
    \centerline{\includegraphics[width=40mm,scale=2]{assets/car-sensors.png}}
    \caption{Population car sensors(whiskers)}
    \label{fig:car-sensors}
\end{figure}

\section{Introduction}
Today, as the world is ushering into the era of automating things, one of key product of the industries which is yet
to be automated completely is a vehicle which is also intelligent. According to Pcmag \cite{pcmag_unknown}, "An autonomous vehicle is a
computer-controlled car that drives itself". There are many industries which are leading the research in autonomous
vehicles, some of the most prominent are Google, Tesla and NIO. Research nowadays is inclining towards becoming leader
in the new age of driver-less car. However, the current driver-less car is yet far from being the intelligent autonomous
car. Some autonomous vehicles uses LiDAR (Light Detection And Ranging) technology, that measures distance to a
target by illuminating the target with pulsed laser light and measuring the reflected pulses with a sensor. Otherwise, tesla mainly focus is
too use video for the environment perception. For this work, as mentioned before, each population car will have three sensors acting as distance
sensors and the goal of the car is to drive through all the track without crashing into the wall.
The motivation for this work came from applied artificial intelligence Msc. degree teacher in Fundamentals of Artificial Intelligence,
Alberto Simões, who proposed the idea of using a genetic algorithm to create a self-driving car with a 2nd order polynomial function
acting as a controller for the car instead of using neural networks to control it like a typical state-of-the-art autonomous car.
The following paper is organised as follows, Section 2 covers the topics and methodologies used for this approach, Section 3 explains about the proposed
method and algorithms used to develop the autonomous driving agent, Section 4 covers the experiments and results obtained from the
state of the art method used, Section 5 concludes the paper by iterating over the findings in the project.

\section{Metodologies}
\subsection{Genetic Algorithm}
Genetic Algorithm is a search metaheuristic that is inspired by Charles Darwin’s theory of natural evolution.
This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction
in order to produce offspring of the next generation. A genetic algorithm process consists in a series of steps as follows.

\subsubsection{Generate Initial population}
For the algorithm to evolve it is necessary to generate an initial population. The initial population is a set of individuals,
where each individual is controlled by an Agent and each Agent is characterized by a set of Genes represented as a value between
-1 and 1. A set of genes is known as a Chromosome. The population with which we start is called the Initial Population.

\subsubsection{Evaluation}
A Fitness function is a system that determines how fit (the ability of an individual to compete with other individuals)
an individual is. It gives a fitness score to each individual which helps quantify the performance.
This function is executed over the performance of the population to quantify and compare the individuals performance.
The fitness used for this particular case is the distance traveled by the car. So, it means that those cars who traveled
the most will rank higher on the selection process.

\subsubsection{Selection}
The process of picking the “fittest” (based on the fitness score generated during Evaluation phase) individuals for
producing the next generation (i.e. the new population for the next cycle of evaluation and reproduction). There isn’t
a strict cut-off based on the fitness score, but state-of-art mehtods typically mention selection based on probabilities
(higher the fitness score, higher the probability to get selected), tournament selection and roulette wheel selection.
After a few investigation of the literature and tests on the subject, we’ve decided delete between 60 and 85% of the population
which ended up working well in our case.

\subsubsection{Crossover}
The process of mixing the genes of the pair of individuals chosen to produce a new pair of individual is called
Crossover or Genetic operation. This process is continued to create a new population. Crossover can be performed in
different methods such as one-point crossover, two-point crossover, uniform crossover and so on.
We ended up using uniform crossover between top two ranked cars (by fitness) to produce a new pair of cars (each new car gene
has 0.50 probability to be selected from the top one car or from the top two car) as illustrated in the figure \ref{fig:crossover}.

\begin{figure}[t]
    \centerline{\includegraphics[width=80mm,scale=4]{assets/uniform_crossover.png}}
    \caption{Uniform crossover (randomly mixed chromosome from parents)}
    \label{fig:crossover}
\end{figure}

\subsubsection{Mutation}
In certain new individuals, some of their genes can be subjected to a Mutation with a low random probability.
This implies that some of the Genes (bits) in the Chromosome (sequence of bit) can be altered (flipped). Mutation
helps to maintain diversity within the population and prevent premature convergence. This step of the repopulate process
was applied in every new car added to the population. Each new car chromosome would have a random gene reinitialized
(random value between -1 and 1).

\subsubsection{Converging}
In order to avoid convergence, ten percent of completely fresh individuals are added to the population after the mutation.

\subsection{Proportional Integral Derivative Controller}
A PID Controller or a Proportional-Integral-Derivative controller is a control loop feedback mechanism (controller)
widely used in industrial control systems. PID control is the most common control algorithm used in industry and
has been universally accepted in industrial control. The popularity of PID controllers can be attributed partly to
their robust performance in a wide range of operating conditions and partly to their functional simplicity, which
allows engineers to operate them in a simple, straightforward manner. A PID controller calculates an error value
as the difference between a measured process variable and a desired setpoint (desired outcome). The controller attempts
to minimize the error by adjusting the process through the use of a manipulated variable. In order to control how the error
is minimized the components Proportional-Integral-Derivative (PID) must be changed according to the application itself.
This kind of controller was really usefull as it was used to fix a huge problem in the agent evolution simulation.

\section{Implementation}
\subsection{Simulation}
In order to simulate the autonomous driving agent on a complex environment, we needed to create the environment
which can be used to test the agent. The most popular approach is to use the Unity game engine but we've decided to strict the
project language to Python only just for the challenge itself and use the PyGame library which is also a good choice for 2D games.
The simulation consists of a top view track with four different tracks(four difficulty levels) and three different types of cars
(PID controlled car, Agent controlled car, User controlled car). The car controlled by the User, which is meant to be used as a debug car,
is the only car who does not have distance sensors. Each Agent car that hits the track border is eliminated. The simulation also has some
usefull info displayed on the screen about the current generation (weights, best fitness, cars alive, generation number) and the car controller output.

\begin{figure}[b]
    \centerline{\includegraphics[width=70mm,scale=4]{assets/simulation.png}}
    \caption{Pygame simulation for the genetic algorithm}
    \label{fig:simulation}
\end{figure}

\subsection{Agent controller}
In a population of cars, there is an agent for each one of these cars. The Agent controls the car based on a value that
is applied to the car's rotation angle and this value corresponds to the output of the 2nd order polynomial function
math function \emph{w1*a + w2*b + w3*c + w5*a*c + w6*b*c + w7*a**2 + w8*b**2 + w9*c**2} where the inputs \emph{a, b, c} are
the distances of the car sensors at the moment and the weights will be the gene values of the Agent's current
chromosome. The returned value will be normalized to fit the range we are looking for (i.e. between -180 and 180) to be then applied
to the car's angle for the car to turn.

\subsection{Genetic algorithm}
For the genetic algorithm, it was established that the simulation would start with a population of 100 cars(A.1). Each car has an
agent that controls it. Each agent has a chromosome with 9 genes in it which corresponds to the 9 weights that will be applied to
car controller function (2nd polynomial) mentioned before.
Each gene has a value between -1 and 1 that is initially assigned randomly. After the current round ends: (A.2) all the agents are ranked
based on their fitness score which corresponds to the distance traveled by the car in the current round, and each car that crosses
the finish line its also compensated for it; (A.3) Between 15 and 40% of population agents are filtered out for a new generation;
(A.4) the top 2 parents crossover in a uniform way to give birth to new cars until we have 100 cars again; (A.5) a mutation
is made to every new child in a way that there's a fresh gene in every new child chromosome; (A.6) 10% of the cars are replaced with
new fresh ones in order to avoid convergence.

\section{Experiments \& Results}
\subsection{Unwanted behaviour}
During the population evolution there were a few problems that were easily solved with a few tweaks on the code itself but after a few generations
some cars were behaving in a way that was not desired. The cars would tend to drive in circles or even drive in the opposite direction they were supposed to
be driving. This behaviour is a good example of what a good behavior for the agent can be not the desired one. This behavior would make the cars rank higher
in the population due to the distance traveled from the cars using this method. Of course, once a car finds this behavior, all the population tend to convergence
into that unwanted behaviour. To fix this problem, it was implemented a different type of car with a PID controller. Setting the controller setpoint
to the middle of the road and tweaking the components of the PID controller, made the car drive exactly as desired without crashing into the walls.
It was then attached to this PID controlled car a 'cleaner line' that would wipe out all the cars with unwanted behaviours (like those who were circling in a loop)
once the car collided with the line.

\begin{figure}[b]
    \centerline{\includegraphics[width=70mm,scale=4]{assets/bad-behaviour.png}}
    \caption{Unwanted behaviour (cars spinning)}
    \label{fig:bad-behavious}
\end{figure}

\subsection{Results}
After this implementation all the simulation went well and after about 173 generations the car would now be able to drive perfectly without crashing and with
a better behaviour(faster) than the PID controlled car. The evolved agent was tested in every single track(beginner, easy, medium and hard) and managed to drive
perfectly in all of them.

\section{Conclusions}
Self-driving is still an active and emerging area in real-world applications. Although there's a lack of large-scale
public datasets available in order to train solid deep learning models. In this work, we showed how state-of-art methods can be
validated in the virtual world using serious games before being tested in the real world. Nowadays there's more advanced simulation
softwares that try to replicate the real world environment like CARLA software where its possible to test trained Deep Learning models
along with other usefull techniques. We hope, that this work motivates others to learn more about genetic algorithms and artificial
intelligence \cite{AIMA} in general.

\bibliographystyle{abbrv}
\bibliography{citations}

\vspace{12pt}
\end{document}


text:
\documentclass[a4paper]{article}

\def\npart{II}

\def\ntitle{Differential Geometry}
\def\nlecturer{M.\ Dafermos}

\def\nterm{Lent}
\def\nyear{2018}

\input{header}

\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\Int}{Int}
\newcommand*{\inner}{\innerproduct}

\begin{document}

\input{titlepage}

\tableofcontents

\section{Smooth Manifolds}

\subsection{Definitions}

\begin{definition}[Smooth]\index{smooth}
  Let \(U \subseteq \R^n\) be an open set and \(f: U \to \R^m\). \(f\) is said to be \emph{smooth} if
  \[
    \frac{\p^{|\alpha|} f}{\p x^\alpha}
  \]
  exists for all multi-indices \(\alpha\).
\end{definition}

\begin{notation}
  A multi-index \(\alpha = (\alpha_1, \dots, \alpha_n)\) is a tuple of non-negative integers and \(|\alpha| = \sum_{i = 1}^n \alpha_i\).
\end{notation}

\begin{definition}[Smooth]\index{smooth}
  Let \(X \subseteq \R^n\) be a subset. \(f: X \to \R^m\) is \emph{smooth} if for all \(x \in X\), there exists \(U \subseteq \R^n\), \(x \in U\) such that there exists smooth \(\tilde f: U \to \R^m\) extending \(f|_{X \cap U}\). i.e.\ the following diagram commutes
  \[
    \begin{tikzcd}
      U \ar[r, "\tilde f"] & \R^m \\
      U \cap X \ar[u, "\iota"] \ar[ur, "f"']
    \end{tikzcd}
  \]
\end{definition}

\begin{remark}\leavevmode
  \begin{enumerate}
    \item This is a local property.
    \item \(X\) is a topological space with subspace topology induced from \(\R^n\). \(f\) is smooth implies that \(f\) is continuous.
    \end{enumerate}
\end{remark}

\begin{definition}[Diffeomorphism]\index{diffeomorphism}
  Let \(X \subseteq \R^n\) and \(Y \subseteq \R^m\). A map \(f: X \to Y\) is a \emph{diffeomorphism} if \(f\) is smooth and bijective and its inverse \(f^{-1}: Y \to X\) is also smooth.
\end{definition}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item Diffeomorphism implies homeomorphism (with repsect to the subspace topology).
  \item Diffeomorphism is an equivalence relation.
  \end{enumerate}
\end{remark}

\begin{definition}[Manifold]\index{manifold}
  A \emph{\(k\)-dimensional manifold} is a set \(X \subseteq \R^N\) such that for all \(x \in X\) there exists \(V \subseteq X\) open, \(x \in V\) such that \(V\) is diffeomorphic to an open subset \(U \subseteq \R^k\), i.e.\ \(X\) is locally diffeomorphic to \(\R^k\).
\end{definition}

\begin{remark}
  The diffeomorphism \(\varphi: U \to V\) is called a \emph{local parameterisation} and its inverse \(\varphi^{-1}: V \to U\) is called \emph{coordinate charts}. More specifically, let \(x_i: \R^k \to \R\) be the projection of the \(i\)th coordinate and we have \emph{local coordinate} \(x_i \compose \varphi^{-1}: V \to \R\). However, sometimes we abuse the notation and just write \(x_i: V \to \R\) for the above map.
\end{remark}

\begin{notation}
  Write \(\dim X = k\) if \(X\) is a \(k\)-dimensional manifold.
\end{notation}

\begin{eg}\leavevmode
  \begin{enumerate}
  \item \(\R^N\) is an \(N\)-dim manifold. For example, \(\varphi: \R^N \stackrel{\id}{\to} \R^N\).
  \item An open subset \(V \subseteq \R^N\) is an \(N\)-dim manifold, for example by taking \(\varphi\) to be the restriction \(\id|_V\).
  \item In general, if \(X\) is a manifold and \(V \subseteq X\) is an open subset then \(V\) is also a manifold.
  \item The \(n\)-sphere, \(S^n \subseteq \R^{n + 1} = \{x_1^2 + \dots + x_{n + 1}^2 = 1\}\) is an \(n\)-dim manifold. Suppose \(x \in S^n\) lies in the upper half hyperplane define by \(x_{n + 1} > 0\). Take
    \[
      V = S^n \cap \{x_{n + 1} > 0\},\, U = \{(x_1, \dots, x_n): \sum_{i = 1}^n x_i^2 < 1\} = B(\V 0, 1) \subseteq \R^n
    \]
    and define
    \begin{align*}
      \varphi: U &\to V \\
      (x_1, \dots, x_n) &\mapsto \left(x_1, \dots, x_n, +\sqrt{1 - (x_1^2 + \dots + x_n^2)}\right)
    \end{align*}
    Let's do a reality check: the map consists of algebraic operations so is smooth. It is easy to check that the image lies in \(V\). Its inverese is the projection onto the first \(n\) coordinates, which is the restriction of a smooth function so also smooth.

    Similarly, if \(x\) lies in \(\{x_{n + 1} < 0\}\), change \(+\) to \(-\) in the last coordinate of \(\varphi\) will do. This accounts for ``most'' points, with the exception of those on the equator. However, there is nothing special about \(x_{n + 1}\) so we may repeat for the other coordinates. As
    \[
      S^n = \bigcup_{i = 1}^{n + 1} \left( (S^n \cap \{x_i > 0\}) \cup (S^n \cap \{x_i < 0\}) \right)
    \]
    (which in English says that at least one coordinate is non-zero), we have covered \(S^n\) so done.
  \end{enumerate}
\end{eg}

\begin{ex}
  Suppose \(X \subseteq \R^n\) and \(Y \subseteq \R^m\) are manifolds. Show that \(X \times Y \subseteq \R^n \times \R^m = \R^{n + m}\) is a manifold of dimension \(\dim X + \dim Y\).
\end{ex}

\begin{definition}[Submanifold]\index{manifold!submanifold}
  Let \(X \subseteq \R^N\) be a manifold. A manifold \(Y \subseteq \R^N\) such that \(Y \subseteq X\) is a \emph{submanifold} of \(X\).
\end{definition}

\begin{remark}
  By definition, all manifolds are submanifolds of \(\R^N\) for some \(N\).
\end{remark}

Note that we have yet shown that the dimension of a manifold is well-defined but we will do so in a while. Assuming so, we define

\begin{definition}[Codimension]\index{codimension}
  The \emph{codimension} of \(Y\) in \(X\) is
  \[
    \codim_X(Y) = \dim X - \dim Y.
  \]
\end{definition}

\subsection{Tangent space}

\begin{definition}[Differential]\index{differential}
  Let \(U \subseteq \R^n\) and \(f: U \to \R^m\) be a smooth map. The \emph{differential} of \(f\) at \(x \in U\), \(df_x\) is a linear map
  \begin{align*}
    df_x: \R^n &\to \R^m \\
    h &\mapsto \lim_{t \to 0} \frac{f(x + th) - f(x)}{t}
  \end{align*}
\end{definition}

Explicitly, \(df_x\) is represented by the matrix
\[
  \left( \frac{\p f}{\p x_j} \right) \text{ where } f =
  \begin{pmatrix}
    f_1 \\
    \vdots \\
    f_m
  \end{pmatrix}
  .
\]
It then follows that
\[
  df_x(h) = \left(\frac{\p f}{\p x_j}\right)
  \begin{pmatrix}
    h_1 \\
    \vdots \\
    h_n
  \end{pmatrix}
  .
\]

\begin{proposition}[Chain rule]
  Let \(f: U \to V, g: V \to \R^p\) be smooth maps where \(U \subseteq \R^n, V \subseteq \R^m\). Let \(x \in U\) and \(f(x) \in V\). Then
  \[
    d(g \compose f)_x = dg_{f(x)} \compose df_x.
  \]
\end{proposition}

The aim of this section is to define differentials of maps between manifolds. Before that we have to find where differential lives. Certainly in \(\R^n\) it is a linear map living in a linear space.

Let \(X \subseteq \R^N\) be a \(k\)-dim manifold and \(x \in X\). Let \(\varphi\) be a local parameterisation around \(x\). Wlog assume \(\varphi^{-1}(x) = 0\). Note that \(\varphi\) is defined on an open subset of \(\R^k\) so we can do calculus on it (this is false for \(\varphi^{-1}\) as \(V \subseteq \R^N\) may not be open). We can define
\[
  d\varphi_0: \R^k \to \R^N.
\]

\begin{definition}[Tangent space]\index{tangent space}
  The \emph{tangent space} of \(X\) at \(x\), denoted \(T_xX\), is \(d\varphi_0(\R^k)\), a subspace of \(\R^N\).
\end{definition}

For this to be a good definition, we need to show that it is independent of \(\varphi\) and \(\dim d\varphi_0(\R^k) = k\).

Suppose \(\varphi: U \to V\) and \(\tilde \varphi: \tilde U \to \tilde V\) are parameterisations around \(x\), again assumming wlog \(\varphi(0) = x = \tilde \varphi(0)\). By taking intersection we can assume \(V = \tilde V\). Write
\[
  \varphi = \tilde \varphi \compose \underbrace{(\tilde \varphi^{-1} \compose \varphi)}_{U \to \tilde U}.
\]
The term in the parenthesis is a map between open subsets of \(\R^k\) so we can do calculus on it. By chain rule
\[
  d\varphi_0 = d\tilde \varphi_0 \compose d(\tilde \varphi^{-1} \compose \varphi)_0.
\]
Note that \(\varphi^{-1} \compose \tilde \varphi\) is the inverse of \(\tilde \varphi^{-1} \compose \varphi\) so by applying chain rule to \(\id\), we get
\[
  \id = d(\varphi^{-1} \compose \tilde \varphi)_0 \compose d(\tilde \varphi^{-1} \compose \varphi)_0
\]
so both of them are invertible. Thus
\[
  d\varphi_0(\R^k) = d\tilde \varphi_0(\R^k).
\]

Next we want to show \(\dim d\varphi_0(\R^k) = k\). Certainly linear algebra tells us that it is at most \(k\). By definition there exists a smooth \(\psi: W \to \R^k\), where \(W \subseteq \R^N\) is an open subset containing \(x\) such that
\[
  \psi|_{X \cap W} = \varphi^{-1}.
\]
Assume wlog \(V \subseteq X \cap W\). Then
\[
  \id_U = \psi \compose \varphi
\]
so by chain rule
\[
  \id = d\psi_x \compose d\varphi_0.
\]
Thus \(d\varphi_0(\R^k)\) is \(k\)-dimensional.

\begin{remark}
  The functions \(\varphi^{-1} \compose \tilde \varphi\) are called \emph{transition functions} and will appear later in the course.
\end{remark}

\begin{corollary}
  The dimension of a manifold is well-defined.
\end{corollary}

\begin{ex}
  If \(X \subseteq \R^N\) is a manifold and \(Y\) is a submanifold of \(X\) then
  \[
    T_yY \leq T_yX
  \]
  for all \(y \in Y\). In particular \(\codim_X(Y) \geq 0\).
\end{ex}

\begin{eg}\leavevmode
  \begin{enumerate}
  \item \(T_x\R^N = \R^N\).
  \item Let \(X\) be an open subset of \(\R^N\). Then \(T_xX = \R^N\).
  \item Let
    \[
      X = \{(x_1, x_2, \dots, x_k, 0, \dots, 0)\} \subseteq \R^N
    \]
    which can be seen as the image of the embedding \(\varphi: \R^k \to \R^N\). This is a \(k\)-dim manifold. This is a linear map so \(d\varphi_x = \varphi\). Thus \(T_xX = X\). In general, this holds if \(\varphi\) is an injective linear map.
  \item Let \(S^n \subseteq \R^{n + 1}\). Given a point \(x \in S^n\) with \(x_{n + 1} > 0\), use the parameterisation
    \begin{align*}
      \varphi: B(\V 0, 1) &\to \R^{n + 1} \\
      (x_1, \dots, x_n) &\mapsto \left(x_1, \dots, x_n, + \sqrt{1 - x_1^2 - \dots - x_n^2}\right)
    \end{align*}
    Then
    \[
      \im d\varphi_{(x_1, \dots, x_n)} = \text{span}\left\{\frac{\p \varphi}{\p x_1}, \dots, \frac{\p \varphi}{\p x_n}\right\}.
    \]
    We have
    \[
      \frac{\p \varphi}{\p x_i} = \left(0, \dots, 1, \dots, 0, -\frac{x_i}{x_{n + 1}}\right)
    \]
    and we can verify that for all \(i\),
    \[
      \frac{\p \varphi}{\p x_i} \cdot (x_1, \dots, x_n, x_{n + 1}) = 0
    \]
    so \(T_xS^n\) is \(\{v: v \cdot x = 0\} \subseteq \R^{n + 1}\).
  \end{enumerate}
\end{eg}

Now we go on to define differential of maps between manifolds. Let \(f: X \to Y\) be a smooth map of manifolds where \(X \subseteq \R^n, Y \subseteq \R^m\). Let \(\varphi:U \to V\) and \(\tilde \varphi: \tilde U \to \tilde V\) be local parameterisations around \(x\) and \(f(x)\), where \(U \subseteq \R^k, \tilde U \subseteq \R^\ell\). wlog we assume \(\varphi(0) = x, \tilde \varphi(0) = f(x)\). We also assume \(f(V) \subseteq \tilde V\).

We can thus define a map \(\tilde \varphi^{-1} \compose f \compose \varphi: U \to \tilde U\) and do calculus on it. As \(T_xX = \im d\varphi_0\) and \(d\varphi_0\) is an injective map, we can define the inverse of its restriction to the image, denoted by
\[
  (d\varphi_0)^{-1}: T_xX \to \R^k.
\]

\begin{definition}[Differential]\index{differential}
  The \emph{differential map} of \(f\) at \(x \in X\), denoted \(df_x\), is a linear map \(df_x: T_xX \to T_{f(x)}Y\), defined as the composition
  \[
    d\tilde \varphi_0 \compose d(\tilde \varphi^{-1} \compose f \compose \varphi)_0 \compose (d\varphi_0)^{-1}.
  \]

\[
  \begin{tikzcd}
    T_xX \ar[r, "df_0"] & T_{f(x)}Y \\
    \R^k \ar[u, "d\varphi_0"] \ar[r, "d(\tilde \varphi^{-1} \compose f \compose \varphi)_0"'] & \R^\ell \ar[u, "d\tilde\varphi_0"']
  \end{tikzcd}
\]
\end{definition}

Now as everything else we defined in differential geometry, we have to check that it is independent of parameterisation. It will be a horrible job, and one that you would want to do only (at most) once in your lifetime.

Let \(\psi, \tilde \psi\) be another pair of parameterisations. Define \(\varphi\) in terms of transition maps
\[
  \varphi = \psi \compose (\psi^{-1} \compose \varphi).
\]
By chain rule,
\[
  d\varphi_0 = d\psi_0 \compose d(\psi^{-1} \compose \varphi)_0
\]
so
\[
  (d\varphi_0)^{-1} = (d(\psi^{-1} \compose \varphi)_0)^{-1} \compose (d\psi_0)^{-1} = d(\varphi^{-1} \compose \psi)_0 \compose (d\psi_0)^{-1}
\]
where the last equality comes from applying chain rule to
\[
  (\varphi^{-1} \compose \psi) \compose (\psi^{-1} \compose \varphi) = \id.
\]
Thus
\begin{align*}
  df_x &= d\tilde \varphi_0 \compose d(\tilde \varphi^{-1} \compose f \compose \varphi)_0 \compose (d\varphi_0)^{-1} \\
       &= d\tilde \varphi_0 \compose d(\tilde \varphi^{-1} \compose f \compose \varphi)_0 \compose d(\varphi^{-1} \compose \psi)_0 \compose (d\psi_0)^{-1} \\
       &= d\tilde \varphi_0 \compose d(\tilde \varphi^{-1} \compose f \compose \psi)_0 \compose (d\varphi_0)^{-1} \\
       &= \cdots \\
       &= d\tilde \psi_0 \compose d(\tilde \psi^{-1} \compose f \compose \psi)_0 \compose (d\psi_0)^{-1}
\end{align*}
where the omitted lines are similar and are left as an exercise.

\begin{proposition}[Chain rule]
  Let \(X, Y, Z\) be manifolds, \(f: X \to Y, g: Y \to Z\) smooth. Then for all \(x \in X\),
  \[
    d(g \compose f)_x = dg_{f(x)} \compose df_x.
  \]
\end{proposition}

\begin{proof}
  Tedious exercise using transition maps and chain rule on maps between Euclidean spaces.
\end{proof}

\begin{theorem}[Inverse Function Theorem]\index{inverse function theorem}
  Let \(f: X \to Y\) be a smooth map between manifolds. If \(df_x: T_xX \to T_{f(x)}Y\) is an isomorphism (which implies that in particular \(\dim X = \dim Y\)), then \(f\) is a local diffeomorphism. In other words, there exists an open subset \(V \subseteq X\) such that \(f|_V: V \to Y\) is a diffeomorphism onto its image.
\end{theorem}

\begin{proof}
  This is easy using Inverse Function Theorem from analysis. Let \(\varphi, \tilde \varphi\) be local parameterisations around \(x\) and \(f(x)\) respectively. Then \(d(\tilde \varphi^{-1} \compose f \compose \varphi)_0\) is surjection \(\R^k \to \R^k\) so \(\tilde \varphi^{-1} \compose f \compose \varphi\) is a local diffeomorphism of Euclidean spaces. Thus \(f\) is a local diffeomorphism of manifolds.
\end{proof}

\begin{ex}
  Suppose \(Y\) is a submanifold of \(X\) and \(f: X \to Z\) is a smooth map between manifolds. Then for all \(y \in Y\), show
  \[
    d(f|_Y)_y = df_y|_{T_yY}.
  \]
\end{ex}

\begin{ex}
  Let \(f: X \to Y, g: X \to Z\) be smooth maps between manifolds. We can define map
  \begin{align*}
    (f, g): X &\to Y \times Z \\
    x &\mapsto (f(x), g(x))
  \end{align*}
  Show that this map is smooth and for all \(x \in X\),
  \[
    d(f, g)|_x = (df_x, dg_x).
  \]
  Thus if differential is thought as a matrix, the map to the product space has differential made of blocks of matrices.
\end{ex}

\subsection{Pre-image theorem}

We defined manifolds in terms of charts but in reality, the pre-image theorem actually gives the most convenient way to define a manifold. First define some terminologies:

\begin{definition}[Critial point, critial value, regular value]\index{critical point}\index{critical value}\index{regular value}
  Let \(f: X \to Y\) be a smooth map between manifolds.
  \begin{itemize}
  \item A \emph{critical point} of \(f\) is a point \(x\) such that \(df_x: T_xX \to T_{f(x)}Y\) fails to be surjective. We denote the set of all critical points \(C\).
  \item A \emph{critical value} of \(f\) is a point \(y \in Y\) such that there exists \(x \in X\) critical and \(f(x) = y\), i.e.\ the set of critical values is \(f(C) \subseteq Y\).
  \item \(y \in Y\) is a \emph{regular value} if \(y\) is not a critical value, i.e.\ \(y \in Y \setminus f(C)\).
  \end{itemize}
\end{definition}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item If \(\dim X < \dim Y\) then \(C = X\).
  \item If \(f^{-1}(y) = \emptyset\), i.e.\ \(y \notin f(X)\) then \(y\) is a regular value.
  \end{enumerate}
\end{remark}

\begin{theorem}[Pre-image theorem]
  Let \(f: X \to Y\) be a smooth map between manifolds. Given \(y\) a regular value of \(f\), \(f^{-1}(y) \subseteq X\) is a submanifold of \(X\) with codimension equal to the dimension of \(Y\), i.e.
  \[
    \dim X - \dim (f^{-1}(y)) = \dim Y.
  \]
\end{theorem}

\begin{remark}
  Suppose \(X\) is non-empty (which we may add to our definition of manifolds). Then this theorem gives a proof that \(\codim \geq 0\) for this particular case.
\end{remark}

\begin{proof}
  Let \(x \in f^{-1}(y)\). Suppose \(X, Y \subseteq \R^N\) and \(q = \dim X - \dim Y\). By surjectivity and rank-nullity, \(\dim \ker df_x = g\). It is an exercise in linear algebra to show that there exists a linear map \(T: \R^N \to \R^q\) such that \(\ker T \cap \ker df_x = 0\). Now define
  \begin{align*}
    F: X &\to Y \times \R^q \\
    x &\mapsto (f(x), T(x))
  \end{align*}
  Then by the exercises above \(F\) is smooth with differential \(dF_x = (df_x, dT_x)\) and \(d(T|_X)_x = dT|_{T_xX} = T|_{T_xX}\) so \(dF_x = (df_x, T)\) which is an isomorphism. Thus by Inverse Function Theorem \(F\) is a diffeomorphism around \(x\). There exists an open neighbourhood of \(x\) \(V \subseteq X\) such that
  \[
    F|_V: V \to f(V) \times \underbrace{T(V)}_{= U \subseteq \R^q}
  \]
  is a diffeomorphism. Then
  \[
    \varphi = (F|_V)^{-1}|_{\{y\} \times U}: U \to V
  \]
  is a local parameterisation of \(f^{-1}(y)\).
\end{proof}

\begin{corollary}
  Suppose \(\dim X = \dim Y\) and \(y\) is a regular value of some \(f: X \to Y\). Then \(f^{-1}(y)\) is a manifold of dimension \(0\).
\end{corollary}

If \(Z \subseteq \R^N\) is a manifold of dimension \(0\), then it is a collection of discrete points, i.e.\ for each \(z \in Z\), there exists an open neighbourhood of \(z\) whose intersection with \(Z\) is \(\{z\}\). Thus if \(X\) is in addition compact, then \(f^{-1}(y)\) is a finite set of points.

\begin{theorem}[Stack of records theorem]
  Under the above assumptions, there exist open neighbourhoods \(W_i\) of \(x_i\)'s such that
  \[
    f^{-1}\left(\bigcap_{i = 1}^n f(W_i) \setminus f(X \setminus \bigcup_{i = 1}^n W_i)\right)
  \]
  is a disjoint union of open neighbourhoods of \(x_i\)'s and the restriction of \(f\) on each of which is a diffeomorphism.
\end{theorem}

Given a regular value \(y\), \(T_xf^{-1}(y) = \ker df_x\). See example sheet 1.

\begin{eg}\leavevmode
  \begin{enumerate}
  \item Let \(S^n \subseteq \R^{n + 1}\) and
  \begin{align*}
    f: S^n &\to \R \\
    (x_1, \dots, x_{n + 1}) &\mapsto x_1^2 + \dots + x_{n + 1}^2
  \end{align*}
  which is smooth. We have
  \[
    df = (2x_1, \dots, 2x_{n + 1})
  \]
  which is surjective everywhere on \(S^n\). Thus by pre-image theorem \(f^{-1}(1) \subseteq \R^{n + 1}\) is a manifold of dimension \(1\), which is precisely \(S^n\).
\item Let \(O(n)\) be the set of \(n \times n\) orthogonal matrices, i.e.\ matrices \(A\) such that \(AA^T = I\). \(O(n)\) can be seen as a subset of \(\matrixring_n(\R) = \R^{n^2}\). Claim that \(O(n)\) is a manifold of dimension \(\frac{n(n - 1)}{2}\).

  Let \(S(n) \subseteq \matrixring_n(\R)\) be the subset of symmetric matrices. This is a subspace of \(\R^{n^2}\) so clearly a submanifold of dimension \(\frac{n(n + 1)}{2}\). Consider that map
  \begin{align*}
    f: \matrixring_n &\to S(n) \\
    A &\mapsto AA^T
  \end{align*}
  which is a smooth map. As \(f^{-1}(I) = O(n)\), if \(I\) is a regular value of \(f\) then \(O(n)\) is a manifold of dimension \(\frac{n(n - 1)}{2}\).
  \begin{align*}
    df_A(H) &= \lim_{s \to 0} \frac{(A + sH)(A + sH)^T - AA^T}{s} \\
            &= AH^T + HA^T
  \end{align*}
  Given \(C \in S(n)\), \(H = \frac{CA}{2}\) satisfies \(df_A(H) = C\) so \(df_A\) is surjective.
  \end{enumerate}
\end{eg}

\begin{remark}
  In addition to being a manifold, \(O(n)\) is a group under matrix multiplication. The group operations are smooth. We call it a \emph{Lie group}. In this case, objects that preserve geometric objects (i.e.\ transformations) are themselves geometric objects.

  It is also worthing pointing out that \(O(n)\) is not connected, as seen from the continuous map \(\det: O(n) \to \{\pm 1\}\). The connected component of identity is called \emph{special orthogonal group}
  \[
    SO(n) = \{A \in O(n): \det A = 1\}.
  \]
\end{remark}

\begin{definition}
  A set \(S \subseteq \R^n\) is said to be \emph{measure \(0\)} if for all \(\varepsilon > 0\) there exists a countable collection of cubes \(C_m\) such that \(S \subseteq \bigcup C_m\) and \(\sum \operatorname{volume} C_m < \varepsilon\).
\end{definition}

\begin{definition}
  Let \(X\) be an \(n\)-dim manfiold and \(S \subseteq X\). \(S\) has \emph{measure \(0\)} if for all local parameterisations \(\varphi: U \to V \subseteq X\), \(\varphi^{-1}(V \cap S) \subseteq \R^n\) is of measure \(0\).
\end{definition}

This is well-defined since we can show any manifold can be parameterised by a chart of countably many parameterisations and the countable union of measure \(0\) subsets in \(\R^n\) has measure \(0\).

\begin{remark}\leavevmode
  \begin{enumerate}
  \item An open subset \(V \subseteq X\) is not of measure \(0\).
  \item Suppose \(Y \subseteq X\) is a submanifold of \(X\) and \(\dim Y < \dim Y\). Then \(Y\) is of measure \(0\) in \(X.\)
  \end{enumerate}
\end{remark}

\begin{theorem}[Sard's Theorem]
  Let \(f: X \to Y\) be a smooth map between manifolds. Then the set of critical values of \(f\) is of measure \(0\) in \(Y\).
\end{theorem}

\begin{corollary}
  Regular values are dense.
\end{corollary}

\subsection{Transversality}

Suppose \(f: X \to Y\) is a smooth map between manifolds and \(Z \subseteq Y\) is a submanifold.

\begin{definition}[Transversality]\index{transversality}
  \(f\) is \emph{transversal to \(Z\)}, denoted \(f \transversal Z\), if for all \(x \in f^{-1}(Z)\),
  \[
    \im df_x + T_{f(x)}Z = T_{f(x)}Y.
  \]
\end{definition}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item If \(f(X) \cap Z = \emptyset\) then \(f\) is vacuously transversal to \(Z\).
  \item This is a generalisation of regular value: if \(Z = \{y\}\) then \(f \transversal Z\) if and only if \(y\) is a regular value of \(f\) since the tangent space of a dimension \(0\) manifold is \(0\).
  \end{enumerate}
\end{remark}

\begin{eg}
  Let \(X = \R, Y = \R^2\), \(f(t) = (0, t)\) and \(Z \subseteq Y\) is the \(x\)-axis. Then \(df_0 = \binom{0}{1}\) and \(T_{(w, 0)}Z = \operatorname{span}\{\binom{w}{0}\}\) so \(\Im df_0 + T_{(w, 0)}Z = \R^2\) so \(f \transversal Z\).
\end{eg}

\begin{eg}
  Let \(f(t) = (t, t^2)\). Then \(df_0 = \binom{1}{0}\) so
  \[
    \Im df_0 + T_{(w, 0)}Z \neq \R^2
  \]
  so \(f\) is not transversal to \(Z\).
\end{eg}

The corresponding generalisation of pre-image theorem is

\begin{theorem}[Transversality theorem]\index{transversality theorem}
  Suppose \(f: X \to Y\) is a smooth map between manifolds and \(Z \subseteq Y\) is a submanifold. If \(f \transversal Z\) then \(f^{-1}(Z) \subseteq X\) is a submanifold of \(X\) with codimension equal to \(\codim_Y(Z)\).
\end{theorem}

\begin{proof}
  It is enough to show that for all \(x \in Z\), there exists \(V \subseteq Z\) open such that \(f^{-1}(V)\) is a submanifold of \(X\), i.e.\ we can work locally to deduce global result. This is because if \(\{V_i\}_{i \in I}\) is a cover of \(Z\) then
  \[
    f^{-1}(Z) = \bigcup_{i \in I} f^{-1}(V_i).
  \]

  Given \(x \in Z\), let \(\codim_Y Z = k\). Claim that there exist \(V \subseteq Z\) open containing \(x\): there exists \(\tilde V \subseteq Y\) open such that
  \[
    V = Z \cap \tilde V =
    \begin{cases}
      h_1 = 0 \\
      h_2 = 0 \\
      \vdots \\
      h_k = 0
    \end{cases}
  \]
  where \(k_i: \tilde V \to \R\) and moreover \(Z \cap \tilde V = h^{-1}(0)\) and \(0\) is a regular value of \(h\). This is basically saying that a submanifold of codimension \(k\) can be expressed as the pre-image of \(0\) where \(0\) is a regular value. This is left as an exercise.

  Now we prove the theorem. wlog assume \(Z = Z \cap \tilde V\). Consider \(h \compose f: X \to \R^k\). Its differential is
  \[
    d(h \compose f)_x = dh_{f(x)} \compose df_x.
  \]
  Claim that \(0\) is a regular value of \(h \compose f\): \(x \in (h \compose f)^{-1}(0)\) if and only if \(x \in f^{-1}(Z)\). Recall that \(T_yZ = \ker dh_y\) (see example sheet). From transversality we know
  \[
    \Im df_x + T_{f(x)}Z = T_{f(x)}Y
  \]
  so
  \[
    \Im df_x + \ker dh_{f(x)} = T_{f(x)}Y.
  \]
  Apply \(dh_{f(x)}\) to both sides, we get
  \[
    \Im dh_{f(x)} \compose df_x = \Im dh_{f(x)} = \R^k
  \]
  where the last equality is by surjectivity.

  Therefore \((h \compose f)^{-1}(0) \subseteq X\) is a submanifold of codimension \(k\). So does \(f^{-1}(Z)\).
\end{proof}

Consider the special case where \(X\) and \(Z\) are both submanifolds of \(Y\), i.e.\ \(f = \iota: X \to Y\). Then \(\iota \transversal Z\) if and only if
\[
  \Im d\iota_x + T_{\iota(x)}Z = T_{\iota(x)}Y
\]
which can be rewritten as
\[
  T_xX + T_xZ = T_xY.
\]
In this case write \(X \transversal Z\) (which is clearly a symmetric relation).

\begin{eg}
  If \(f \transversal Z\), it is not necessarily the case that \(f(X) \transversal Z\). Consider \(X = \R, Y = \R^2\), \(f(t) = (0, t^2)\) and \(Z \subseteq Y\) is the \(x\)-axis. Then \(f^{-1}(Z) \cap X\) is a submanifold of \(X\) of dimension \(0\).
\end{eg}

\begin{corollary}
  If \(\iota^{-1}(Z) \subseteq X\), then \(X \cap Z\) is a submanifold of \(Y\) with codimension
  \[
    \codim_Y(X \cap Z) = \codim_Y X + \codim_Y Z.
  \]
\end{corollary}

\subsection{Manifolds with boundary}

\begin{notation}
  \(\H^n = \{(x_1, \dots, x_n): x_i \geq 0\} \subseteq \R^n\).
\end{notation}

\begin{definition}[Manifold with boundary]\index{manifold!manifold with boundary}
  \(X \subseteq \R^n\) is an \(n\)-dimensional \emph{manifold with boundary} if for all \(x \in X\) there exists \(V \subseteq X\) open, \(U \subseteq \H^n\) open and \(\varphi: U \to V\) a diffeomorphism.
\end{definition}

It is possible that \(U\) is also open in \(\R^n\).

\begin{definition}[Boundary, interior]\index{boundary}\index{interior}
  The \emph{boundary} of \(X\), denoted \(\p X\), is defined to be
  \[
    \p X = \{x: \exists \varphi \text{ as above such that } x = \varphi(x_1, \dots, x_{n - 1}, 0)\}.
  \]
  Equivalently, \(x \in \varphi(U \cap \p \H^n)\) where \(\p \H^n = \{(x_1, \dots, x_{n - 1}, 0)\}\).

  The \emph{interior} of \(X\), denoted \(\Int X\), is defined to be \(X \setminus \p X\).
\end{definition}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item The above definition is consistent, i.e.\ independent of parameterisation: if \(x \in \varphi(U \cap \p H^n)\) for some \(\varphi\) then it holds for all \(\varphi\) such that \(x \in \Im \varphi\).
  \item \(\H^n\) is an \(n\)-dimensional manifold with boundary.
  \item Boundary of manifolds is \emph{not} the same as topological boundary, defined to be the set difference between the closure and the interior.
  \item For any manifold with boundary \(X\), \(\p X\) and \(\Int X\) are manifolds without boundary of dimension \(\dim X - 1\) and \(\dim X\) respectively. This can be seen by restricting image of \(\varphi\) to \(\p \H\) and \(\Int \H\) respectively.
  \end{enumerate}
\end{remark}

\begin{eg}\leavevmode
  \begin{enumerate}
  \item The closed unit ball \(B_n \subseteq \R^n\) is a manifold with bounday, whose boundary is \(\p B_n = S^{n - 1}\).
  \item Any manifold is a manifold with boundary (without boundary).
  \end{enumerate}
\end{eg}

\begin{ex}[Classification of \(1\)-dim connected manifolds with boundary]
  Show that any \(1\)-dim connected manifolds is up to diffeomorphism one of
  \begin{table}[h!]
    \centering
    \begin{tabular}{|c|c|c|}
      \hline
      \(X\) & \(\p X\) & Compactness \\ \hline
      \(S^1\) & \(\emptyset\) & Yes \\ \hline
      \((0, 1)\) & \(\emptyset\) & No \\ \hline
      \([0, 1)\) & \(\{0\}\) & No \\ \hline
      \([0, 1]\) & \(\{0, 1\}\) & Yes \\ \hline
    \end{tabular}
    \caption{\(1\)-dim manifolds}
  \end{table}
\end{ex}

\begin{lemma}
  Let \(X\) be an \(n\)-dim manifold (without boundary) and \(f: X \to \R\) smooth. Suppose \(0\) is a regular value of \(f\). Then \(\{x \in X: f(x) \geq 0\} \subseteq X\) is a submanifold with boundary whose boundary is \(\{x \in X: f(x) = 0\}\).
\end{lemma}

\begin{proof}
  Immediate from pre-image theorem. Suppose \(x \in X\) such that \(f(x) > 0\) then \(x \in f^{-1}((0, \infty)\) which is open in \(X\). If \(f(x) = 0\), just proceed as in pre-image theorem and consider \((F|_U)^{-1}: I \times T(U) \to U\) restricted to \(I \cap \{t \geq 0\}\).
\end{proof}

\begin{eg}
  Let
  \begin{align*}
    f: \R^n &\to \R \\
    (x_1, \dots, x_n) &\mapsto 1 - \sum_{i = 1}^n x_i^2
  \end{align*}
  Then \(B^n = f^{-1}((0, \infty))\) is a manifold with boundary.
\end{eg}

Note that with the definition of tangent space as before, for all \(x \in X\) (even those on the bounday), we have
\[
  \dim dT_xX = \dim X.
\]

Also for \(x \in \p X\),
\[
  T_x\p X \leq T_xX.
\]

Next up is an extension of pre-image theorem

\begin{theorem}
  Let \(X\) be a manifold with boundary and \(f: X \to Y\) be a smooth map betwween manifolds. Suppose \(y \in Y\) is a regular value of \(f\) and \(f|_{\p X}\), then \(f^{-1}(y)\) is a submanifold with boundary of \(X\), with boundary \(\p f^{-1}(y) = f^{-1}(y) \cap \p X\).
\end{theorem}
In this case \(\dim X > \dim Y\).

\begin{proof}
  Note that if \(x \in f^{-1} \cap \Int X\) we can apply pre-image theorem. Thus assume \(x \in f^{-1}(y) \cap \p X\). As an open set in \(\H^n\) with non-empty intersection with its boundary is diffeomorphic to \(\H^n\), assume wlog \(X = \H^n\) and similarly \(Y = \R^m\), where \(\dim X = n, \dim Y = m\).

  Given such an \(x\), there exists \(U\) open in \(\R^n\) containing \(x\) such that there exists \(F: U \to \R^m\) smooth such that \(F|_{U \cap \H^n} = f|_U\). \(y\) is a regular value of \(f\) so \(df_x\) is surjective. For \(U\) small enough, \(df_z\) surjective for all \(z \in U \cap \H^n\). Then \(dF_z\) is surjective for all \(z \in U\). Then \(y\) is a regular value of \(U\).

  We want \(f^{-1}(y) \cap U\) to be a manifold with boundary. Claim that the set equal to \(F^{-1} \cap \H^n\). \(F^{-1}(y)\) is a manifold by pre-image theorem. Introduce projection map
  \begin{align*}
    \pi: \R^n &\to \R \\
    (x_1, \dots, x_n) &\mapsto x_n
  \end{align*}
  Then \(F^{-1}(y) \cap \H^n = F^{-1}(y) \{x: \pi(x) \geq 0\} = \{x: (\pi|_{f^{-1}(y)})^{-1}(x) \geq 0\}\). All we need to do is to show \(0\) is a regular value of the map \((\pi|_{f^{-1}(y)})^{-1}\). But from example sheet
  \[
    d\pi|_{f^{-1}(y)} = \pi|_{T_xF^{-1}(x)} = \pi|_{\ker dF_x} = \pi|_{\ker df_x}.
  \]
  Thus just need to show \(\ker df_x \neq \R^{n - 1} = T_x\p X\). Done by assumption on \(f\).
\end{proof}

If \(f \transversal Z\) and \(f|_{\p X} \transversal Z\)
\blindtext

\subsection{Degree mod \(2\)}

Let \(X\) be a manifold and \(Y\) be a manifold with boundary.

\begin{definition}[Smooth homotopy]\index{smooth homotopy}
  Two smooth maps \(f, g: X \to Y\) are said to be \emph{smoothly homotopic} if there exists a smooth map \(F: [0, 1] \times X \to Y\) such that \(F|_{\{0\} \times X} = f\) and \(F|_{\{1\} \times X} = g\).
\end{definition}

\begin{notation}
  For \(t \in [0, 1]\), \(f_t = F|_{\{t\} \times X}\). It is a restriction of a smooth map so is smooth.
\end{notation}

\begin{remark}
  \(f\) smoothly homeomorphic to \(g\) is an equivalence relation. See example sheet. This is slightly less trivial than its topological counterpart since arbitrary reparameterisation is not necessarily smooth.
\end{remark}

\begin{definition}[Smooth isotopy]\index{smooth isotopy}
  If \(f\) and \(g\) above are smoothly homotopic diffeomorphisms and \(f_t\) is a diffeomrophism for all \(t \in [0, 1]\) then we say that \(F\) is a \emph{smooth isotopy} and \(f\) and \(g\) are \emph{smoothly isotopic}.
\end{definition}

\begin{remark}
  This is also an equivalence relation.
\end{remark}

\begin{lemma}[Homogeneity lemma]\index{homogeneity lemma}
  Let \(X\) be a connected manifold, \(y, z \in X\). Then there exists a map \(\varphi: X \to X\) smoothly isotopic to the identity such that \(\varphi(y) = z\).
\end{lemma}

This says that in differential topology, there is no ``particular'' point in a connected component of a manifold.

\begin{proof}[Sketch of proof]
  Say \(y\) and \(z\) isotopic if there exists such a \(\varphi\). This defines an equivalence relation \(\sim\) on \(X\). It then suffices, by connectivity, to show that the equivalence classes are open. Given \(y \in X\), must find an open neighbourhood \(V\) of \(y\) such that for all \(z \in V\), \(z \sim y\).

  Suffices to show given \(z \in \cl B(0, 1) \subseteq \R^n\), there exists \(F: \R^n \times [0, 1] \to \R^n\) smooth isotopy of diffeomorphisms such that  \(f_0 = \id_{\R^n}\) and \(f_1(0) = z\) with \(f_t|_{\R^n\setminus \cl B(0, 2)}\) (by considering a chart covering ???, we can pushforward the map and extend it by identity outside the ball to ensure smoothness).

  One way to do this is to use cut-off function and ODE theory.
\end{proof}

\begin{lemma}
  Let \(X\) be a compact manifold, \(Y\) a manifold and \(\dim X = \dim Y\). Let \(f, g: X \to Y\) be smoothly homotopic. Let \(y\) be a regular value of both \(f\) and \(g\). Then
  \[
    \# f^{-1}(y) = \# g^{-1}(y) \pmod 2.
  \]
\end{lemma}

\begin{proof}
  Let \(F: X \times [0, 1] \to Y\) be the smooth homotopy between \(f\) and \(g\). Assume first \(y\) is a regular value of \(F\). Note that
  \[
    \p(X \times [0, 1]) = \{0\} \times X \cup \{1\} \times X
  \]
  so denote
  \[
    F|_{\p(X \times [0, 1])} = f \cup g.
  \]
  Then by generalised pre-image theorem, \(F^{-1}(y)\) is a manifold with boundary, whose boundary is
  \[
    \p F^{-1}(y) = F^{-1} \cap \p(X \times [0, 1]) = \left( \bigcup_{x \in f^{-1}(y)}\{0\} \times \{x\}\right) \cup \left( \bigcup_{x \in g^{-1}(y)}\{1\} \times \{x\}\right).
  \]
  By assumption \(F^{-1}(y)\) is a compact \(1\)-dim manifold, which by classification above is a union of disjoint circles or closed intervales. But both of these have even number of boundary points so
  \[
    \# \p F^{-1}(y) = \# f^{-1}(y) + \# g^{-1}(y) = 0 \pmod 2.
  \]

  Suppose instead \(y\) is not a regular value of \(F\). Consider an open neighbourhood \(V \subseteq Y\) of \(y\). By Sard's Theorem the sets of critical values of \(f, g\) and \(F\) are all of measure \(0\), so is the union of them. Then there exist \(\tilde y \in V\) that is a regular value of \(f, g, F\). But by stack of records theorem there exists \(V\) containing \(y\) such that \(f^{-1}(V) = \bigcup_{i = 1}^n U_i\) such that \(f|_{U_i}: U_i \to V\) is a diffeomorphism.
\end{proof}

\begin{theorem}[Degree mod \(2\)]
  If \(y\) and \(z\) are regular values of \(f\) then
  \[
    \# f^{-1}(y) = f^{-1}(z) \pmod (2).
  \]
\end{theorem}

\begin{proof}
  \blindtext
\end{proof}

Putting everyting together, under the assumptions above, we have \(f^{-1}(y)\) does not depend on the choice of regular value \(y\). Moreover if \(g\) is smoothly homotopic to \(f\) then \(g^{-1}(z) = f^{-1}(y) \pmod 2\) for any regular value \(z\) of \(g\).

\begin{definition}[Degree mod \(2\)]\index{degree mod \(2\)}
  Suppose \(X\) is a compact manifold, \(Y\) a connected manifold and \(\dim X = \dim Y\). Let \(f: X \to Y\) be a smooth map. Then the \emph{degree mod \(2\)} of \(f\), denoted \(\deg_2(f)\), is defiend to be \(\# f^{-1}(y) \pmod 2\) for some regular value \(y\) of \(f\).
\end{definition}

By Sard's theorem, there exists a regular value and by theorems above, this is well-defined. Moreover, this only depends on the homotopy class of \(f\).

\begin{eg}\leavevmode
  \begin{enumerate}
  \item Let \(X, Y = S^n\), \(f: X \to Y\) be a constant map. Then \(\deg_2 f = 0\) since we can find \(y \in Y \setminus \Im f\) and \(\# f^{-1}(y) = 0\).
  \item Let \(X, Y = S^n\), \(\id: X \to Y\) be the identity. Then \(\deg_2 \id = 1\). Thus \(f\) and \(\id\) are not smoothly homotopic.
  \end{enumerate}
\end{eg}

\begin{corollary}
  There does not exist a smooth retraction \(B^n \to \p B^n= S^{n - 1}\), i.e.\ a map \(f: B^n \to \p B^n\) such that \(f|_{\p B^n}: \p B^n \to \p B^n\) is the identity.
\end{corollary}

\begin{proof}
  Suppose not. Define
  \begin{align*}
    F: S^{n - 1} \times [0, 1] &\to S^{n - 1} \\
    (x, t) &\mapsto f(tx)
  \end{align*}
  whose smoothness is left as an exercise. Then \(F\) is an homotopy of \(f\) and \(\id\). Absurd.
\end{proof}

\begin{corollary}[Brouwer's fixed point theorem]\index{Brouwer's fixed point theorem}
  Let \(f: B^n \to B^n\) be smooth. Then there exists \(x_0 \in B^n\) such that \(f(x_0) = x_0\).
\end{corollary}

\begin{proof}
  Suppose \(f\) is smooth without fixed point. Then the ray from \(f(x)\) to \(x\) intersects \(\p B^n\) at precisely one point, say \(g(x)\). Claim that \(g\) is smooth (left as an exercise). If \(x \in \p B^n\) then \(g(x) = x\). Then \(g\) is a smooth retraction. Absurd.
\end{proof}

\begin{corollary}[Brouwer's fixed point theorem]\index{Brouwer's fixed point theorem}
  Same true with continuous assumption.
\end{corollary}

\begin{proof}
  Weierstrass approximation theorem.
\end{proof}

\subsubsection{Intersection number mod 2}

Let \(X\) be a compact manifold, \(Y\) be a manifold, \(Z \subseteq Y\) a closed subset. Suppose \(f: X \to Y\) is smooth and \(f \transversal Z\) and \(\dim X + \dim Z = \dim Y\).

\begin{definition}
  The \emph{intersection number mod 2} is
  \[
    I_2(f, Z) = \# f^{-1}(Z) \pmod 2.
  \]
\end{definition}

Claim that if \(f\) and \(g\) are smoothly homotopic and \(g \transversal Z\) then \(I_2(f, Z) = I_2(g, Z)\).

In the speical case \(X \subseteq Y\), we have \(X \transversal Z\) and denote it \(I_2(X, Z)\).

\begin{eg}
  Let \(Y\) be a torus. Let \(X\) and \(Z\) be the two ``perpendicular circles'' on \(Y\). Then \(I_2(X, Z) = 1\).
\end{eg}

It turns out we can still define intersection number \emph{without} the assumption \(X \transversal Z\).

\begin{eg}
  Suppose \(\dim Y\) is even and \(\dim X\) is \(\frac{\dim Y}{2}\). Note that \(X\) is not transversal to \(X\). Let \(Y\) be the Möbius band and \(X\) a central circle, \(I_2(X, X) = 1\).
\end{eg}

\subsection{Abstract manifolds}

\begin{definition}[Smooth manifold]\index{manifold!abstract smooth manifold}
  A \emph{smooth \(n\)-dimensional manifold} is a Hausdorff, second-countable topological space \(X\) together with a collection of maps \(\varphi: U_\alpha \to V_\alpha\) where \(U_\alpha \subseteq \R^n, V_\alpha \subseteq X\), called \emph{charts}, with the following properties:
  \begin{enumerate}
  \item \(\varphi_\alpha: U_\alpha \to V_\alpha\) are homeomorphisms,
  \item \(\bigcup_\alpha V_\alpha = X\),
  \item \(\varphi_\beta^{-1} \compose \varphi_\alpha|_{\varphi_\alpha^{-1}(U_\alpha \cap V_\beta)}\) are diffeomorphisms for all \(\alpha, \beta\),
  \item lastly, it is conventional to require the collection of charts to be maximal, i.e.\ if \(\{\varphi_\alpha\}_\alpha \cup \{\tilde \varphi\}\) satisfies 1, 2, 3 then \(\tilde \varphi = \varphi_\alpha\) for some \(\alpha\).
  \end{enumerate}
\end{definition}

Note that Hausdorffness and second-countability are hereditary properties.

We can now define smooth maps \(X \to \R^m\) and smooth maps between manifolds, similar as before. Also compatibility condition requires us only to check smoothness on an open cover of \(X\).

What about differentials and tangent spaces? Since our manifold \(X\) is no longer sitting inside an Euclidean space, the differential of a chart is not very meaningful. This is point where the abstract theory diverges from what we have learned. In III Differential Geometry you will learn to do it properly using tangent bundles.

\begin{definition}[Immersion, submersion, embedding]\index{immersion}\index{submersion}\index{embedding}
  A smooth map \(f: X \to Y\) between manifolds is an \emph{immersion} if \(df_x\) is injective for all \(x \in X\), a \emph{submersion} if \(df_x\) is surjective for all \(x \in X\), and an \emph{embedding} if it is an immersion and a homeomorphism onto its image.
\end{definition}

\begin{theorem}[Whitney embedding theorem]\index{Whitney embedding theorem}
  Let \(X\) be a smooth manifold. Then there exists an embedding \(f: X \to \R^{2n + 1}\).
\end{theorem}

Thus the abstract formulation of manifold is not any more general than the one we begin with.

In fact, Whitney proved the better upper bound \(\R^{2n}\), which is in fact a sharp bound.

\section{Geometry}

\begin{definition}[Regular curve]
  Let \(X\) be a manifold. A \emph{regular curve} in \(X\) is a smooth immersion \(\gamma: I \to X\) where \(I \subseteq \R\) is an interval, i.e.\ \(d\gamma_t(1) \neq 0\).
\end{definition}

\begin{notation}
  We write \(\dot \gamma(t) = d\gamma_t\).
\end{notation}

\begin{ex}
  Suppose \(X = \R^3\) and \(\gamma(t) = (x(t), y(t), z(t))\), show that \(\dot \gamma(t) = (\dot x(t), \dot y(t), \dot z(t))\).
\end{ex}

\begin{definition}[Arc-length]\index{arc-length}
  Let \(\gamma: I \to \R^3\) is a regular curve and \(t_0 \in I\). The \emph{arc-length} of \(\gamma\) (measured from \(t_0\)) is
  \[
    s(t) = \int_{t_0}^t |\dot \gamma(t')| dt'
  \]
  where \(|\cdot|\) is the Euclidean norm.
\end{definition}

Arc-length is invariant to reparameterisation: a reparameterisation of \(\gamma\) is a map \(\hat \gamma(\hat t)\) such that \(t = t(\hat t)\) is a diffeomorphism, i.e.\ the following diagram commutes:
\[
  \begin{tikzcd}
    I \ar[r, "\gamma"] & \R^3 \\
    \hat I \ar[u] \ar[ur, "\hat \gamma"']
  \end{tikzcd}
\]
Wlog suppose \(\frac{dt}{d\hat t} > 0\). Let \(t_0 = t(\hat t_0)\), then
  \[
    s(t)
    = \int_{t_0}^t |\hat \gamma(t')| dt'
    = \int_{t_0}^t \left| \frac{d\gamma}{dt'} \right| dt'
    = \int_{\hat t_0}^{\hat t} \left| \frac{d\gamma}{d\hat t'} \right| dt'
    = s(\hat t)
  \]

Note that \(s'(t) = |\hat \gamma(t)| \neq 0\) by Fundmental Theorem of Calculus. Thus by Inverse Function Theorem and connectivity \(s(t)\) is a diffeomorphism, i.e.\ can be inverted to \(t(s)\). Thus we can reparameterise any regular curve by \(s\). We will write \(\gamma(s)\) for \(\gamma(t(s))\).

Missed a lecture

Frenet equations

\[
  \begin{pmatrix}
    \dot t \\
    \dot n \\
    \dot b
  \end{pmatrix}
  =
  \begin{pmatrix}
    0 & k & 0 \\
    -k & 0 & -\tau \\
    0 & \tau & 0
  \end{pmatrix}
  \begin{pmatrix}
    t \\
    n \\
    b
  \end{pmatrix}
\]

The curvature \(k\) and torsion \(\tau\) is invariant under isometries.

\begin{theorem}[Fundamental theorem of curves in \(\R^3\)]\index{Fundamental theorem of curves in \(\R^3\)}
  Given smooth function \(k > 0\) and \(\tau(s)\), \(s \in I\), there exists a regular curve \(\alpha: I \to \R^3\) such that \(s\) is the arclength, \(k(s)\) is the curvature and \(\tau(s)\) is the torision of \(\alpha\).

  Moreover, given \(k = \tilde k, \tau = \tilde \tau\), then there exists an isometry of \(\R^3\) such that
  \[
    \tilde \gamma = R \compose \gamma + b.
  \]
\end{theorem}

\begin{proof}
  Let \(b = \tilde \gamma(0) - \gamma(0)\) and we can assume \(\tilde \gamma(0) = \gamma(0) = 0\). Given two orthonormal basis \(\{t(0), s(0), n(0)\}\) and \(\{\tilde t(0), \tilde s(0), \tilde n(0)\}\) in the same orientation, it is an exercise in Euclidean geometry to show that there exists an element \(R \in \SO(3)\) sending the first triplet to the second.

  To avoid excessive notation, replace \(\gamma\) with \(R \compose \gamma\). Then \(\gamma(s)\) and \(\tilde \gamma(s)\) satisfy the Frenet equations, which is a linear ODE, with the same initial condition. Thus by uniqueness of solutions of ODE \(\gamma = \tilde \gamma\).
\end{proof}

Geometric intuition: curvature measures the turning of the tangent, \(k\) the magnitude and \(n\) measures the direction. Torsion measures the non-planiness of a curve.

\begin{proposition}
  Given a regular curve \(\gamma(s)\), \(\tau = 0\) if and only if \(\gamma\) lies in a plane.
\end{proposition}

\begin{proof}
  Suppose \(\tau = 0\). Then \(\dot b = 0\) so \((t \wedge n)' = 0\). Let \(\Pi\) be the plane spanned by \(t\) and \(n\) and so \(\Pi(s) = \Pi_0\) is constant.

  Consider the plane \(\gamma(0) + \Pi\), claim \(\gamma(I) \subseteq \gamma(0) + \Pi_0\): this is equivalent to claiming that \(\gamma(s) - \gamma(0) \in \Pi\) for all \(s\). But
  \[
    \gamma(s) - \gamma(0) = \int_0^s \gamma'(u)du = \int_0^s t(u)du \in \Pi.
  \]

  The other direction is left as an exercise.
\end{proof}

\begin{definition}[Plane curve]\index{plane curve}
  A regular curve is said to be a \emph{plane curve} if its image lies in a plane \(\Pi \subseteq \R^3\).
\end{definition}

Wlog we will consider all plane curves as maps \(\gamma: I \to \R^2\).

For regular plane curves, there is an alternative definition of the curvature:

\begin{definition}[Signed curvature]\index{signed curvature}
  Let \(\gamma(s)\) be a plane curve in \(\R^2\) parameterised by arc-length \(s\). \(t = \dot \gamma(s)\) is the tangent. Pick \(n(s)\) so that \(t, n\) has the usual orientation (exercise: exhibit such \(n\)). Then \(\dot t(s) \cdot t(s) = 0\) so define \emph{signed curvature} \(k(s)\) to be such that
  \[
    \dot t(s) = k(s)n(s)
  \]
  where \(k(s) \in \R\), i.e.\ not necessarily non-vanishing.
\end{definition}

Note the subtleties in the order of terms being defined: in general regular curves we defined \(k(s)\) and \(n(s)\) in terms of \(\dot t(s)\) but for plane curves, we fixed \(n(s)\) first (using orientation of orthonormal basis) and then define \(k(s)\) to be the signed magitude of \(\dot t(s)\).

\begin{ex}
  Define the Frenet formulae for plane curves:
  \begin{align*}
    \dot t(s) &= k(s)n(s) \\
    \dot n(s) &= -k(s)t(s)
  \end{align*}
\end{ex}

\subsection{Isoperimetric inequality in the plane}

The is the first global result we meet in differential geometry. Let \(\gamma\) be a smooth simple closed curve in \(\R^2\), i.e.\ \(\gamma: S^1 \to \R^2\) is a smooth embedding. Thanks to

\begin{theorem}[Jordan curve theorem]
  \(\gamma(S^1)\) is the boundary of a bounded, simply-connected open set in \(\R^2\).
\end{theorem}
we let \(\Omega\) be the bouned open set (alternatively assume \(\cl \Omega\) is a \(2\)-manifold with boundary in \(\R^2\) with boundary diffeomorphic to \(S^1\)).

\begin{note}
  We want to define \(\alpha(\R) = \alpha(S^1)\).

  Let \(\alpha: \R \to \R^2\) be a regular curve parameterised by arc-length. Let \(L\) be the first \(s > 0\) such that \(\alpha(L) = \alpha(0)\). Then \(\alpha\) be periodic with period \(L\). \(L\) is the arc-length of \(\gamma\).
\end{note}

\begin{theorem}[Isoperimetric inequality]\index{isoperimetric inequality}
  \[
    L^2 \geq 4\pi \operatorname{area}(\Omega)
  \]
  with equality if and only if \(\gamma\) is a circle.
\end{theorem}

\begin{remark}
  It suffices to assume \(\alpha\) is \(C^1\).
\end{remark}

Write \(\alpha(s) = (x(s), y(s))\) where \(x(s)\) and \(y(s)\) are \(C^1\) functions. Let \(\V V: \R^2 \to \R^2\) be the identity and think of it as a vector field. By divergence theorem applied to \(\V V\) in \(\Omega\),
\begin{align*}
  2 \operatorname{area}(\Omega)
  &= \int_\Omega \divergence \V V \\
  &= \int_0^L \V V \cdot (-n) ds \\
  &\leq \int_0^L \norm{\V V(s)} ds \\
  &\leq \left( \int_0^L \norm{\V V(s)}^2 ds \int_0^L 1^2 ds \right)^{1/2}
\end{align*}

Missed a lecture

\subsection{Riemannian metric}

something something Riemannian metric. See printed notes.

\begin{definition}[Isometry]\index{isometry}
  Let \(X\) and \(Y\) be (Riemannian) manifolds with Riemannian metrics \(g_p\) and \(\tilde g_q\) respectively. We say \(X\) and \(Y\) are \emph{isometric} if there exists \(f: X \to Y\) smooth such that
  \[
    df_x: T_xX \to T_{f(x)}Y
  \]
  is an isometry of inner product spaces, i.e.\ for all \(v, w \in T_xX\),
  \[
    g_x(v, w) = \tilde g_{f(x)}(df_x(v), df_x(w)).
  \]
  Furthermore \(df_x\) is invertible.
\end{definition}

Note that conventions vary. If \(df_x\) is not required to be invertible then \(f\) is usually called an \emph{isometric embedding}.

\begin{definition}[Local isometry]\index{isometry}
  Two Riemannian manifolds \(X\) and \(Y\) are \emph{locally isometric} around \(p \in X\) if there exist \(V \ni p\) open in \(X\) and \(W\) open in \(Y\) such that \(f: V \to W\) is an isometry.
\end{definition}

\begin{question}\leavevmode
  \begin{enumerate}
  \item When are two surfaces \(X\) and \(Y\) (say embedded in \(\R^3\)) locally isometric? Globally isometric?
  \item When is \(X\) locally isometric to the plane? (intrinsic geometry)
  \item When do \(X\) and \(Y\) differ by a Euclidean isometry, i.e.\ \(Y = R(X) + b\) where \(R \in \SO(3)\)? (extrinsic geometry)
  \end{enumerate}
\end{question}

Let \(X\) be a Riemannian \(2\)-manifold. Let \(\varphi: U \to V\) be a local parameterisation. Define
\begin{align*}
  E(u, v) &= g(\varphi_u, \varphi_u) > 0 \\
  F(u, v) &= g(\varphi_u, \varphi_v) \\
  G(u, v) &= g(\varphi_v, \varphi_v) > 0
\end{align*}
with \(EG - F^2 > 0\) and \(E, F, G\) smooth. Claim that \(\begin{psmallmatrix} E & F \\ F & G \end{psmallmatrix}\) defines a Riemannian metric.

A converse question is, given such \(E, F, G\), does there exist a local parameterisation \(\varphi: U \to V\) such that \(E, F, G\) are coefficients of \(I_p\)? The answer is positive for analytic functions, but in more general settings this is still an open problem. Thus it is possible that local Riemannian geometry is richer than Euclidean geometry.

First fundamental form

\begin{eg}[Embedded torus]

\end{eg}

\begin{ex}
  Do for general surfaces of revolution.
\end{ex}

\begin{definition}
  Let \(X\) be a surface in \(\R^3\). Let \(\varphi: U \to V\) be a local parameterisation. Let \(\Omega \subseteq V\) be an open set with smooth boundary. Then the area of \(\Omega\) is
  \[
    \int_{\varphi^{-1}(\Omega)} |\varphi_u \times \varphi_v| dudv.
  \]
\end{definition}

Claim that the definition is independent of parameterisation. Use chain rule for change of variable.

\begin{ex}
  \[
    \operatorname{area} \Omega = \int_{\varphi^{-1}(\Omega)} \sqrt{EG - F^2} dudv
  \]
  so the area depends only on the first fundamental form. Thus an isometry preserves area. In the other words, area is an intrinsic geometric property.
\end{ex}

\begin{remark}
  Using partition of unity, we can drop the restriction that \(\Omega\) lies in the range of a local parameterisation. In fact there exists a Borel measure on \(X\), denoted \(dA\), such that
  \[
    \operatorname{area} (\Omega) = \int_\Omega dA.
  \]
  Subsequently, we can define the integral of any smooth (actually measurable) map with respect to the measure.

  Note that \(E \subseteq X\) has measure zero as defined before if and only if \(E\) has measure \(0\) with respect to \(dA\).
\end{remark}

\begin{eg}
  The area of the embedded torus \(X\) define before is
  \[
    \operatorname{area}(X)
    = \int_0^{2\pi}\int_0^{2\pi} r(a + r\cos u) dudv
    = 4\pi^2 a r.
  \]
\end{eg}

\subsection{Gauss map}

Let \(X\) be a surface in \(\R^3\). Let \(\varphi: U \to V\) be a local parameterisation. Given \(p \in X\), \(\varphi_u, \varphi_v\) form a basis for \(T_pX\). Define a map
\begin{align*}
  f: V &\to S^2 \\
  p &\mapsto \frac{(\varphi_u \times \varphi_v)(\varphi^{-1}(p))}{|(\varphi_u \times \varphi_v)(\varphi^{-1}(p))|}
\end{align*}
which is a smooth map such that \(f(p) \perp T_pX\).

Note that the map with such property is not unique, for example taking it negative value.

\begin{definition}[Gauss map]\index{Gauss map}
  Let \(X\) be a surface in \(\R^3\). A \emph{Gauss map} of \(X\) is a smooth map \(N: X \to S^2\) such that \(N(p) \perp T_pX\) for all \(p \in X\).
\end{definition}

\begin{note}
  Let \(X\) be connected. If there exists a Gauss map then there exists precisely 2 Gauss maps \(N, -N\). Moreover
  \[
    N = \pm \frac{\varphi_u \times \varphi_v}{|\varphi_u \times \varphi_v|}
  \]
  in a local chart.
\end{note}

\begin{definition}[Orientability]\index{orientability}
  If there exists a Gauss map, we say \(X\) is \emph{orientable}. \((X, N)\) is called an \emph{oriented surface}.
\end{definition}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item There exists non-orientable surface, such as the Möbius band.
  \item The above definition is an extrinsic one. It is possible to characterise orientability intrinsically using transition maps.
  \end{enumerate}
\end{remark}

\begin{eg}
  The sphere is orientable, with \(N = \pm \id\).
\end{eg}

Let \(X\) be an orientable surface and \(N: X \to S^2\) a Gauss map. Consider the differential \(dN_p: T_pX \to T_{N(p)}S^2\). Since \(N(p) \perp T_pX\) by definition, and \(N(p) \perp T_{N(p)} S^2\) by the observation in the example above, we can identify \(T_pX = T_{N(p)}S^2\). Thus we can treat \(dN_p: T_pX \to T_pX\) as an endormorphism of an inner product space. Next time we will show that it is self-adjoint with respect to the first fundamental form.

\blindtext

\subsection{Theorema Egregium}

Since \(\{\varphi_u, \varphi_v, N\}\) form an orthonormal basis, we can express \(\varphi_{uu}, \varphi_{uv}\) etc as unique linear combinations of them. But what are the indices? Recall that
\[
  e = - \inner{\varphi_u, N_u} = \inner{\varphi_{uu}, N}
\]
and \(N\) is orthogonal to \(\varphi_U, \varphi_v\) so we have
\[
  \varphi_{uu}(u, v) = \Gamma_{11}^1(u, v) \varphi_u + \Gamma_{11}^2 \varphi_v + eN
\]
and etc.

\begin{definition}
  \(\Gamma_{ij}^k\) are called the \emph{Christoffel symbols}.
\end{definition}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item The Christoffel symbols are symmetric with repsect to lower indices, i.e.\ \(\Gamma_{ij}^k = \Gamma_{ji}^k\).
  \item \(\Gamma_{ij}^k = A(E, F, G, \p E, \dots, \p G)\) where \(A\) is a universal function. Take the inner product of the above relations with \(\varphi_u\) and recoginising \(\inner{\varphi_u, \varphi_u} = E\), we get
    \begin{align*}
      \Gamma_{11}^1 E + \Gamma_{1}^2 F &= \inner{\varphi_{uu}, \varphi_u} = \frac{1}{2} \p_u \inner{\varphi_u, \varphi_u} = \frac{1}{2} \p_u E \\
      \Gamma_{11}^1 F + \Gamma_{1}^2 G &= \inner{\varphi_{uu}, \varphi_v} = \p_u \inner{\varphi_u, \varphi_v} - \inner{\varphi_u, \varphi_{vu}} = \p_u F - \frac{1}{2} \p_v E
    \end{align*}
    Write it in matrix form,
    \[
      \begin{pmatrix}
        E & F \\
        F & G
      \end{pmatrix}
      \begin{pmatrix}
        \Gamma_{11}^1 \\
        \Gamma_{11}^2
      \end{pmatrix}
      =
      \begin{pmatrix}
        \frac{1}{2} \p_u E \\
        \p_u F - \frac{1}{2} \p_v E
      \end{pmatrix}
    \]
    We can repeat for the other \(\Gamma_{ij}^k\)'s.
  \end{enumerate}
\end{remark}

Let's go on and continue differentiating. Differentiate * with respect to \(v\) and ** with respect to \(u\), and by symmetry of partial derivatives,
\begin{align*}
  &\p_v \Gamma_{11}^1 \varphi_u + \p_v \Gamma_{11}^2 \varphi_v + (\p_v e) N + \Gamma_{11}^1 \varphi_{uv} + \Gamma_{11}^2 \varphi_{vv} + e N_v \\
  =& \p_u \Gamma_{12}^1 \varphi_u + \p_u \Gamma_{12}^2 \varphi_v + (\p_u f) N + \Gamma_{12}^1 \varphi_{uu} + \Gamma_{12}^2 \varphi_{vu} + f N_u
\end{align*}
Expand this in our favourite basis \(\{\varphi_u, \varphi_v, N\}\), we get three equations, each for a basis element. The first three components on each side are already in this form. Look up in * and **, we get
\begin{align*}
  \p_v \Gamma_{11}^2
\end{align*}

\blindtext

And after some algebra we find that \(K\) can be expressed purely in terms of the first fundamental form and its derivative.

\section{Critical points of length and curve}

Suppose \(X \subseteq \R^3\) is a surface and \(p, q \in X\). Let \(\Omega(p, q)\) be the set of all regular paths from \(p\) to \(q\). Then the length could be seen as a functional on \(\Omega(p, q)\). Since length depends only on the first fundamental form, i.e.\ an intrinsic geometric quantity, it turns out that the curves minimising the length functional are also special and intrinsic to the surface. They are called \emph{geodesic}.

Similarly, area is also a functional on the space of all surfaces. The area-miniming surfaces are called \emph{minimal surfaces} and eventually we can derive an equation depending on the mean curvature.

\printindex

\iffalse
Classical differential geometry concerning geometries of curves and surfaces, from a modern point of view

Contents:
I: notions of smmoth \(k\)-dim manifolds. We study differential topology.

Geometry is concerned with the study of rigid motions

invariants of curves: \(k\) curvature, \(\tau\) torsion
invariant of surfaces: \(K\) mean curvature, \(K\) Gaussian curvature
\fi

\end{document}

ext: tex

max_stars_repo_name: geniusKuang/tripos

max_issues_repo_name: b-mehta/tripos

max_forks_repo_name: b-mehta/tripos


text:
\subsection{The Levi-Civita connection}

For any metric tensor there is only one connection which preserves the metric and is torsion free.

max_stars_repo_name: adamdboult/nodeHomePage

max_issues_repo_name: adamdboult/nodeHomePage

max_forks_repo_name: adamdboult/nodeHomePage


text:
% TODO: #2 Flesh out outline and ensure it's ok.
\chapter*{Outline}
\begin{enumerate}
    \item Lit review
    \item DDD-FEM
    \item Analytic tractions
          \begin{enumerate}
              \item Traction errors
              \item Reaction force errors
              \item Simulations
              \item Recommendations and Conclusions
          \end{enumerate}
    \item Parallelising tractions
          \begin{enumerate}
              \item Algorithms
              \item Performance
              \item Simulations
              \item Recommendations and Conclusions
          \end{enumerate}
    \item EasyDD v2.0
          \begin{enumerate}
              \item Adaptive integration
              \item New mobility law
              \item Surface velocities
              \item Collisions
              \item Code redesign
          \end{enumerate}
    \item Future work
          \begin{enumerate}
              \item Julia redesign
              \item Preliminary comparisons
          \end{enumerate}
    \item Conclusions
    \item Appendices
          \begin{enumerate}
              \item Collaboratory summary
          \end{enumerate}
\end{enumerate}


text:
\label{sec:Method}
% describe the method we use

Algorithm~\ref{alg:nlls_solve} describes the method used to minimize the cost function
$F(\vx)$ in equation (\ref{eq:nlls_problem}). This is an iterative method that, at each iteration, calculates and returns a step $\vs$ that reduces the model by an acceptable amount by solving (or approximating a solution to) either the trust-region subproblem (\ref{eq:tr_subproblem}) or a regularized problem (\ref{eq:reg_subproblem}).

\begin{algorithm}
\caption{nlls\_solve}
\label{alg:nlls_solve}
  \begin{algorithmic}[1]
    \State  {\tt {\bf function} \tx }$=${\tt nlls\_solve}$(\iter[0]{\tx},\text{\tt options}{\tt[,W]})$
    \If {${\tt W}$ not present}
    \State ${\tt W=I}$
    \EndIf
    \State $\sigma = ${\tt options\ct regularization\_weight}, $p = ${\tt options\ct regularization\_power}
    \State $\iter[0]{\tr} =  {\tt W * }${\tt eval\_r}$(\iter[0]{\tx})$, $\iter[0]{\tJ} = {\tt W *}$ {\tt eval\_J}$(\iter[0]{\tx})$
    \Comment Evaluate residual and Jacobian at initial guess
    \State $\Delta = ${\tt options\ct initial\_radius}
    \State $ \iter[0]{\tg} = - {\iter[0]{\tJ}}^T\iter[0]{\tr} - \sigma \|\iter[0]{\tx}\|^{p-2}\iter[0]{\tx}$
    \State $\tt normF_0 = 0.5\|\iter[0]{\tr}\|^2 + \frac{\sigma}{p} \|\iter[0]{\tx}\|^p$
    \If {{\tt options\ct model == 1}}
    \Comment Gauss-Newton model
    \State $\iter[0]{\thess} = {\tt 0}$
    \State {\tt use\_second\_derivatives = false}
    \ElsIf {{\tt options\ct model == 2}}
    \Comment (Quasi-)Newton
    \State $\iter[0]{\thess} = ${\tt eval\_HF}${\tt (\iter[0]{\tx},W * \iter[0]{\tr})}$
    \State {\tt use\_second\_derivatives = true}
    \ElsIf {{\tt options\ct model == 3}}
    \Comment Hybrid algorithm
    \State {\tt hybrid\_tol = options\ct hybrid\_tol * }
    ${\tt (\| \iter[0]{\tg} \| / normF_0 )}$
    \State $\iter[0]{\thess} = {\tt 0}$
    \Comment Use first-order information only initially
    \State {\tt use\_second\_derivatives = false}
    \State ${\iter[temp]{\thess}} = {\tt 0}$
    \Comment Build up a Hessian in parallel when Gauss-Newton used
    \ElsIf{{\tt options\ct model == 4}}
    \Comment Use the Newton-Tensor model
    \State $\iter[0]{\thess} = ${\tt eval\_HF}${\tt (\iter[0]{\tx},W * \iter[0]{\tr})}$
    \If{$p \ne 0$ and $p \ne 2$}
    \State $\iter[0]{\thess}  = \iter[0]{\thess}  + \sigma \|\iter[0]{\tx}\|^{p-2}
    \left(I + \frac{{\iter[0]{\tx}}{\iter[0]{\tx}}^T}{\|\iter[0]{\tx}\|^2}\right)$
    \EndIf
    \State {\tt use\_second\_derivatives = true}
    \EndIf
    \For { $k = {\tt 0}, \dots, \text{\tt options\ct maxit}$}
      \While{ ${\tt success} \ne  1$ }
        \State ${\td}$ = \Call{{\tt calculate\_step}}{{$\tt
            \iter[k]{\tJ}, \iter[k]{\tr}, \iter[k]{\thess},\iter[k]{\tg},\Delta$}}
        \Comment Calculate a potential step $\td$
        \State $\iter[k+1]{\tx} = \iter[k]{\tx} + \td$
        \State $\iter[k+1]{\tr} = {\tt W * \text{\tt eval\_r}}(\iter[k]{\tx})$
        \State ${\tt normF_{k+1}}  = 0.5\|\iter[k+1]{\tr}\|^2 + \frac{\sigma}{p} \|\iter[k+1]{\tx}\|^p$
        \Comment Evaluate the residual at the new point
        \State $\rho = \tt (normF_{k+1} - normF_k)/(m_k(0) - m_k(\td)) $
        \Comment If model is good, $\rho$ should be close to one
          \If{ ${\tt \rho } >$ {\tt control\ct eta\_successful}}
          \State ${\tt success} = 1$
        \EndIf
        \State ${\tt \Delta = }${\tt update\_trust\_region\_radius}${\tt (\Delta,\rho)}$
      \EndWhile
      \State $\iter[k+1]{\tJ} = {\tt W * \text{\tt eval\_J}}(\iter[k+1]{\tx})$
      \Comment Evaluate the Jacobian at the new point
      \State $\iter[k+1]{\tg} = -{\iter[k+1]{\tJ}}^T\iter[k+1]{\tr}- \sigma \|\iter[k+1]{\tx}\|^{p-2}\iter[k+1]{\tx}$
      \If {{\tt \text{\tt options\ct model} == 3}}
        \If {{\tt use\_second\_derivatives}}
          \If { $\|\iter[k+1]{\tg}\| > \|\iter[k]{\tg} \| $}
          \State {\tt use\_second\_derivatives = false}
          \Comment Switch back to Gauss-Newton
          \State ${\iter[temp]{\thess}} = \iter[k]{\thess}$, $\iter[k]{\thess} = 0$
          \Comment Copy Hessian back to temp array
          \EndIf
        \Else
      \algstore{myalg}
  \end{algorithmic}

\end{algorithm}

\begin{algorithm}
  \ContinuedFloat
  \begin{algorithmic}
    \algrestore{myalg}

          \If { $ \tt \|\iter[k+1]{\tg}\| / normF_{k+1} < \text{\tt hybrid\_tol}$}
          \State {\tt hybrid\_count = hybrid\_count + 1}
          \Comment Update the number of steps in a row this has failed
          \If {{\tt hybrid\_count == options\ct hybrid\_count\_switch\_its}}
            \State {\tt use\_second\_derivatives = true}x
            \State {\tt hybrid\_count = 0}
            \State ${\iter[temp]{\thess}} = {\iter[k]{\thess}}$
            \Comment Copy approximate Hessian back
          \EndIf
          \EndIf
        \EndIf
      \If {{\tt ({\bf not} use\_second\_derivatives) {\bf and} ({\bf not} options\ct exact\_second\_derivatives) } }
      \State ${\iter[temp]{\thess}} = \Call{{\tt rank\_one\_update}}{\td ,\iter[k]{\tg},\iter[k+1]{\tg}, \iter[k+1]{\tr},\iter[k]{\tJ},\iter[temp]{\thess}}$
      \EndIf
    \EndIf

    \If { {\tt use\_second\_derivatives} }
      \If { {\tt options\ct exact\_second\_derivatives} }
        \State $\iter[k+1]{\thess} = {\tt \text{\tt eval\_HF}(\iter[0]{\tx},W\iter[0]{\tr})}$
      \Else
        \State ${\iter[k+1]{\thess}} = \Call{{\tt rank\_one\_update}}{\td ,\iter[k]{\tg},\iter[k+1]{\tg}, \iter[k+1]{\tr},\iter[k]{\tJ},\iter[k]{\thess}}$
      \EndIf
    \EndIf
    \If{$p \ne 0$ and $p \ne 2$}
    \State $\iter[k+1]{\thess}  = \iter[k+1]{\thess}  + \sigma \|\iter[k+1]{\tx}\|^{p-2}
    \left(I + \frac{{\iter[k+1]{\tx}}{\iter[k+1]{\tx}}^T}{\|\iter[k+1]{\tx}\|^2}\right)$
    \EndIf

    \If {$ \tt\|\iter[k+1]{\tr}\| < max(${\tt options\ct stop\_g\_absolute}, {\tt options\ct stop\_g\_relative}$* \|\iter[k]{\tr}\|)$}
    \State {\tt return}
    \Comment converged due to residual being small
    \ElsIf{$ \tt\frac{\|\iter[k+1]{\tg}\|}{\|\iter[k+1]{\tr}\|} < max( \text{\tt options\ct stop\_g\_absolute}, \text{\tt options\ct stop\_g\_relative} * \left(\frac{\|\iter[0]{\tg}\|}{\|\iter[0]{\tr}\|}\right))$}
    \State {\tt return}
    \Comment converged due to gradient being small
    \EndIf
    \EndFor
  \end{algorithmic}
\end{algorithm}

The subroutine \texttt{nlls\_iterate} performs one iteration of the algorithm
\texttt{nlls\_solve}, allowing the user greater control over stopping and/or monitoring the progress of the algorithm.

\subsection{Incorporating the regularization term}
\label{sec:reg_problem}

If a non-zero regularization term is required in (\ref{eq:nlls_problem}), then this is handled by transforming the problem internally into a least squares problem.  The
formulation used will depend on the value of $p$.

{\bf If $\bf p = 2$}, we solve a least squares problem with $n$ additional degrees of freedom.
The new function, $\widehat{\vr} : \mathbb{R}^{n}\rightarrow\mathbb{R}^{m+n}$, takes $\widehat{\vr}_i(\vx) = \vr_i(\vx)$, for $i = 1,\dots, m$, and $\widehat{\vr}_{m+j}(\vx) =
\sqrt{\sigma}[\vx]_j$ for $j = 1,\dots, n$, where $[\vx]_j$ denotes the $j$th component of $\vx$.  We therefore have that $\nabla \widehat{\vr}_{m+j}(\vx) = \sqrt{\sigma}\ve^j$ (where $[\ve^j]_i = \delta_{ij}$), and the second derivatives vanish.

{\bf If $\bf p \ne 2$}, then we solve a least squares problem
 with one additional degree of freedom.  In this case the new function, $\widehat{\vr} : \mathbb{R}^{n}\rightarrow\mathbb{R}^{m+1}$, again takes $\widehat{\vr}_i(\vx) = \vr_i(\vx)$, for $i = 1,\dots, m$, but now $\widehat{\vr}_{m+1}(\vx) = \left(\frac{2\sigma}{p}\right)^{\frac{1}{2}}\|\vx\|^{\frac{p}{2}}.$  We therefore have that
$\nabla \widehat{\vr}_{m+1}(\vx) = \left(\frac{2\sigma}{p}\right)^{\frac{1}{2}}\|\vx\|^{\frac{p-4}{2}}\vx^T$.
The second derivative is given by %on the value of $p$:
\(
\nabla^2\widehat{\vr}_{m+1} =
%\begin{cases}
%   \hspace{1.5cm}\sigma^{\frac{1}{2}} I & \text{if } p = 2 \\
   \left(\frac{2\sigma}{p}\right)^{\frac{1}{2}}\|\vx\|^{\frac{p-4}{2}}\left(I + \frac{\vx\vx^T}{\|\vx\|^2}\right).% & \text{otherwise}
%\end{cases}.
\)

Either problem can be solved implictly from the un-regularized problem by updating the relevant quantities in the algorithm, as shown in Algorithm~\ref{alg:nlls_solve}.

\subsection{The models}
\label{sec:model_description}

A vital component of the algorithm is the choice of model employed.  There are four choices
available, controlled by the parameter {\tt  nlls\_method\ct model}.

\begin{description}
  \item {\tt options\ct model = 1}: this implements the {\bf Gauss-Newton} model.  Here we replace $\vr(\iter[k]{\vx} + \vs)$ by its first-order Taylor approximation, $\vr(\iter{\vx}) + \iter{\vJ}\vs$. The model is therefore given by    \begin{equation}
m_k^{GN}(\vs) = \frac{1}{2} \|\vr(\iter{\vx}) + \iter{\vJ}\vs\|_\vW^2.
\label{eq:gauss-newton-model}
\end{equation}
\item {\tt options\ct model = 2}: this implements the {\bf Newton} model.
Here, instead of approximating the residual, $\vr(\cdot)$, we take as our model the second-order Taylor approximation of the function, $F(\iter[k+1]{\vx}).$  Namely, we use
\begin{equation}
  \label{eq:newton-model}
  m_k^{N}(\vs) = F(\iter{\vx}) + {\iter{\vg}}^T\vs + \frac{1}{2}\vs^T\left( {\iter{\vJ}}^T \vW \iter{\vJ} + \iter{\vH}\right) \vs,
\end{equation}
where $\iter{\vg} = {\iter{\vJ}}^T\vW \vr(\iter{\vx})$ and $\iter{\vH} = \sum_{i=1}^m\iter[i]{r}(\iter{\vx}) \vW \nabla^2 \iter[i]{r}(\iter{\vx}).$
Note that $m_k^{N}(\vs) = m_k^{GN}(\vs) + \frac{1}{2}\vs^T\iter{\vH} \vs$.

If the second derivatives of $\vr(\cdot)$ are not available
(i.e., {\tt options\ct exact\_second\_derivatives = false}),
then the method approximates the matrix $\iter{\vH}$ using the method of Dennis, Gay, and Welsch [4, Chapter 10];
see Algorithm~\ref{alg:rank_one_update}.

\item {\tt options\ct model = 3}: this implements a {\bf hybrid} model.
In practice the Gauss-Newton model tends to work well far away from the solution, whereas
Newton performs better once we are near to the minimum (particularly if the residual is
large at the solution).
This option will try to switch between these two models, picking the model that is most appropriate for the step.
In particular, we start using $m_k^{GN}(\cdot)$,
and switch to $m_k^{N}(\cdot)$ if $\|{\iter{\vg}}\|_2 \leq ${\tt options\ct hybrid\_tol}$\frac{1}{2}\|\vr(\iter{\vx})\|^2_\vW$ for more than {\tt options\ct hybrid\_switch\_its} iterations in a row. If, in subsequent iterations, we fail to get
a decrease in the function value, then the algorithm interprets this as being not sufficiently close to the solution, and thus switches back to using the Gauss-Newton model.

\item {\tt options\ct model = 4}: this implements a {\bf Newton-tensor} model.
This uses a second order Taylor approximation to the residual, namely
\[r_i(\iter{\vx} + \vs) \approx (\iter{\vt}(\vs))_i := r_i(\iter{\vx}) + (\iter{\vJ})_i\vs + \frac{1}{2}\vs^T B_{ik}\vs,\]
where $(\iter{\vJ})_i$ is the {\tt i}th row of $\iter{\vJ}$, and $B_{ik}$ is $\nabla^2 r_i(\iter{\vx})$.  We use this to define our model
\begin{equation}
  \label{eq:newton-tensor-model}
  m_k^{NT}(\vs) = \frac{1}{2}\|\vt_k(\vs)\|_\vW^2.
\end{equation}

\end{description}

\begin{algorithm}
\caption{{\tt rank\_one\_update}}
\label{alg:rank_one_update}
  \begin{algorithmic}
    \State {\bf function} $\iter[k+1]{\thess} = $ \Call{{\tt rank\_one\_update}}{$\td ,\iter[k]{\tg},\iter[k+1]{\tg}, \iter[k+1]{\tr},\iter[k]{\tJ},\iter[k]{\thess}$}
    \State $\ty = \iter[k]{\tg} - \iter[k+1]{\tg}$ \State
    $\widehat{\ty} = {\iter[k]{\tJ}}^T \iter[k+1]{\tr} -
    \iter[k+1]{\tg}$ \State $\widehat{\iter[k]{\thess}} = \min\left(
      1, \frac{|\td^T\widehat{\ty}|}{|\td^T\iter[k]{\thess}\td|}\right)
    \iter[k]{\thess}$ \State $\iter[k+1]{\thess} =
    \widehat{\iter[k]{\thess}} + \left(({\iter[k+1]{\widehat{\ty}}} -
      \iter[k]{\thess}\td )^T\td\right)/\ty^T\td$

  \end{algorithmic}
\end{algorithm}

\subsection{The subproblem solves}
\label{sec:subproblem solves}

The main algorithm (Algorithm \ref{alg:nlls_solve}) calls a number of subroutines.
The most vital is the subroutine {\tt calculate\_step}, which finds a step that
minimizes the model chosen, subject to a globalization strategy.  The algorithm
supports the use of two such strategies: using a trust-region, and regularization.
If Gauss-Newton, (quasi-)Newton, or a hybrid method is used
({\tt options\ct model = 1,2,3}), then the model function is quadratic, and
the methods available to solve the subproblem are described in
Sections \ref{sec:trust-region} and \ref{sec:regularization}.
If the Newton-Tensor model is selected ({\tt options\ct model = 4}), then this
model is not quadratic, and the methods available are described in Section~\ref{sec:newton_tensor_subproblem}.

Note that, when calculating the step, if the initial regularization parameter $\sigma$ in (\ref{eq:nlls_problem}) is
non-zero, then we must modify ${\iter[k]{\tJ}}^T\iter[k]{\tJ}$  to take into
account the Jacobian of the modified least squares problem being solved.  Practically, this amounts to making the change
\[
{\iter[k]{\tJ}}^T\iter[k]{\tJ} = {\iter[k]{\tJ}}^T\iter[k]{\tJ} +
 \begin{cases}
   \sigma I & \text{if }p = 2\\
   \frac{\sigma p}{2} \|\iter[k]{\vx}\|^{p-4}\iter[k]{\vx}{\iter[k]{\vx}}^T & \text{otherwise}
 \end{cases}.
\]

\subsubsection{The trust region method ({\tt options\ct type\_of\_method = 1})}
\label{sec:trust-region}

If {\tt options\ct type\_of\_method = 1}, then a trust-region method is used.  Such a method solves the subproblem (\ref{eq:tr_subproblem}), and we take as our next step
the minimum of the model within some radius of the current point.  The method used to solve
this is dependent on the control parameter {\tt options\ct nlls\_method}. The algorithms called for each of the options are listed below:
\begin{description}
\item {\tt options\ct nlls\_method = 1}: this approximates the solution to (\ref{eq:tr_subproblem}) by using Powell's dogleg method.  This takes as the step a linear combination of the Gauss-Newton step and the steepest descent step, and the method used is described in Algorithm \ref{alg:dogleg}.
\item {\tt options\ct nlls\_method = 2}: this solves the trust region subproblem using the trust region solver of  Adachi, Iwata, Nakatsukasa, and Takeda.  This reformulates the
problem (\ref{eq:tr_subproblem}) as a generalized eigenvalue problem, and solves that.  See
[1] for more details.
\item {\tt options\ct nlls\_method = 3}: this solves the trust region subproblem using
a variant of the More-Sorensen method.  In particular, we implement Algorithm 7.3.6
 in Trust Region Methods by Conn, Gould and Toint [2].
\item {\tt options\ct nlls\_method = 4}: this solves the trust region subproblem by first
converting the problem into the form
$$\min_\vp \vw^T \vp + \frac{1}{2} \vp^T \vD \vp \quad {\rm s.t.} \quad \|\vp\| \leq \Delta,$$
where $\vD$ is a diagonal matrix.  We do this by performing an eigen-decomposition of
the Hessian in the model.  Then, we call the {\sc Galahad} routine {\sc DTRS}; see
the {\sc Galahad} [3] documentation for further details.
\end{description}

\begin{algorithm}
\caption{dogleg}
\label{alg:dogleg}
  \begin{algorithmic}[1]
    \State {\bf function} \Call{{\tt dogleg}}{{$\tt
            \tJ, {\tr}, \thess, \tg,\Delta$}}
        \State $\alpha = \|\tg\|^2 / \|\tJ * \tg\|^2$
        \State $\td_{\rm sd} = \alpha \,\tg$
        \State Solve $\td_{\rm gn} = \arg \min_{\tx}\|\tJ \tx- \tr\|_2$
        \If {$\|\td_{\rm gn}\| \leq \Delta$}
        \State $\td = \td_{\rm gn}$
        \ElsIf {$\|\alpha \, \td_{\rm sd}\| \geq \Delta$}
        \State $\td = (\Delta / \|\td_{\rm sd}\|) \td_{\rm sd}$
        \Else
        \State $\td = \alpha \, \td_{\rm sd} + \beta\, (\td_{\rm gn} - \alpha \td_{\rm sd})$, where $\beta$ is chosen such that $\|\td\| = \Delta$
        \EndIf
  \end{algorithmic}
\end{algorithm}

\subsubsection{Regularization ({\tt options\ct type\_of\_method = 2})}
\label{sec:regularization}

If {\tt options\ct type\_of\_method = 2}, then the next step is taken to be the minimum
of the model with a regularization term added (\ref{eq:reg_subproblem}).  At present,
only one method of solving this subproblem is supported:

\begin{description}
\item {\tt options\ct nlls\_method = 4}: this solves the regularized subproblem by first
converting the problem into the form
$$\min_\vp \vw^T \vp + \frac{1}{2} \vp^T \vD \vp + \frac{1}{p}\|\vp\|_2^p,$$
where $\vD$ is a diagonal matrix.  We do this by performing an eigen-decomposition of
the Hessian in the model.  Then, we call the {\sc Galahad} routine {\sc DRQS}; see
the {\sc Galahad} [3] documentation for further details.
\end{description}

\subsubsection{Newton-Tensor subproblem}
\label{sec:newton_tensor_subproblem}

If {\tt options\ct model = 4}, then the non-quadratic Newton-Tensor model is used.  As such, none of the established subproblem solvers described in Section~\ref{sec:trust-region} or Section~\ref{sec:regularization} can be used.

If we use regularization (with $p=2$), then the subproblem we need to solve is of the form
\begin{equation}
\min_\vs \frac{1}{2}\sum_{i=1}^mW_{ii}{(\vt_k(\vs))_i}^2 + \frac{1}{2\Delta_k}\|\vs\|_2^2
\label{eq:reg_newton_tensor_subproblem}
\end{equation}
Note that (\ref{eq:reg_newton_tensor_subproblem}) is a sum-of-squares,
and as such can be solved by calling {\tt ral\_nlls} recursively.
We support two options:
\begin{description}
  \item {\tt options\ct inner\_method = 1}:
    if this option is selected, then {\tt nlls\_solve} is called to
    solve (\ref{eq:newton-tensor-model}) directly.  The current regularization parameter
    of the `outer' method is used as a base regularization in the `inner' method,
    so that the (quadratic) subproblem being solved in the `inner' call is of the form
    \[ \min_\vs \, m_k(\vs) + \frac{1}{2}\left(\frac{1}{\Delta_k} + \frac{1}{\delta_k}\right)\|\vs\|_B^2, \]
    where $m_k(\vs)$ is a quadratic model of (\ref{eq:newton-tensor-model}), $\Delta_k$ is the
    (fixed) regularization parameter of the outer iteration, and $\delta_k$ the regularization
    parameter of the inner iteration, which is free to be updated as required by the method.

  \item {\tt options\ct inner\_method = 2}: in this case we use {\tt ral\_nlls} to solve
    the regularized model (\ref{eq:reg_newton_tensor_subproblem}) directly.
    The number of parameters for this subproblem is $n+m$.  Specifically, we have a
    problem of the form
    \[
    \min_\vs \frac{1}{2} \|\widehat{\vr}(\vs)\|_\vW^2,
    \quad \text{where }
    (\widehat{\vr}(\vs))_i =
    \begin{cases}
      (\vt_k(\vs))_i &  1 \leq i \leq m \\
      \frac{1}{\sqrt{\Delta_k}}s_i& m+1 \leq i \leq n+m
    \end{cases}.
    \]
    This subproblem can then be solved using any of the methods described in
    Sections~\ref{sec:trust-region} or \ref{sec:regularization}.
\end{description}

\subsection{Accepting the step and updating the parameter}
\label{sec:step_accept}

Once a step has been suggested, we must decide whether or not to accept the step, and whether the trust region radius or regularization parameter, as appropriate, should grow, shrink, or remain the same.

These decisions are made with reference to a parameter, $\rho$, which measures the
ratio of the actual reduction in the model to the predicted reduction in the model.
If this is larger than {\tt options\ct eta\_successful}, then the is step accepted (see Line 28 of Algorithm~\ref{alg:nlls_solve}).

The value of $\Delta_k$ then needs to be updated, if appropriate.
The package supports two options: if
\begin{description}
\item  {\tt options\ct tr\_update\_strategy = 1:} in this case a step-function is used to decide whether or not to increase or decrease $\Delta_k$.
\item {\tt options\ct tr\_update\_strategy = 2}, then a continuous function is used to
  make the decision.
\end{description}
The method used is outlined in Algorithm~\ref{alg:update_tr}.

\begin{algorithm}
\caption{update\_trust\_region}
\label{alg:update_tr}
\begin{algorithmic}[1]
  \State {\bf function} $\Delta = $ \Call{{\tt update\_trust\_region\_radius}}{{$\Delta, \rho$}}
    \If {{\tt options\ct tr\_update\_strategy == 1}}
      \If {{$\tt \rho \leq \text{\tt options\ct eta\_success\_but\_reduce}$}}
      \State $\tt \Delta = \text{\tt options\ct radius\_reduce} * \Delta$
      \Comment reduce $\Delta$
      \ElsIf{{$\tt \rho \leq  \text{\tt options\ct eta\_very\_successful}$}}
      \State $\tt \Delta = \Delta$
      \Comment $\Delta$ stays unchanged
      \ElsIf{{$\tt \rho \leq \text{\tt options\ct eta\_too\_successful}$}}
      \State $\tt \Delta = \text{\tt options\ct radius\_increase} * \Delta$
      \Comment increase $\Delta$
      \ElsIf{{$\tt \rho > \text{\tt options\ct eta\_too\_successful}$}}
      \State $\tt \Delta = \Delta$
      \Comment too successful: accept step, but don't change $\Delta$
      \EndIf
    \ElsIf{{\tt options\ct tr\_update\_strategy == 2}}
    \State [on first call, set $\nu = 2.0$]
      \If{{$\tt \rho \geq \text{\tt options\ct eta\_too\_successful}$}}
        \State $\Delta = \Delta$
        \Comment $\Delta$ stays unchanged
      \ElsIf{{$\tt \rho > \text{\tt options\ct eta\_successful}$}}
        \State $\tt \Delta = \Delta * \min\left(\text{\tt options\ct radius\_increase},
          1 - \left( (\text{\tt options\ct radius\_increase} -1)*((1 - 2*\rho)^3)  \right)\right)$
        \State $\tt \nu = \text{\tt options\ct radius\_reduce}$
      \ElsIf{{$\tt \rho \leq \text{\tt options\ct eta\_successful}$}}
        \State $ \Delta = \nu * \Delta$
        \State $ \nu = 0.5 * \nu$
      \EndIf
    \EndIf
  \end{algorithmic}
\end{algorithm}

\hslreferences\\
$[1]$ Adachi, Satoru and Iwata, Satoru and Nakatsukasa, Yuji and Takeda, Akiko (2015).
Solving the trust region subproblem by a generalized eigenvalue problem.
Technical report, Mathematical Engineering, The University of Tokyo.\\
$[2]$ Conn, A. R., Gould, N. I., \& Toint, P. L. (2000). Trust region methods. SIAM.\\
$[3]$ Gould, N. I., Orban, D., \& Toint, P. L. (2003). GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization. ACM Transactions on Mathematical Software (TOMS), 29(4), 353-372.\\
$[4]$ Nocedal, J., \& Wright, S. (2006). Numerical optimization. Springer Science \& Business Media.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "nlls_fortran"
%%% End:

max_stars_repo_name: andpic/RALFit

max_issues_repo_name: andpic/RALFit

max_forks_repo_name: andpic/RALFit