Выпуклый анализ - Convex analysis

Трехмерный выпуклый многогранник. Выпуклый анализ включает в себя не только изучение выпуклых подмножеств евклидовых пространств, но и изучение выпуклых функций на абстрактных пространствах.

Выпуклый анализ - это раздел математики, посвященный изучению свойств выпуклых функций и выпуклых множеств , часто с приложениями в выпуклой минимизации , подобласти теории оптимизации .

Выпуклые множества

Подмножество некоторого векторного пространства называется выпуклым, если оно удовлетворяет любому из следующих эквивалентных условий: ${\ Displaystyle C \ substeq X}$ ${\ displaystyle X}$

1. Если реально, а затем${\ Displaystyle 0 \ Leq г \ Leq 1}$${\ displaystyle x, y \ in C}$${\ displaystyle rx + (1-r) y \ in C.}$
2. Если реально и с то${\ Displaystyle 0 <г <1}$${\ displaystyle x, y \ in C}$${\ Displaystyle х \ neq y,}$${\ displaystyle rx + (1-r) y \ in C.}$
3. ${\ displaystyle (r + s) C = rC + sC}$для всего позитивного реального и${\ displaystyle r> 0}$${\ displaystyle s> 0.}$

Выпуклые функции

Выпуклая функция на отрезке.

На всем протяжении будет карта, оцениваемая в расширенных действительных числах с областью, которая является выпуклым подмножеством некоторого векторного пространства. Карта является выпуклой функцией, если ${\ displaystyle f: X \ to [- \ infty, \ infty]}$ ${\ Displaystyle [- \ infty, \ infty] = \ mathbb {R} \ чашка \ {\ pm \ infty \}}$ ${\ displaystyle \ operatorname {domain} f = X}$${\ displaystyle f: X \ to [- \ infty, \ infty]}$

${\ Displaystyle f (rx + (1-r) y) \ leq rf (x) + (1-r) f (y)}$

( Выпуклость ≤ )

выполняется для любого действительного числа и любого с Если это остается верным, когда определяющее неравенство ( Выпуклость ≤ ) заменяется строгим неравенством ${\ Displaystyle 0 <г <1}$${\ displaystyle x, y \ in X}$${\ displaystyle x \ neq y.}$${\ displaystyle f}$

${\ Displaystyle f (rx + (1-r) y) <rf (x) + (1-r) f (y)}$

( Выпуклость < )

тогда называется строго выпуклой . ${\ displaystyle f}$

Выпуклые функции связаны с выпуклыми множествами. В частности, функция является выпуклой тогда и только тогда, когда ее надграфик${\ displaystyle f}$

Функция (черным цветом) является выпуклой тогда и только тогда, когда ее надграфик, который является областью над ее графиком (зеленым цветом), является выпуклым множеством .

График двумерной выпуклой функции${\ displaystyle x ^ {2} + xy + y ^ {2}.}$

${\ displaystyle \ operatorname {epi} f: = \ left \ {(x, r) \ in X \ times \ mathbb {R} ~: ~ f (x) \ leq r \ right \}}$

( Определение эпиграфа )

- выпуклое множество. Эпиграфы расширенных действительных функций играют роль в выпуклом анализе, аналогичную роли, которую играют графики действительных функций в реальном анализе . В частности, эпиграф расширенной функции с действительными значениями обеспечивает геометрическую интуицию, которую можно использовать для формулирования или доказательства гипотез.

Область определения функции обозначается, а ее эффективной областью определения является множество ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\ displaystyle \ operatorname {domain} f}$

${\ displaystyle \ operatorname {dom} f: = \ {x \ in X ~: ~ f (x) <\ infty \}.}$

( dom f def. )

