Псевдовыпуклая функция

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

Формальное определение

Вещественнозначная функция ƒ, определённая на (непустом) выпуклом открытом множестве X в конечномерном евклидовом пространстве $\mathbb {R} ^{n}$, называется псевдовыпуклой, если для всех x, y ∈ X, таких что $\nabla f(x)\cdot (y-x)\geqslant 0$, мы имеем $f(y)\geqslant f(x)$. Здесь $\nabla f$ является градиентом ƒ, определённым формулой

$\nabla f=\left({\frac {\partial f}{\partial x_{1}}},\dots ,{\frac {\partial f}{\partial x_{n}}}\right).$

Свойства

Любая выпуклая функция псевдовыпукла, но обратное неверно. Например, функция $f(x)=x+x^{3}$ псевдовыпукла, но не выпукла. Любая псевдовыпуклая функция квазивыпукла, но обратное не верно, поскольку функция $f(x)=x^{3}$ квазивыпукла, но не псевдовыпукла. Псевдовыпуклость представляют в первую очередь интерес, поскольку точка x* является локальным минимумом псевдовыпуклой функции ƒ тогда и только тогда, когда она является стационарной точкой функции ƒ, что случается при обращении градиента функции ƒ в нуль на x*:

$\nabla f(x^{*})=0.$.

Обобщения на недиффиренцируемые функции

Понятие псевдовыпуклости может быть обобщено на недифференцируемые функции следующим образом. Если дана функция $f:X\to \mathbb {R}$, то можно определить её верхнюю производную Дини как

$f^{+}(x,u)=\limsup _{h\to 0^{+}}{\frac {f(x+hu)-f(x)}{h}}$

где u является любым единичным вектором. Говорят, что функция псевдовыпукла, если она возрастает в любом направлении, где верхняя производная Дини положительна. Более точно, её можно описать в терминах субдифференциала $\partial f$ следующим образом:

• Для всех $x,y\in X$, если существует $x^{*}\in \partial f(x)$, такая что $\langle x^{*},y-x\rangle \geqslant 0\,,$ то $f(x)\leqslant f(z)$ для всех z на отрезке, соединяющем x и y.

Связанные понятия

Псевдовогнутая функция — это функция, отрицательная для которой псевдовыпукла. Псевдолинейная функция — это функция, которая одновременно псевдовыпукла и псевдовогнута. Например, задачи дробно-линейного программирования имеют псевдолинейные целевые функции и линейные ограничения-неравенства. Эти свойства позволяют решать задачи дробного программирования вариантом симплекс-метода (Джорджа Б. Данцига).

См. также

• Псевдовыпуклость