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

(68 intermediate revisions by 3 users not shown) | |||

Line 3: | Line 3: | ||

Steward: Dajun Yue, Fengqi You<br> | Steward: Dajun Yue, Fengqi You<br> | ||

Date Presented: May 25, 2014 <br> | Date Presented: May 25, 2014 <br> | ||

− | =Introduction= | + | =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). The problem is solved (assuming there IS a solution) either by iteratively solving for | + | [[File:InteriorPointMethod.png|thumb|300px|right|Examples of logarithmic barrier functions.]] |

+ | 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. | + | 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<br> | ||

+ | Minimize <math>f_0(x)</math><br> | ||

+ | subject to <math> f_i(x) \leq 0</math><br> | ||

+ | <math>Ax=b</math><br> | ||

+ | 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<br> | ||

+ | minimize <math> f_0(x) + \sum_i^m I_-(f_i(x))</math><br> | ||

+ | st <math> Ax=b</math><br> | ||

+ | where <math> I_-(x)=\left|\begin{array}{cc}0& x \leq 0\\ \infty & x > 0\end{array}\right|</math><br><br> | ||

+ | This problem, however, is not continuous. A modification can be made by approximating <math>I_-(x)</math> 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<br> | ||

+ | <math>\phi(x)=-\sum_i^mlog(-f_i(x))</math><br> | ||

+ | which blows up if any of our constraints are violated. Our LP problem now becomes<br> | ||

+ | minimize <math> f_0(x) + \frac{1}{t}\phi(x)</math><br> | ||

+ | st <math> Ax=b</math><br> | ||

+ | <br> | ||

+ | 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 <math>Ax=b</math> from the original problem, but give increasingly more optimized values for the objective function, with the inequality constraints <math>f_i(x)</math> not necessarily equal to 0. | ||

+ | ==Algorithm== | ||

+ | Given strictly feasible <math>x, t:=t^0>0,\mu >1, \epsilon<0</math><br> | ||

+ | '''repeat'''<br> | ||

+ | 1. Compute <math>x^*(t)</math> by minimizing <math>tf_0 + \phi </math> subject to <math>Ax = b</math>, starting at x.<br> | ||

+ | 2. Update <math>x:=x^*(t)</math>.<br> | ||

+ | 3. Quit if <math>\frac{m}{t} \leq \epsilon</math>, else<br> | ||

+ | 4. Increase <math>t:=\mu t</math>[3] | ||

− | == | + | ==Example== |

+ | min <math> f(x) = x_1 - 2x_2 </math><br> | ||

+ | s.t. <math> 1 + x_1 - (x_2)^2 >= 0 </math><br> | ||

+ | |||

+ | <math> x_2 >= 0 </math><br> | ||

+ | |||

+ | Use the Frisch barrier function to yield the unconstrained problem: | ||

+ | |||

+ | min <math> r(c,x) = x_1 - 2x_2 - clog(1+x_1-(x_2)^2) - clog(x_2) </math> | ||

+ | |||

+ | For a specific parameter c, the first order necessary conditions for optimality are: | ||

+ | |||

+ | <math> 1 - c/(1+x_1-(x_2)^2) = 0 </math> | ||

+ | |||

+ | <math> -2 + 2cx_2/(1+x_1-(x_2)^2) - c/x_2 = 0 </math> | ||

+ | |||

+ | Hence | ||

+ | |||

+ | <math> c = 1 + x_1 - (x_2)^2 </math> | ||

+ | |||

+ | substituting c in | ||

+ | |||

+ | <math> -2 + 2cx_2/(1+x_1-(x_2)^2) - c/x_2 = 0 </math> | ||

+ | |||

+ | we obtain | ||

+ | |||

+ | <math> (x_2)^2 - x_2 - (1/2)c = 0 </math> | ||

+ | |||

+ | Hence | ||

+ | |||

+ | <math> x_2 = (1 +/- sqrt(1+2c))/2 </math>, of which the positive is the only feasible solution | ||

+ | |||

+ | =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: | ||

+ | [[File:345pic.JPEG|thumb|300px|right|Number of iterations required for PD IP method to solve randomly generated standard LPs of different dimensions, with n = 2m. Error bars show standard deviation.]] | ||

+ | minimize <math>f(x)</math> | ||

+ | |||

+ | s.t. <math>g_i(x)\ge 0</math> with <math>i = 1,...,m</math>. | ||

+ | |||

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

+ | |||

+ | minimize <math>f(x)</math> | ||

+ | |||

+ | s.t. <math>g(x)- s = 0</math> with <math>s \ge 0</math>. | ||

+ | |||

+ | The logrithmic barrier function is now introduced: | ||

+ | |||

+ | minimize <math> f(x) - \mu~ \sum_{i=1}^m\log(s_i)</math> | ||

+ | |||

+ | s.t. <math>h(x)-s=0</math> | ||

+ | |||

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

+ | |||

+ | minimize <math>f(x) - \mu~ \sum_{i=1}^m\log(s_i) - y^T(g(x) - s)</math> | ||

+ | |||

+ | Next, set all of the derivatives equal to 0: | ||

+ | |||

+ | <math>\nabla f(x) - \nabla g(x)^Ty = 0</math> | ||

+ | |||

+ | <math>- \mu W^{-1} e + y = 0</math> | ||

+ | |||

+ | <math>g(x) - s = 0</math> | ||

