\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

\thispagestyle{empty}

\title{}
\author{}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{../#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\noindent §58: EXTREMA MIT NEBENBEDINGUNGEN \\[0.8cm]
58.1 Motivation: \\
In §57  haben wir notwendige und hinreichende Kriterien kennengelernt, um lokale Extrema einer Funktion mehrerer Variablen zu bestimmen. Oft
sucht man jedoch auch Extrema einer Funktion unter der Einschränkung, dass bestimmte Nebenbedingungen erfüllt sein müssen. \\[0.5cm]
58.2 Beispiel: \glqq Verpackungsminimierung\grqq\ im $\SetR^2$ \\
Gesucht ist ein Rechteck maximalen Inhalts bei einem vorgegebenen Umfang $u$. \\
D.h. maximiere
$$f(x,y) = x \cdot y \quad \text{(} x,y \text{: Seitenlängen)}$$
unter der Nebenbedingung
$$g(x,y) = 2x +2y - u = 0$$ \\[0.3cm]
Lösungsmöglichkeit 1: (spezieller) \\
Löse die Nebenbedingung nach einer Variablen auf:
$$2y = u - 2x \Rightarrow y = \frac{u}{2} - x \quad (*)$$
Setze dies in $f(x,y) = x \cdot y$ ein. Damit lautet das neue Optimierungsproblem: \\
maximiere $$\tilde{f}(x) = x \left( \frac{u}{2} - x \right)$$
d.h. die Nebenbedingung reduziert die Freiheitsgrade (Variablen) von 2 auf 1. \\
Notwendige Bedingung für ein Maximum:
$$0 \stackrel{!}{=} \tilde{f}'(x) = \frac{u}{2} - 2x \Rightarrow x = \frac{u}{4}$$
in $(*)$: $\displaystyle y = \frac{u}{4}$ \\
Da $\displaystyle \tilde{f}'' \left(\frac{u}{4} \right) = -2 < 0$ ist, handelt es sich tatsächlich um ein Maximum. Das optimale Rechteck ist somit ein
Quadrat mit Seitenlänge $\displaystyle \frac{u}{4}$. \\
Bemerkung: \\
Diese Lösungsmöglichkeit setzt voraus, dass wir die Nebenbedingung nach einer Variablen auflösen können. Falls dies nicht möglich ist, bietet sich die
folgende Lösungsmöglichkeit an: \\[0.3cm]
Lösungsmöglichkeit 2: (allgemeiner) \\
Wir maximieren eine erweiterte Zielfunktion, in die die Nebenbedingung bereits eingearbeitet ist
\begin{eqnarray*}
	F( x,y,\lambda ) & := & f(x,y) + \lambda g(x,y) \\
	& = & x \cdot y + \lambda (2x+2y-u)
\end{eqnarray*}
mit einer zusätzlichen Variablen $\lambda$ (Lagrange-Multiplikator). \\
Notwendige Bedingung für ein Maximum
$$0 = \left( \begin{array}{c}F_x \\ F_y \\ F_z\end{array} \right) = \left( \begin{array}{c}y + 2\lambda \\ x + 2\lambda \\ 2x+2y-u\end{array} \right)$$
Wir sehen: Die dritte Gleichung drückt die Nebenbedingung $g(x,y) = 0$ aus. \\
Auflösen der 1. und 2. Gleichung nach $\lambda$:
$$
	\left. \begin{array}{l}x = -2 \lambda \\ y = -2 \lambda\end{array} \right\} \Rightarrow x = y
$$
Einsetzen in 3. Gleichung: $$4x -u = 0 \Rightarrow x = \frac{u}{4} = y$$
Mit Zusatzüberlegung zeigt man, dass tatsächlich ein Maximum vorliegt. \\[0.5cm]
58.3 Allgemeine Vorgehensweise \\
Sei $D \subset \SetR^n$ offen und $f: D \to \SetR$. Wir suchen Extrema von $f(x) = f(x_1, ..., x_n)$ unter den $m$
Nebenbedingungen
$$
	\left. \begin{array}{c} g_1(x_1, ..., x_n) = 0 \\ \vdots \\ g_m(x_1, ..., x_n) = 0\end{array} \right\} g(x) = 0
