# Difference between revisions of "Interior-point method for LP"

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

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$
$Ax=b$
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
$\phi(x)=-\sum_i^mlog(-f_i(x))$
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$

This allows us to use Newton's method to follow what is called a Central Path, which is a series of points we iterate through that all satisfy the equality constraints $Ax=b$ from the original problem, but give increasingly more optimized values for the objective function, with the inequality constraints $f_i(x)$ not necessarily equal to 0.

## Algorithm

Given strictly feasible $x, t:=t^0>0,\mu >1, \epsilon<0$
repeat
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]

## Example

min $f(x) = x_1 - 2x_2$
s.t. 1 + x_1 - (x_2)^2

# 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_i(x)\ge 0$ with $i = 1,...,m$.

We now introduce slack variables to turn all inequalities into non-negativities:

minimize $f(x)$

s.t. $g(x)- s = 0$ with $s \ge 0$.

The logrithmic barrier function is now introduced:

minimize $f(x) - \mu~ \sum_{i=1}^m\log(s_i)$

s.t. $h(x)-s=0$

Now incorporate the equality constraint(s) into the objective function using Lagrange multipliers:

minimize $f(x) - \mu~ \sum_{i=1}^m\log(s_i) - y^T(g(x) - s)$

Next, set all of the derivatives equal to 0:

$\nabla f(x) - \nabla g(x)^Ty = 0$

$- \mu W^{-1} e + y = 0$

$g(x) - s = 0$

Rearranging:

# Conclusion

## Sources

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