Interior Point Methods: A Survey, Short Survey of Applications to Power Systems, and Research Opportunities

In the past fifteen years, research on Interior Point Methods (IPM) and their
applications were very extensive. Both IPM theory and computational
implementations evolved very fast. IPM variants are being extended to solve all kind
of programs: from linear to nonlinear and from convex to non-convex, and they are
being applied to solve many practical problems, including engineering optimization
problems. The first known IPM method is Frisch’s (1955) [1] logarithmic barrier
method that was later extensively studied by Fiacco and McCormick [2]. The modern
era of IPM started with Karmarkar’s paper [3] and his IPM for Linear Programming
(LP) where solution time up to 50 times faster than simplex method were reported.
The name “interior point” comes from LP notation. Namely, IPM methods move
through the interior of the feasible region towards the optimal solution. This is in
contrast to the simplex algorithm, which follows a sequence of adjacent extreme
points to the optimal solution. Because of this strong link to the LP almost every
tutorial survey of IPM methods starts with IPM for LP and then extends it to the nonlinear
programming problems. This is the case with this report. IPM are usually
classified into three main categories: Projective methods, affine-scaling methods, and
primal-dual methods. Among the different IPMs the primal-dual (including primal-dual
algorithms that incorporate predictor and corrector) algorithms have gained a
reputation for being the most efficient. The main steps in every IPM method are [4]:
transforming an inequality constrained optimization problem to equality constrained
one, formulate Lagrange function using logarithmic barrier functions, set the firstorder
optimality conditions, and apply Newton’s method to the set of equations
coming from the first-order optimality conditions. This report is organized in such a
way to reflect these main steps. For the first the equality constrained nonlinear
optimization problem is considered. Since the main breakthrough in IPM methods has
been made in Karmarkar’s paper [3] within the context of linear programming, the LP
is then considered. The approach is then extended to nonlinear problems. A survey of
IPM methods applications in solving different electric power system optimization
problems is given. Some research opportunities are identified and shortly discussed in
the report. The review of available software computational engines is given. Finally, a
small NLP example is included in the paper and a NLP solver, built around
SPOOLES (SParse Object-Oriented Linear Equations Solver) [5] as a linear algebra
kernel, is applied to solve the problem.