Konvexe Funktion - Convex function

Konvexe Funktion auf einem Intervall.
Eine Funktion (in Schwarz) ist genau dann konvex, wenn die Region über ihrem Graphen (in Grün) eine konvexe Menge ist .
Ein Graph der bivariaten konvexen Funktion x 2 + xy + y 2 .

In der Mathematik ist eine reellwertige Funktion wird aufgerufen , konvex , wenn das Liniensegment zwischen zwei beliebigen Punkten auf dem Graphen der Funktion nicht unter dem Diagramm zwischen den beiden Punkten liegen. Äquivalent ist eine Funktion konvex, wenn ihr Epigraph (die Menge der Punkte auf oder über dem Funktionsgraphen) eine konvexe Menge ist . Eine zweimal differenzierbare Funktion einer einzelnen Variablen ist genau dann konvex, wenn ihre zweite Ableitung auf ihrem gesamten Definitionsbereich nicht negativ ist. Bekannte Beispiele für konvexe Funktionen einer einzelnen Variablen sind die quadratische Funktion und die Exponentialfunktion . Einfach ausgedrückt bezieht sich eine konvexe Funktion auf eine Funktion, die die Form einer Tasse hat , und eine konkave Funktion hat die Form einer Kappe .

Konvexe Funktionen spielen in vielen Bereichen der Mathematik eine wichtige Rolle. Sie sind besonders wichtig bei der Untersuchung von Optimierungsproblemen , wo sie sich durch eine Reihe praktischer Eigenschaften auszeichnen. Zum Beispiel hat eine streng konvexe Funktion auf einer offenen Menge nicht mehr als ein Minimum. Auch in unendlichdimensionalen Räumen erfüllen konvexe Funktionen unter geeigneten Zusatzhypothesen weiterhin solche Eigenschaften und sind daher die am besten verstandenen Funktionale in der Variationsrechnung . In der Wahrscheinlichkeitstheorie wird eine auf den Erwartungswert einer Zufallsvariable angewendete konvexe Funktion immer nach oben durch den Erwartungswert der konvexen Funktion der Zufallsvariablen begrenzt. Dieses Ergebnis, bekannt als Jensen-Ungleichung , kann verwendet werden, um Ungleichungen wie die arithmetisch-geometrische Mittelungleichung und die Hölder-Ungleichung abzuleiten .

Definition

Visualisierung einer konvexen Funktion und der Jensen-Ungleichung

Sei eine konvexe Teilmenge eines reellen Vektorraums und eine Funktion.

Dann heißt konvex genau dann, wenn eine der folgenden äquivalenten Bedingungen erfüllt ist:

  1. Für alle :
    Die rechte Seite stellt die Gerade zwischen und in der Kurve von als Funktion der Zunahme von bis oder Abnahme von bis dar, die diese Linie überstreicht. In ähnlicher Weise stellt das Argument der Funktion auf der linken Seite die Gerade zwischen und in oder der -Achse des Graphen von So dar. Diese Bedingung erfordert, dass die Gerade zwischen einem beliebigen Paar von Punkten auf der Kurve von über oder gerade . liegt trifft die Grafik.
  2. Für alle und alle , die :
    Der Unterschied dieser zweiten Bedingung in Bezug auf die obige erste Bedingung besteht darin, dass diese Bedingung die Schnittpunkte (z. B. und ) zwischen der geraden Linie, die durch ein Paar von Punkten auf der Kurve von (die gerade Linie wird durch die rechte Seite dieser Bedingung) und die Kurve der ersten Bedingung enthält die Schnittpunkte wie sie wird oder an oder oder Tatsächlich müssen die Schnittpunkte nicht in einer konvexen Bedingung mit betrachtet werden
    weil und immer wahr sind (also nicht sinnvoll, Teil einer Bedingung zu sein).

Die zweite Aussage, die konvexe Funktionen charakterisiert, die in der reellen Geraden bewertet werden, ist auch die Aussage, die verwendet wird, um konvexe Funktionen zu definieren , die in der erweiterten reellen Zahlengeraden bewertet werden , wo eine solche Funktion einen Wert annehmen darf (aber nicht muss) . Die erste Anweisung wird nicht verwendet, weil sie es erlaubt , oder als Wert zu nehmen , in welchem ​​Fall, wenn bzw. , dann undefiniert wäre (weil die Multiplikationen und undefiniert sind). Die Summe ist auch undefiniert, so dass eine konvexe erweiterte reellwertige Funktion typischerweise nur genau einen von und als Wert annehmen darf .

