Теорема данскинса - Danskins theorem

В выпуклый анализ, Теорема Данскина это теорема который предоставляет информацию о производные из функция формы

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

Теорема имеет приложения в оптимизация, где он иногда используется для решения минимакс проблемы. Первоначальная теорема Дж. М. Данскина, изложенная в его монографии 1967 г. «Теория максимума-минимума и ее приложения к задачам размещения оружия», Спрингер, штат Нью-Йорк, предоставляет формулу для производной по направлению от максимума a (не обязательно выпуклого) направленно дифференцируемая функция. При адаптации к случаю выпуклой функции эта формула дает следующую теорему, приведенную в несколько более общей форме в качестве предложения A.22 в докторской диссертации 1971 г. Диссертация Д. П. Бертсекаса "Управление неопределенными системами с описанием неопределенности множеством принадлежностей". Доказательство следующей версии можно найти в книге Бертсекаса "Нелинейное программирование" 1999 г. (раздел B.5).

Заявление

Теорема применима к следующей ситуации. Предполагать ${\displaystyle \phi (x,z)}$ это непрерывная функция двух аргументов,

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

куда ${\displaystyle Z\subset {\mathbb {R} }^{m}}$ это компактный набор. Далее предположим, что ${\displaystyle \phi (x,z)}$ является выпуклый в ${\displaystyle x}$ для каждого ${\displaystyle z\in Z}$.

В этих условиях теорема Данскина дает выводы относительно выпуклости и дифференцируемость функции

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

Чтобы сформулировать эти результаты, мы определяем набор точек максимизации ${\displaystyle Z_{0}(x)}$ в качестве

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

Теорема Данскина дает следующие результаты.

Выпуклость

${\displaystyle f(x)}$ является выпуклый.

Направленные производные

В производная по направлению из ${\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),}$

куда ${\displaystyle \phi '(x,z;y)}$ - производная по направлению функции ${\displaystyle \phi (\cdot ,z)}$ в ${\displaystyle x}$ в направлении ${\displaystyle y}$.

Производная

${\displaystyle f(x)}$ является дифференцируемый в ${\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}}.}$

Субдифференциальный

Если ${\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)\right\}}$

куда ${\displaystyle \mathrm {conv} }$ указывает на выпуклый корпус операция.

Расширение

Доктор философии 1971 г. Диссертация Берцекаса ^[1] (Предложение A.22) доказывает более общий результат, который не требует, чтобы ${\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\}}$

куда ${\displaystyle \partial \phi (x,z)}$ является субдифференциалом ${\displaystyle \phi (\cdot ,z)}$ в ${\displaystyle x}$ для любого ${\displaystyle z}$ в ${\displaystyle Z}$.

Смотрите также

• Теорема о максимуме
• Теорема о конверте
• Лемма Хотеллингса

Рекомендации

1. Кандидат наук. Диссертация Д. П. Бертсекаса

• Данскин, Джон М. (1967). Теория Макс-Мин и ее приложения к задачам размещения оружия. Нью-Йорк: Спрингер.
• Бертсекас, Дмитрий П. (1971). Управление неопределенными системами с множественным описанием неопределенности. Кембридж, Массачусетс: докторская диссертация, Массачусетский технологический институт.
• Бертсекас, Дмитрий П. (1999). Нелинейное программирование. Бельмонт, Массачусетс: Athena Scientific. стр.737. ISBN  1-886529-00-0.