About preconditioning

Contents

    1 Preconditioner
           Example
           When do you need preconditioner
           Preconditioners supported by ALGLIB
    2 Downloads section

Preconditioner

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.

Example

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.

When do you need preconditioner

You will need preconditioner if:

Sometimes preconditioner just accelerates convergence, but in some difficult cases it is impossible to solve problem without good preconditioning.

Preconditioners supported by ALGLIB

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.

Download ALGLIB for C++ / C# / ...

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:

ALGLIB 3.12.0 for C++

C++ library.
Delivered with sources.
Monolithic design.
Extreme portability.
Editions:   FREE   COMMERCIAL

ALGLIB 3.12.0 for C#

C# library with native kernels.
Delivered with sources.
VB.NET and IronPython wrappers.
Extreme portability.
Editions:   FREE   COMMERCIAL

ALGLIB 3.12.0 for Delphi

Delphi wrapper around C core.
Delivered as precompiled binary.
Compatible with FreePascal.
Editions:   FREE   COMMERCIAL

ALGLIB 3.12.0 for CPython

CPython wrapper around C core.
Delivered as precompiled binary.
Editions:   FREE   COMMERCIAL