Prof. Dr. H. Maurer SS 89

Optimierung II

Übungsblatt 2 , Abgabe: 27.04.1989 , 10.00 Uhr

Aufgabe 4: (2+4 Punkte)

(a) Es seien f : R^{n+1} → R, a, b : R^{n} → R C^{1}-Funktionen. Dann ist die Funktion F : R^{n} → R mit

F (x) := ∫_{a(x)}^{b(x)} f(x, t)dt , x ∈ R^{n} ,

eine C^{1}-Funktion. Geben sie die Optimalittsbedingungen 1. Ordnung fr ein lokales Minimum \overline{x} von F an.

(b) Die DGL

L[v] = \frac{dv}{dt} + t v = 0 , v(0) = 1 ,

hat die Lsung v(t) = e^{−t^{2}/2}. Zur nherungsweisen Bestimmung dieser Lsung im Intervall [0, 1] macht man den Ansatz

v(t) ∼ w(x_{1}, x_{2}, t) = 1 + x_{1}t + x_{2}t^{2} , 0 ≤ t ≤ 1 .

Man bestimme x_{1}, x_{2} so, da beim Einsetzen von w(x_{1}, x_{2}, t) in die DGL die Fehlerquadratsunmme

F (x_{1}, x_{2}) = ∫_{0}^{1}(L[w(x_{1}, x_{2}, t)])^{2}dt

minimal wird.

\underline{Hinweis:} Benutze (a) und berechne ein LGS fr x_{1}, x_{2}. Zur Kontrolle:

x_{1} = −1.191 , x_{2} = 0.073

Aufgabe 5: (1+1+1+2 Punkte) Fr eine Teilmenge M ⊂ R^{n} heit

M^{+} := {λ ∈ R^{n} | λx ≥ 0 ∀ ∈ M}

der Dualkegel von M. Man zeige:

(a) M^{+} ist ein abgeschlossener Kegel.

(b) Es gilt: M^{+} = (\overline{M})^{+}

(c) Wie lt sich Satz (3.5) mit Hilfe des dualen Kegels ausdrcken?

(d) Zeichnen Sie den Dualkegel zur Menge.

M = {(x_{1}, x_{2}) ∈ R^{2} | x_{1} + x_{2} ≥ 1 , x_{1} − 2x_{2} ≥ 1}

Aufgabe 6: (2+1 Punkte)

(a) Beweisen Sie Lemma (A.2) (viii).

(b) Ist K ein konvexer Kegel, x ∈ K, und K(x) die konische Hlle von K bzgl. x, so gilt: K(x)^{+} = {λ ∈ K^{+} | λx = 0}

Aufgabe 7: (4 Punkte) Beweisen Sie Lemma (3.3).

Prof. Dr. H. Maurer SS 89

Optimierung II

Übungsblatt 3 , Abgabe: 11.05.1989 , 10.00 Uhr Aufgabe 8: (3+3 Punkte)

(a) Seien f : R^{n} × R^{k} → R, g : R^{n} × R^{k} → R^{n} C^{1}-Abbildungen mit det(g_{x}(x, u)) ≠ 0

fr (x, u) ∈ R^{n} × R^{k}. Fr das Optimierungsproblem

min_{(x,u)∈Rn×Rk} {f(x, u) | g(x, u) = 0}

gebe man notwendige Optimalittsbedingungen 1. Ordnung an. Man benutze hierfr den Satz ber implizite Funktionen und gebe das Ergebnis in Termen von f, g und deren Ableitungen an.

(b) Man lse das Optimierungsproblem

min \{\frac{1}{2} (\frac{x^{2}}{a^{2}} + \frac{u^{2}}{b^{2}} ) | xu − c = 0\} , c > 0 ,

grafisch und analytisch. Aufgabe 9: (3+3 Punkte) Seien f : R^{n} → R differenzierbar, K ⊂ R^{n} konvex, A eine m × n-Matrix und b ∈ R^{n}.

(a) Zeigen Sie:

T (K, \overline{x}) = cℓK(\overline{x}) .

