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

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

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

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

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

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

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

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

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

Если, кроме того,

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

Примеры

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

См. также

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

Ссылки

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

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

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

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

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

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

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

[4] Йоханссон, Эдвард; Петерссон, Дэвид (2016). Оптимизация параметров равновесных решений систем действия масс (магистерская диссертация). стр. 13–14 . Проверено 26 октября 2016 г.

[1]

[2]

[3]

[4]

v т и Выпуклый анализ и вариационный анализ
Основные понятия	Выпуклая комбинация Выпуклая функция Выпуклый набор
Темы (список)	Теория Шоке Выпуклая геометрия Выпуклое метрическое пространство Выпуклая оптимизация Двойственность Множитель Лагранжа Преобразование Лежандра Локально выпуклое топологическое векторное пространство Симплекс
Карты	Выпуклое сопряжение Вогнутый ( Закрыто К- Логарифмически Правильный Псевдо- Квази- ) Выпуклая функция Функция инвекс Преобразование Лежандра Полунепрерывность Субпроизводная
Основные результаты (список)	Теорема Каратеодори Вариационный принцип Экланда Теорема Фенхеля – Моро. Неравенство Фенхеля-Янга Неравенство Дженсена Неравенство Эрмита–Адамара. Теорема Крейна – Милмана Лемма Мазура Лемма Шепли – Фолкмана. Робинсон-Урсеску Саймонс Урсеску
Наборы	Выпуклая оболочка ( Ортогонально , Псевдо- ) Выпуклое множество Эффективный домен Эпиграф Гипограф Джон эллипсоид Объектив Радиальное множество / Алгебраическая внутренняя часть Зонотоп
Ряд	Выпуклые ряды, связанные ( (cs, lcs)-замкнутые , (cs, bcs)-полные , (нижние) идеально выпуклые , (H x ) и (Hw x ) )
Двойственность	Двойная система Разрыв двойственности Сильная двойственность Слабая двойственность
Приложения и связанное с ними	Выпуклость в экономике