Search

In the article titled Central Path and Barrier Algorithms for Linear Programs in this encyclopedia, the main ideas underlying the modern interior-point methods are presented. In these methods the central path plays a crucial role. To start these methods one needs a starting point on or close to the central path. Given such a point, a variant of Newton's method is used to generate a sequence of iterates that converges to an optimal solution of the problem. In this section, we show how to get into the situation that a starting point on the central path is known. This goes via the construction of an artificial problem whose solution either yields an optimal solution for a given problem, or detects that no such solution exists. Keywords: linear optimization; central path; interior-point method; optimal partition; self-dual embedding

In this article, the main ideas underlying the modern interior-point methods are presented. We discuss primal, dual, and primal-dual methods and show that each of these methods can be used to solve a linear optimization problem in polynomial time. It is made clear that the central path plays a crucial role in each of the methods. The described methods require a starting point on or close to the central path. Given such a point, a variant of Newton's method can be used to construct a numerical procedure that generates a sequence of iterates that converges to an optimal solution of the problem. Keywords: linear optimization; central path; interior-point method; barrier function; primal method; primal–dual method; dual method; KKT condition; complexity