Функция называется собственно , если и для всех С другой стороны , это означает , что существует какой - то в области , в которой и также никогда не равняться В словами, функция собственно , если его область не пуста, она никогда не принимает значение и он также не тождественно равен Если - собственная выпуклая функция, то существует некоторый вектор и такой, что ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\ displaystyle \ operatorname {dom} f \ neq \ varnothing}$${\ displaystyle f (x)> - \ infty}$ ${\ displaystyle x \ in \ operatorname {domain} f.}$${\ displaystyle x}$${\ displaystyle f}$${\ Displaystyle е (х) \ в \ mathbb {R}}$${\ displaystyle f}$${\ displaystyle - \ infty.}$${\ displaystyle - \ infty,}$${\ displaystyle + \ infty.}$${\ displaystyle f: \ mathbb {R} ^ {n} \ to [- \ infty, \ infty]}$${\ displaystyle b \ in \ mathbb {R} ^ {n}}$${\ Displaystyle г \ в \ mathbb {R}}$

${\ Displaystyle е (х) \ geq х \ cdot br}$     для каждого ${\ displaystyle x}$

где обозначает скалярное произведение этих векторов. ${\ displaystyle x \ cdot b}$

Выпуклый конъюгат

Выпуклый сопряженное расширенной вещественная функция (не обязательно выпуклый) является функция от (непрерывного) двойного пространства от и ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\ displaystyle f ^ {*}: X ^ {*} \ to [- \ infty, \ infty]}$ ${\ displaystyle X ^ {*}}$${\ displaystyle X,}$

${\ displaystyle f ^ {*} \ left (x ^ {*} \ right) = \ sup _ {z \ in X} \ left \ {\ left \ langle x ^ {*}, z \ right \ rangle -f (г) \ право \}}$

где скобки обозначают каноническую двойственность бисопряженным из является карта определяется для каждого If обозначает множество значных функций на том отображении определенного называются преобразованием Лежандр-Фенхель . ${\ displaystyle \ left \ langle \ cdot, \ cdot \ right \ rangle}$ ${\ displaystyle \ left \ langle x ^ {*}, z \ right \ rangle: = x ^ {*} (z).}$${\ displaystyle f}$${\ displaystyle f ^ {**} = \ left (f ^ {*} \ right) ^ {*}: X \ to [- \ infty, \ infty]}$${\ displaystyle f ^ {**} (x): = \ sup _ {z ^ {*} \ in X ^ {*}} \ left \ {\ left \ langle x, z ^ {*} \ right \ rangle -f \ left (z ^ {*} \ right) \ right \}}$${\ displaystyle x \ in X.}$${\ Displaystyle \ OperatorName {Func} (X; Y)}$${\ displaystyle Y}$${\ displaystyle X,}$${\ displaystyle \ operatorname {Func} (X; [- \ infty, \ infty]) \ to \ operatorname {Func} \ left (X ^ {*}; [- \ infty, \ infty] \ right)}$${\ displaystyle f \ mapsto f ^ {*}}$

Субдифференциальное множество и неравенство Фенхеля-Юнга

Если и тогда Субдифференциал набор является ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\ displaystyle x \ in X}$

${\ Displaystyle {\ begin {alignat} {4} \ partial f (x): & = \ left \ {x ^ {*} \ in X ^ {*} ~: ~ f (z) \ geq f (x) + \ left \ langle x ^ {*}, zx \ right \ rangle {\ text {для всех}} z \ in X \ right \} && ({\ text {«}} z \ in X {\ text {' '}} {\ text {можно заменить на:}} {\ text {«}} z \ in X {\ text {таким образом, что}} z \ neq x {\ text {' '}}) \\ & = \ left \ {x ^ {*} \ in X ^ {*} ~: ~ \ left \ langle x ^ {*}, x \ right \ rangle -f (x) \ geq \ left \ langle x ^ {*} , z \ right \ rangle -f (z) {\ text {для всех}} z \ in X \ right \} && \\ & = \ left \ {x ^ {*} \ in X ^ {*} ~: ~ \ left \ langle x ^ {*}, x \ right \ rangle -f (x) \ geq \ sup _ {z \ in X} \ left \ langle x ^ {*}, z \ right \ rangle -f ( z) \ right \} && {\ text {Правая часть:}} f ^ {*} \ left (x ^ {*} \ right) \\ & = \ left \ {x ^ {*} \ in X ^ {*} ~: ~ \ left \ langle x ^ {*}, x \ right \ rangle -f (x) = f ^ {*} \ left (x ^ {*} \ right) \ right \} && { \ text {Взятие}} z: = x {\ text {в}} \ sup {} {\ text {дает неравенство}} \ leq. \\\ end {alignat}}}$

