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

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

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

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

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

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

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

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

Функция, определенная на выпуклом подмножестве реального векторного пространства, является квазивыпуклой, если для всех и мы имеем ${\ displaystyle f: S \ to \ mathbb {R}}$ ${\ displaystyle S}$ ${\ displaystyle x, y \ in S}$ ${\ Displaystyle \ лямбда \ в [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 _ {\ альфа} (е) = \ {х \ середина е (х) \ Leq \ альфа \}}$

Если к тому же

{\ Displaystyle е (\ лямбда х + (1- \ лямбда) у) <\ макс {\ большой \ {} е (х), е (у) {\ большой \}}}

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

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

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

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

{\ Displaystyle е (\ лямбда х + (1- \ лямбда) у)> \ мин {\ большой \ {} е (х), е (у) {\ большой \}}}

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

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

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

Приложения

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

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

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

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

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

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

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

максимум квазивыпуклых функций (т.е. ) квазивыпуклый. Точно так же максимум строгих квазивыпуклых функций строго квазивыпуклый. Аналогичным образом , минимальные из квазивогнутых функций квазивогнутая, а минимум строго-квазивогнутых функций строго-квазивогнутый. ${\ 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 ч (х) = \ inf _ {у \ в С} е (х, у)}$

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

Сумма квазивыпуклых функций, определенных в одной и той же области, не обязательно должна быть квазивыпуклой: другими словами, если они квазивыпуклые, то не обязательно квазивыпуклые. ${\ Displaystyle е (х), г (х)}$ ${\ Displaystyle (е + г) (х) = е (х) + г (х)}$
Сумма квазивыпуклых функций, определенных в разных областях (т. Е. Если они квазивыпуклые, ) не обязательно должна быть квазивыпуклой. Такие функции называются «аддитивно разложенными» в экономике и «отделимыми» в математической оптимизации . ${\ Displaystyle е (х), г (у)}$ ${\ Displaystyle ч (х, у) = е (х) + г (у)}$

Примеры

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

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

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

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

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

[1] Ди Гульельмо (1977 , стр. 287–288): Ди Гульельмо, Ф. (1977). «Невыпуклая двойственность в многокритериальной оптимизации». Математика исследования операций . 2 (3): 285–291. DOI : 10.1287 / moor.2.3.285 . JSTOR 3689518 . Руководство по ремонту 0484418 .

[2] Ди Гульельмо, F. (1981). «Оценки разрыва двойственности для дискретных и квазивыпуклых задач оптимизации». В Шайбле Зигфрид; Зиемба, Уильям Т. (ред.). Обобщенные вогнутость в оптимизации и экономике: Труды Института перспективных исследований НАТО провели в Университете Британской Колумбии, Ванкувер, Британская Колумбия, август 4-15, 1980 . Нью-Йорк: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. С. 281–298. ISBN 0-12-621120-5 . Руководство по ремонту 0652702 .

[3] Kiwiel, Кшиштоф C. (2001). «Сходимость и эффективность субградиентных методов квазивыпуклой минимизации». Математическое программирование, Series A . 90 (1). Берлин, Гейдельберг: Springer. С. 1–25. DOI : 10.1007 / PL00011414 . ISSN 0025-5610 . MR 1819784 . Кивил признает, что Юрий Нестеров первым установил, что квазивыпуклые задачи минимизации могут быть эффективно решены.

[4] Йоханссон, Эдвард; Петерссон, Дэвид (2016). «Оптимизация параметров равновесных решений систем массового действия» : 13–14 . Проверено 26 октября +2016 . Цитировать журнал требует |journal= ( помощь )

Languages

In other projects