Introduction to optimisation topics
« Previous | Up ↑ | Next »
An optimisation problem is usually defined as a function to minimise:
\[\min_x f(x)\]
- $x$ is a set of unknown variables, or decision variables;
- variables are defined on a given domain, e.g. $\mathbb{R}$, $\mathbb{N}$, or $\{0,…4\}$;
- $f$ is an objective function, or sometimes evaluation function.
Modelling a problem consists in identifying decision variables and an objective function.
Example:
Find the optimal angle to fire a cannon to maximize the distance it travels down range.
Solution (click to unfold)
- Define the referential, sum the forces applying to a cannon ball of mass $m$, integrate, etc.
$$y = -\frac{g}{2 v_0^2\, \cos^2 \alpha} x^2 + \tan \alpha\, x$$
- The range of the cannonball writes:
$$ d = \frac{v_0^2\, \sin (2\alpha)}{g} $$
- The sine function is continuous and differentiable:
$$\alpha_{max} = 45^{\circ}$$
Constraint optimisation adds up to this definition with a slight addition:
\[\min_x f(x) \textsf{ with } c(x)\]
- $c$ is a constraint, i.e. a function from the domain of $x$ with values taken among $\left\{\top, \bot\right\}$.
In case of non-constrained optimisation, we have \(\forall x: c(x)\)
There is no general method to find the optimum to such problem, however there are general methods to solve problems fitting a given paradigm (see the cannon ball problem, that was easy, right?)
Scope of the course
During this course, we will go through various paradigms, fitting different characteristics of the problems we analyse.
Depending on how we choose to model problems (discrete domains, differentiable functions, linear functions, black box models, etc.), we will be able to choose which method is the best fit.
The main characteristic of each of these optimisation paradigms is:
- genericity: methods should be applicable to wide range of problems;
- efficiency: methods should converge to the solution with reasonable resources (basically, a personal laptop);
- robustness: methods should be stable even with noise in data, or with floating point arithmetics.
During the course of this class, we will in particular look through:
- differentiable functions;
- global and local optimisation;
- linear functions;
- discrete optimisation: values in domains such as $\mathbb{Z}$ or $\{0, 1\}$;
- satisfaction problem when $f$ is constant but $c$ is not;
- stochastic methods when two executions of the same problem may not return the same solution.
« Previous | Up ↑ | Next »