Konvexe Funktionen

03.06.2013, 16:51

10001000Nick1

Konvexe Funktionen

Meine Frage:
Hallo,

ich habe mal eine Frage zu einem Beweis aus der Analysis-Vorlesung.
Wir wollten beweisen, dass für $\begin{eqnarray*} f\in C^1(\Omega), \Omega\subseteq\mathbb{R}^n \end{eqnarray*}$ offen und konvex, gilt:
$\begin{eqnarray*} \text{f ist konvex} \Rightarrow f(y)\geq f(x)+Df(x)\cdot (y-x)^T\quad \forall x,y\in\Omega. \end{eqnarray*}$

Meine Ideen:
Im Beweis haben wir geschrieben: Wir reduzieren die Aussage auf den 1-dimensionalen Fall (n=1).
Betrachte die Funktion $\begin{eqnarray*} \varphi:[0,1]\to\mathbb{R}, \varphi(t):=(1-t)f(x)+tf(y)-f((1-t)x+ty). \end{eqnarray*}$

f konvex $\begin{eqnarray*} \Rightarrow \varphi(t)\geq 0\quad \forall t\in[0,1], \varphi(0)=f(x)-f(x)=0. \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow\varphi'(0)\geq 0 \end{eqnarray*}$ (falls nicht, dann $\begin{eqnarray*} \exists \delta>0 \end{eqnarray*}$ , so dass $\begin{eqnarray*} \varphi(t)<0 \quad \forall t\in[0,\delta] \end{eqnarray*}$ )

$\begin{eqnarray*} \Rightarrow 0\leq \varphi'(0)=-f(x)+f(y)-Df(x)\cdot (-x+y)^T \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow f(y)\geq f(x)+Df(x)\cdot (y-x)^T \end{eqnarray*}$ .

Meine Frage: Warum darf man das einfach auf den eindimensionalen Fall reduzieren?

Zweiten Beitrag hier reinkopiert und gelöscht. Steffen

OK, ich glaube, das ist so gemeint, dass man mit $\begin{eqnarray*} f \end{eqnarray*}$ die eindimensionale Funktion $\begin{eqnarray*} \varphi \end{eqnarray*}$ konstruiert, die Funktion $\begin{eqnarray*} f \end{eqnarray*}$ darf selbst aber trotzdem mehrdimensional sein.

Könnte mir dann vielleicht jemand bei den folgenden Aufgaben helfen?
Sei $\begin{eqnarray*} \Omega \subseteq \mathbb{R}^n \end{eqnarray*}$ offen und konvex, $\begin{eqnarray*} f\in C^1(\Omega). \end{eqnarray*}$

a) Zeigen Sie: $\begin{eqnarray*} f(y)\geq f(x)+Df(x)\cdot (y-x)^T\quad \forall x,y \in \Omega \Rightarrow (Df(y)-Df(x))\cdot (y-x)^T\geq 0 \quad \forall x,y \in \Omega \end{eqnarray*}$

b) Zeigen Sie: $\begin{eqnarray*} (Df(y)-Df(x))\cdot (y-x)^T\geq 0 \quad \forall x,y \in \Omega \Rightarrow \text{f ist konvex.} \end{eqnarray*}$

Für den eindimensionalen Fall dürfen wir diese Aussagen als bekannt voraussetzen.

Muss ich das auch mit dieser Funktion $\begin{eqnarray*} \varphi \end{eqnarray*}$ machen?

05.06.2013, 17:59

tmo

Auf diesen Beitrag antworten »

Erstmal zur Notation: Ich bin ein bisschen erstaunt über die Notation $\begin{eqnarray*} Df(x) \cdot v^T \end{eqnarray*}$ .

$\begin{eqnarray*} Df(x) \end{eqnarray*}$ ist ja ein Zeilenvektor (Jacobimatrix an der Stelle x). An einen solchen multipliziert man einen Spaltenvektor. Und normalerweise ist $\begin{eqnarray*} v = y-x \end{eqnarray*}$ doch ein Spaltenvektor, d.h. warum transponiert ihr nochmal? verwirrt

Dann zu den Beweisen:

Zunächst mal zum obigen Beweis: Ja du hast das schlussendlich richtig erkannt. $\begin{eqnarray*} f \end{eqnarray*}$ ist eine Funktion in mehreren Veränderlichen und $\begin{eqnarray*} \varphi \end{eqnarray*}$ jedoch nur in einer Veränderlichen, nämlich $\begin{eqnarray*} t \end{eqnarray*}$ .

Dann zur a): Vertausche in der Vorraussetzung einfach mal x und y. Dann erhältst du ja eine weitere Ungleichung. Dann addiere einfach beide.

05.06.2013, 18:31

10001000Nick1

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Erstmal zur Notation: Ich bin ein bisschen erstaunt über die Notation $\begin{eqnarray*} Df(x) \cdot v^T \end{eqnarray*}$ .

$\begin{eqnarray*} Df(x) \end{eqnarray*}$ ist ja ein Zeilenvektor (Jacobimatrix an der Stelle x). An einen solchen multipliziert man einen Spaltenvektor. Und normalerweise ist $\begin{eqnarray*} v = y-x \end{eqnarray*}$ doch ein Spaltenvektor, d.h. warum transponiert ihr nochmal? verwirrt

