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

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

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

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

[math]\displaystyle{ \nabla f = \left(\frac{\partial f}{\partial x_1},\dots,\frac{\partial f}{\partial x_n}\right). }[/math]

Свойства

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

[math]\displaystyle{ \nabla f(x^*) = 0. }[/math].

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

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

[math]\displaystyle{ f^+(x,u) = \limsup_{h\to 0^+} \frac{f(x+hu) - f(x)}{h} }[/math]

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

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

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

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

См. также

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