What is optimization?

What is optimization?
Optimization refers to the process of finding the "best" values for a set of parameters to minimize or maximize an objective. For example, getting to work in time is an optimization problem with parameters of "when to leave, which buss to take, what to wear, with what speed to walk, etc." and the objective is to "arrive at work in time, not later, nor earlier". This can be surprisingly complex, especially in the real-world problems.



Constraints, objectives, and dynamic environment: 
When you leave home, you do know that you need to take bus number 412, and not 420, 440, or any other numbers to go to work. If it is rainy, then you need to dress appropriately, and so on. These are not really parameters, but they impose limitations on the parameters, hence called constraints. For another example, let's say you are running a mine operation and you know you have 20 trucks available per day, each with the capacity of 200 tons. These are your constraints, you cannot optimize your operation and get to a solution that needs 21 trucks, such solution is an "infeasible" solution. Constraints make the optimization problem "smaller" regarding feasibility. This, however, may not always be beneficial for reasons that require more in-depth discussions.

It is also not always the case that you need to optimize one objective, but you may actually need to optimize multiple, potentially conflicting, objectives. For example, assume that a food company wants to sell its products. Of course, they would like to maximize their margin, but there are other objectives such as keeping the customers happy to make sure they will come back. For example, if you're going to drive to some place, the faster you go, the less safe you are. If you go very very slow, then you will be very safe, but you will arrive late. So, safety and driving speeds, if they are objectives of a hypothetical problem, are quite conflicting.