Berechnen Sie T (K, \overline{x}) und L(S, \overline{x}) im Falle K = \{x ∈ R^{n} | Ax = b\}.

(b) Beweisen Sie: Ist \overline{x} eine lokale Minimalstelle des Problems

min {f(x) | Ax = b} ,

so gibt es λ ∈ R^{m} mit f′(\overline{x}) + λA = 0. \underline{Hinweis:} Benutzen sie Satz (3.5) und (a).

Aufgabe 10: (2+3+3 Punkte)

(a) Sei f : R^{n} → R differenzierbar und sei C ⊂ R^{n} konvex.

\underline{Man zeige:} Fr eine lokale Minimalstelle \overline{x} des Problems

min {f(x) | x ∈ C}

gilt

f′(\overline{x})(x − \overline{x}) ≥ 0 fr alle x ∈ C .

(b) Sei C ⊂ R^{n} eine konvexe, abgeschlossene Menge und sei y ∉ C. \underline{Man zeige:} Es gibt einen eindeutig bestimmten Punkt \overline{x} mit

∥\overline{x} − y∥_{2} = min \{∥x − y∥_{2} |x ∈ C\} .

Der Punkt \overline{x} ist charakterisiert durch

(\overline{x} − y)^{T} (x − \overline{x}) ≥ 0 fr alle x ∈ C .

\overline{x} heit die Projektion von y auf C.

(c) (cone projection theorem) Sei K ⊂ R^{n} ein abgeschlossener konvexer Kegel. \underline{Man zeige:} Jedes Element y ∈ R^{n} kann eindeutig zerlegt werden in

y = x_{0} − x_{1}, x_{0} ∈ K, x_{1}^{T} ∈ K^{+}, x_{1}^{T} x_{0} = 0,

wobei x_{0} die Projektion von y auf K ist (vgl. (b)) und K^{+} der duale Kegel ist (vgl. Aufgabe 5).

Aufgabe 11: (3 Punkte) Sei

\begin{aligned}S & = & \{(x, y) ∈ R^{2} & | & 1 − x^{2} − (y − 1)^{2} ≤ 0 & , \\ & & & & x^{2} + (y − 2)^{2} − 4 ≤ 0 & , & −y^{2} − x ≤ 0\} . \end{aligned}

Man skizziere S und berechne den Tangentialkegel von S in allen Randpunkten \overline{x} von S.

Optimierung II

Übungsblatt 4 , Abgabe: 01.06.1989 , 10.00 Uhr

Aufgabe 12: (1+3 Punkte) Die Mengen S_{α} seien gegeben durch

S_{α} = {x ∈ R^{2} | x_{2} − x1^{α} ≤ 0, −x_{2} − x1^{α} ≤ 0} , α ≥ 1.

(a) Skizzieren Sie S_{α} fr α ≥ 1.

(b) Berechnen Sie die Kegel T (S_{α}, \overline{x}) und L(S_{α}, \overline{x}) fr \overline{x} = (0, 0)^{T}, α ≥ 1. Fr welche α ≥ 1 ist \overline{x} regulr?

Aufgabe 13: (4 Punkte) Sei \overline{x} eine \underline{regulre} Minimalstelle des Optimierungsproblems

\begin{aligned}min\{f(x) | & g_{i}(x) ≤ 0, & i = 1,…, k \\ & g_{i}(x) = 0, & i = k + 1,…, m\} . \end{aligned}

Beweisen Sie die Bedingungen von KUHN/TUCKER in Satz (4.4) direkt mit dem Dualittssatz der linearen Optimierung.

Aufgabe 14: (1+4+1 Punkte) Die kostenminimale Lagerung von n Gtern fhrt auf das Optimierungsproblem (Gtermengen x_{i}, i = 1,…, n)

(P) min \{∑_{i=1}^{n} (a_{i}x_{i} + \frac{b_{i}}{x_{i}} ) | ∑_{i=1}^{n} c_{i}x_{i} = d, x > 0\}

mit positiven Konstanten a, b_{i}, c_{i}, d.

