Ergänzungen zum Skriptum

Operations Research 1
Verschiedene Typen von nichtlinearen
Optimierungsproblemen

Das Standard-NLOP lautet:

Maximiere f (x)
unter
g(x) ≤ 0,
h(x) = 0,
wobei f : Rn → R, g : Rn → Rm , h : Rn → Rp .

Optimierungsprobleme ohne Nebenbedingungen

(unconstraint optimization)
In diesem Fall besteht das Optimierungsproblem nur aus der Zielfunktion.
Falls die Funktion f (x) dierenzierbar ist, dann stellt
∇f (x∗ ) = 0
eine notwendige Bedingung für eine Lösung x∗ dar. Im Falle von Nichtnega-
tivitätsbedinungen einer Komponente xj ≥ 0 lautet die Bedingung:
∂f ∗ ≤ 0 falls x∗j = 0
(
(x )
∂xj = 0 falls x∗j > 0
Falls die Funktion f (x) konkav ist, dann ist obige Bedingung auch hin-
reichend.

1
Optimierungsprobleme mit linearen Nebenbedingungen
(optimization with linear constraints)
Diese Problemklasse zeichnet sich dadurch aus, daÿ alle Nebenbedingungen
lineare Funktionen sind, nur die Zielfunktion ist nichtlinear. Abhängig von
den Eigenschaften der Zielfunktion sind die allgemeinen Bedingungen der
nichtlinearen Optimierungsprobleme (KKT, Sattelpunkt, Duale Bedingung)
anwendbar. Es gibt jedoch spezielle Lösungsalgorithmen die auf dem Prinzip
der Simplexmethode für lineare Optimierungsproblemen basieren, wobei hier
die nichtlineare Zielfunktion berücksichtigt werden muÿ.

Quadratische Programmierung
(quadratic programming)

Dieses Problem ist eigentlich ein Spezialfall in der Klasse von Optimierungs-
problemen mit linearen Nebenbedingungen, denn zusätzlich muÿ die Ziel-
funktion quadratisch sein. Daher ist der einzige Unterschied zwischen einem
linearen Programm und einem quadratischen Programm, daÿ in der Zielfunk-
tion das Quadrat einzelner Variablen, beziehungsweise das Produkt zweier
Variablen auftritt. Speziell für konkave Zielfunktionen gibt es Erweiterungen
des Simplexalgorithmus, die in diesen Fällen anwendbar sind.

Konvexe Programmierung
(convex programming)
Ein konvexes Programm liegt vor, wenn

1. f (x) konkav,
2. g(x) konvex und
3. h(x) an

sind. Für allgemeine konvexe Optimierungsprobleme sind die Sattelpunkts-

bedingung und die duale Bedingung hinreichend und im Falle von Regula-
ritätsannahmen auch notwendig. Im Falle der Dierenzierbarkeit sind auch
die KKT-Bedingungen hinreichend und bei entsprechenden Regularitätsan-
nahmen notwendig.

2
Programmierung bei separablen Funktionen
(separable programming)

Dieses Problem ist ein Spezialfall eines konvexen Programms, bei dem sowohl
f (x) als auch g(x) separable Funktionen sind, d.h.
n n
fj (xj ) und gi (x) =
X X
f (x) = gij (xj ).
j=1 j=1

Diese Optimierungsprobleme lassen sich durch lineare Programme appro-

ximieren und somit mit Algorithmen für LPs lösen.

Nichtkonvexe Programmierung
(nonconvex programming)
Diese Klasse umfaÿt alle nichtlinearen Probleme, die nicht die Voraussetzun-
gen für konvexe Programme erfüllen. In diesem Fall kann, falls ein lokales
Maximum gefunden wurde, nicht garantiert werden, daÿ dieses auch ein glo-
bales Maximum ist. Es gibt aber für einige Spezialfälle Methoden um lokale
Maxima zu nden.

Geometrische Programmierung
(geometric programming)

Für ein geometrisches Programm benötigen wir folgendene Funktionen

n
a
für i = 1, ..., N + 1,
Y
Pi (x) = ci xj ij
j=1

mit ci > 0. Das geometrische Programm lautet dann:

Minimiere g0 (x) =
X
Pi (x)
i∈I0

unter
Pi (x) ≤ 0 für j = 1, ..., m,
X
gj (x) =
i∈Ij

3
wobei Ij ⊆ {1, ..., N + 1} ∀j = 0, .., m und Ij ∩ Ik = ∅ ∀j 6= k gilt. Funktionen
dieser Form werden verallgemeinerte positive Polynome (= Posynome) ge-
nannt. Ein geometrische Problem kann durch Transformation auf die neuen
Variablen y1 , ..., yn mit
xj = eyj
in ein konvexes Optimierungsproblem übergeführt werden.

Quotientenoptimierung
(fractional programming)

In diesem Fall kann die Zielfunktion als Bruch dargestellt werden:

f1 (x)
Maximiere f (x) = .
f2 (x)

Man versucht diese Probleme durch Transformation auf andere Problem-

klassen zurückzuführen. Zum Beispiel kann ein lineares gebrochenes Pro-
gramm ( f1 (x) und f2 (x) und die Nebenbedingungen sind linear) auf ein li-
neares Programm zurückgeführt werden. Wenn f1 (x) konkav, f2 (x) und g(x)
konvex (und h(x) an) sind, kann das Problem in ein konvexes Programm
transformiert werden.