Neue effiziente Abstiegrichtung eines primal-dualen Wegverfolgungsalgorithmus für die lineare Programmierung

Wir stellen einen neuen primal-dualen Innenpunktalgorithmus mit einem vollen Newton-Schritt zur Lösung linearer Optimierungsprobleme vor. Der neu vorgeschlagene Ansatz basiert auf der Anwendung einer neuen Funktion auf eine einfache äquivalente Form der Zentrierungsgleichung des Systems, die den zentralen Pfad definiert. Somit erhalten wir eine neue effiziente Suchrichtung für den betrachteten Algorithmus. Darüber hinaus beweisen wir, dass die Methode die untersuchten Probleme in polynomialer Zeit löst und dass der erhaltene Algorithmus die bislang beste bekannte Komplexitätsgrenze für die lineare Optimierung hat. Schließlich wird eine vergleichende numerische Studie berichtet, um die Effizienz des vorgeschlagenen Algorithmus zu zeigen.