(a) Man zeige: (P) ist ein konvexes Optimierungsproblem.

(b) Man berechne die optimale Lsung \overline{x} ∈ R^{n} und den zugehrigen LAGRANGE-Multiplikator \overline{λ} ∈ R.

\underline{Hinweis:} \overline{λ} ist Nullstelle einer nichtlinearen Gleichung unter der Voraussetzung

d > ∑_{i=1}^{n} c_{i}(b_{i}/a_{i})^{1/2} .

(c) Man berechne \overline{x}, \overline{λ} explizit im Falle a_{i} = a c_{i}, i = 1,…, n, a > 0.

Aufgabe 15: (2+2 Punkte)

(a) Zeigen Sie:

max {∏_{i=1}^{n} x_{i} ; ∑_{i=1}^{n} x_{i} = 1, x_{i} ≥ 0 fr i = 1,…, n} = n^{−n}.

(b) Zeigen Sie: Fr alle x ∈ R^{n} mit x ≥ 0 gilt:

n \sqrt{∏_{i=1}^{n}}x_{i} ≤ \frac{1}{n} ∑_{i=1}^{n} x_{i}

Aufgabe 16: (3+6 Punkte) Gegeben seien k Punkte a_{1},…, a_{k} ∈ R^{n}, k > 1. Das Problem, eine kleinstmgliche Kugel zu finden, welche a_{1},…, a_{k} enthlt, fhrt auf das Optimierungsproblem

(P)  min_{x∈Rn,z∈R} {f(x, z) | g_{i}(x, z) ≤ 0, i = 1,…, k} ,
f(x, z) := z ,
g_{i}(x, z) := ∥x − a_{i}∥^{2} − z, i = 1,…, k

Es sei ∥ · ∥ die euklidische Norm.

(a) Man berlege, da eine optimale regulre Lsung (x_{0}, z_{0}) existiert und bestimme die Bedingungen von KUHN/TUCKER in (x_{0}, z_{0}).

*(b) Sei R = \sqrt{z_{0}} der Radius der Kugel und

d = max_{i,j=1,...,k} ∥a_{i} − a_{j}∥

der maximale Abstand. Man beweise die Abschtzung

d ≥ R (\frac{2k}{k − 1})^{1/2} .

Verbessern Sie die Abschtzung mit q := Anzahl der aktiven Indizes.

\underline{Hinweis zu (b):} Zeigen Sie mit Hilfe von (a) und unter Verwendung von D_{ij} = ∥a_{i} − a_{j}∥^{2} = ∥a_{i} − x_{0} − (a_{j} − x_{0})∥^{2} die Beziehungen:

2R^{2} = ∑_{i,j=1}^{k} λ_{i}D_{ij}λ_{j} ,

∑_{i≠j} λ_{i}D_{ij}λ_{j} ≤ d^{2} ∑_{i≠j} λ_{i}λ_{j} ,

∑_{i≠j} λ_{i}λ_{j} = 1 − ∑_{i} λ_{i}^{2} ≤ 1 − \frac{1}{k}

Optimierung II

Übungsblatt 5 , Abgabe: 08.06.1989 , 10.00 Uhr

Aufgabe 17: (4 Punkte) Bestimmen Sie smtliche lokale und globale Minimalstellen des Problems

min{x^{2} + y^{2} + z^{2} | z − xy − 5 = 0}.

Deuten Sie dieses Problem geometrisch.

Aufgabe 18: (4 Punkte) Fr das Optimierungsproblem

min{4c − x − 3y − 20z | x^{2} + 3y^{2} − 20z^{2} + c^{2} = 0}, c > 0,

bestimme man

(a) smtliche Punkte (x, y, z, λ), welche den Bedingungen von KUHN / TUCKER gengen.

(b) die (globale) Minimalstelle.

Aufgabe 19: (4 Punkte) Man beweise die notwendigen Bedingungen zweiter Ordnung in Satz (5.12)(i) fr Gleichungsrestriktionen g(x) = 0. \underline{Hinweis:} Die in Satz (3.11) angegebene Kurve x : [−ϵ, ϵ] → S mit