Die zweite Aussage kann auch die Definition erhalten geändert werden strenge Konvexität , wobei letztere durch den Ersatz erhalten die strenge Ungleichheit Explizit die Karte heißt streng konvex , wenn und nur wenn für alle reellen und alle , so dass :

Eine streng konvexe Funktion ist eine Funktion, bei der die Gerade zwischen einem beliebigen Punktpaar auf der Kurve mit Ausnahme der Schnittpunkte zwischen der Geraden und der Kurve über der Kurve liegt.

Die Funktion heißt konkav (bzw. streng konkav ), wenn ( multipliziert mit -1) konvex (bzw. streng konvex ) ist.

Alternative Namensgebung

Der Begriff konvex wird oft als konvex nach unten oder konkav nach oben bezeichnet , und der Begriff konkav wird oft als nach unten konkav oder nach oben konvex bezeichnet . Wenn der Begriff "konvex" ohne die Schlüsselwörter "up" oder "down" verwendet wird, bezieht er sich ausschließlich auf einen becherförmigen Graphen . Als Beispiel bezieht sich Jensens Ungleichung auf eine Ungleichung, die eine konvexe oder konvexe (aufwärts) Funktion beinhaltet.

Eigenschaften

Viele Eigenschaften konvexer Funktionen haben für Funktionen vieler Variablen dieselbe einfache Formulierung wie für Funktionen einer Variablen. Siehe unten die Eigenschaften für den Fall vieler Variablen, da einige von ihnen nicht für Funktionen einer Variablen aufgeführt sind.

Funktionen einer Variablen

  • Angenommen, eine Funktion einer reellen Variablen ist auf einem Intervall definiert, und es sei
    ( Man beachte , dass die Steigung der Purpurlinie in der obigen Zeichnung ist, die Funktion
    R ist symmetrisch in Mitteln dass R nicht ändert durch Austausch und ). konvex ist , wenn und nur wenn ist monoton nicht abnehm in für jedes feste (oder umgekehrt). Diese Charakterisierung der Konvexität ist sehr nützlich, um die folgenden Ergebnisse zu beweisen.
  • Eine konvexe Funktion einer reellen Variablen, die auf einem offenen Intervall C definiert ist, ist stetig auf erlaubte linke und rechte Ableitungen , und diese sind monoton nicht abnehmend . Als Folge ist differenzierbar überhaupt aber höchstens abzählbar viele Punkte, die Menge , auf die kann aber noch dicht sein , nicht differenzierbar ist. Wenn geschlossen ist, kann es an den Endpunkten von fehlschlagen (ein Beispiel wird im Abschnitt Beispiele gezeigt ).
  • Eine differenzierbare Funktion einer Variablen ist konvex auf einem Intervall , wenn und nur wenn sein Derivat ist monoton nicht abnehm auf diesem Intervall. Wenn eine Funktion differenzierbar und konvex ist, dann ist sie auch stetig differenzierbar .
  • Eine differenzierbare Funktion einer Variablen ist auf einem Intervall genau dann konvex, wenn ihr Graph über allen ihren Tangenten liegt :
    für alle x und y im Intervall.
  • Eine zweimal differenzierbare Funktion einer Variablen ist auf einem Intervall genau dann konvex, wenn ihre zweite Ableitung dort nicht negativ ist; dies gibt einen praktischen Test für die Konvexität. Optisch "krümmt sich" eine zweifach differenzierbare konvexe Funktion nach oben, ohne Knicke in die andere Richtung ( Wendepunkte ). Wenn ihre zweite Ableitung in allen Punkten positiv ist, ist die Funktion streng konvex, aber die Umkehrung gilt nicht. Zum Beispiel ist die zweite Ableitung von is , die null ist , aber streng konvex ist.
    • Diese Eigenschaft und die obige Eigenschaft in Bezug auf "...seine Ableitung ist monoton nicht abnehmend ..." sind nicht gleich, denn wenn sie in einem Intervall nicht negativ ist, dann ist sie auf monoton nicht abnehmend, während ihre Umkehrung nicht wahr ist. zum Beispiel ist auf monoton nicht abnehmend, während seine Ableitung an einigen Stellen auf nicht definiert ist .
  • Wenn eine konvexe Funktion einer reellen Variablen, und , dann ist additiv auf den positiven reellen Zahlen , also für positive reelle Zahlen und .
