\part{Fundamentals}


\chapter{Optimization problems}

Mathematical optimization seeks to apply mathematics to real life problems to determine the most efficient allocation of 'resources' (whether that be physical resources, time, or any other abstraction of the term). The nature of mathematical optimization may differ depending on the type of problem; the subfield of linear programming (LP) draws extensively from convex analysis and linear algebra, however nonlinear integer programming would require a deeper understanding of combinatorics and number theory.

Mathematical optimization studies the solutions to 'optimization problems'; finding the most optimal element in some set according to some order. Even though the definition of an optimization problem can be stated by means of elementary set theory and order theory, the range of optimization problems that can be stated varies greatly, and the solution methods for different problems reach from practically all fields of mathematics.


Nevertheless, the fundamentals of mathematical optimization pays some homage to a range of definitions and concepts, most of which lie at the interplay of elementary set theory, order theory, and algebra.

Before one even considers the use of mathematics to solve optimization problems, they would have to resort to a framework to define their problem in a mathematical sense. We start by developing the tools that can describe various rules in which a resource may legally be allocated.


\begin{definition}
A \emph{dependent variable (DV)} $x$ is a variable representing some quantity that can be changed. It often represents an amount of some 'resource' available to us.
\end{definition}

We will often use a vector $\mathbf{x}$ to represent the vector with the dependent variables as entries.

Often we want to impose rules on which values dependent variables can have. For instance, perhaps $x_1$ should never be less than $x_2$.

\begin{definition}
The \emph{feasible region} $X$ is the set of all permissible combinations of values that the DVs may have. Elements of the feasible region are called \emph{feasible solutions}.
\end{definition}

The DVs essentially provide a way of quantifying the thing we seek to optimally distribute, and feasible regions

It's crucial to have some method to determine how optimal elements of the feasible region really are. This method is represented as a function, and its its minimum or maximum.

\begin{definition}
An \emph{objective function (OF)} $f : X \to Y$ is a function whose domain is restricted to the feasible region. This function determines a way to compare how 'desirable' different feasible solutions are.
\end{definition}


\begin{definition}
A \emph{goal function (GF)} $g : F \to \mathbb{R}$ is a function that maps OFs to the 'most desirable' element in its image. Commonly, these are either the $\min$ or $\max$ functions.
\end{definition}



\begin{definition}
An \emph{optimization problem} is a 3-tuple $(X,f,g)$ of a feasible region$X$, an objective function $f$ with $X$ as its domain, and a 'goal' set function $g$ that states how to determine the optimal solution from the objective function ($\min$ or $\max$).
Problems with the $\min$ goal function are minimization optimization problems, while those endowned with the $\max$ goal function are maximization optimization functions.
\end{definition}

We now define what constitutes a solution to an optimization problem.

\begin{definition}
	The \emph{optimal solution} of an optimization problem $(X,f,g)$ is the following represented by $z$.
	\[ z=g \{ f(x) : x \in X \} \]
\end{definition}

\begin{definition}
An \emph{optimal parameter} of an optimization problem $(X,f,g)$ is an element $x_0$ in the feasible region that optimizes the OF.
\[\mathbf{x}_0 \in X \text{ is an optimal parameter of }(X,f,g) \iff  f(\mathbf{x}_0)=g_{\mathbf{x}\in X} (f) \} \]
\end{definition}

Note that the optimal parameter and solution may not exist (i.e be undefined or unbounded; we will get to these soon), making someoptimization problems degenerate.

One can show a special relationship between the min and max goal functions that essentialy implies that the two types of optimization problems can trivially be converted from one to another.

\begin{theorem}[Min-Max equivalence]
Given a minimization optimization problem $(X,f,\min)$,the maximization problem $(X,-f,-\max)$ has the same optimal solution and optimal parameters.
\end{theorem}

This claims that minimization and maximization differs only by a sign. Because of this result, the majority of this book will discuss and present theory based on minimization optimization functions. 

Now let's discuss the rather 'dissapointing' types of optimization problems.

\begin{definition}[Infeasible optimization problem]
A minimization optimization problem is \emph{infeasible} iff its feasibility region is the null set. 
\[(X,f,g) \text{ is infeasible } \iff X=\emptyset\]
\end{definition}

It makes no sense to discuss how to execute an impossible task 'optimally'; the notion of infeasibility captures this.


\begin{definition}[Unbounded optimization problem]
An optimization problem is \emph{unbounded} iff for any element of the feasible region, one can always find a more optimal element in the feasible region.
	\[(X,f,\leq) \text{ is unbounded} \iff \forall x \in X (\exists y \in X [ f(y) < f(x)] )\]
	%\[(X,f,\min) \text{ is unbounded} \iff \forall x \in X (\exists y \in X [ f(y) < f(x)] )\]
	%\[(X,f,\max) \text{ is unbounded} \iff \forall x \in X (\exists y \in X [ f(y) > f(x)] )\]
\end{definition}

It makes no sense to discuss how to execute an impossible task 'optimally'; the notion of infeasibility captures this.



The notion of an optimization problem pretty much defines the scope of this branch of mathematics; if some dilemma is reducible to an optimization problem, the theory of this field may prove useful.

Granted, this definition of an optimization problem is quite general and indeed encompasses many trivial problems, impossible problems, and even problems defined in such a way thatone can do no better than a brute force algorithm on its feasible region.

Here is a basic optimization problem to build some inuition with the mathematical notation.

\begin{example}
John is 185cm tall and Jane is 167cm tall. A pair of Yeezys add 3cm to one's height and a pair or Air Forces add 5cm. Which combination of person and pair of shoes is closest to 176cm, given that shoes must be worn?
	\[f(\mathbf{x})=|176-x_1+x_2|\]
	\[X = \{ \begin{bmatrix}185\\3\end{bmatrix},\begin{bmatrix}185\\5\end{bmatrix},\begin{bmatrix}167\\3\end{bmatrix},\begin{bmatrix}167\\5\end{bmatrix} \}\]
		\[z=\min_{\mathbf{x}\in X}(f)=4\]
		\[\mathbf{x}_0 = \mathrm{argmin}_{\mathbf{x}\in X}(f)=\begin{bmatrix}167\\5\end{bmatrix}\]
\end{example}

This problem in itself is kind of dull (there could be worse problems, imagine a problem with only one element in its feasible region!), however this notation can also express optimization problems in much more complicated contexts.


\chapter{Constraints}

Let's consider the following example.

\begin{example}
Enter a God awful example here with 3 inequalities
\end{example}

This example does something pretty interesting; it defines its feasible region with respect to 3 different inequalities which all have to be satisfied, or in the fancy language of set theory and mathematical logic, it defines the feasible region by using a conjunction of predicates in the setbuilder logic.

\begin{definition}
A \emph{constraint} is some condition (technically called a 'predicate') on the dependent variables. These can be used to define types of feasible regions so that all feasible solutions must satisfy each constraint.
\end{definition}


One can take the notion of a constraint to create extremely bizzare (and even ill-posed) optimization problems, however inequalities and equalities are by far the most common type of constraint; the use of minimum and maximum functions as well as the fact that inequalities are widely studied constraints is precisely why order theory has so much to bestow upon mathematical optimization.