Interior point method

The interior point method is one of the two most often used linear programming algorithms (the other one is the simplex method, which is also included in ALGLIB).

This article provides a high-level overview of the ALGLIB implementation of the interior point method. It discusses questions like the algorithm's strong and weak sides and its stability and performance properties. The ALGLIB linear programming API is described in this separate article.

The interior point method for linear programming

Algorithm

The interior point method converts a linear programming problem (a constrained one) to an unconstrained optimization problem. The idea is to incorporate equality/inequality constraints into the target function by means of adding a so-called barrier term. The barrier function increases to infinity as its argument approaches the boundary of the feasible set - as a result, iteration is forced to stay in the internals of the feasible region.

If one carefully decreases barrier width and solves resulting unconstrained optimization subproblems with Newton's method, the interior point method can converge in 10-30 iterations (independently from the problem dimensionality).

On one hand, Newton's method is usually associated with high iteration cost due to necessity of the matrix factorization step. On the other hand, most linear optimization problems are sparse - thus, one may greatly benefit from having well optimized sparse symmetric factorization codes. The net result is that the interior point method is quite competitive with the simplex method and often outperforms it.

Comparison with the simplex method

The simplex method is, in some sense, dual to the interior point method:

• The interior point method converges in 10-30 iterations, but the iteration cost is very high. The simplex method has a very low iteration cost, but it needs about O(N+M) iterations to converge.
• The interior point method, like other barrier methods, returns points that approach bounds from the interior of the feasible region. The simplex method returns solutions that 'stick to bounds', i.e., it prefers points located exactly at the boundary of the feasible set. As result, sometimes the simplex method and the interior point method return slightly different solutions (that still have same target function value).
• Finally, the interior point method is fairly easy to accelerate - the overall algorithm structure is very simple, with most time being spent in sparse Cholesky/LDLT factorization. Contrary to that, the simplex method is a very complex algorithm with data access patterns that are hard to optimize.

Performance aspects

In this section, we review various factors that influence interior point method performance.

Task properties

Sparse matrix factorization is the most time-consuming part of the interior point method - on large-scale problems, it takes more than 99% of the running time. Thus, algorithm performance mostly depends on the performance of the underlying sparse linear algebra kernels and the sparsity pattern of the constraint matrix A.

Roughly speaking, increasing the fill factor of A by 2x results in an at least 4x increase in the running time. This formula is just a crude approximation and ignores the fact that different sparsity patterns result in different amounts of fill-in. The worst-case running time (A is dense or produces too much fill-in during factorization) is proportional to min(MN²,NM²).

C++, C#, SIMD, and parallelism

Interior point method running time also depends on the specific ALGLIB computational core chosen:

• native computational core, which is written in C and is available from C++, C#, Python, and Delphi
• SIMD-capable .NET computational core, which requires .NET 5 or higher and is available from C#
• managed .NET computational core, which is compatible with any .NET framework present and is available from C#, VB.NET, and IronPython

The native core (can be used from C++, C#, Python and Delphi) is the fastest one. It is written in C and it uses highly optimized SIMD-capable sparse linear algebra kernels. As result, working with native computational core is preferable. If you use ALGLIB for C++, you are already on the winning side. C# users may find it beneficial to use a C# wrapper around native core (available in the commercial edition).

The SIMD-capable .NET computational core utilizes hardware intrinsics (SIMD intrinsics) introduced in the recent releases of .NET Framework. It provides performance comparable to that of the native SIMD kernels, albeit somewhat slower because it is still C#. It is also a pure C# implementation, i.e., you do not have to deliver native binaries with your app. It is the second-best option for C# users, and it is available in both the commercial and free editions of ALGLIB.

Finally, there is a fully managed .NET computational core, which is available from C#, VB.NET, and IronPython. This core is the most portable .NET implementation of ALGLIB: it does not use unsafe code and it works with any .NET framework released since .NET Framework 2.0. The only downside is that it is much slower than the previous two options.

More on performance

As we mentioned above, the interior point method spends most of its running time in sparse LDLT factorization. Sparse direct methods are harder to accelerate with SIMD/SMP than their dense counterparts. However, something can be done - in particular, supernodal LDLT, used by the interior point method, has SIMD and SMP potential.

We discussed some aspects of interior point method performance in the subsection above. However, every new release of ALGLIB adds performance-related improvements, so the situation is always changing. We refer you to this article on supernodal LDLT factorization for up-to-date information.

Working with the interior point solver

Linear programming functionality is provided by the minlp subpackage. The minlpstate class provides a common interface for all solvers (simplex method and interior point method) supported by ALGLIB. This interface is described in this separate article, which explains how to specify and solve linear programming problems with ALGLIB.

This article is licensed for personal use only.