Zum Inhalt springen

Subdifferential

aus Wikipedia, der freien Enzyklopädie

Das Subdifferential ist eine Verallgemeinerung des Gradienten auf nicht differenzierbare konvexe Funktionen. Das Subdifferential spielt eine wichtige Rolle in der konvexen Analysis sowie der konvexen Optimierung.

Definition

Sei <math> f\colon\mathbb{R}^n\to\mathbb{R}</math> eine konvexe Funktion. Ein Vektor <math>g\in\R^n</math> heißt Subgradient von <math>f</math> an der Stelle <math>x_0</math>, wenn für alle <math>x\in\R^n</math> gilt<ref>R. T. Rockafellar Convex analysis 1970., p.214</ref>

<math> f(x) \geq f(x_0) + \langle g, x-x_0 \rangle </math>,

wobei <math>\langle \cdot , \cdot \rangle</math> das Standardskalarprodukt bezeichnet.

Das Subdifferential <math>\partial f(x_0) </math> ist die Menge aller Subgradienten von <math>f</math> im Punkt <math>x_0</math>.<ref>R. T. Rockafellar Convex analysis 1970., p.215</ref>

Existieren die folgenden Grenzwerte <math display="block">a=\lim_{x\to x_0^-} \frac{f(x)-f(x_0)}{x-x_0},</math> <math display="block">b=\lim_{x\to x_0^+} \frac{f(x)-f(x_0)}{x-x_0},</math> so wird das Intervall <math>[a,b]</math> aller Subgradienten das Subdifferential der Funktion <math>f</math> bei <math>x_0</math> genannt und wird als <math>\partial f(x_0) :=[a,b]</math> geschrieben.

Für eine konvexe Funktion gilt <math>a\leq b</math>, für eine nicht konvexe Funktion braucht dies nicht zu gelten und dann ist <math>\partial f(x_0)=\emptyset</math>.

Anschauung

Datei:Subgradienten.svg
Subgradienten einer konvexen Funktion

Intuitiv bedeutet diese Definition für <math>n=1</math>, dass der Graph der Funktion <math>f</math> überall über der Geraden <math>G</math> liegt, die durch den Punkt <math>(x_0,f(x_0))</math> geht und die Steigung <math>g</math> besitzt:

<math>G=\{(x,y)\in\R^2\mid y=g\cdot(x-x_0)+f(x_0)\}</math>

Da die Normalengleichung von <math>G</math> gerade

<math>-g\cdot(x-x_0)+1\cdot(y-f(x_0))=0</math>

ist, ist die Normale an <math>G</math> also <math>(-g,1)\in\R^2</math>.

Im allgemeinen Fall <math>n\geq 1</math> liegt <math>f</math> über der Hyperebene, die durch den Fußpunkt <math>(x_0,f(x_0))</math> und die Normale <math>(-g,1)\in\R^{n+1}</math> gegeben ist.

Wegen des Trennungssatzes ist das Subdifferential einer stetigen konvexen Funktion überall nichtleer.

Beispiel

Das Subdifferential der Funktion <math>f\colon\mathbb{R}\rightarrow\mathbb{R}</math>, <math>x\mapsto|x|</math> ist gegeben durch:

<math>\partial f(x_0)=\begin{cases}\{-1\} & x_0<0\\

\left[-1,1\right] & x_0=0\\ \{1\} & x_0>0\end{cases}</math> Eine ähnliche Eigenschaft ist bei der Lasso-Regression für die Herleitung der Soft-Threshold-Funktion wichtig.

Beschränktheit

Sei <math>f\colon\mathbb{R}^n\rightarrow\mathbb{R}</math> stetig und sei <math>X\subset\mathbb{R}^n</math> beschränkt. Dann ist die Menge <math>\bigcup_{x_0\in X}\partial f(x_0)</math> beschränkt.

Beweis

Sei <math>f\colon\mathbb{R}^n\rightarrow\mathbb{R}</math> stetig und sei <math>X\subset\mathbb{R}^n</math> beschränkt. Setze <math>\varepsilon:=\sup |f(\overline{U_1(X)})|</math> wobei <math>\overline{U_1(X)}=\{x\in\mathbb{R}^n\mid{\rm dist}(x,X)\leq1\}</math>. Angenommen, <math>\bigcup_{x_0\in X}\partial f(x_0)</math> ist nicht beschränkt, dann gibt es für <math>R:=2\varepsilon</math> ein <math>x_0\in X</math> und ein <math>g\in\partial f(x_0)</math> mit <math>\|g\|_2>R=2\varepsilon</math>. Sei <math>x:=\frac{1}{\|g\|_2} g+x_0</math>. Somit sind <math>x_0,x\in\overline{U_1(X)}</math>. Wir erhalten die Abschätzung

<math>g^T(x-x_0)=\frac{1}{\|g\|_2}g^T g=\|g\|_2 > 2\varepsilon\geq\left|f(x)-f(x_0)\right|\geq f(x)-f(x_0)</math>.

<math>g</math> ist also kein Subgradient. Das ist ein Widerspruch.

Differenzierbarkeit

Ist die Funktion differenzierbar in <math>x_0 \in \mathrm{int}\,\mathrm{dom}\,f</math>, so gilt:

<math>\partial f(x_0) = \left\{\nabla f(x_0)\right\}</math>

Siehe <ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Yaron Singer|Yaron Singer: }}{{#if:|{{#if:Advanced Optimzation|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Advanced Optimzation}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Advanced Optimzation}}}}|[{{#invoke:URLutil|getNormalized|1=https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Advanced Optimzation}}}}]}}{{#if:| ({{{format}}}{{#if:{{#if: 2022-01-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf}}%7C%7C}}}}{{#if:Advanced Optimzation|{{#if:{{#invoke:WLink|isValidLinktext|1=Advanced Optimzation|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2022-01-27 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2022-01-27 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2022-01-27 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:1234775||(?)}}}}}}{{#if: Proposition 42022-01-27|;}}}}{{#if: 2022-01-27| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2022-01-27 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2022-01-27|class=Zitationswartung}} }} {{#invoke:DateTime|format|2022-01-27|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:{{#if: 2022-01-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2022-01-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}Proposition 4|{{#if: Proposition 4|: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: Proposition 4 

   | {{#if: 
       | {{#if: Proposition 4
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> für einen Beweis.

Zudem gilt: Ist das Subdifferential <math>\partial f(x_0)</math> einelementig, so ist <math>f</math> an der Stelle <math>x_0</math> differenzierbar.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>

Literatur

<references />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Subdifferential&oldid=1234775“