Nachweisen

Da ist konvex, indem man eine der obigen konvexen Funktionsdefinitionen verwendet und daraus folgt, dass für alle reellen

Daraus folgt, dass
  • Eine Funktion ist Mittelpunkt konvex auf einem Intervall, wenn für alle
    Diese Bedingung ist nur geringfügig schwächer als die Konvexität. Zum Beispiel ist eine reellwertige messbare Lebesgue-Funktion , die Mittelpunkt-konvex ist, konvex: Dies ist ein Satz von Sierpinski . Insbesondere ist eine stetige Funktion, die konvex im Mittelpunkt ist, konvex.

Funktionen mehrerer Variablen

  • Eine in den erweiterten reellen Zahlen bewertete Funktion ist genau dann konvex, wenn ihr Epigraph
    ist eine konvexe Menge.
  • Eine auf einem konvexen Gebiet definierte differenzierbare Funktion ist genau dann konvex, wenn sie für alle im Gebiet gilt.
  • Eine zweimal differenzierbare Funktion mehrerer Variablen ist konvex auf einer konvexen Menge , wenn und nur wenn seine Hesse - Matrix der zweiten partiellen Ableitungen ist positiv semidefinite auf das Innere des konvexen Menge.
  • Für eine konvexe Funktion sind die Unterebenenmengen und with konvexe Mengen. Eine Funktion, die diese Eigenschaft erfüllt, wird als quasikonvexe Funktion bezeichnet und kann keine konvexe Funktion sein.
  • Folglich ist die Menge der globalen Minimierer einer konvexen Funktion eine konvexe Menge: - konvex.
  • Jedes lokale Minimum einer konvexen Funktion ist auch ein globales Minimum . Eine streng konvexe Funktion hat höchstens ein globales Minimum.
  • Die Jensensche Ungleichung gilt für jede konvexe Funktion . If ist eine Zufallsvariable, die Werte im Bereich von dann annimmt, wobei E die mathematische Erwartung bezeichnet . Tatsächlich sind konvexe Funktionen genau diejenigen, die die Hypothese der Jensenschen Ungleichung erfüllen .
  • Eine homogene Funktion erster Ordnung zweier positiver Variablen und (d. h. eine Funktion, die für alle positiven reellen Werte erfüllt ), die in einer Variablen konvex ist, muss in der anderen Variablen konvex sein.

Operationen, die die Konvexität erhalten

  • ist genau dann konkav, wenn konvex ist.
  • Nicht negative gewichtete Summen:
    • wenn und alle konvex sind, dann ist es auch . Insbesondere ist die Summe zweier konvexer Funktionen konvex.
    • diese Eigenschaft erstreckt sich auch auf unendliche Summen, Integrale und Erwartungswerte (sofern sie existieren).
  • Elementweises Maximum: Sei eine Sammlung konvexer Funktionen. Dann ist konvex. Der Definitionsbereich von ist die Sammlung von Punkten, an denen der Ausdruck endlich ist. Wichtige Sonderfälle:
    • Wenn konvexe Funktionen sind, dann ist es auch
    • Satz von Danskin : Wenn konvex ist, dann ist konvex, auch wenn C keine konvexe Menge ist.
  • Komposition:
    • Wenn f und g konvexe Funktionen sind und g über einem univariaten Bereich nicht abnehmend ist, dann ist es konvex. Wenn zum Beispiel konvex ist, dann ist es auch . weil konvex und monoton steigend ist.
    • Wenn f konkav ist und g konvex und über einem univariaten Bereich nicht ansteigend ist, dann ist es konvex.
    • Konvexität ist invariant unter affinen Karten: das heißt, wenn f konvex mit Domain , dann so ist , wo mit Domain .
  • Minimierung: Wenn konvex in dann ist konvex in x , vorausgesetzt, C ist eine konvexe Menge und
  • Wenn konvex ist, dann ist seine Perspektive mit Domäne konvex.

Stark konvexe Funktionen

