Ergänzungen zum Skriptum

Operations Research 1
Lösungsalgorithmen für nichtlineare
Optimierungsprobleme

1 Lösungsverfahren für 1-dimensionale Optimie-

rungsproblem ohne Nebenbedingungen

Lösungsverfahren für 1-dimensionale Probleme spielen deshalb eine wichtige

Rolle, weil viele Verfahren für komplexe Probleme ein solches 1-dimensionales
Optimierungsproblem beinhalten.

1.1 1-dimesionale Suche ohne Verwendung von Ablei-

tungen
Das Grundprinzip der 1-dimensionalen Suchverfahren besteht darin, ein vor-
gegebenes Intervall, in dem das Maximum liegt, und in dem keine weiteren
lokalen Extremumsstellen enthalten sind, Schritt für Schritt zu verkleinern,
bis man eine gewünschte Genauigkeit erreicht hat.

Initialisierung: setze k=1 und [ak , bk ] = [a, b].

Iteration:

1. Wähle zwei Punkte λk , µk ∈ (ak , bk ) mit λk < µ k . Falls

(a) f (λk ) > f (µk ), dann setze [ak+1 , bk+1 ] = [ak , µk ].

(b) f (λk ) ≤ f (µk ), dann setze [ak+1 , bk+1 ] = [λk , bk ].

1
 2. Ersetze k durch k+1 und gehe zu 1.

Abbruchbedingung: Wenn |bk −ak | < ε kleiner als die Toleranz ε ist, dann
wird die Iteration abgebrochen und das Intervall [ak , bk ] zurückgeliefert.

Die verschiedenen Algorithmen unterscheiden sich in der Wahl der Punkte

λk , µk . So werden zum Beispiel beim Verfahren des Goldenen Schnittes diese
Punkte so gewählt, daÿ die Funktionsauswertung im aktuellen Iterations-
schritt auch im darauolgenden Schritt verwendet werden kann. Das heiÿt,
es muÿ entweder f (λk )
f (µk ) berechnet werden, aber nicht beides. Um
oder
dies zu erreichen, müssen λk = αak + (1 − α)bk und µk = (1 − α)ak + αbk
√
5−1
gewählt werden, wobei α = ist.
2

1.2 1-dimensionale Suche unter Verwendung von Ablei-

tungen
Wenn die Ableitung zur Verfügung steht, dann ist ja die Suche nach dem
Maximum gleichbedeutend mit der Suche nach der Nullstelle der Ableitung
(unter der Voraussetzung, daÿ die Funktion nur eine Extremumstelle im An-
fangsintervall besitzt). Steht nur die 1. Ableitung zur Verfügung so kann man
zum Beispiel ein Bisektionsverfahren folgendermaÿen anwenden:

Initialisierung: setze k=1 und [ak , bk ] = [a, b].

Iteration:

ak +bk
1. Setze x= 2
. Falls

(a) f 0 (x) < 0, dann setze [ak+1 , bk+1 ] = [ak , x].

(b) f 0 (x) > 0, dann setze [ak+1 , bk+1 ] = [x, bk ].
2. Ersetze k durch k+1 und gehe zu 1.

Abbruchbedingung: Wenn |bk −ak | < ε kleiner als die Toleranz ε ist, dann
wird die Iteration abgebrochen und das Intervall [ak , bk ] zurückgeliefert.
0
Falls f (x) = 0, dann ist x die Lösung und die Iteration wird ebenfalls
abgebrochen.

Falls auch noch die 2. Ableitung zur Verfügung steht kann man ein Newton-
Verfahren anwenden:

2
Initialisierung: setze k=1 und Startwert x0 ∈ [a, b].

Iteration:

f 0 (xk )
1. Setze xk+1 = xk − f ”(xk )
2. Ersetze k durch k+1 und gehe zu 1.

Abbruchbedingung: Wenn |f 0 (xk )| < ε kleiner als die Toleranz ε ist, dann
wird die Iteration abgebrochen und xk zurückgeliefert.

Wenn der Startwert hinreichend nahe beim Optimum gewählt wird, sodaÿ ge-
wisse Bedingungen erfüllt sind, so kann man auch die Anzahl der Iterationen
bestimmen, die notwendig sind, um eine vorgegebene Toleranz zu erreichen.
In diesem Fall entfällt die Abbruchbedingung.

2 Lösungsverfahren für mehrdimensionale Op-

timierungsprobleme ohne Nebenbedingungen

Der wichtigste und meistverwendete Algroithmus ist das Gradientenverfah-

ren. Wie der Name schon sagt, wird in diesem Fall der Gradient der Funktion
benötigt. In fast allen Fällen ist die Zielfunktion dierenzierbar, was nicht
heiÿt, daÿ der Gradient einfach oder überhaupt analytisch zu berechnen ist.
Jedoch kann der Gradient im Falle der Dierenzierbarkeit auch numerisch
approximiert werden mittels niten Dierenzen. Unter der Annahme, daÿ
der Gradient der Zielfunktion zur Verfügung steht, kann folgendes Gradient-
verfahren formuliert werden (Voraussetzung ist natürlich, daÿ die Funktion
nur ein lokales Maximum hat.):

Initialisierung: setze k=1 und Startwert x 0 ∈ G ⊂ Rn .

Iteration:

1. Löse das 1-dimensionale Optimierungsproblem