x(0) = \overline{x}, x^{·} (0) = v ∈ L(S, \overline{x})

ist eine C^{2}-Kurve. Man berechne

\frac{d^{2}}{dt^{2}} f(x(t))|_{t=0}

unter Benutzung der Kuhn-Tucker-Bedingung.

Optimierung II

Übungsblatt 6 , Abgabe: 15.06.1989 , 10.00 Uhr

Aufgabe 20: (2+3+3 Punkte) Gegeben sei das parameterabhngige Optimierungsproblem

min {f(x, ϵ) | g(x, ϵ) ≤ 0} , ϵ = (ϵ_{1}, ϵ_{2}) ∈ R^{2}, ϵ_{1} > 0 ,
f(x, ϵ) = x_{1} + ϵ_{2}x_{2} ,  g(x, ϵ) = x_{1}^{2} + x_{2}^{2} − ϵ_{1}^{2} .

(a) Berechnen Sie die optimale Lsung x = x(ϵ) und den zugehrigen Multiplikator λ = λ(ϵ).

(b) Skizzieren Sie die Niveaulinien des optimalen Wertes f(x(ϵ), ϵ) = const. und verifizieren Sie die Schattenpreisformel in (6.18)(ii).

(c) Geben Sie die Matrizen A_{0} und B_{0} in (6.18)(i) an und verifizieren Sie (dx/dϵ, dλ/dϵ)^{T} = −A_{0}^{−1}B_{0} durch Einsetzen der Lsungen x(ϵ), λ(ϵ) aus (a).

\underline{Hinweis:}

A_{0}^{−1} = \frac{1}{2ϵ_{1}^{2}} ( \begin{matrix}\frac{x_{2}^{2}}{λ} & −\frac{x_{1}x_{2}}{λ} & x_{1} \\ −\frac{x_{1}x_{2}}{λ} & \frac{x_{1}^{2}}{λ} & x_{2} \\ x_{1} & x_{2} & −λ \end{matrix} )

Aufgabe 21: (4 Punkte) Gegeben sei das Strungsproblem (6.4)

(P_{ϵ})  min_{x∈Rn} {f(x, ϵ) | g(x, ϵ) ∈ K} , ϵ ∈ R^{p} ,

mit C^{1}-Abbildungen f, g. Es existiere eine Umgebung E ⊂ R^{p} von ϵ = 0 und eine C^{1}-Abbildung x(·) : E → R^{n} mit:

(a) x(ϵ) ist lokale Minimalstelle von (P_{ϵ}) fr ϵ ∈ E,

(b) fr \overline{x} = x(0) ist Λ(\overline{x}) = \{\overline{λ}\} einpunktig.

Man beweise die \underline{Schattenpreisformel}

\frac{df(x(ϵ), ϵ)}{dϵ}|_{ϵ=0} = L_{ϵ}(\overline{x}, \overline{λ}, 0) .

\underline{Hinweis:} Untersuchen Sie die Funktion F (ϵ) = \overline{λ}(g(x(ϵ), ϵ) − g(\overline{x}, 0)) in E.

Programmieraufgaben zur Optimierung II

Übungsblatt 1 , Abgabe: 26.06.1989 , 10.00 Uhr

Zur Lösung der nachfolgenden Aufgaben benutze man die FORTRAN-Programme der IMSL-Bibliothek:

(1) \underline{Quadratische Optimierung:} DQPROG, S. 892-894.

(2) \underline{Nichtlineare Optimierung:} DNCONF, S. 895-902; DNCONG, S. 903-908.

Die Aufgaben sind entnommen aus (HI) D.M. HIMMELBLAU: Applied Nonlinear Programming, McGraw-Hill, 1972.

Aufgabe 1: (HI), S. 405, 406, Problem 10 Für den Parameter ϵ ∈ [0, 1] sei das Problem

minimiere f(x, ϵ) := g^{T} x + x^{T} Cx + ∑_{j=1}^{5} d_{j}(ϵx_{j}^{2} + (1 − ϵ)x_{j}^{3})

