1 Preconditioner
Example
When do you need preconditioner
Preconditioners supported by ALGLIB
2 Downloads section
Preconditioning is a transformation which transforms optimization problem into a form more suitable to solution. Usually this transformation takes form of the linear change of the variables - multiplication by the preconditioner matrix. The most simple form of the preconditioning is a scaling of the variables (diagonal preconditioner) with carefully chosen coefficients.
Below you can find an example of the preconditioner accelerating convergence. Original function is a narrow valley and optimizer bounces off the walls of the valley while approaching to the solution. Finally, it arrives to the isoline f=1, but it needs 4 iterations to reach it. After the scaling curvature of the function became more simple and we need only one step in order to move far below f=1.
In the example above we used very basic optimization algorithm - steepest descent method. You can understand it by noticing that steps are always made in the direction of the antigradient, without accumulating information about curvature of the function. Both L-BFGS and CG would have started to turn search direction toward extremum right after the first iteration. But it does not mean that good optimization algorithm does not need preconditioner. Good preconditioner can significantly (up to several times) speed up optimization progress.
You will need preconditioner if:
Sometimes preconditioner just accelerates convergence, but in some difficult cases it is impossible to solve problem without good preconditioning.
ALGLIB package supports several preconditioners:
Different optimizer support different types of preconditioners, but first three are supported by all ALGLIB optimizers.
This article is licensed for personal use only.
ALGLIB Project offers you two editions of ALGLIB:
ALGLIB Free Edition:
delivered for free
offers full set of numerical functionality
extensive algorithmic optimizations
no low level optimizations
non-commercial license
ALGLIB Commercial Edition:
flexible pricing
offers full set of numerical functionality
extensive algorithmic optimizations
high performance (SMP, SIMD)
commercial license with support plan
Links to download sections for Free and Commercial editions can be found below: