Moderne Algorithmen der endlichdimensionalen Nichtlinearen Optimierung

Andreas Griewank

Übersicht zur Vorlesung (Sommersemester 2004):

Ziel

Den Teilnehmern sollen die mathematischen Grundlagen und softwaretechnische Umsetzung der aktuell leistungstärksten NLP Löser vermittelt werden. In der Übung werden bestimmte, öffentlich verfügbare Pakete vorgestellt und verglichen.

Vorkenntnisse

Die Teilnehmern sollten die folgenden Basisalgorithmen kennen bzw dem Skript Grundlagen der Optimierung vom WS 2003/4 entnehmen.

• Strahlsuche Armijo/Interpolation
• (P)CG linear/nichtlinear
• BFGS mit Liniensuche
• Projezierte Gradienten
• Nullraumverfahren zur SQP Schrittberechnung

Die folgenden Basisalgorithmen werden in der Vorlesung vorgestellt:

• Trustregion Variante von CG und BFGS
• Quadratische Programmierung

Die folgenden Erweiterungen des Zielfunktionales sind in der Vorlesung zu erläutern:

• Linearer Lagrangeterm
• Barriere logarithmisch/reziprok
• Strafterm l-1/l-2
• Filter/Vektorbewertungen

Die folgenden Hilfsalgorithmen der Linearen Algebra werden aus der Nutzerperspektive erwähnt aber nicht im Detail erläutert.

• , , und mit Rang-1 Aufdatierungen

Software

Die folgenden Programmierumgebungen sollen erläutert und selektiv genutzt werden.

• Mathematische Umgebungen: Matlab/Scilab
• Differentiationswerkzeuge: ADOL-C/Tapenade für C++/Fortran
• Modellierungssprachen: AMPL/GAMS
• Testumgebung: CUTEr

Diskussion

Je nach Anzahl der Teilnehmer sollen die folgenden Optimierungsalgorithmen/Pakete dargestellt und diskutiert werden

Augmented Lagrangian:

MINOS ( Saunders et al), LANCELOT (Toint et al ), Pennon( Kocvara et al)

Sequential Quadratic Programming:

NPSOL/SNOPT ( Gill et al ), NLPQL(Schittkowski), SPRNLP/SOCS ( Betts et al )

Interior Point

KNITRO ( Nocedal et al ), LOQO(Vanderbei), IPOPT ( Waechter et al)

(Nearly) Feasible Points:

DONLP2 ( Spelucci ), FSQP ( Tits )

Terminplan für Übung

21.4.

Einführung in Matlab (J. Riehme)

28.4.

Üben mit Matlab

5.5.

Vorlesung und Übung zu AD ( J. Riehme )

12.5.

Einführung in AMPL ( J. Bacallao )

19.5.

Einführung in GAMS ( J. Bacallao )

26.5.

Einführung in CUTEr ( A. Ponomarenko )

anschliessend

Vorträge über Algorithmen Pakete in Reihung Lagrange, SQP, Innere Punkte!!