Direkt zum Inhalt

Lexikon der Mathematik: zentraler Pfad

eine Kurve, die bei der Lösung linearer (und auch allgemeinerer) Programmierungsprobleme unter Anwendung einer Inneren-Punkte Methode wichtig ist.

Sei \begin{eqnarray}{c}^{T}\cdot x\to \min \end{eqnarray} unter den Nebenbedingungen \begin{eqnarray}x\in M:=\{x\in {{\mathbb{R}}}^{n}|A\cdot x=b,x\ge 0\}\end{eqnarray} ein lineares Optimierungsproblem mit A ∈ ℝm×n, c ∈ ℝn, b ∈ ℝn.

Existiert ein xM mit x > 0, dann gibt es für jedes μ > 0 einen eindeutigen Minimalpunkt des Problems \begin{eqnarray}{c}^{T}\cdot x-\mu \cdot \displaystyle \sum _{i=1}^{n}\mathrm{ln}\,({x}_{i})\end{eqnarray} unter den Nebenbedingungen \begin{eqnarray}A\cdot x=b,\,\,\,x\gt 0.\end{eqnarray} Die Kurve \begin{eqnarray}\{x(\mu )|\mu \gt 0\}\end{eqnarray} bildet den zentralen Pfad für die Zulässigkeitsmenge M. Ihm versuchen Innere-Punkte Methoden für immer kleiner werdendes μ → 0+ in einen Minimalpunkt des Ausgangsproblems hinein zu folgen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos