Теорема Данскинса - Википедия - Danskins theorem

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

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

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

Заявление

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

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

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

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

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

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

${ 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} е (х) = макс _ {г in Z_ {0} (х)} фи '(х, г; у),}$

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

Производная

${ displaystyle f (x)}$ является дифференцируемый в ${ displaystyle x}$ если ${ Displaystyle Z_ {0} (х)}$ состоит из одного элемента ${ 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 фи (х, г)}$ дифференцируема по ${ 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) верно}}$

куда ${ 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 (х, z)}$ является субдифференциалом ${ displaystyle phi ( cdot, z)}$ в ${ displaystyle x}$ для любого ${ displaystyle z}$ в ${ displaystyle Z}$.

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

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

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

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