Das Konzept der starken Konvexität erweitert und parametrisiert den Begriff der strikten Konvexität. Eine stark konvexe Funktion ist auch streng konvex, aber nicht umgekehrt.

Eine differenzierbare Funktion heißt stark konvex mit Parameter m > 0, wenn für alle Punkte x , y in ihrem Bereich folgende Ungleichung gilt :

oder, allgemeiner,
wo ist irgendeine norm . Einige Autoren, wie zum Beispiel, bezeichnen Funktionen, die diese Ungleichung erfüllen, als elliptische Funktionen.

Eine äquivalente Bedingung ist die folgende:

Es ist nicht notwendig, dass eine Funktion differenzierbar ist, um stark konvex zu sein. Eine dritte Definition für eine stark konvexe Funktion mit Parameter m ist, dass für alle x , y im Definitionsbereich und

Beachten Sie, dass diese Definition sich der Definition für strikte Konvexität als m → 0 annähert und mit der Definition einer konvexen Funktion für m = 0 identisch ist . Trotzdem gibt es Funktionen, die streng konvex sind, aber nicht stark konvex für jedes m > 0 ( siehe Beispiel unten).

Wenn die Funktion zweimal stetig differenzierbar ist, dann wird sie stark mit dem Parameter konvex

m , wenn und nur wenn für alle x in der Domäne, in dem ich die Identität und die Hesse - Matrix , und die Ungleichheit bedeutet , dass ist positiv semidefinit . Dies ist äquivalent zu der Forderung, dass der minimale Eigenwert von mindestens m für alle x sein muss . Wenn der Definitionsbereich nur die reelle Gerade ist, dann ist nur die zweite Ableitung, so dass die Bedingung zu wird . Wenn m = 0, dann bedeutet dies, dass die Hesse-Funktion positiv semidefinit ist (oder wenn der Bereich die reelle Gerade ist, bedeutet dies, dass ), was impliziert, dass die Funktion konvex und vielleicht streng konvex, aber nicht stark konvex ist.

Unter der Annahme, dass die Funktion zweimal stetig differenzierbar ist, kann man zeigen, dass die untere Schranke von stark konvex ist. Unter Verwendung

des Satzes von Taylor existiert
so dass
Dann
durch die Annahme über die Eigenwerte, und damit erhalten wir die zweite starke Konvexitätsgleichung oben.

Eine Funktion ist mit Parameter

m genau dann stark konvex, wenn die Funktion
ist konvex.

Die Unterscheidung zwischen konvex, streng konvex und stark konvex kann auf den ersten Blick subtil sein. Wenn zweimal stetig differenzierbar ist und der Definitionsbereich die reelle Gerade ist, dann können wir sie wie folgt charakterisieren:

  • konvex genau dann, wenn für alle
