|
|
|
|
|
Interior Point MethodInterior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems. These algorithms have been inspired from algorithms by Narendra Karmarkar for linear programming, developed in 1984. The basic elements of the method consists of a self-concordant barrier function used to encode the convex set. Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set. The idea of encoding the feasible set using a barrier and designing barrier methods was studied in the early 1960s by Fiacco McCormick and others. These ideas were mainly developed for general nonlinear programming. Nestrov and Nemirovskii came up with a special class of such barriers that can be used to encode any convex set. They guarantee that the number of iterations of the algorithm is bounded by a polynomial in the dimension and accuracy of the solution. Practical implementation usually refer to Mehrotra's predictor-corrector algorithm.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|