$$
mit $m<n$. \\
Statt der $m$ Nebenbedingungen $g(x) = 0$ führen wir $m$ zusätzliche Variablen $(\lambda_1, ..., \lambda_m)^T =: \lambda$ ein (sogenannte
Lagrange-Multiplikatoren) und maximieren / minimieren statt $f(x,y)$ die Lagrange-Funktion $F(x,\lambda) = f(x) + \lambda^T \cdot g(x)$. \\
Damit haben wir ein Extremalproblem mit $n$ Variablen und $m$ Nebenbedingung in ein Extremalproblem mit $n+m$ Variablen ohne explizite Nebenbedingungen
umgewandelt. \\[0.5cm]
58.4 Bemerkung: \\
Man kann zeigen, dass der Ansatz 58.3 funktioniert. \\
Sei $D \subset \SetR^n$ offen und seien $f,g_1, ..., g_m: D \to \SetR$ $C^1$-Funktionen. Ferner sei $\xi \in D$ ein lokales Extremum von
$f(x)$ und der Nebenbedingung $g(x) = 0$, und es gelte die \glqq Regularitätsbedingung\grqq\ $rang(Jg(\xi)) = m$. Dann existieren
Lagrange-Multiplikatoren $\lambda_1, ... \lambda_m$, sodass die Lagrange-Funktion $F(x) = f(x) + \lambda^T g(x)$ die notwendige Bedingung
$\nabla F(\xi) = 0$ erfüllt. \\[0.5cm]
58.5 Beispiel \\
Sei $A \in \SetR^{n \times n}$ symmetrisch. Bestimme die Extrema der quadratischen Form $x^TAx$ unter der Nebenbedingung $|x| = 1$. \\
Lösung:
\begin{eqnarray*}
	F(x, \lambda) & = & x^TAx + \lambda(1-x^Tx) \\
	& = & \sum_{i,j=1}^n x_i x_j a_{ij} + \lambda \left( 1-\sum_{i=1}^n x_i^2 \right)
\end{eqnarray*}
Notwendige Bedingung:
$$0 \stackrel{!}{=} \nabla^T F = (F_{x_1}, ..., F_{x_n}, F_\lambda)$$
Mit
$$\frac{\partial}{\partial x_k} \sum_{i,j=1}^n x_i x_j a_{ij} = \sum_{j=1}^n x_i a_{kj} + \sum_{i=1}^n x_i \underbrace{a_{ik}}_{a_{ki}} = 2 \sum_{j=1}^n x_j a_{kj}$$
folgt:
$$0 = \left( \begin{array}{c}F_{x_1} \\ \vdots \\ F_{x_n} \\ F_\lambda\end{array} \right) = \left( \begin{array}{c}2 \sum_{j=1}^n a_{1j}x_j - 2\lambda x_1 \\ \vdots \\ 2\sum_{j=1}^n a_{nj} x_j - 2\lambda x_n \\ 1-\sum_{i=1}^n x_i^2\end{array} \right)$$
Die Gleichungen $1$ bis $n$ besagen, dass $x$ Eigenvektor von $A$ zum Eigenwert $\lambda$ ist:
$$\sum_{j=1}^n a_{kj} x_j = \lambda x_k \quad (k=1,...,n)$$
Gleichung $n+1$ fordert, dass $|x|$ auf $1$ normiert ist. Für einen Eigenvektor $x$ mit $|x|=1$ gilt:
$$f(x) = x^TAx = x^T \lambda x = \lambda$$
Somit wird $F(x)$ durch den Eigenvektor zum größten (kleinsten) Eigenwert von $A$ maximiert (minimiert). \\
In der Informatik benötigt man dieses Resultat z.B. bei der Bewegungsanalyse in digitalen Bildfolgen. \\
58.6 Beispiel: \\
Bestimme eine notwendige Bedingung für das Vorliegen von Extrema von
$$f(x,y,z) = 5x+y-3z$$
auf dem Schnitt der Ebene
$$x+y+z=0$$
mit der Kugeloberfläche
$$x^2+y^2+z^2 = 1$$
Lösung: \\
Die Lagrange-Funktion lautet
$$F(x,y,z,\lambda, \mu) = 5x+y-3z + \lambda (x+y+z) + \mu (x^2+y^2+z^2-1)$$
$$0 = \left( \begin{array}{c}F_x \\ F_y \\ F_z \\ F_\lambda \\ F_\mu\end{array} \right) = \left( \begin{array}{c}5 + \lambda + 2\mu x \\ 1 + \lambda + 2\mu y \\ -3 + \lambda + 2\mu z \\ x + y + z \\ x^2 + y^2 + z^2 - 1\end{array} \right)$$
5 Gleichungen mit 5 Unbekannten. \\
Nach einigen Umformungen ergibt sich, dass
$$\left( \begin{array}{c}x \\ y \\ z \\ \lambda \\ \mu\end{array} \right) = \left( \begin{array}{c}\frac{1}{\sqrt{2}} \\ 0 \\ -\frac{1}{\sqrt{2}} \\ 1 \\ -2 \sqrt{2}\end{array} \right) \quad \text{und} \quad \left( \begin{array}{c}x \\ y \\ z \\ \lambda \\ \mu\end{array} \right) = \left( \begin{array}{c}-\frac{1}{\sqrt{2}} \\ 0 \\ \frac{1}{\sqrt{2}} \\ 1 \\ 2 \sqrt{2}\end{array} \right)$$
dieses Gleichungssystem lösen.

\end{document}