Interior-point method for LP

From optimization
Revision as of 17:38, 25 May 2014 by Voitek (Talk | contribs)

Jump to: navigation, search

Authors: John Plaxco, Alex Valdes, Wojciech Stojko. (ChE 345 Spring 2014)
Steward: Dajun Yue, Fengqi You
Date Presented: May 25, 2014


Introduction and Uses

Interior point methods are a type of algorithm that are used in solving both linear and nonlinear convex optimization problems that contain inequalities as constraints. The LP Interior-Point method relies on having a linear programming model with the objective function and all constraints being continuous and twice continuously differentiable. In general, a problem is assumed to be strictly feasible, and will have a dual optimal that will satisfy Karush-Kuhn-Tucker (KKT) constraints described below. The problem is solved (assuming there IS a solution) either by iteratively solving for KKT conditions or to the original problem with equality instead of inequality constraints, and then applying Newton's method to these conditions.

Interior point methods came about from a desire for algorithms with better theoretical bases than the simplex method. While the two strategies are similar in a few ways, the interior point methods involve relatively expensive (in terms of computing) iterations that quickly close in on a solution, while the simplex method involves usually requires many more inexpensive iterations. From a geometric standpoint, interior point methods approach a solution from the interior or exterior of the feasible region, but are never on the boundary.[1]

There are two important interior point algorithms: the barrier method and primal-dual IP method. The primal-dual method is usually preferred due to its efficiency and accuracy. Major differences between the two methods are as follows. There is only one loop/iteration in primal-dual because there is no distinction between outer and inner iterations as with the barrier method. In primal-dual, the primal and dual iterates do not have to be feasible.[3]

Barrier Method Algorithm

For the barrier method algorithm, there a few approximations that must be made. Given a problem in the form of
Minimize f_0(x)
subject to  f_i(x) \leq 0
we must reformulate it to implicitly include the inequalities in the objective function. We can do this by creating a function that greatly increases the objective if a constraint is not met. Our conditions then changes to
minimize  f_0(x) + \sum_i^m I_-(f_i(x))
st  Ax=b
where  I_-(x)=\left|\begin{array}{cc}0& x \leq 0\\ \infty & x > 0\end{array}\right|

This problem, however, is not continuous. A modification can be made by approximating I_-(x) as a logarithm log(-x), which approaches infinity when x approaches 0 as we want, and makes all functions twice differentiable. We then put the logarithm over a variable that sets a level of accuracy for the approximation we make. Here we will call that variable t. We define
which blows up if any of our constraints are violated. Our LP problem now becomes
minimize  f_0(x) + \frac{1}{t}\phi(x)
st  Ax=b


Given strictly feasible x, t:=t^0>0,\mu >1, \epsilon<0
1. Compute x^*(t) by minimizing tf_0 + \phi subject to Ax = b, starting at x.
2. Update x:=x^*(t).
3. Quit if \frac{m}{t} \leq \epsilon, else
4. Increase t:=\mu t[3]

Primal-Dual IP Algorithm

The primal-dual interior-point method can easily be understood by using the simplest NLP problem; one with only inequality constraints. Consider the following:

minimize f(x) s.t. g(x) \ge 0~~ x \in \mathbb{R}^n, g(x) \in \mathbb{R}^m~~~~~~(1).




1. R.J. Vanderbei, Linear Programming: Foundations and Extensions (Chp 17-22). Springer, 2008.
2. J. Nocedal, S. J. Wright, Numerical optimization (Chp 14). Springer, 1999.
3. S. Boyd, L. Vandenberghe, Convex Optimization (Chp 11). Cambridge University Press, 2009