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

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

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

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

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

В математике , А квазивыпуклая функция является реальной значной функцией , определенной на интервале или на выпуклое подмножество вещественного векторного пространства таким образом, что прообраз любого множества вида является выпуклым множеством . Для функции одной переменной на любом участке кривой высшая точка является одной из конечных точек. Отрицательный элемент квазивыпуклой функции называется квазивогнутым .${\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] однако такие теоретически «эффективные» методы используют правила шага «расходящихся рядов» , которые были впервые разработаны для классических субградиентных методов . Классические субградиентные методы, использующие правила расходящихся рядов, намного медленнее, чем современные методы выпуклой минимизации, такие как методы субградиентной проекции, методы связки спуска и методы негладкой фильтрации .

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

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

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

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

• максимум квазивыпуклых функций (т.е. ) квазивыпуклый. Точно так же максимум строгих квазивыпуклых функций строго квазивыпуклый. ^[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 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
• Вогнутость

Ссылки [ править ]

• Авриэль М., Диверт У., Шейбл С. и Занг И., Generalized Concavity , Plenum Press, 1988.
• Крузе, Ж.-П. (2008). «Квазивогнутость». В Durlauf, Steven N .; Блюм, Лоуренс Э (ред.). Новый экономический словарь Пэлгрейва (второе изд.). Пэлгрейв Макмиллан. С. 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.
• Глоссарий математического программирования
• Вогнутые и квазивогнутые функции - Чарльз Уилсон, Департамент экономики Нью-Йоркского университета
• Квазивогнутость и квазивыпуклость - Мартин Дж. Осборн, факультет экономики Университета Торонто