Interior-point method
Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s. In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time and is also very efficient in practice. It enabled solutions of linear programming problems that were beyond the capabilities of the simplex method. In contrast to the simplex method, it reaches a best solution by traversing the interior of the feasible region. The method can be generalized to convex programming based on a self-concordant barrier function used to encode the convex set. Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. The idea of encoding the feasible set using a barrier and designing barrier methods was studied by Anthony V. Fiacco, Garth P. McCormick, and others in the early 1960s. 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 Arkadi Nemirovski 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, 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. 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 following nonlinear optimization problem with inequality constraints:

This inequality-constrained optimization problem is solved by converting it into an unconstrained objective function whose minimum we hope to find efficiently. Specifically, 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 gradient of a differentiable function  is denoted . The gradient of the barrier function is

In addition to the original ("primal") variable  we introduce a Lagrange multiplier-inspired dual variable 

Equation (4) is sometimes called the "perturbed complementarity" condition, for its resemblance to "complementary slackness" in KKT conditions. We try to find those  for which the gradient of the barrier function is zero. Substituting  from (4) into (3), we get an equation for the gradient:

where the matrix  is the Jacobian of the constraints . 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. Let  be the search direction for iteratively updating . Applying Newton's method to (4) and (5), we get an equation for :

where  is the Hessian matrix of ,  is a diagonal matrix of , and  is the diagonal matrix of . Because of (1), (4) the condition

should be enforced at each step. This can be done by choosing appropriate :

See also
Affine scaling
Augmented Lagrangian method
Chambolle-Pock algorithm
Karush–Kuhn–Tucker conditions
Penalty method

References

Bibliography 

 
 
 
 

Optimization algorithms and methods