Например, в важном частном случае, когда является нормой , можно показать, что если тогда это определение сводится к: ${\ Displaystyle е = \ | \ cdot \ |}$${\ displaystyle X}$${\ displaystyle 0 \ neq x \ in X}$

${\ displaystyle \ partial f (x) = \ left \ {x ^ {*} \ in X ^ {*} ~: ~ \ left \ langle x ^ {*}, x \ right \ rangle = \ | x \ | {\ text {и}} \ left \ | x ^ {*} \ right \ | = 1 \ right \}}$     а также     ${\ displaystyle \ partial f (0) = \ left \ {x ^ {*} \ in X ^ {*} ~: ~ \ left \ | x ^ {*} \ right \ | \ leq 1 \ right \}. }$

Для любого и которое называется неравенством Фенхеля-Юнга . Это неравенство является равенством (т.е. ) тогда и только тогда, когда именно таким образом субдифференциальное множество напрямую связано с выпуклым сопряженным${\ displaystyle x \ in X}$${\ displaystyle x ^ {*} \ in X ^ {*},}$ ${\ displaystyle f (x) + f ^ {*} \ left (x ^ {*} \ right) \ geq \ left \ langle x ^ {*}, x \ right \ rangle,}$${\ displaystyle f (x) + f ^ {*} \ left (x ^ {*} \ right) = \ left \ langle x ^ {*}, x \ right \ rangle}$${\ displaystyle x ^ {*} \ in \ partial f (x).}$${\ displaystyle \ partial f (x)}$${\ displaystyle f ^ {*} \ left (x ^ {*} \ right).}$

Двояковыпуклый

Бисопряженных функции является сопряженным конъюгатом, как правило , записывается в виде бисопряженного полезно для показа когда сильное или слабой двойственность удержания ( с помощью функции возмущения ). ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\ displaystyle f ^ {**}: X \ to [- \ infty, \ infty].}$

Для любого неравенство следует из неравенства Фенхеля – Юнга . Для собственных функций , если и только если оно выпукло и полунепрерывно снизу по теореме Фенхеля – Моро . ${\ displaystyle x \ in X,}$${\ Displaystyle е ^ {**} (х) \ leq f (х)}$${\ displaystyle f = f ^ {**}}$ ${\ displaystyle f}$

Выпуклая минимизация

Минимизации выпуклых ( первичная ) проблема является одной из форм

найти, когда заданы выпуклая функция и выпуклое подмножество${\ Displaystyle \ Inf _ {х \ в М} е (х)}$${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\ Displaystyle M \ substeq X.}$

Двойная проблема

В теории оптимизации принцип двойственности гласит, что проблемы оптимизации можно рассматривать с одной из двух точек зрения: с основной проблемы или с двойственной проблемы.

В общем случае даны две двойственные пары, разделенные локально выпуклыми пространствами, а затем, учитывая функцию, мы можем определить прямую задачу как нахождение такой, что ${\ Displaystyle \ влево (Х, Х ^ {*} \ вправо)}$${\ displaystyle \ left (Y, Y ^ {*} \ right).}$${\ displaystyle f: X \ к [- \ infty, \ infty],}$${\ displaystyle x}$

${\ displaystyle \ inf _ {x \ in X} f (x).}$

Если есть условия ограничения, их можно встроить в функцию , указав где - индикаторная функция . Тогда пусть - функция возмущения такая, что${\ displaystyle f}$${\ displaystyle f = f + I _ {\ mathrm {constraints}}}$${\ displaystyle I}$${\ displaystyle F: X \ times Y \ to [- \ infty, \ infty]}$${\ displaystyle F (x, 0) = f (x).}$

Двойственная задача по отношению к выбранной функции возмущений задаются

${\ displaystyle \ sup _ {y ^ {*} \ in Y ^ {*}} - F ^ {*} \ left (0, y ^ {*} \ right)}$

где - выпуклая сопряженная по обеим переменным${\ displaystyle F ^ {*}}$${\ displaystyle F.}$

Разрыв двойственности разница правых и левых частей неравенства

