Satz von Danskin - Danskin's theorem

In der konvexen Analysis ist der Satz von Danskin ein Satz, der Informationen über die Ableitungen einer Funktion der Form provides liefert

${\displaystyle f(x)=\max_{z\in Z}\phi(x,z).}$

Das Theorem hat Anwendungen in der Optimierung , wo es manchmal verwendet wird, um Minimax- Probleme zu lösen . Der ursprüngliche Satz von JM Danskin in seiner 1967 erschienenen Monographie "The Theory of Max-Min and its Applications to Weapons Allocation Problems", Springer, NY, liefert eine Formel für die Richtungsableitung des Maximums von a (nicht unbedingt konvex) gerichtet differenzierbare Funktion. An den Fall einer konvexen Funktion angepasst, ergibt diese Formel den folgenden Satz, der in etwas allgemeinerer Form als Proposition A.22 im Ph.D. Dissertation von DP Bertsekas, "Kontrolle unsicherer Systeme mit einer Set-Membership Description of the Uncertainty". Einen Beweis für die folgende Version findet sich im 1999 erschienenen Buch "Nonlinear Programming" von Bertsekas (Abschnitt B.5).

Aussage

Der Satz gilt für die folgende Situation. Angenommen ist eine stetige Funktion von zwei Argumenten, ${\displaystyle \phi(x,z)}$

${\displaystyle \phi :{\mathbb{R}}^{n}\times Z\rightarrow {\mathbb{R}}}$

wo ist eine kompakte Menge . Nehmen Sie weiter an, dass in für jede konvex ist . ${\displaystyle Z\subset {\mathbb{R}}^{m}}$${\displaystyle \phi(x,z)}$${\displaystyle x}$${\displaystyle z\in Z}$

Unter diesen Bedingungen liefert der Satz von Danskin Rückschlüsse auf die Konvexität und Differenzierbarkeit der Funktion

${\displaystyle f(x)=\max_{z\in Z}\phi(x,z).}$

Um diese Ergebnisse zu formulieren, definieren wir die Menge der Maximierungspunkte als ${\displaystyle Z_{0}(x)}$

${\displaystyle Z_{0}(x)=\left\{{\overline {z}}:\phi (x,{\overline {z}})=\max _{z\in Z}\phi (x ,z)\rechts\}.}$

Der Satz von Danskin liefert dann die folgenden Ergebnisse.

Konvexität

${\displaystyle f(x)}$ist konvex .

Richtungsderivate

Die Richtungsableitung von in Richtung , bezeichnet mit , ist gegeben durch ${\displaystyle f(x)}$${\displaystyle y}$${\displaystyle D_{y}\f(x)}$

${\displaystyle D_{y}f(x)=\max_{z\in Z_{0}(x)}\phi '(x,z;y),}$

wobei die Richtungsableitung der Funktion bei in die Richtung .${\displaystyle \phi '(x,z;y)}$${\displaystyle \phi (\cdot,z)}$${\displaystyle x}$${\displaystyle y}$

Derivat

${\displaystyle f(x)}$ist differenzierbar an , wenn ein einzelnes Element aus . In diesem Fall ist die Ableitung von (oder der Gradient von wenn ein Vektor) gegeben durch ${\displaystyle x}$${\displaystyle Z_{0}(x)}$${\displaystyle {\overline {z}}}$${\displaystyle f(x)}$${\displaystyle f(x)}$${\displaystyle x}$

${\displaystyle {\frac {\partial f}{\partial x}}={\frac {\partial\phi(x,{\overline {z}})}{\partial x}}.}$

Subdifferential

Wenn differenzierbar in Bezug auf für alle , und wenn kontinuierlich in Bezug auf für alle , dann ist die Subdifferential von gegeben durch ${\displaystyle \phi(x,z)}$${\displaystyle x}$${\displaystyle z\in Z}$${\displaystyle \partial\phi /\partial x}$${\displaystyle z}$${\displaystyle x}$${\displaystyle f(x)}$

${\displaystyle \partial f(x)=\mathrm {conv} \left\{{\frac {\partial\phi(x,z)}{\partial x}}:z\in Z_{0}(x) \Recht\}}$

wobei die konvexe Hüllenoperation angibt .${\displaystyle \mathrm {conv}}$

Erweiterung

Der 1971 Ph.D. Die These von Bertsekas (Proposition A.22) beweist ein allgemeineres Ergebnis, das nicht differenzierbar ist. Stattdessen wird davon ausgegangen, dass es sich um eine erweiterte reellwertige abgeschlossene echte konvexe Funktion für jede in der kompakten Menge handelt , dass das Innere des effektiven Bereichs von nicht leer ist und dass dies auf der Menge stetig ist . Dann ist für alle in das Subdifferential von at gegeben durch ${\displaystyle \phi (\cdot,z)}$${\displaystyle \phi (\cdot,z)}$${\displaystyle z}$${\displaystyle Z}$${\displaystyle int(dom(f))}$${\displaystyle f}$${\displaystyle \phi}$${\displaystyle int(dom(f))\times Z}$${\displaystyle x}$${\displaystyle int(dom(f))}$${\displaystyle f}$${\displaystyle x}$

${\displaystyle \partial f(x)=\mathrm {conv} \left\{\partial\phi(x,z):z\in Z_{0}(x)\right\}}$

wo ist das Subdifferential von at für irgendein in . ${\displaystyle \partial\phi(x,z)}$${\displaystyle \phi (\cdot,z)}$${\displaystyle x}$${\displaystyle z}$${\displaystyle Z}$

Siehe auch

• Maximumsatz
• Hüllkurvensatz
• Hotellinge Lemma

Verweise

• Danskin, John M. (1967). Die Theorie von Max-Min und ihre Anwendungen auf Probleme der Waffenzuordnung . NY: Springer.
• Bertsekas, Dimitri P. (1971). Kontrolle unsicherer Systeme mit einer Set-Mitgliedschaft Beschreibung der Unsicherheit . Cambridge, MA: Doktorarbeit, MIT.
• Bertsekas, Dimitri P. (1999). Nichtlineare Programmierung . Belmont, MA: Athena Scientific. S.  737 . ISBN 1-886529-00-0.