unter Ax ≥ b, x ≥ 0, (x ∈ R^{5}),

gegeben mit

A = ( \begin{matrix}−16 & 2 & 0 & 1 & 0 \\ 0 & −2 & 0 & 0.4 & 2 \\ −3.5 & 0 & 2 & 0 & 0 \\ 0 & −2 & 0 & −4 & −1 \\ 0 & −9 & −2 & 1 & −2.8 \\ 2 & 0 & −4 & 0 & 0 \\ −1 & −1 & −1 & −1 & −1 \\ −1 & −2 & −3 & −2 & −1 \\ 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 1 & 1 & 1 \end{matrix} ) 10 × 5 Matrix,

\begin{aligned}b & = & (−40, −2, −0.25, −4, −4, −1, −40, −40, 5, 1)^{T} ∈ R^{10}, \\ g & = & (−15, −27, −36, −18, −12)^{T} ∈ R^{5} , \\ d & = & (d_{1},…, d_{5}) = (4, 8, 10, 6, 2) ∈ R^{5} , \end{aligned}

C = ( \begin{matrix}30 & −20 & −10 & 32 & −10 \\ −20 & 39 & −6 & −31 & 32 \\ −10 & −6 & 10 & −6 & −10 \\ 32 & −31 & −6 & 39 & −20 \\ −10 & 32 & −10 & −20 & 30 \end{matrix} )  5 × 5 Matrix .

Man berechne die optimale Lösung \overline{x} ∈ R^{5} und den optimalen Wert f(\overline{x}, ϵ) für die Parameter ϵ = 1, ϵ = \frac{1}{2}, ϵ = 0.

\underline{Hinweis:} Für ϵ = 1 erhält man ein quadratisches Optimierungsproblem mit f(\overline{x}, 1) = −29.8564. Beachten Sie die Problemstellung im IMSL-Programm QPROG!

Aufgabe 2: (HI), S. 415, Problem 16 Das Problem, die Fläche eines Sechzehnecks mit Durchmesser d = 1 zu maximieren, führt auf das Optimierungsproblem mit x ∈ R^{9}:

Maximiere f(x) = \frac{1}{2}(x_{1}x_{4} − x_{2}x_{3} + x_{3}x_{9} − x_{5}x_{9} + x_{5}x_{8} − x_{6}x_{7})

unter  1 − x_{3}^{2} − x_{4}^{2} ≥ 0
1 − x_{9}^{2} ≥ 0
1 − x_{5}^{2} − x_{6}^{2} ≥ 0
1 − x_{1}^{2} − (x_{2} − x_{9})^{2} ≥ 0
1 − (x_{1} − x_{5})^{2} − (x_{2} − x_{6})^{2} ≥ 0
1 − (x_{1} − x_{7})^{2} − (x_{2} − x_{8})^{2} ≥ 0
1 − (x_{3} − x_{5})^{2} − (x_{4} − x_{6})^{2} ≥ 0
1 − (x_{3} − x_{7})^{2} − (x_{4} − x_{8})^{2} ≥ 0
1 − x_{7}^{2} − (x_{8} − x_{9})^{2} ≥ 0
x_{1}x_{4} − x_{2}x_{3} ≥ 0
x_{3}x_{9} ≥ 0
− x_{5}x_{9} ≥ 0
x_{5}x_{8} − x_{6}x_{7} ≥ 0
x_{9} ≥ 0

\underline{Hinweis:} Zum optimalen Funktionswert

f(\overline{x}) = 0.866025

gehören \underline{zwei} optimale Lösungen \overline{x} ∈ R^{9} mit \overline{x}_{i} = \overline{x}_{i+4}, i = 1, 2, 3, 4. Man finde beide Lösungen mit Startdaten: x_{i} ∈ [0, 1], i = 1,…, 9.

Aufgabe 3: (HI), S. 395, 396, Probleme 4, 4a Nach der Theorie von GIBBS befindet sich ein chemisches System dann im Gleichgewicht, wenn die freie Energie des Systems