Finally, the real-world is full of variabilities. Either it is unplanned maintenance on some equipment in the mine or sudden start of hail, the optimized schedule is always impossible to follow to the full. This adds another level of sophistication to the optimization in real-world. This variability may impact objectives (e.g., some stupid driver hits you, although you were driving very slowly) or constraints (e.g., number of available trucks for today is 10 rather than 20 as some needed maintenance because of yesterday's heavy snow).


Importance of the model:

When you face an equation that formulates a minimization or maximum problem, everything is clear, you can immediately hire a mathematician to find a tool to solve the problem. However, arriving at that equation from the first place is not easy. Consider for example a mine owner with many trucks, different roads they may take, different places they may dump their material or load it. Different schedules that might be optimized for drivers of the trucks and all public holidays and unscheduled leaves and unseen advert weather, all of which define one optimization problem: maximize the revenue. It is thus essential to understand how this problem is modeled as, finally, it is the model that is optimized. Hence, the accuracy of the model is the bottleneck for the efficiency of the final solution. Think about how tiny little simplifications in the model can end up to massive variations between the optimized solution for the model and the optimum solution for the real problem.

Theoretical discussion:
An optimization problem includes a set of variables, objective functions, constraints, and configurations. Adding the dynamic environment (changes in constraints and objective during the time) also need to be considered. Accordingly, an optimization problem in a generic form is defined by:

$$\forall t>0 \text{ Find }x\in {\mathcal{F}}_t \subseteq S \subseteq \mathbb{R}^d \text{ such that } \forall y\in \mathcal{F}_t, ~ C\left(f_t\left(x\right),f_t\left(y\right)\right) \text{ is true}$$

where \(t\) is time, \({\mathcal{F}}_t\) is the feasible space defined by equalities and inequalities (constraints, see below), \(S\) is a \(d\) dimensional rectangle in \(\mathbb{R}^d\) such that \(l_j\le x_j\le u_j\), \(j=\{1,{\dots},d\}\) (\(l_{j}\) and \(u_{j}\) are the lower and upper bounds of the \(j^{th}\) variable), \(f_t\left(x\right):\mathrm{S}\to \mathbb{R}^p\) is the objective function at the time \(t\) (\(p\) is the number of objectives), and \(C(f(a), f(b))\) is a comparison operator to compare two solutions based on their objective functions (see below). Note that, it is not always the case that $$ S \in \mathbb{R}^d $$ (this is called a contious space optimization problem). Some optimization problems require discrete values in their variables (so-called discrete optimization problems), where the values of the variables might not be ordered.

The notation \(f^i_t\left(x\right)\) refers to the value of the \(i^{th}\) objective at the point \(x\) at time \(t\). The feasible space \( \mathcal{F}_t \) is defined as: for any \(t_0\), \(x\) belongs to \({\mathcal{F}}_{t_0}\) if and only if

• \(x\mathrm{\in }\mathrm{S}\) and
• \(g_{i,t_0}\left(x\right)\le 0,\ for\ i=1\ to\ q\) and
• \(g_{i,t_0}\left(x\right)\mathrm{=0,\ }for\mathrm{\ }i\mathrm{=}q\mathrm{+1\ }to\mathrm{\ }m\)

where constraints \(g_{i,t_0}\left(x\right)\mathrm{:\ }\mathbb{R}^d\mathrm{\to }\mathbb{R}\) for all i and \(t{}_{0}\). Also, the operator \(C(a, b)\) is defined as:

$$
C\left(f\mathrm{(}a\mathrm{),}f\left(b\right)\right)\mathrm{=}\left\{ \begin{array}{ll}
true & if~ a ~ dominates ~ b \\
false & if~ b ~ dominates ~ a \\
equal & if ~ \forall i \in\left\{\mathrm{1,\dots ,}p\right\}\mathrm{\ }f^i\left(a\right)\mathrm{=}f^i\left(b\right) \\
null&if\mathrm{\ }not\mathrm{\ }a\mathrm{\ }nor\mathrm{\ }b\mathrm{\ }dominate\mathrm{\ }each\mathrm{\ }other \end{array}
\right.\mathrm{\ }
$$

where \(a\) dominates \(b\) iff \(\mathrm{\forall }i\mathrm{\in }\left\{\mathrm{1,\dots ,}p\right\}\mathrm{\ }f^i\left(a\right)\mathrm{\le }f^i\left(b\right)\) and \(\mathrm{\exists }i\mathrm{\in }\left\{\mathrm{1,\dots ,}p\right\}\mathrm{\ }f^i\left(a\right)\mathrm{<}f^i\left(b\right)\).


Several categories of problems appear according to the definition of OP:

• Unconstrained/constrained OP: if \(q=m=0\). In this case, \({\mathcal{F}}_t\) is equal to \(S\) for all \(t\). If \(m>q>0\) then the problem is called a constrained OP (\({\mathcal{F}}_t\) is a subspace of \(S\)), 
• Single/multi objective OP: if \(p=1\), the problem is called a single objective OP, otherwise it is called a multi objective OP, 
• Objectives dynamic/static OP: if \(\forall x\in S\ \forall t_0,t_1\ C\left(f_{t_0}\left(x\right),f_{t_1}\left(x\right)\right)is\ equal\) then the problem is called an objective static OP, otherwise it is called an objective dynamic OP
• Constraints dynamic/static OP: if \(\mathrm{\forall }i\mathrm{\ }\mathrm{\forall }x\mathrm{\in }S\mathrm{\ }\mathrm{\forall }t_0,t_{\mathrm{1}}\mathrm{\ }g_{i,t_0}\left(x\right)\mathrm{=}g_{i,t_{\mathrm{1}}}\left(x\right)\) then the problem is called constraint static, otherwise it is called constraints dynamic.

In multiobjective OP, Because of the presence of more than one objective, the term "best solution" losses its meaning. The reason is that a solution may be better than another based on one objective while worse than that based on another objective. However, space (set of solutions) is partially-ordered. Hence, there is "the best set of solutions" rather than the best solution. The best set of solutions forms a so-called Pareto front, the set of all solutions that are better than other solutions in at least one objective while they are not worse than them in other objectives.

Problem landscape and  search space:
The variables of the optimization problem form different dimensions. Hence, the solutions of an optimization problem can be considered as points in the "space" of the problem, each solution has the same number of dimensions as of the number of variables. The space of the problem is called the search space, where an algorithm search for the optimum. The problem landscape then includes all points in the search space, paired with their objective value.

The landscape of the Griewank function, a standard benchmark optimization problem

Local optima:
A local optimum of an optimization problem is a point that is better than all other points in its "neighborhood". In a continuous space optimization problem (the variables are continuous values), this can be measured by gradient, hence, a local optimum of an optimization problem with continuous-space variables is a point for which the gradient is zero. The best local optimum among all local optima is called the "global optimum". Glocal optimum might not be unique, as of local optimum might not. Algorithms that seek a set of optima (local or global) are called "niching algorithms" (methods that search for a set of high-quality solutions rather than a single very high-quality solution).

Famous types:
Perhaps the most famous type of an optimization problem is the continuous unconstrained space single objective optimization problems where the objective is convex. This means that there is only one local optimum for the optimization problem while that point is also the global optimum. If the objective function is linear then it is convex for sure. Under some conditions, quadratic formulations may also be convex. Convex optimization problems can be solved to their optimality using convex optimization algorithms that minimize the gradient (or higher-order derivatives) of the objective of the optimization function. The assumption here is that the formulation for the optimization problem has been given. See Evolutionary Algorithms.

By R. Bonyadi