Interior point methods (also referred to as
barrier methods) are a certain class of
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
s to solve linear and nonlinear
convex optimizationConvex optimization is a subfield of mathematical optimization, which is concerned with minimizing convex functions. Given a real vector space together with a convex, real-valued function...
problems.
These algorithms have been inspired by
Karmarkar's algorithmKarmarkar'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 KarmarkarNarendra 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 programmingIn mathematics, linear programming is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints...
. The basic elements of the method consists of a self-concordant
barrier functionIn 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 setIn 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. For example, a solid cube is convex, but anything that is hollow or has a dent in it, for example, a crescent shape, is not...
. Contrary to the
simplex methodIn mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerically solving linear programming problems...
, 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 functionIn 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.
Interior point methods (also referred to as
barrier methods) are a certain class of
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
s to solve linear and nonlinear
convex optimizationConvex optimization is a subfield of mathematical optimization, which is concerned with minimizing convex functions. Given a real vector space together with a convex, real-valued function...
problems.
These algorithms have been inspired by
Karmarkar's algorithmKarmarkar'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 KarmarkarNarendra 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 programmingIn mathematics, linear programming is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints...
. The basic elements of the method consists of a self-concordant
barrier functionIn 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 setIn 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. For example, a solid cube is convex, but anything that is hollow or has a dent in it, for example, a crescent shape, is not...
. Contrary to the
simplex methodIn mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerically solving linear programming problems...
, 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 functionIn 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 setIn 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...
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 programmingIn 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 programmingSequential quadratic programming is one of the most popular and robust algorithms for nonlinear continuous optimization. The method is based on solving a series of subproblems designed to minimize a quadratic model of the objective subject to a linearization of the constraints...
).
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
iterationIteration 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 complexityIn computer science, polynomial time refers to the running time of an algorithm, that is, the number of computation steps a computer or an abstract machine requires to evaluate the algorithm....
and, moreover, that was competitive with the simplex method.
Already
KhachiyanLeonid Genrikhovich Khachiyan was a Russian 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 methodThe ellipsoid method is an algorithm for solving convex optimization problems. It was introduced by Naum Z. Shor, Arkady Nemirovsky, and David B. Yudin in 1972, and used by Leonid Khachiyan to prove the polynomial-time solvability of linear programs. At the time, the ellipsoid method was the only...
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 algorithmMehrotra'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.