Interior point methods (also referred to as barrier methods) are a certain class of algorithms to solve linear and nonlinear convex optimization problems. These algorithms have been inspired by Karmarkar's algorithm, developed by Narendra Karmarkar in 1984 for linear programming. The basic elements of the method consists of a self-concordant barrier function used to encode the convex set.

PropertyValue
dbpprop:abstract
  • Interior point methods (also referred to as barrier methods) are a certain class of algorithms to solve linear and nonlinear convex optimization problems. These algorithms have been inspired by Karmarkar's algorithm, developed by Narendra Karmarkar in 1984 for linear programming. The basic elements of the method consists of a self-concordant barrier function used to encode the convex set. Contrary to the simplex method, it reaches an optimal solution by traversing the interior of the feasible region. 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, amongst others, Anthony V. Fiacco and Garth P. McCormick. These ideas were mainly developed for general nonlinear programming, but they were later abandoned due to the presence of more competitive methods for this class of problems. Yurii Nesterov and Arkadii 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. Karmarkar's breakthrough revitalized the study of interior point methods and barrier problems, showing that it was possible to create an algorithm for linear programming characterized by polynomial complexity and, moreover, that was competitive with the simplex method. Already Khachiyan's ellipsoid method was a polynomial time algorithm; however, in practice it was too slow to be of practical interest. The class of primal-dual path-following interior point methods is considered the most successful. Mehrotra's predictor-corrector algorithm provides the basis for most implementations of this class of methods.
  • Innere-Punkte-Verfahren sind in der Optimierung eine Klasse von Algorithmen zur Lösung von Optimierungsaufgaben. Ihr Hauptanwendungsgebiet sind lineare oder quadratische Programme. Sie werden aber auch zur Lösung (allgemeiner) nichtlinearer Programme, semidefinierter Programme oder Komplementaritätsproblemen eingesetzt. Im Vergleich zu den traditionelleren Active-Set-Methoden zeichnen sich Innere-Punkte-Verfahren durch bessere theoretische Eigenschaften und schnellere Konvergenz für sehr große dünnbesetzte Probleme aus. Ein Nachteil ist, dass sie vergleichbar ungeeignet zum Lösen einer Serie von Optimierungsaufgaben sind (was für viele Algorithmen der ganzzahligen Optimierung, wie z. B. Branch and Bound oder Schnittebenenverfahren, wichtig ist).
  • Les méthodes de point intérieur forment une classe d'algorithmes qui permettent de résoudre des problèmes d'optimisation convexe (linéaire ou non). Les méthodes de points intérieurs se répartissent en plusieurs familles: La méthode « affine scaling » (optimisation sur des ellipsoïdes) La méthode de réduction du potentiel (notion de barrière, chemin central, relaxation) (La méthode du chemin central est le représentant le plus important de cette famille)
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • Interior point methods (also referred to as barrier methods) are a certain class of algorithms to solve linear and nonlinear convex optimization problems. These algorithms have been inspired by Karmarkar's algorithm, developed by Narendra Karmarkar in 1984 for linear programming. The basic elements of the method consists of a self-concordant barrier function used to encode the convex set.
  • Innere-Punkte-Verfahren sind in der Optimierung eine Klasse von Algorithmen zur Lösung von Optimierungsaufgaben. Ihr Hauptanwendungsgebiet sind lineare oder quadratische Programme. Sie werden aber auch zur Lösung (allgemeiner) nichtlinearer Programme, semidefinierter Programme oder Komplementaritätsproblemen eingesetzt.
  • Les méthodes de point intérieur forment une classe d'algorithmes qui permettent de résoudre des problèmes d'optimisation convexe (linéaire ou non). Les méthodes de points intérieurs se répartissent en plusieurs familles: La méthode « affine scaling » (optimisation sur des ellipsoïdes) La méthode de réduction du potentiel (notion de barrière, chemin central, relaxation) (La méthode du chemin central est le représentant le plus important de cette famille)
rdfs:label
  • Interior point method
  • Innere-Punkte-Verfahren
  • Méthode du point intérieur
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of