Interior point method
Encyclopedia
Interior point methods are a certain class of algorithm
s to solve linear and nonlinear convex optimization problems.
The interior point method was invented by John von Neumann
. Von Neumann suggested a new method of linear programming, using the homogeneous linear system of Gordan (1873) which was later popularized by Karmarkar's algorithm
, developed by Narendra Karmarkar
in 1984 for linear programming
. The method consists of a self-concordant barrier function
used to encode the convex set
. Contrary to the simplex method
, it reaches an optimal solution by traversing the interior of the feasible region.
Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function
over a convex set. The idea of encoding the feasible set
using a barrier and designing barrier methods was studied in the early 1960s by, amongst others, Anthony V. Fiacco and Garth P. McCormick. These ideas were mainly developed for general nonlinear programming
, but they were later abandoned due to the presence of more competitive methods for this class of problems (e.g. sequential quadratic programming
).
Yurii Nesterov and Arkadii Nemirovskii came up with a special class of such barriers that can be used to encode any convex set. They guarantee that the number of iteration
s of the algorithm is bounded by a polynomial in the dimension and accuracy of the solution.
Karmarkar's breakthrough revitalized the study of interior point methods and barrier problems, showing that it was possible to create an algorithm for linear programming characterized by polynomial complexity and, moreover, that was competitive with the simplex method.
Already Khachiyan
's ellipsoid method
was a polynomial time algorithm; however, in practice it was too slow to be of practical interest.
The class of primal-dual path-following interior point methods is considered the most successful.
Mehrotra's predictor-corrector algorithm
provides the basis for most implementations of this class of methods.
For simplicity consider the all-inequality version of a nonlinear optimization problem:
The logarithmic barrier function
associated with (1) is
Here
is a small positive scalar, sometimes called the "barrier parameter". As 
converges to zero the minimum of 
should converge to a solution of (1)
The barrier function gradient
where
is the gradient of the original function 
and the matrix 
is the constraint 
Jacobian
In addition to the original ("primal") variable
we introduce a Lagrange multiplier inspired dual variable 
(sometimes called "slack variable")
(4) is sometimes called the "perturbed complementarity" condition, for its resemblance to "complementary slackness" in KKT conditions
We try to find those
which turn gradient of barrier function to zero
Applying (4) to (3)
The intuition behind (5) is that the gradient of should lie in the subspace spanned by the constraints' gradients. The "perturbed complementarity" with small
(4) can be understood as the condition that the solution should either lie near the boundary 
or that the projection of the gradient 
on the constraint component 
normal should be almost zero.
Applying Newton's method to (4) and (5) we get an equation for
update 
:
is the Hessian matrix
of and
is a diagonal matrix
of
Because of (1), (4) the condition
should be enforced at each step. This can be done by choosing appropriate
:
.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s to solve linear and nonlinear convex optimization problems.
The interior point method was invented by John von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
. Von Neumann suggested a new method of linear programming, using the homogeneous linear system of Gordan (1873) which was later popularized by Karmarkar's algorithm
Karmarkar's algorithm
Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time...
, developed by Narendra Karmarkar
Narendra Karmarkar
Narendra K. Karmarkar is an Indian mathematician, renowned for developing Karmarkar's algorithm. He is listed as an ISI highly cited researcher.- Biography :...
in 1984 for linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
. The method consists of a self-concordant barrier function
Barrier function
In constrained optimization, a field of mathematics, a barrier function is a continuous function whose value on a point increases to infinity as the point approaches the boundary of the feasible region . It is used as a penalizing term for violations of constraints...
used to encode the convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
. Contrary to the simplex method
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
, it reaches an optimal solution by traversing the interior of the feasible region.
Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function
Linear function
In mathematics, the term linear function can refer to either of two different but related concepts:* a first-degree polynomial function of one variable;* a map between two vector spaces that preserves vector addition and scalar multiplication....
over a convex set. The idea of encoding the feasible set
Candidate solution
In optimization , a candidate solution is a member of a set of possible solutions to a given problem. A candidate solution does not have to be a likely or reasonable solution to the problem – it is simply in the set that satisfies all constraints.The space of all candidate solutions is called the...
using a barrier and designing barrier methods was studied in the early 1960s by, amongst others, Anthony V. Fiacco and Garth P. McCormick. These ideas were mainly developed for general nonlinear programming
Nonlinear programming
In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
, but they were later abandoned due to the presence of more competitive methods for this class of problems (e.g. sequential quadratic programming
Sequential quadratic programming
Sequential quadratic programming is an iterative method for nonlinear optimization. SQP methods are used on problems for which the objective function and the constraints are twice continuously differentiable....
).
Yurii Nesterov and Arkadii Nemirovskii came up with a special class of such barriers that can be used to encode any convex set. They guarantee that the number of iteration
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
s of the algorithm is bounded by a polynomial in the dimension and accuracy of the solution.
Karmarkar's breakthrough revitalized the study of interior point methods and barrier problems, showing that it was possible to create an algorithm for linear programming characterized by polynomial complexity and, moreover, that was competitive with the simplex method.
Already Khachiyan
Leonid Khachiyan
Leonid Genrikhovich Khachiyan was a Soviet mathematician of Armenian descent who taught Computer Science at Rutgers University. He was most famous for his Ellipsoid algorithm for linear programming, which was the first such algorithm known to have a polynomial running time...
's ellipsoid method
Ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm, which finds an optimal solution in a finite number of steps.The...
was a polynomial time algorithm; however, in practice it was too slow to be of practical interest.
The class of primal-dual path-following interior point methods is considered the most successful.
Mehrotra's predictor-corrector algorithm
Mehrotra predictor-corrector method
Mehrotra's predictor–corrector method in optimization is an implementation of interior point methods. It was proposed in 1989 by Sanjay Mehrotra....
provides the basis for most implementations of this class of methods.
Primal-dual interior point method for nonlinear optimization
The primal-dual method's idea is easy to demonstrate for constrained nonlinear optimization.For simplicity consider the all-inequality version of a nonlinear optimization problem:
- minimize
subject to 
The logarithmic barrier function
Barrier function
In constrained optimization, a field of mathematics, a barrier function is a continuous function whose value on a point increases to infinity as the point approaches the boundary of the feasible region . It is used as a penalizing term for violations of constraints...
associated with (1) is
Here
is a small positive scalar, sometimes called the "barrier parameter". As converges to zero the minimum of should converge to a solution of (1)The barrier function gradient
Gradient
In vector calculus, the gradient of a scalar field is a vector field that points in the direction of the greatest rate of increase of the scalar field, and whose magnitude is the greatest rate of change....
where
is the gradient of the original function and the matrix is the constraint JacobianIn addition to the original ("primal") variable
we introduce a Lagrange multiplier inspired dual variable (sometimes called "slack variable")(4) is sometimes called the "perturbed complementarity" condition, for its resemblance to "complementary slackness" in KKT conditions
We try to find those
which turn gradient of barrier function to zeroApplying (4) to (3)
The intuition behind (5) is that the gradient of should lie in the subspace spanned by the constraints' gradients. The "perturbed complementarity" with small
(4) can be understood as the condition that the solution should either lie near the boundary or that the projection of the gradient on the constraint component normal should be almost zero.Applying Newton's method to (4) and (5) we get an equation for
update : is the Hessian matrixHessian matrix
In mathematics, the Hessian matrix is the square matrix of second-order partial derivatives of a function; that is, it describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named...
of and
is a diagonal matrixDiagonal matrix
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero. The diagonal entries themselves may or may not be zero...
of
Because of (1), (4) the condition
should be enforced at each step. This can be done by choosing appropriate
:.