max f (xk + λ∇f (xk ))

λ

wobei λ ≥ 0. Die Lösung ist λk .

2. Setze xk+1 = xk + λk ∇f (xk ).

3
 3. Ersetze k durch k+1 und gehe zu 1.

Abbruchbedingung: Wenn ||∇f (xk )|| < ε kleiner als die Toleranz ε ist,
dann wird die Iteration abgebrochen und xk zurückgeliefert.

Wenn die Zielfunktion nicht dierenzierbar ist, dann ersetzt man ∇f (xk )
durch eine geeignete Richtung (zum Beispiel der Reihe nach alle Einheits-
vektoren). Der Abbruch erfolgt dann, wenn die Dierenz ||xk+1 − xk || unter
eine vorgegebene Toleranz fällt. Es gibt eine Vielzahl von Algorithmen, die
geeignete Richtungen ohne den Gradienten auswählen. Zum Beispiel werdend
beim Verfahren der konjugierten Richtungen Richtungen dk gewählt,
die Linearkombinationen des Gradienten der Zielfunktion an den bisherigen
0
Approximationslösungen xk sind, und die dk−1 Qdk = 0 für eine positiv de-
nite, symmetrische Matrix Q erfüllen.

3 Lösungsverfahren für mehrdimensionale Op-

timierungsprobleme mit Nebenbedingungen

3.1 Verfahren zulässiger Richtungen

siehe Skriptum

3.2 SUMT - Sequential Unconstrained Minimization (Ma-

ximization) Technique
3.2.1 Strafkostenverfahren

siehe Skriptum

3.2.2 Barriereverfahren

Dieses Verfahren ist ähnlich dem Strafkostenverfahren, nur nähert man sich
hier nicht von auÿerhalb dem zulässigen Bereich, sondern man startet inner-
halb und verhindert durch eine sogenannte Barrierefunktion, das man den
zulässigen Bereich verlässt. Das heiÿt, eine Barrierefunktion β(x, µ) erfüllt
folgende Bedingungen:

1. β(x, µ) ist klein, falls x weit von den Grenzen des zulässigen Bereiches
entfernt ist.

4
 2. β(x, µ) ist groÿ, falls x nahe an den Grenzen des zulässigen Bereiches
ist.

3. β(x, µ) → 0, wenn der Abstand von x zum Rand des zulässigen Berei-
ches → 0.

Ein Barrierefunktion für ein NLOP mit Gleichheits-, Ungleichheits- und

Nichtnegativitätsbedingungen wäre

m p n
X µ X hj (x)2 X µ
β(x, µ) = + √ + .
i=1
−gi (x) j=1 µ k=1
xk

Es muss dann das Hilfsproblem

max f (x) − β(x, µ)

x

gelöst werden, wobei µ>0 ein fester Parameter ist. Läÿt man nun µ&0
gehen, so erhält die Lösung des ursprünglichen Problems.

Initialisierung: setze k = 1 und Startwert x0 ∈ X , sowie µ1 > 0 und

θ ∈ (0, 1) geeignet.

Iteration:

1. Löse das Optimierungsproblem ohne Nebenbedingungen

max f (x) − β(x, µk )

x

mittels eines Gradientenverfahrens mit Startwert xk−1 . Die Lösung

ist xk .
2. Setze µk+1 = θµk , ersetze k durch k+1 und gehe zu 1.

Abbruchbedingung: Falls ||xk − xk−1 || < ε kleiner als die Toleranz ε ist,
beende Iteration und liefere xk als Lösung.

5
3.3 Verfahren nach Frank-Wolfe (Algorithmus mit se-
quentieller Approximation durch LPs)
Voraussetzung für dieses Verfahren ist, das nur lineare Ungleichheits- und
Nichtnegativitätsbedingungen auftreten (also: Ax ≤ b und x ≥ 0).
Die Idee dieses Verfahrens ist das NLOP durch Approximation mit linea-
0
ren Problemen zu lösen. Hat man einen zulässigen Punkt x ∈ X so kann
man die Zielfunktion durch den Gradienten linear approximiern

f (x) ≈ f (x0 ) + ∇f (x0 )(x − x0 ).

Da ja f (x0 ) und ∇f (x0 )x0 x sind, kann man die Zielfunktion f (x) durch die
neue lineare Zielfunktion
F (x) = ∇f (x0 )x
ersetzen. Zusammen mit den linearen Nebenbedingungen ergibt sich nun ein
lineares Programm, daÿ man zum Beispiel mit einem Simplexalgorithmus
lösen kann. Zusammengefaÿt sieht der Algorithmus folgendermaÿen aus:

Initialisierung: setze k=1 und Startwert x0 ∈ X .

Iteration:

1. Löse das lineare Optimierungsproblem

max ∇f (xk−1 )x
x

unter Ax ≤ b und x ≥ 0. Die Lösung ist xLP

k .

2. Löse das 1-dimensionale Optimierungsproblem

max f (xk−1 + λ(xLP

k − xk−1 ))
λ

unter λ ∈ [0, 1] und setze xk entsprechend der Lösung dieses Pro-

blems.

3. Ersetze k durch k+1 und gehe zu 1.

Abbruchbedingung: Falls ||xk − xk−1 || < ε kleiner als die Toleranz ε ist,
beende Iteration und liefere xk als Lösung.