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

Cindyxchen (Talk | contribs) (→References) |
Cindyxchen (Talk | contribs) |
||

Line 5: | Line 5: | ||

The interior point (IP) method for nonlinear programming was pioneered by Anthony V. Fiacco and Garth P. McCormick in the early 1960s. The basis of IP method restricts the constraints into the objective function ([http://en.wikipedia.org/wiki/Duality_%28optimization%29 duality]) by creating a barrier function. This limits potential solutions to iterate in only the feasible region, resulting in a much more efficient algorithm with regards to time complexity. | The interior point (IP) method for nonlinear programming was pioneered by Anthony V. Fiacco and Garth P. McCormick in the early 1960s. The basis of IP method restricts the constraints into the objective function ([http://en.wikipedia.org/wiki/Duality_%28optimization%29 duality]) by creating a barrier function. This limits potential solutions to iterate in only the feasible region, resulting in a much more efficient algorithm with regards to time complexity. | ||

− | To ensure the program remains within the feasible region, a factor, <math>\mu</math>, is added to "penalize" close approaches to the boundaries. This approach is analogous to the use of an invisible fence to keep dogs in an unfenced yard. As the dog moves closer to the boundaries, the more shock he will feel. In the case of the IP method, the amount of shock is determined by <math>\mu</math>. A large value of <math>\mu</math> gives the analytic center of the feasible region. As <math>\mu</math> decreases and approaches 0, the optimal value is calculated by tracing out a central path. With small incremental decreases in <math>\mu</math> during each iteration, a smooth curve is generated for the central path. This method is accurate, but time consuming and computationally intense. Instead, Newton's method is often used to approximate the central path for non-linear programming. Using one Newton step to estimate each decrease in <math>\mu</math> for each iteration, a polynomial ordered time complexity is achieved, resulting in a small zig-zag central path and convergence to the optimal solution. | + | =Penalty and Barrier Method= |

+ | [[File:IP_NLP_Ellipse.png|thumb|250px|right|A trajectory of local unconstrained minimizers of the logarithmic barrier function (red).]] | ||

+ | To ensure the program remains within the feasible region, a factor, <math>\mu</math>, is added to "penalize" close approaches to the boundaries. This approach is analogous to the use of an invisible fence to keep dogs in an unfenced yard. As the dog moves closer to the boundaries, the more shock he will feel. In the case of the IP method, the amount of shock is determined by <math>\mu</math>. A large value of <math>\mu</math> gives the analytic center of the feasible region. As <math>\mu</math> decreases and approaches 0, the optimal value is calculated by tracing out a central path. With small incremental decreases in <math>\mu</math> during each iteration, a smooth curve is generated for the central path. This method is accurate, but time consuming and computationally intense. Instead, Newton's method is often used to approximate the central path for non-linear programming. Using one Newton step to estimate each decrease in <math>\mu</math> for each iteration, a polynomial ordered time complexity is achieved, resulting in a small zig-zag central path and convergence to the optimal solution.<br><br> | ||

− | + | The logarithmic barrier function is based on the logarithmic interior function: | |

+ | <math>B(x, \mu) = f(x) - \muI_log(x) = f(x) - \mu\sum_{i=1}^m ln(x_i)</math><br> | ||

− | |||

− | |||

=Conclusion= | =Conclusion= |

## Revision as of 23:12, 23 May 2015

Author names: Cindy Chen

Steward: Dajun Yue and Fengqi You

## Contents |

# Introduction

The interior point (IP) method for nonlinear programming was pioneered by Anthony V. Fiacco and Garth P. McCormick in the early 1960s. The basis of IP method restricts the constraints into the objective function (duality) by creating a barrier function. This limits potential solutions to iterate in only the feasible region, resulting in a much more efficient algorithm with regards to time complexity.

# Penalty and Barrier Method

To ensure the program remains within the feasible region, a factor, , is added to "penalize" close approaches to the boundaries. This approach is analogous to the use of an invisible fence to keep dogs in an unfenced yard. As the dog moves closer to the boundaries, the more shock he will feel. In the case of the IP method, the amount of shock is determined by . A large value of gives the analytic center of the feasible region. As decreases and approaches 0, the optimal value is calculated by tracing out a central path. With small incremental decreases in during each iteration, a smooth curve is generated for the central path. This method is accurate, but time consuming and computationally intense. Instead, Newton's method is often used to approximate the central path for non-linear programming. Using one Newton step to estimate each decrease in for each iteration, a polynomial ordered time complexity is achieved, resulting in a small zig-zag central path and convergence to the optimal solution.

The logarithmic barrier function is based on the logarithmic interior function:

**Failed to parse(unknown function '\muI'): B(x, \mu) = f(x) - \muI_log(x) = f(x) - \mu\sum_{i=1}^m ln(x_i)**

# Conclusion

The IP method was later adapted for linear programming by Karmarkar in 1984. As a polynomial-time linear programming method, it solved complex linear problems 50 times faster than the simplex method. Multiple solvers utilize the IP method for non-linear programming, such as IPOPT and KNITRO, both of which were developed by IEMS professors at Northwestern University. Although successful, the IP method is no longer as popular since the creation of more competitive methods, such as sequential quadratic programming.

# References

1. Forsgren, Anders; Gill, Philip E.; Wright, Margaret H. "Interior Methods for Nonlinear Optimization." Society for Industrial Applied Mathematics Review. 44.4: 525-597. Link.

2. Shanno, David. "Who Invented the Interior Point Method?" Documenta Mathematica Extra Volume ISMP (2012): 55-64. Link