Квазивыпуклая функция

Математическая функция с выпуклыми множествами нижнего уровня

Квазивыпуклая функция, которая не является выпуклой

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

Функция плотности вероятности нормального распределения является квазивогнутой, но не вогнутой.

Двумерная нормальная плотность соединений является квазивогнутой.

В математике квазивыпуклая функция — это вещественная функция , определенная на интервале или на выпуклом подмножестве вещественного векторного пространства, такая, что обратный образ любого множества вида является выпуклым множеством . Для функции одной переменной вдоль любого участка кривой наивысшая точка является одной из конечных точек. Отрицательная точка квазивыпуклой функции называется квазивогнутой . ${\displaystyle (-\infty ,a)}$

Квазивыпуклость — более общее свойство, чем выпуклость, поскольку все выпуклые функции также являются квазивыпуклыми, но не все квазивыпуклые функции являются выпуклыми. Одномерные унимодальные функции являются квазивыпуклыми или квазивогнутыми, однако это не обязательно так для функций с несколькими аргументами . Например, двумерная функция Розенброка является унимодальной, но не квазивыпуклой, а функции со звездно-выпуклыми множествами подуровней могут быть унимодальными, не будучи квазивыпуклыми.

Определение и свойства

Функция, определенная на выпуклом подмножестве действительного векторного пространства, является квазивыпуклой, если для всех и имеем ${\displaystyle f:S\to \mathbb {R} }$ ${\displaystyle S}$ ${\displaystyle x,y\in S}$ ${\displaystyle \lambda \in [0,1]}$

${\displaystyle f(\lambda x+(1-\lambda )y)\leq \max {\big \{}f(x),f(y){\big \}}.}$

Другими словами, если таково, что всегда верно, что точка, расположенная непосредственно между двумя другими точками, не дает более высокого значения функции, чем обе другие точки, то является квазивыпуклой. Обратите внимание, что точки и , а также точка, расположенная непосредственно между ними, могут быть точками на прямой или, в более общем смысле, точками в n -мерном пространстве. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle y}$

Квазилинейная функция является как квазивыпуклой, так и квазивогнутой.

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

Альтернативный способ (см. введение) определения квазивыпуклой функции состоит в требовании, чтобы каждое множество подуровней было выпуклым множеством. ${\displaystyle f(x)}$ ${\displaystyle S_{\alpha }(f)=\{x\mid f(x)\leq \alpha \}}$

Если к тому же

${\displaystyle f(\lambda x+(1-\lambda )y)<\max {\big \{}f(x),f(y){\big \}}}$

для всех и , то строго квазивыпукла . То есть строгая квазивыпуклость требует, чтобы точка, расположенная непосредственно между двумя другими точками, давала меньшее значение функции, чем одна из других точек. ${\displaystyle x\neq y}$ ${\displaystyle \lambda \in (0,1)}$ ${\displaystyle f}$

Квазивогнутая функция — это функция, отрицательная часть которой является квазивыпуклой, а строго квазивогнутая функция — это функция, отрицательная часть которой является строго квазивыпуклой. Эквивалентно функция является квазивогнутой, если ${\displaystyle f}$

${\displaystyle f(\lambda x+(1-\lambda )y)\geq \min {\big \{}f(x),f(y){\big \}}.}$

и строго квазивогнутым, если

${\displaystyle f(\lambda x+(1-\lambda )y)>\min {\big \{}f(x),f(y){\big \}}}$

(Строго) квазивыпуклая функция имеет (строго) выпуклые нижние контурные множества , в то время как (строго) квазивогнутая функция имеет (строго) выпуклые верхние контурные множества .

Функция, которая является одновременно квазивыпуклой и квазивогнутой, называется квазилинейной .

Частным случаем квазивогнутости, если , является унимодальность , при которой существует локально максимальное значение. ${\displaystyle S\subset \mathbb {R} }$

Приложения

Квазивыпуклые функции находят применение в математическом анализе , математической оптимизации , теории игр и экономике .

Математическая оптимизация

В нелинейной оптимизации квазивыпуклое программирование изучает итерационные методы , которые сходятся к минимуму (если он существует) для квазивыпуклых функций. Квазивыпуклое программирование является обобщением выпуклого программирования . ^[1] Квазивыпуклое программирование используется при решении «суррогатных» двойственных задач , чьи двузадачные задачи обеспечивают квазивыпуклые замыкания исходной задачи, которые, следовательно, обеспечивают более узкие границы, чем выпуклые замыкания, предоставляемые лагранжевыми двойственными задачами . ^[2] Теоретически задачи квазивыпуклого и выпуклого программирования могут быть решены за разумное время, где число итераций растет как полином в размерности задачи (и в обратной величине допустимой ошибки аппроксимации); ^{[3] однако, такие теоретически} « эффективные» методы используют правила размера шага «расходящегося ряда» , которые были впервые разработаны для классических методов субградиента . Классические субградиентные методы, использующие правила расходящихся рядов, намного медленнее современных методов выпуклой минимизации, таких как методы субградиентной проекции, методы пучкового спуска и методы негладкой фильтрации.

Экономика и уравнения в частных производных: теоремы о минимаксе

В микроэкономике квазивогнутые функции полезности подразумевают, что потребители имеют выпуклые предпочтения . Квазивыпуклые функции важны также в теории игр , промышленной организации и теории общего равновесия , в частности, для приложений теоремы Сиона о минимаксе . Обобщая теорему Джона фон Неймана о минимаксе , теорема Сиона также используется в теории уравнений с частными производными .

Сохранение квазивыпуклости