Das liegt daran, dass wir folgendes definiert haben: $\begin{eqnarray*} \mathbb{R}^m=\left\{(x_1,...x_m)|x_i\in\mathbb{R}\quad\forall i\in\{1,...m\}\right\} \end{eqnarray*}$ und $\begin{eqnarray*} {\mathbb{R}^m}^*=\left\{ \begin{pmatrix} x_1 \\ \vdots \\ x_m \end{pmatrix}\Bigg| x_i\in\mathbb{R}\quad\forall i\in\{1,...m\}\right\} . \end{eqnarray*}$ Da $\begin{eqnarray*} x,y\in\Omega\subseteq \mathbb{R}^n \end{eqnarray*}$ ist, sind ja dann x und y und (y-x) Zeilenvektoren. Und da Df(x) bzw. Df(y) Zeilenvektoren sind, muss man (y-x) transponieren, damit man das dann multiplizieren kann.

OK, a) ist wirklich einfach mit deinem Tipp. Bloß, erst mal auf diesen Tipp zu kommen, ist schon etwas schwieriger...
Braucht man bei a) eigentlich die Voraussetzung, dass $\begin{eqnarray*} \Omega \end{eqnarray*}$ konvex ist? Das habe ich doch gar nicht verwendet, oder?

05.06.2013, 18:58

tmo

Auf diesen Beitrag antworten »

Komische Definitionen habt ihr da... verwirrt

Insbesondere sind bei euch die Ableitungen von reellwertigen Funktionen keine Linearformen (also Elemente des Dualraums), sondern Vektoren. Naja egal...

Die b) kriegst du so:

Betrachte $\begin{eqnarray*} \psi = - \varphi \end{eqnarray*}$ (wobei $\begin{eqnarray*} \varphi \end{eqnarray*}$ wie da oben aus dem Beweis ist). Es ist ja dann $\begin{eqnarray*} \psi(t) \leq 0 \end{eqnarray*}$ zu zeigen.

Zeige $\begin{eqnarray*} (\psi'(t_1)-\psi'(t_2))(t_1-t_2) \geq 0 \end{eqnarray*}$ . Da du den eindimensionalen Fall benutzen darfst, ist $\begin{eqnarray*} \psi \end{eqnarray*}$ also konvex.

Wegen $\begin{eqnarray*} \psi(1)=\psi(0) = 0 \end{eqnarray*}$ folgt dann das Gewünschte.

05.06.2013, 19:47

10001000Nick1

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \psi(t)=-(1-t)f(x)-tf(y)+f((1-t)x+ty) \end{eqnarray*}$

$\begin{eqnarray*} (\psi'(t_1)-\psi'(t_2))(t_1-t_2)=(Df((1-t_1)x+t_1y)(y-x)^T-Df((1-t_2)x+t_2y)(y-x)^T)(t_1-t_2) \end{eqnarray*}$

$\begin{eqnarray*} = (Df((1-t_1)x+t_1y)-Df((1-t_2)x+t_2y))(y-x)^T(t_1-t_2)= (Df(\textcolor{red}{x}+t_1(y-x))-Df(\textcolor{red}{x}+t_2(y-x))(t_1(y-x)-t_2(y-x))^T \end{eqnarray*}$

Aber was mache ich jetzt mit den roten x? Wenn die wegfallen würden, wäre das ja laut Voraussetzung größer gleich 0. Oder ist da irgendwas falsch?

05.06.2013, 20:02

tmo

Auf diesen Beitrag antworten »

Das rote x kannst du doch einfach in der rechten Klammer (die die transponiert wird) dazu schreiben. Einmal mit Plus und einmal mit Minus...

05.06.2013, 20:16

10001000Nick1

Auf diesen Beitrag antworten »

Wieso das denn? verwirrt

05.06.2013, 22:14

tmo

Auf diesen Beitrag antworten »

Die Frage ist eher: Warum nicht? Du kannst doch immer +x - x dazu schreiben. Da passiert doch nichts.

05.06.2013, 22:31

10001000Nick1

Auf diesen Beitrag antworten »

Achso, jetzt versteh ich, was du meintest. Ich dachte, ich soll die roten x da irgendwie wegnehmen und in der rechten Klammer dazuschreiben. Also so etwas ähnliches wie Ausklammern oder so.. Aber jetzt ist es ja klar.

Vielen Dank. Wink

06.06.2013, 10:15

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von 10001000Nick1
Braucht man bei a) eigentlich die Voraussetzung, dass $\begin{eqnarray*} \Omega \end{eqnarray*}$ konvex ist? Das habe ich doch gar nicht verwendet, oder?

Die Konvexität der Definitionsmenge braucht man ganz einfach dafür, dass man den Begriff "konvexe Funktion" überhaupt definieren kann, denn dort kommt ja der Ausdruck $\begin{eqnarray*} f((1-t)x+ty) \end{eqnarray*}$ vor. Man muss ja sicher stellen, dass $\begin{eqnarray*} f \end{eqnarray*}$ an dieser Stelle überhaupt definiert ist.

Neue Frage »

Antworten »

Konvexe Funktionen

Verwandte Themen