\chapter{Introduction}

Many of the recent advances in modern sciences have been possible due to the improvements made in computational and optimisation theory developed over the course of the last decades. Various fields ranging from electrical engineering and mechanics, to economics and molecular modelling, have been able to take advantage of the latest developments in the sphere of mathematical optimisation. Mostly, this area provides mechanisms through which the optimal solution to a problem, also known as optimum, is produced.
\\

Since very ancient times, people have been developing models and theories to deal with various optimisations problems in order to achieve the best possible results for specific tasks in everyday life. While interesting in theory, those ideas had very little practical use due to the daunting amount of computational effort required. It was not until the advent of the computer that those early thoughts have been resurrected and resulted in what is now regarded as a growing branch of applied mathematics.
\\

On the other hand, whilst computers have evolved rapidly over the last years and are able to cope with an enormous amount of computation, the problem of precision, that is, accurate calculation, is still one of great significance even today. The issue arises from the floating-point representation widely available in today's computers which is known to have limited precision. However, certain scientific and engineering applications cannot tolerate the presence of any such rounding errors, as these may lead to catastrophic events. For example, in computational geometry we may need to deal with infinite amount of precision in order to accurately track the position of objects and points in space. This is known as an emerging trend in exact computation, explained further in this work.

\section{Motivation}

In this context of approximation and computability, differential equations, introduced in the 17th century by Newton and Leibniz, play a central role in modern mathematics and have countless applications in almost all branches of contemporary science. Several numerical approaches for computing the solutions to differential equations have been developed, including the well-known Euler and Runge-Kutta methods. These have been shown, however, to suffer from a great loss of precision as their error estimation is too conservative to be of any practical use \cite{ref1}.
\\

One classical problem is the famous \textit{initial-value problem}, which states that, given an initial condition and an ordinary/partial differential equation that models some evolution of a system, we can determine the unknown function describing the underlying process. For such problems, a novel technique for computing the unique solution up to any desired accuracy has been proposed in \cite{ref1} (such a solution is guaranteed to exist under certain assumptions). The basic idea is that, at each stage of the computation, one can obtain two continuous maps which provide upper and lower bounds for the solution, essentially giving the precise error. \\

A related problem to the one described above -- and formulated again in \cite{ref1} and \cite{ref2} --, concerns the idea of \textit{consistency} of two given maps subject to some constraints and will make most of the subject of the present work. A pair of functions $(f, g)$, representing function and derivative information, respectively, is said to be \textit{consistent} if one can find a third map $h$ which is approximated by the first element of the pair and whose derivative information is approximated by the second component of the pair. \\

Furthermore, assuming that $f$ is defined by lower and upper constraints on its value and $g$ is restricted to lie within rectangles (or hyper-rectangles, if referring to higher dimensional spaces), then the property of consistency is \textit{decidable} upon solving a finite set of inequalities which represent the constraints of a linear programming problem. Finally, if such a map $h$ exists, then we can construct the minimal and maximal piecewise linear surfaces which are consistent with the information from both $f$ and $g$.

\section{Objectives}

This discussion brings us to the aim of this project, which is twofold: 

\begin{itemize}
	\item Firstly, to implement the linear programming test that decides consistency when the function approximation is interval-valued and the gradient constraints lie within hyper-rectangles, for a certain partitioning of an $n$-dimensional domain. Also, in case the test indicates consistency, the task is to determine the global bounding surfaces;
	\item Secondly, to study a more general setting in which the derivative constraints are considered to lie within convex polyhedra, rather than hyper-rectangles, which is a more challenging problem.
\end{itemize}

\section{Contributions}

As a project which required both practical implementation and deep theoretical study in the field of multi-variable differentiable calculus, we made the following contributions:

\begin{itemize}
	\item \textbf{Linear Programming Algorithms for Determining the Least and Greatest Piecewise-Linear Maps in the Rectangular Case} \\
	We extended the linear programming test presented in \cite{ref2}, which can decide consistency for rectangular derivative constraints in an arbitrary dimension $n\ge 2$, to also account for the explicit construction of the minimal and maximal piecewise-linear surfaces. We also provide a simple analytical proof of the result.
	\item \textbf{Framework for Deciding Consistency in the Rectangular Case Using Linear Programming}\\
	We implemented a general framework to check consistency of function and rectangular derivative information in an arbitrary $n$-dimensional domain, $n\ge 2$, by using the linear programming test from \cite{ref2}. Whenever the test indicates consistency, we also determine the least and greatest surfaces by means of the above linear programming algorithms. We also created a simple GUI to allow for the visualisation of the 3D piecewise linear surfaces in the case of a two-dimensional domain.
	\item \textbf{Decidability of Consistency for a Two-Dimensional Triangle with Convex Derivative Constraints} \\
	We also develop a simple algorithm for deciding consistency in the particular instance when the domain is given by a two-dimensional triangle in which the function information is also interval-valued, but the derivative constraints lie within a convex polygon, rather than a simple rectangle.  
	\end{itemize}
	


