Interior-point method for LP

From optimization
Revision as of 16:31, 25 May 2014 by JohnPlaxco (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

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.

General Idea

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).

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