Interior Point Method
Interior point methods (also referred to as barrier methods) are a certain class of algorithms 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 iterations 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.
Read more about Interior Point Method: Primal-dual Interior Point Method For Nonlinear Optimization
Famous quotes containing the words interior, point and/or method:
“The monk in hiding himself from the world becomes not less than himself, not less of a person, but more of a person, more truly and perfectly himself: for his personality and individuality are perfected in their true order, the spiritual, interior order, of union with God, the principle of all perfection.”
—Thomas Merton (1915–1968)
“Beautiful credit! The foundation of modern society. Who shall say that this is not the golden age of mutual trust, of unlimited reliance upon human promises? That is a peculiar condition of society which enables a whole nation to instantly recognize point and meaning in the familiar newspaper anecdote, which puts into the mouth of a distinguished speculator in lands and mines this remark:M”I wasn’t worth a cent two years ago, and now I owe two millions of dollars.””
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“In child rearing it would unquestionably be easier if a child were to do something because we say so. The authoritarian method does expedite things, but it does not produce independent functioning. If a child has not mastered the underlying principles of human interactions and merely conforms out of coercion or conditioning, he has no tools to use, no resources to apply in the next situation that confronts him.”
—Elaine Heffner (20th century)