x .
  • streng konvex, wenn für alle
  • x (Anmerkung: Dies ist ausreichend, aber nicht notwendig).
  • stark konvex genau dann, wenn für alle
  • x .

    Sei zum Beispiel streng konvex und nehme an, dass es eine Folge von Punkten gibt, so dass . Allerdings ist die Funktion nicht stark konvex, da sie beliebig klein wird.

    Eine zweimal stetig differenzierbare Funktion auf einem kompakten Gebiet , die für alle erfüllt, ist stark konvex. Der Beweis dieser Aussage folgt aus dem

    Extremwertsatz , der besagt, dass eine stetige Funktion auf einer kompakten Menge ein Maximum und ein Minimum hat.

    Stark konvexe Funktionen sind im Allgemeinen einfacher zu handhaben als konvexe oder streng konvexe Funktionen, da sie eine kleinere Klasse sind. Wie streng konvexe Funktionen haben stark konvexe Funktionen eindeutige Minima auf kompakten Mengen.

    Gleichmäßig konvexe Funktionen

    Eine gleichmäßig konvexe Funktion, mit einem Modul , ist eine Funktion , dass für alle

    x , y in der Domäne und t ∈ [0, 1] , erfüllt
    wobei eine Funktion ist, die nicht negativ ist und nur bei 0 verschwindet. Dies ist eine Verallgemeinerung des Konzepts der stark konvexen Funktion; indem wir nehmen, erhalten wir die Definition der starken Konvexität.

    Beispiele

    Funktionen einer Variablen

    • Die Funktion hat , also ist
    f eine konvexe Funktion. Es ist auch stark konvex (und damit auch streng konvex), mit starker Konvexitätskonstante 2.
  • Die Funktion hat , also ist
  • f eine konvexe Funktion. Sie ist streng konvex, obwohl die zweite Ableitung nicht in allen Punkten streng positiv ist. Es ist nicht stark konvex.
  • Die Absolutwertfunktion ist konvex (wie in dem reflektierten
  • Dreiecksungleichung ), obwohl es keinen Derivat an dem Punkt hat  x  = 0. Es ist nicht streng konvex.
  • Die Funktion für ist konvex.
  • Die Exponentialfunktion ist konvex. Sie ist auch streng konvex, da , aber nicht stark konvex, da die zweite Ableitung beliebig nahe Null sein kann. Allgemeiner gesagt , die Funktion ist
  • logarithmisch konvex , wenn F eine konvexe Funktion ist. Manchmal wird stattdessen der Begriff "superkonvex" verwendet.
  • Die durch for definierte Funktion mit Domäne [0,1] ist konvex; es ist kontinuierlich im offenen Intervall (0, 1), aber nicht kontinuierlich bei 0 und 1.
  • Die Funktion x 3 hat die zweite Ableitung 6 x ; also ist sie auf der Menge mit x 0 konvex und auf der Menge mit  x  ≤ 0
  • konkav .
  • Beispiele für Funktionen, die monoton steigend, aber nicht konvex sind, umfassen und .
  • Beispiele für Funktionen, die konvex, aber nicht monoton steigend sind, umfassen und .
  • Die Funktion hat was größer als 0 ist, wenn
  • x > 0 ist, also konvex auf dem Intervall . Es ist im Intervall konkav .
  • Die Funktion mit , ist im Intervall konvex und im Intervall konvex , aber nicht konvex im Intervall , wegen der Singularität bei 
  • x  = 0.

    Funktionen von n Variablen

    LogSumExp , auch Softmax-Funktion genannt, ist eine konvexe Funktion.
  • Die Funktion auf dem Gebiet der
  • positiv-bestimmten Matrizen ist konvex.
  • Jede reellwertige lineare Transformation ist konvex, aber nicht streng konvex, denn wenn f linear ist, dann . Diese Aussage gilt auch, wenn wir „konvex“ durch „konkav“ ersetzen.
  • Jede reellwertige affine Funktion , dh jede Funktion der Form , ist gleichzeitig konvex und konkav.
  • Jede Norm ist eine konvexe Funktion, durch die Dreiecksungleichung und positive Homogenität .
  • Der Spektralradius einer nichtnegativen Matrix ist eine konvexe Funktion ihrer diagonalen Elemente.
  • Siehe auch

    Anmerkungen

    Verweise

    • Bertsekas, Dimitri (2003). Konvexe Analyse und Optimierung . Athena wissenschaftlich.
    • Borwein, Jonathan und Lewis, Adrian. (2000). Konvexe Analyse und nichtlineare Optimierung. Springer.
    • Donoghue, William F. (1969). Verteilungen und Fourier-Transformationen . Akademische Presse.
    • Hiriart-Urruty, Jean-Baptiste, und Lemaréchal, Claude . (2004). Grundlagen der konvexen Analyse. Berlin: Springer.
    • Krasnosel'skii MA , Rutickii Ya.B. (1961). Konvexe Funktionen und Orlicz-Räume . Groningen: P. Noordhoff Ltd.
    • Lauritzen, Niels (2013). Konvexität im Grundstudium . Weltwissenschaftliche Veröffentlichung.
    • Lünberger, David (1984). Lineare und nichtlineare Programmierung . Addison-Wesley.
    • Lünberger, David (1969). Optimierung durch Vektorraummethoden . Wiley & Söhne.
    • Rockafellar, RT (1970). Konvexe Analyse . Princeton: Princeton University Press.
    • Thomson, Brian (1994). Symmetrische Eigenschaften reeller Funktionen . CRC-Presse.
    • Zălinescu, C. (2002). Konvexanalyse in allgemeinen Vektorräumen . River Edge, NJ: World Scientific Publishing Co., Inc. S. xx+367. ISBN 981-238-067-1. MR  1.921.556 .

    Externe Links