Псевдовыпуклая функция
Псевдовыпуклая функция — это функция, которая ведёт себя подобно выпуклой функции с точки зрения нахождения её локального минимума, но не обязательно выпукла. Неформально, дифференцируемая функция псевдовыпукла, если она возрастает в любом направлении, где имеет положительную производную по направлению.
Формальное определение
[править | править код]Вещественнозначная функция ƒ, определённая на (непустом) выпуклом открытом множестве X в конечномерном евклидовом пространстве , называется псевдовыпуклой, если для всех x, y ∈ X, таких что , мы имеем [1]. Здесь является градиентом ƒ, определённым формулой
Свойства
[править | править код]Любая выпуклая функция псевдовыпукла, но обратное неверно. Например, функция псевдовыпукла, но не выпукла. Любая псевдовыпуклая функция квазивыпукла, но обратное не верно, поскольку функция квазивыпукла, но не псевдовыпукла. Псевдовыпуклость представляют в первую очередь интерес, поскольку точка x* является локальным минимумом псевдовыпуклой функции ƒ тогда и только тогда, когда она является стационарной точкой функции ƒ, что случается при обращении градиента функции ƒ в нуль на x*:
- [1].
Обобщения на недиффиренцируемые функции
[править | править код]Понятие псевдовыпуклости может быть обобщено на недифференцируемые функции следующим образом[2]. Если дана функция , то можно определить её верхнюю производную Дини как
где u является любым единичным вектором. Говорят, что функция псевдовыпукла, если она возрастает в любом направлении, где верхняя производная Дини положительна. Более точно, её можно описать в терминах субдифференциала следующим образом:
- Для всех , если существует , такая что то для всех z на отрезке, соединяющем x и y.
Связанные понятия
[править | править код]Псевдовогнутая функция — это функция, отрицательная для которой псевдовыпукла. Псевдолинейная функция — это функция, которая одновременно псевдовыпукла и псевдовогнута[3]. Например, задачи дробно-линейного программирования имеют псевдолинейные целевые функции и линейные ограничения-неравенства. Эти свойства позволяют решать задачи дробного программирования вариантом симплекс-метода (Джорджа Б. Данцига)[4][5][6].
См. также
[править | править код]Примечания
[править | править код]- ↑ 1 2 Mangasarian, 1965.
- ↑ Floudas, Pardalos, 2001.
- ↑ Rapcsak, 1991.
- ↑ Craven, 1988, с. 145.
- ↑ Kruk, Wolkowicz, 1999, с. 795–805.
- ↑ Mathis, Mathis, 1995, с. 230–234.
Литература
[править | править код]- Craven B. D. Fractional programming. — Berlin: Heldermann Verlag, 1988. — Т. 4. — С. 145. — (Sigma Series in Applied Mathematics). — ISBN 3-88538-404-3.
- Serge Kruk, Henry Wolkowicz. Pseudolinear programming // SIAM Review. — 1999. — Т. 41. — С. 795–805. — doi:10.1137/S0036144598335259. — .
- Frank H. Mathis, Lenora Jane Mathis. A nonlinear programming algorithm for hospital management // SIAM Review. — 1995. — Т. 37, № 2. — С. 230–234. — doi:10.1137/1037046. — .
- Christodoulos A. Floudas, Panos M. Pardalos. Generalized monotone multivalued maps // Encyclopedia of Optimization. — Springer, 2001. — С. 227. — ISBN 978-0-7923-6932-5.
- Rapcsak T. On pseudolinear functions // European Journal of Operational Research. — 1991. — Т. 50, вып. 3. — С. 353–360. — ISSN 0377-2217. — doi:10.1016/0377-2217(91)90267-Y.
- Mangasarian O. L. Pseudo-Convex Functions // Journal of the Society for Industrial and Applied Mathematics Series A Control. — 1965. — Январь (т. 3, вып. 2). — С. 281–290. — ISSN 0363-0129. — doi:10.1137/0303020.
Для улучшения этой статьи желательно:
|