Main help page | OVi
Tutorial | Optimization Methods | Mathematical
Expressions
Visualization | The
Ovi User Interface
Optimization methods
The basic idea of optimization is to seek the best (lowest) possible solution.
For finding the minimum of a general objective function we need optimization
methods of different level. For one-dimensional functions we need to find
an interval where the function is unimodal. This implies that the function
has one and only one minimum point in the interval. So-called line search
methods then find that minimum point.
For multi-dimensional functions a search direction is first determined
and then the line search methods are needed to find an appropriate step-size
(to be taken into the search direction).
In constrained optimization methods, the feasibility of the solutions
have to be quaranteed, for example, by penalizing techniques.
All the methods will find better and better values during the iteration
prosess. Therefore we know that the new point is nearer to the optimal
point than the earlier point.
All the methods have a final accuracy, called the
epsilon.
Current methods
All the methods are from Optimointi-lecture note by Kaisa Miettinen
unless otherwise stated.
Unimodal bracketing
-
Minimum Bracketing
From Numerical Recipes pp. 400.
-
Stepwise Search
The method is usually used with the Quadratic Interpolation
but it also works with other methods. There is one really bad disadvantage
in this method: while it iterates, it looks for the minimum bracketed area
only from the direction of the positive x-axis (related to the starting
point.) So when you are using this method, be very careful.
Line Search
-
Quadratic Interpolation
The basic idea of this method is to try to fit a parabola between three
points. These three points are named a, b and c in the Statistic
window these three points are named a, b and c. Then look for the minimum
point of this parabola (that is to be the fourth point) and pick up three
best points of those four. Next fit a new parabola to go through the points
and so on. Usually this is the best method used.
-
Golden Section
Golden Section method is similar to the Dichotomous
Search, but instead of using the middle points, it calculates a new
point using a golden section rule. It uses less calculations than the Dichotomous
Search.
-
Dichotomous Search
This is a very basic method. The idea is to divide the currect bracketed
line to two parts of equal size. Then consider two points near the middle
point (with the distance of epsilon) and calculate which one's function
value is smaller. New end points will be chosen so that the smaller value
is between those points, i.e. the other endpoint is one of the previous
endpoints and the other end point is one of the middle points (The one
with the greater value).
-
Brent
Multi-Dimensional
-
Univariate Search
This is a basic method for multidimensional optimization. The idea
of this method is to optimize one variable at the time. Therefore the search
directions will be the same as the coordinate axes. The convergence is
quite slow and sometimes it cannot find the optimum.
-
Method of Hooke and Jeeves
This is similar to the Univariate Search,
but in addition to optimizing one variable at the time, a pattern search
phase is used. The basic idea of pattern search is to take the difference
of the univariate directions as a new search direction and to use it to
find a new point.
-
Method of Powell
This is one of the best direct pattern search methods. The main difference
to the method of Hooke and Jeeves is that one
direction of the coordinate axis is replaced by the direction of the pattern
search phase.
-
Steepest Descent Method (Gradient Method)
This is the simplest method using the derivatives, therefore it is
sometimes called the Gradient method. The minimum point will always be
found from the opposite direction of the gradient. Convergence is quite
slow (linear), but it is global.
-
Method of Newton
This method is based on the use of the Hessian and its inverse. The
Newton method has quadratic convergence, so the optimum will be found faster
than by using the Steepest Descent method, for
example. However, the convergence is local.
-
Quasi-Newton Method
There are many Quasi-Newton methods among which we have chosen two.
The methods are based on the Newton method.
The idea of the methods is to approximate the Hessian or its inverse by
a matrix which is easier (and faster) to calculate.
Currently there are two different approximations. One is called Davidson-Fletcher-Powell
(DFP) and the other Broyden-Fletcher-Goldfarb-Shanno (BFGS). DFP approximates
the inverse of the Hessian (secant rule) when BFGS approximates the Hessian
(inverse secant rule). In DFP, the updating of the matrix is easier to
do than in BFGS, where the truncation errors are less critical.
-
Conjugate Gradient Method
Conjugate Gradient methods have originally been developed to solve
linear algebraic equations. Nowadays, they are also used in unconstrained
optimization. These methods are not as fast as Quasi-Newton
methods, but they demand less memory to operate properly. Therefore they
are important when solving large-scale problems. When solving smaller problems
Quasi-Newton methods are normally faster.
Conjugate Gradient methods are based on conjugate search directions
and the spirit of the Steepest Descent method.
The convergence is faster because the old directions are used as a part
of a new direction.
The system contains the conjugate gradient method of Fletcher and Reeves.
Methods for constrained problems
When using the following methods, the constraints forming the feasible
region have to be given.
-
Exterior Penalty Function Method
This method will seek the minimum by starting from 'outside' of the
feasible region. The constraints will be added to the objective function
with a penalty parameter. When the constraints are violated, a penalty
term will be activated. Both equalities and inequalities are allowed in
constraints when using this method.
The penalty parameter plays a very important role in this method. The
penalty parameter must be positive and its increment multiplier must be
greater than 1.
-
Interior Penalty Function Method
This method is similar to the Exterior Penalty Function
Method, but instead of starting from outside, the process starts from
inside the feasible region. Only inequalities are allowed in the constraints
when using this method.
The penalty parameter must be positive and its decrement multiplier
must be between 0 and 1.
-
Augmented Lagrangian Method
Augmented Lagrangian function contains the objective function, weighted
constraint functions and some quadratic penalty terms. During the iteration
prosess, the penalty parameters are approximated (as well as in the penalty
functions). Only equalities in constraints are allowed when using this
method.
The penalty parameter has to be positive.
The Stopping Rules
All the methods have some kind of rule to stop the iteration with the tolerance
of epsilon. This rule is called an epsilon. Basically the epsilon is the
distance between two points, i.e, between current point and previous point.
Line search methods use epsilon as a distance between two points.
Multidimensional methods calculate a norm of the last two points. Methods
using gradient calculate a norm from the gradient.