Beweis zu Minima

10.11.2011, 15:28

Ruud

Beweis zu Minima

Meine Frage:
Hallo ich habe folgendes Problem:

Gegeben seien M c R^n und f: R^n -> R. Dann gilt:

Für alle a < 0, b Element von R:

min (a*f(x) + b) = a (max f(x)) + b. x Element von M

Meine Ideen:
Meine Idee war folgende:

Definiere g(x) := a * f(x) x element M
und h(x) := b y element M

-> min (a*f(x) + b) = min (g(x) + h(x)) = min g(x) + min h(x)

Da h(x) = b eine Konstante ist die immer den gleichen Wert hat folgt
min h(x) = b

min g(x) = - max (-g(x)) = - max (-a * f(x)) für a < 0
<-> - max (a * f(x)) für a > 0

Definiere: k (x') = a * x' a > 0. Da k(x') offensichtlich eine streng monoton wachsende Funktion ist.

Anwendung: max (a * f(x)) <-> a * max f(x))

-> - max (a * f(x)) = - a * max (f(x)) a > 0 <->
a * max (f(x)) a < 0

-> Zusammengebaut: min (a*f(x) + b) = a (max f(x)) + b.

Ist meine Lösung so korrekt oder gibts da ein Problem der Menge M oder sind iwelche Umformungen nicht logisch schlüssig ?

10.11.2011, 22:50

Abakus

Auf diesen Beitrag antworten »

RE: Beweis zu Minima
Hallo,

ohne LateX ist das kaum zu lesen. Mir ist aufgefallen, dass du die Existenz des Minimums voraussetzt, was passiert, wenn es nicht existiert?

Ansonsten, versuche den Beweis kürzer zu fassen. Lässt sich das b zB nicht rausziehen und das einfach begründen?

Abakus smile

11.11.2011, 11:32

Ehos

Auf diesen Beitrag antworten »

RE: Beweis zu Minima
Zum Beweis erinnere ich an die Definitionen eines Maximums bzw. Minimums.

Definition:
Eine beliebige Funktion $\begin{eqnarray*} h(x) \end{eqnarray*}$ hat bei $\begin{eqnarray*} x_0 \end{eqnarray*}$ ein Maximum/Minimum, wenn um diese Stelle eine Kugelumgebung exitistiert, in der alle Funktionswerte kleiner/größer sind als $\begin{eqnarray*} h(x_0) \end{eqnarray*}$ . Für beliebige Einheitsvektoren $\begin{eqnarray*} \vec n \end{eqnarray*}$ und genügend kleine $\begin{eqnarray*} \epsilon \end{eqnarray*}$ gilt also

Maximum: $\begin{eqnarray*} h(x_0)>h(x_0+\vec n\epsilon) \end{eqnarray*}$
Maximum: $\begin{eqnarray*} h(x_0)<h(x_0+\vec n\epsilon) \end{eqnarray*}$

Satz:
Für alle a<0 und beliebige b gilt

$\begin{eqnarray*} \text{Min}[a \cdot f(x)+b]=a \cdot \text{Max}[f]+b \end{eqnarray*}$

Beweis:
Wir setzen voraus, dass die Funktion $\begin{eqnarray*} a\cdot f(x)+b \end{eqnarray*}$ bei $\begin{eqnarray*} x_0 \end{eqnarray*}$ ein Minimum hat, also

$\begin{eqnarray*} \text{Min}[a\cdot f(x)+b]=a\cdot f(x_0)+b \end{eqnarray*}$ (Gleichung *)

Wendet man also obige Definition eines Minimums an, ist dies gleichbedeutend mit

$\begin{eqnarray*} a\cdot f(x_0)+b<a \cdot f(x_0+\vec n\epsilon)+b \end{eqnarray*}$

Wir subtrahieren auf beiden Seiten b

$\begin{eqnarray*} a\cdot f(x_0)<a \cdot f(x_0+\vec n\epsilon) \end{eqnarray*}$

Wir dividieren beide Seiten durch a, wobei sich wegen a<0 das Zeichen < umkehrt zu >, also

$\begin{eqnarray*} f(x_0)>f(x_0+\vec n\epsilon) \end{eqnarray*}$

Laut obiger Definition des Maximums bedeutet dies, dass f(x) bei $\begin{eqnarray*} x_0 \end{eqnarray*}$ ein Maximum besitzt, also

$\begin{eqnarray*} \text{Max}[f(x)]=f(x_0) \end{eqnarray*}$

Wir multiplizieren dies mit a und addieren b

$\begin{eqnarray*} a\cdot \text{Max}[f(x)]+b=a\cdot f(x_0)+b \end{eqnarray*}$

Dies setzen wir mit (Gleichung *) gleich und haben damit die gewünschte Aussage bewiesen.

11.11.2011, 13:12

Ruud

Auf diesen Beitrag antworten »

Oh Danke für den sehr ausführlichen Beweis. Ist meine Lösung dann mathematisch falsch? Bzw an welcher Stelle verhalte ich mich nicht mehr nach den Spielregeln eines Beweises?

Entschuldigt die Darstellung, beim nächsten mal verwende ich LateX =)

11.11.2011, 20:22

Abakus

Auf diesen Beitrag antworten »

Zur Lösung von Ehos 2 Bemerkungen:

- zum einen ist der Ausgangspunkt ein strenges Minimum (ein Minimum und alle Werte in einer Umgebung sind echt größer). Das kann so sein, muss aber nicht.

- zum anderen geht es um das Minimum auf der Menge M, und da können noch andere Dinge passieren als nur in einer (kleinen) lokalen Umgebung (die ja noch nicht mal in M enthalten sein muss).

Es geht wohl so dennoch, aber ein bisschen Nachdenken ist noch dabei.

