An analytical comparison between primal – dual interior point methods and simplex method

Abstract

In this work, we have highlighted the effectiveness of interior-point method over simplex method. Primal-Dual Interior Method is one of the algorithms in interior-point method which borrow a few simple ideas from nonlinear optimization which include the Lagrangian multiplier, KKT condition, Duality theorem and others. The duality gap serves as a terminationcriteria while the relevance of the central path for Linear Programming (LP) is to show that the limit of the central path exists when ρ ⟶ 0 in Interior Point Method (IPM). As the strength of the barrier function is decreased while solving the sequence of unconstrained problems, the optimum follows a well-defined path (hence the term “Path following”) that ends at the optimal solution to the original problem. IPMs tend to find an exact optimal solution that is in the “centre” of the optimal set as opposed to the Simplex Method (SM) that finds the “corner” (vertex) of the optimal set as shown in the figures below.