Interior point method

Interior-point method in the optimization of a class of algorithms for solving optimization tasks. Their main area of ​​application are linear or quadratic programs. They are also used to solve ( generalized ) nonlinear programs, semi -defined programs or complementarity problems.

Compared to the traditional active set methods ( eg simplex method ) to interior-point methods are characterized by better theoretical properties ( polynomial complexity) and faster convergence for very large sparse problems. A disadvantage is that they are comparable unsuitable for solving a series of optimization problems (which many algorithms for integer programming, such as branch and bound or cutting-plane method is important ).

Task

In the simplest case interior-point methods are used to the linear problem

To solve. Where A is a matrix, and c, b and m are each n- dimensional vectors. The allowable amount is in the shape of a polyhedron. From the theory of linear optimization is well known that an optimum solution of the optimization problem is assumed in one of the corners of the polyhedron. In contrast to the simplex method, which moves along the edges from corner to corner, try interior-point method a path to the optimum by the " inside" of the polyhedron to find.

History

Logarithmic barrier methods were first described by Ragnar Frisch (1956). As an important early reference on the subject of barrier method applies Fiacco and McCormick (1968). They were then, however, inefficient, and ( by the logarithms of very small numbers) as numerically unstable. As birth of the interior -point method is commonly the work of Narendra Karmarkar in 1984, in which he for the first time describes a polynomial potentially usable in most algorithm for nonlinear problems. This algorithm had already many similarities to modern methods, even if the major breakthroughs that interior points method made ​​a true competitor for the simplex method, occurred only in the 1990s (eg, Mehrotra (1992)).

Derivation

From today's point of view, there are different ways to motivate interior-point method. A possibility is logarithmic barrier: Here, the Positivitätsbedingungen be replaced by logarithmic penalty terms in the objective function (this is a parameter ). So instead of the original problem to solve

For small values ​​of is very large, so one tries by punishing small x values ​​to keep the solution of the optimization problem inside the set of positive coordinates. This penalty is smaller, the smaller is the parameter. In the limit, it is expected that the solution of the barrier problem converges to the solution of the original problem. The barrier problem is a ( strictly ) convex problem, its ( only global ) solution is found by applying the Lagrange multiplier set as a solution of the (nonlinear) system of equations

For each value of this system of equations has a unique solution. The set of solutions for various describes a path ( the central path) which connects the center of the allowable Analytical polyhedron ( for ) with the solution of the original problem ( for ). Algorithmic the system of equations can be solved by Newton's method. In interior-point method of the parameters is reduced after each iteration of Newton's method. By suitable heuristics ensures that the convergence of Newton's method and the run synchronously.

Properties

  • Interior-point methods are globally convergent.
  • The short- step variant of the interior-point method takes in the worst case iterations to find the solution of a linear problem with accuracy. This is currently the best known theoretical bound. The short- step method is inferior in practice, however, other variants.
  • In practice observed iterations.

Algorithm

Variants of the method and environments

There are several variants of interior-point method, which differ mainly in the choice of and. The most important are short- step method, cross- step method and Predictor - Corrector method ( prediction and correction). In order to describe them in the following environments of the central path required:

And

Here is the interior of the feasible set. The central path is defined by the condition. In the environment, the Euclidean norm of the deviation of the vector of is limited in the environment is only required that the products are not too small.

The variants of interior-point method are as follows:

  • Short step procedure:. appropriate parameter and set. When the starting point is, this is also true for all other Iterationspunkte.
  • Long- step process: can be selected. It is set to and chosen such that the following also applies.
  • Predictor - Corrector method: It is selected first, and the maximum for this case is determined ( Predictor ). This provides an estimate of the optimum, which is now selected in the second step. In the second step is also attempts to correct the error of the third linearization equation () by Newton's method. In the Predictor - Corrector method, the above Newton system of equations for two different right-hand sides is solved. It is possible to implement this very efficiently ( Cholesky decomposition ).

The Predictor - Corrector method is superior to the other variants in practice, however, is to analyze heavier and has worse theoretical properties.

Time complexity#Polynomial time
413013
de