f(x) := ∑_{j=1}^{n} x_{j} [c_{j} + ℓn \frac{x_{j}}{∑_{j=1}^{n} x_{j}} ]

x_{j} : Anzahl der Mole der j-ten Komponente des Systems,
c_{j} : konstant bei gegebenem Druck und gegebener Temperatur,

minimal ist unter zusätzlichen Massen-Bilanzgleichungen. Für das System \frac{1}{2}N_{2}H_{4} + \frac{1}{2}O_{2} erhält man das Optimierungsproblem mit x ∈ R^{10}:

Minimiere  f(x)
unter  g_{1}(x) = x_{1} + 2x_{2} + 2x_{3} + x_{6} + x_{10} − 2 = 0 ,
g_{2}(x) = x_{4} + 2x_{5} + x_{6} + x_{7}  − 1 = 0 ,
g_{3}(x) = x_{3} + x_{7} + x_{8} + 2x_{9} + x_{10} − 1 = 0 ,
x ≥ 0 ,

(das Atomgewicht von H, N, 0 ist 2, 1, 1)

\underline{Konstanten:}

c_{1} = −6.089,  c_{2} = −17.164, c_{3} = −34.054, c_{4} = −5.914 ,
c_{5} = −24.721,  c_{6} = −14.986, c_{7} = −24.100, c_{8} = −10.708 ,
c_{9} = −26.662, c_{10} = −22.179.

(a) Lösen Sie das Problem mit der Beschränkung x_{j} ≥ 1. E − 4, j = 1,…, 10, und ersetzen Sie x_{j} durch |x_{j}|. Startwerte: x_{j} ∈ [0.05, 0.5], j = 1,…, 10, Optimaler Wert: f(\overline{x}) = −47.76.

(b) Führen Sie die neuen Variablen y ∈ R^{10} ein durch

x_{i} = exp(y_{i}) ≥ 0 ,  j = 1,…, 10  ,

und lösen Sie das resultierende Optimierungsproblem bzgl. y. Startwerte: y_{j} ∈ [−2., −3.], j = 1,…, 10. Benutzen sie das Programm DNCONG.

Programmieraufgaben zur Optimierung II

Übungsblatt 2 , Abgabe: 04.07.1989 , 10.00 Uhr

Aufgabe 4: Gegeben sei das in Beispiel (7.4) betrachtete diskrete dynamische Optimierungsproblem (optimale Lagerhaltung):

Minimiere ∑_{j=1}^{N}(y_{j−1}^{2} + y_{j−1} + z_{j−1} + 0.1v_{j}^{2} + v_{j} + 2w_{j}^{2})

unter y_{j} = y_{j−1} +  v_{j} − d_{j} ,
z_{j} = z_{j−1} + w_{j} ,
v_{j} ≤ z_{j−1}  ,
0 ≤ y_{j} ≤  10  ,  (j = 1,…, N)
0 ≤ z_{j}  ≤  50  ,
0 ≤ v_{j} ≤  50  ,
−5 ≤ w_{j} ≤  5  ,
y_{0} = 0  , z_{0} = 40  .

Die Nachfrage sei (d_{j}) = (30, 40, 50, 30,…). Berechnen Sie die optimale Lsung fr N = 3, 4 mit dem IMSL - Programm DNCONF bzw. DN2ONF. berlegen sie dazu, da die Restriktionen 0 ≤ v_{j} ≤ 50, 0 ≤ z_{j} (j = 1, 2, 3, 4) in den brigen Restriktionen enthalten sind. *\underline{Freiwillige Kontrolle:} Prfen Sie fr N = 3 die adjungierte Gleichung

λ_{j−1} = −H_{jx}(\overline{x}_{j−1}, \overline{u_{j}}, λ_{j}, μ_{j}) , j = 3, 2 ,

in Satz (8.3)(b) \underline{explizit} nach. Beachten Sie dabei das Vorzeichen der Restriktionen g_{j}(x) ≥ 0 (j = m_{e} + 1,…, m) in DNCONF.