+ | |||

+ | Rearranging: | ||

+ | |||

+ | <math> \nabla f(x) - \nabla g(x)^Ty = 0 </math> | ||

+ | |||

+ | <math>W Y e = \mu e</math> | ||

+ | |||

+ | <math>g(x) - s = 0</math> | ||

+ | |||

+ | Utilize Newton's Method to determine the search directions, <math> \Delta x, \Delta s, \Delta y </math>: | ||

+ | |||

+ | ::<math>\begin{bmatrix} G(x,y) & 0 & -A(x)^T \\ 0 & Y & W \\ A(x) & -I & 0 \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta s \\ \Delta y \end{bmatrix} = \begin{bmatrix} -\nabla f(x) + A(x)^T y \\ \mu e - W Y e \\ -g(x) + s \end{bmatrix}</math> | ||

+ | |||

+ | where <math>G(x,y) = \nabla^2 f(x) - \sum_{i=1}^m\ y_i \nabla^2 g_i(x)</math> | ||

+ | |||

+ | and <math> A(x) = \nabla g(x)</math> | ||

+ | |||

+ | Using the 2nd equation, we solve for <math>\Delta s</math>, the result of which is the reduced KKT system: | ||

+ | |||

+ | <math>\begin{bmatrix} -G(x, y) & A^T(x) \\ A(x) & WY^{-1} \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta y \end{bmatrix} = \begin{bmatrix} \nabla f(x) - A^T(x) y \\ -g(x) + \mu Y^{-1} e \end{bmatrix} </math> | ||

+ | |||

+ | From here, perform iterations: | ||

+ | |||

+ | <math> x^{k+1} = x^{k} + \alpha^k \Delta x^k</math> | ||

+ | |||

+ | <math> s^{k+1} = s^{k} + \alpha^k \Delta s^k</math> | ||

+ | |||

+ | <math> y^{k+1} = y^{k} + \alpha^k \Delta y^k</math> | ||

+ | |||

+ | =Conclusion= | ||

+ | The Interior Point method approximates the constraints of a linear programming model as a set of boundaries surrounding a region. These approximations are used when the problem has constraints that are discontinuous or otherwise troublesome, but can me modified so that a linear solver can handle them. Once the problem is formulated in the correct way, Newton's method is used to iteratively approach more and more optimal solutions within the feasible region. | ||

+ | Two practical algorithms exist in IP method: barrier and primal-dual. Primal-dual method is a more promising way to solve larger problems with more efficiency and accuracy. As shown in the figure above, the number of iterations needed for the primal-dual method to solve a problem increases logarithmically with the number of variables, and standard error only increases rapidly when a very large number of dimensions exist. | ||

+ | = Sources = | ||

1. R.J. Vanderbei, Linear Programming: Foundations and Extensions (Chp 17-22). Springer, 2008.<br> | 1. R.J. Vanderbei, Linear Programming: Foundations and Extensions (Chp 17-22). Springer, 2008.<br> | ||

2. J. Nocedal, S. J. Wright, Numerical optimization (Chp 14). Springer, 1999. <br> | 2. J. Nocedal, S. J. Wright, Numerical optimization (Chp 14). Springer, 1999. <br> | ||

3. S. Boyd, L. Vandenberghe, Convex Optimization (Chp 11). Cambridge University Press, 2009 | 3. S. Boyd, L. Vandenberghe, Convex Optimization (Chp 11). Cambridge University Press, 2009 |

## Latest revision as of 19:20, 7 June 2014

Authors: John Plaxco, Alex Valdes, Wojciech Stojko. (ChE 345 Spring 2014)

Steward: Dajun Yue, Fengqi You

Date Presented: May 25, 2014

## Contents |

# 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

subject to

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

st

where

This problem, however, is not continuous. A modification can be made by approximating 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

st

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 from the original problem, but give increasingly more optimized values for the objective function, with the inequality constraints not necessarily equal to 0.

## Algorithm

Given strictly feasible

**repeat**

1. Compute by minimizing subject to , starting at x.

2. Update .

3. Quit if , else

4. Increase [3]

## Example

min

s.t.

Use the Frisch barrier function to yield the unconstrained problem:

min

For a specific parameter c, the first order necessary conditions for optimality are:

Hence

substituting c in

we obtain

Hence

, of which the positive is the only feasible solution

# 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

s.t. with .

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

minimize

s.t. with .

The logrithmic barrier function is now introduced:

minimize

s.t.

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

minimize

Next, set all of the derivatives equal to 0:

Rearranging:

Utilize Newton's Method to determine the search directions, :

where

and

Using the 2nd equation, we solve for , the result of which is the reduced KKT system:

From here, perform iterations:

# Conclusion

The Interior Point method approximates the constraints of a linear programming model as a set of boundaries surrounding a region. These approximations are used when the problem has constraints that are discontinuous or otherwise troublesome, but can me modified so that a linear solver can handle them. Once the problem is formulated in the correct way, Newton's method is used to iteratively approach more and more optimal solutions within the feasible region. Two practical algorithms exist in IP method: barrier and primal-dual. Primal-dual method is a more promising way to solve larger problems with more efficiency and accuracy. As shown in the figure above, the number of iterations needed for the primal-dual method to solve a problem increases logarithmically with the number of variables, and standard error only increases rapidly when a very large number of dimensions exist.

# 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