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

(→Introduction) |
|||

Line 5: | Line 5: | ||

=Introduction= | =Introduction= | ||

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. The problem is solved (assuming there IS a solution) either by iteratively solving for Karun-Kush-Tucker (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 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. The problem is solved (assuming there IS a solution) either by iteratively solving for Karun-Kush-Tucker (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, | ||

=Uses= | =Uses= |

## Revision as of 15:51, 25 May 2014

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

Steward: Dajun Yue, Fengqi You

Date Presented: May 25, 2014

## Contents |

# Introduction

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. The problem is solved (assuming there IS a solution) either by iteratively solving for Karun-Kush-Tucker (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,

# Uses

# Algorithm

# Example

# 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