Операции, сохраняющие квазивыпуклость

• Максимум квазивыпуклых функций (т.е. ) является квазивыпуклым. Аналогично, максимум строго квазивыпуклых функций является строго квазивыпуклым. ^[4] Аналогично, минимум квазивогнутых функций является квазивогнутым, а минимум строго-квазивогнутых функций является строго-квазивогнутым. ${\displaystyle f=\max \left\lbrace f_{1},\ldots ,f_{n}\right\rbrace }$
• композиция с неубывающей функцией: квазивыпуклая, неубывающая, то является квазивыпуклой. Аналогично, если квазивогнутая, неубывающая, то является квазивогнутой. ${\displaystyle g:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ ${\displaystyle h:\mathbb {R} \rightarrow \mathbb {R} }$ ${\displaystyle f=h\circ g}$ ${\displaystyle g:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ ${\displaystyle h:\mathbb {R} \rightarrow \mathbb {R} }$ ${\displaystyle f=h\circ g}$
• минимизация (т.е. квазивыпуклое, выпуклое множество, тогда является квазивыпуклым) ${\displaystyle f(x,y)}$ ${\displaystyle C}$ ${\displaystyle h(x)=\inf _{y\in C}f(x,y)}$

Операции, не сохраняющие квазивыпуклость

• Сумма квазивыпуклых функций, определенных в одной и той же области, не обязательно должна быть квазивыпуклой. Другими словами, если являются квазивыпуклыми, то не обязательно должны быть квазивыпуклыми. ${\displaystyle f(x),g(x)}$ ${\displaystyle (f+g)(x)=f(x)+g(x)}$
• Сумма квазивыпуклых функций, определенных на разных доменах (т.е. если квазивыпуклы, ), не обязательно является квазивыпуклой. Такие функции называются «аддитивно разлагаемыми» в экономике и «разделимыми» в математической оптимизации . ${\displaystyle f(x),g(y)}$ ${\displaystyle h(x,y)=f(x)+g(y)}$

Примеры

• Всякая выпуклая функция является квазивыпуклой.
• Вогнутая функция может быть квазивыпуклой. Например, является как вогнутой, так и квазивыпуклой. ${\displaystyle x\mapsto \log(x)}$
• Любая монотонная функция является как квазивыпуклой, так и квазивогнутой. В более общем смысле, функция, которая убывает до некоторой точки и возрастает от этой точки, является квазивыпуклой (сравните унимодальность ).
• Функция пола является примером квазивыпуклой функции, которая не является ни выпуклой, ни непрерывной. ${\displaystyle x\mapsto \lfloor x\rfloor }$

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

• Выпуклая функция
• Вогнутая функция
• Логарифмически вогнутая функция
• Псевдовыпуклость в смысле нескольких комплексных переменных (не обобщенная выпуклость)
• Псевдовыпуклая функция
• Функция Invex
• Конкавификация

Ссылки

1. Ди Гульельмо (1977, стр. 287–288): Ди Гульельмо, Ф. (1977). «Невыпуклая двойственность в многокритериальной оптимизации». Математика исследования операций . 2 (3): 285–291. doi :10.1287/moor.2.3.285. JSTOR  3689518. MR  0484418.
2. Ди Гульельмо, Ф. (1981). «Оценки разрыва двойственности для дискретных и квазивыпуклых задач оптимизации». В Шайбле, Зигфрид; Циемба, Уильям Т. (ред.). Обобщенная вогнутость в оптимизации и экономике: Труды Института передовых исследований НАТО, проведенные в Университете Британской Колумбии, Ванкувер, Британская Колумбия, 4–15 августа 1980 г. Нью-Йорк: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. стр. 281–298. ISBN 0-12-621120-5. МР  0652702.
3. Kiwiel, Krzysztof C. (2001). «Сходимость и эффективность субградиентных методов для квазивыпуклой минимизации». Математическое программирование, Серия A. 90 ( 1). Берлин, Гейдельберг: Springer: 1–25. doi :10.1007/PL00011414. ISSN  0025-5610. MR  1819784. S2CID  10043417.Кивил признает, что Юрий Нестеров первым установил, что задачи квазивыпуклой минимизации могут быть решены эффективно.
4. Йоханссон, Эдвард; Петерссон, Дэвид (2016). Оптимизация параметров для равновесных решений систем массового действия (диссертация на степень магистра наук). стр. 13–14 . Получено 26 октября 2016 г.

• Авриэль, М., Диверт, В. Э., Шайбл, С. и Занг, И., Обобщенная вогнутость , Plenum Press, 1988.
• Крузе, Ж.-П. (2008). «Квазивогнутость». В Дурлауф, Стивен Н.; Блюм, Лоуренс Э. (ред.). Новый экономический словарь Пэлгрейва (второе изд.). Palgrave Macmillan. стр. 815–816. doi :10.1057/9780230226203.1375. ISBN 978-0-333-78676-5.
• Сингер, Иван Абстрактный выпуклый анализ . Серия монографий и продвинутых текстов Канадского математического общества. Публикация Wiley-Interscience. John Wiley & Sons, Inc., Нью-Йорк, 1997. xxii+491 стр.  ISBN 0-471-16015-6 

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

• SION, M., «Об общих теоремах о минимаксе», Pacific J. Math. 8 (1958), 171-176.
• Глоссарий математического программирования
• Вогнутые и квазивогнутые функции — Чарльз Уилсон, экономический факультет Нью-Йоркского университета
• Квазивогнутость и квазивыпуклость - Мартин Дж. Осборн, Университет Торонто , факультет экономики