@ Ruud: ich freue mich auf dein LaTeX Augenzwinkern

, hier nur mal deinen ersten Teil betrachtet:

Zitat:

Meine Idee war folgende:

Definiere g(x) := a * f(x) x element M

und h(x) := b y element M

-> min (a*f(x) + b) = min (g(x) + h(x)) = min g(x) + min h(x)

Was ist das y? Das führt schon dazu, dass dein h in der Luft schwebt (vermutlich nur Schreibfehler, aber sollen wir raten?). Dann dein letztes "=", in der du das Minimum auseinanderziehst, das geht so nicht:

$\begin{eqnarray*} 0 = min \{x - x : x \in [0, 1]\} \neq min \{x : x \in [0, 1]\} + min \{- x : x \in [0, 1]\} = 0 - 1 = -1 \end{eqnarray*}$

usw.

Abakus smile

13.11.2011, 20:30

Ruud

Auf diesen Beitrag antworten »

Gegeben seien :
$\begin{eqnarray*} M \subset \mathbb R^{n} \end{eqnarray*}$ und $\begin{eqnarray*} f: \mathbb R^{n} -> \mathbb R . \end{eqnarray*}$

Dann gilt: $\begin{eqnarray*} \forall a < 0, b \in \mathbb R \end{eqnarray*}$
$\begin{eqnarray*} min (a*f(x) + b) = a *(max f(x)) + b. \end{eqnarray*}$ $\begin{eqnarray*} x \in M \end{eqnarray*}$

Meine Idee war folgende:
Definiere:
$\begin{eqnarray*} g(x) := a * f(x) \end{eqnarray*}$ $\begin{eqnarray*} x \in M \end{eqnarray*}$
$\begin{eqnarray*} h(y) := b \end{eqnarray*}$ $\begin{eqnarray*} y \in 1 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow min (a*f(x) + b) = min (g(x) + h(y)) = min (g(x)) + min (h(y)) \end{eqnarray*}$

Da h(y) = b eine Konstante ist die immer den gleichen Wert hat folgt:
min (h(y)) = b

$\begin{eqnarray*} min g(x) = - max(-g(x)) = -max (-a * f(x)) \end{eqnarray*}$ $\begin{eqnarray*} \forall a < 0 \end{eqnarray*}$
<-> $\begin{eqnarray*} max (a * f(x)) \end{eqnarray*}$ $\begin{eqnarray*} \forall a > 0 \end{eqnarray*}$

Definiere:
$\begin{eqnarray*} k (x') = a * x' a > 0 \end{eqnarray*}$ .
Da k(x') offensichtlich eine streng monoton wachsende Funktion ist.

Anwendung: $\begin{eqnarray*} max (a * f(x)) \end{eqnarray*}$ <-> $\begin{eqnarray*} a * max (f(x)) \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow - max (a * f(x)) = - a * max (f(x)) a > 0 \end{eqnarray*}$
<-> $\begin{eqnarray*} a * max (f(x)) \forall a < 0 \end{eqnarray*}$

Zusammengebaut:
$\begin{eqnarray*} min (a*f(x) + b) = a (max f(x)) + b. \end{eqnarray*}$

Es kann übrigens davon ausgegangen werden, dass die jeweiligen Minima existieren.

Es ist außerdem noch z.Z., dass die lokalen / bzw. globalen Optimalpunkte überein stimmen.

13.11.2011, 20:43

Ruud

Auf diesen Beitrag antworten »

Ich hoffe, dass ist jetzt besser so.

Ich glaube, ich erkenne die Schwachstellen meines Beweises mit dem h(y). Mein Gedankengang war halt der, dass ich den Term reduzieren kann, sodass ich folgende Formel anwenden kann:

Es seien $\begin{eqnarray*} X \subset \mathbb R^{n}, Y \subset \mathbb R^{m}, f: X -> \mathbb R \end{eqnarray*}$ und $\begin{eqnarray*} g: Y -> \mathbb R \end{eqnarray*}$

Dann gilt:

$\begin{eqnarray*} min (f(x) + g(y)) = min (f(x)) + min (g(y)) \end{eqnarray*}$
$\begin{eqnarray*} (x,y) \in X \end{eqnarray*}$ x $\begin{eqnarray*} Y ............ x \in X .......... y \in Y \end{eqnarray*}$

15.11.2011, 00:09

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Ruud
Meine Idee war folgende:
Definiere:
$\begin{eqnarray*} g(x) := a * f(x) \end{eqnarray*}$ $\begin{eqnarray*} x \in M \end{eqnarray*}$
$\begin{eqnarray*} h(y) := b \end{eqnarray*}$ $\begin{eqnarray*} y \in 1 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow min (a*f(x) + b) = min (g(x) + h(y)) = min (g(x)) + min (h(y)) \end{eqnarray*}$

OK, vorher habe ich deine Schreibweise falsch gelesen und völlig falsch verstanden, weil Kommas usw. fehlen.

Also du sollst etwas zeigen und definierst es dann mit anderen Bezeichnungen. Dafür soll es dann plötzlich ohne Beweis gelten und dann schreibst du es wieder zurück?

Es ist doch in diesem Spezialfall gerade zu beweisen, dass du das Minimum auseinanderziehen kannst.

Meine Idee wäre eher, die beiden Richtungen ">=" und "<=" zu zeigen.

Abakus smile

18.11.2011, 10:14

Ruud

Auf diesen Beitrag antworten »

Ah okay. Das geht natürlich nicht =)
Ich habe den Gedankengang von Ehos mal nachvollzogen, der erschien mir logisch schlüssig. Das kann man ja dann einmal für lokale Minima bzw globale Minima zeigen. Vielen Dank euch!

Neue Frage »

Antworten »

Beweis zu Minima

Verwandte Themen