${\ displaystyle \ sup _ {y ^ {*} \ in Y ^ {*}} - F ^ {*} \ left (0, y ^ {*} \ right) \ leq \ inf _ {x \ in X} F (x, 0).}$

Этот принцип такой же, как и слабая двойственность . Если две стороны равны друг другу, то говорят, что проблема удовлетворяет сильной двойственности .

Есть много условий для сохранения сильной двойственности, таких как:

• ${\ Displaystyle F = F ^ {**}}$где это функция возмущения , связанная с прямыми и двойственными задачами и является бисопряженным из ;${\ displaystyle F}$${\ displaystyle F ^ {**}}$${\ displaystyle F}$
• основная задача - это задача линейной оптимизации ;
• Условие Слейтера для задачи выпуклой оптимизации .

Двойственность Лагранжа

Для выпуклой задачи минимизации с ограничениями-неравенствами

${\ Displaystyle \ мин {} _ {х} е (х)}$при условии для${\ Displaystyle g_ {я} (х) \ leq 0}$${\ Displaystyle я = 1, \ ldots, м.}$

двойственная лагранжева задача

${\ Displaystyle \ sup {} _ {и} \ inf {} _ {х} L (х, и)}$при условии для${\ Displaystyle и_ {я} (х) \ geq 0}$${\ Displaystyle я = 1, \ ldots, м.}$

где целевая функция - это двойственная функция Лагранжа, определяемая следующим образом: ${\ Displaystyle L (х, и)}$

${\ Displaystyle L (х, и) = е (х) + \ сумма _ {j = 1} ^ {m} u_ {j} g_ {j} (x)}$

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

• Выпуклость в экономике
  • Невыпуклость (экономика)
• Список тем о выпуклости  - статья со списком в Википедии
• Вернер Фенчель

Заметки

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

• Баушке, Хайнц Х .; Комбетс, Патрик Л. (28 февраля 2017 г.). Выпуклый анализ и теория монотонных операторов в гильбертовых пространствах . CMS Книги по математике. Springer Science & Business Media . ISBN 978-3-319-48311-5. OCLC  1037059594 .
• Бойд, Стивен ; Ванденберге, Ливен (8 марта 2004 г.). Выпуклая оптимизация . Кембриджская серия по статистической и вероятностной математике. Кембридж, Великобритания Нью-Йорк: Издательство Кембриджского университета . ISBN 978-0-521-83378-3. OCLC  53331084 .
• Хириарт-Уррути, Ж.-Б. ; Лемарешаль, К. (2001). Основы выпуклого анализа . Берлин: Springer-Verlag. ISBN 978-3-540-42205-1.
• Кусраев АГ; Кутателадзе, Семен Самсонович (1995). Субдифференциалы: теория и приложения . Дордрехт: Kluwer Academic Publishers. ISBN 978-94-011-0265-0.
• Рокафеллар, Р. Тиррелл ; Уэтс, Роджер Дж.-Б. (26 июня 2009 г.). Вариационный анализ . Grundlehren der Mathematischen Wissenschaften. 317 . Берлин, Нью-Йорк: Springer Science & Business Media . ISBN 9783642024313. OCLC  883392544 .
• Рудин, Вальтер (1991). Функциональный анализ . Международная серия по чистой и прикладной математике. 8 (Второе изд.). Нью-Йорк, штат Нью-Йорк: McGraw-Hill Science / Engineering / Math . ISBN 978-0-07-054236-5. OCLC  21163277 .
• Певец, Иван (1997). Абстрактный выпуклый анализ . Серия монографий и расширенных текстов Канадского математического общества. Нью-Йорк: John Wiley & Sons, Inc., стр. Xxii + 491. ISBN 0-471-16015-6. Руководство по ремонту  1461544 .
• Stoer, J .; Витцгалл, К. (1970). Выпуклость и оптимизация в конечных размерах . 1 . Берлин: Springer. ISBN 978-0-387-04835-2.
• Зэлинеску, Константин (30 июля 2002 г.). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, штат Нью-Джерси, Лондон: World Scientific Publishing . ISBN 978-981-4488-15-0. Руководство по ремонту  1921556 . OCLC  285163112 .

Внешние ссылки

• СМИ, связанные с анализом Convex на Викискладе?