Non-linear Optimisation
Non-linear Optimisation
Mathematical formulation
Optimisation aims to find the minimum (or equivilently the maximum) of some objective,
or loss function , given a set of parameters
We might also have a set of constraints, for example a parameter might be required to
be non-negative (e.g. a concentration or population number). These are often written as
a set of equality and inequality constraints
Or these might simply be defined as bounds in parameter space that restrict the
minimisation to a given domain
Useful terms
Modelling is the process of defining the objective function , the parameters of
interest , and the constraints. The algorithms for performing the minimisation
fall under the field of optimisation. Sub-fields of this are concerned with the
minimisation of discrete function, often called integer programming. Confusingly, it
is common to see the terms "optimisation" and "programming" used interchangeably, as the
latter term was coined before the 1940s, and does not refer to computer software
programming at all.
If the function is linear, then there are specific algorithms for this class of
problem that fall under the topic of linear programming, or linear optimisation. The
more general problem of a non-linear is termed non-linear programming, or
non-linear optimisation. If a set of equality and/or inequality constraints are needed
then algorithms that deal with these fall under the topic of constrained optimisation.
An important distinction when looking at optimisation problems is the notion of global
versus local optimisation. The latter finds a point in parameter space that
has a function value greater than the surrounding points, but might not
necessarily be the global minimum. These algorithms are often initialised to a point
that is near to the minima of interest. The more general problem of global optimisation
is significantly more difficult as it requires that the optimisation be robust to
finding and rejecting such local minima. For a function that is convex, then local and
global minimisation are the same, which is very advantagous since local minimisation
algorithms are often both faster and often have more guarentees of convergence. The
function is a convex function if its domain is a convex set, and for any
two points and :
The term convex programming is used to describe the case of contrained optimisation
where is convex, the equality constraints are linear and the inequality contraints
are concave.
Non-linear optimisation and Root-Finding
Non-linear optimisation is closely related to finding the roots, or zeros, of a
function. This can be seen easily by considering the fact that at each local minima or
maxima of the function the value of the gradient of is zero, i.e. .
Therefore finding a local minima or maxima of corresponds to finding the zeros of
the function .
Other reading
- Numerical optimization by Nocedal, Jorge; Wright, Stephen J., 1960-
- Bazaraa, Sherali, and Shetty, Nonlinear Optimization, 2/e, Wiley
- Griva, Nash, and Sofer, Linear and Nonlinear Optimization, 2/e, SIAM Press
- Luenberger, Linear and Nonlinear Programming, 3/e, Springer
- Bertsekas, Nonlinear Programming, Athena
- Ruszczynski, Nonlinear Optimization, Princeton University Press
- Broyden, C. G. (1972). "Quasi-Newton Methods". In Murray, W. (ed.). Numerical Methods for Unconstrained Optimization. London: Academic Press. pp. 87–106. ISBN 0-12-512250-0.