Выпуклые множества и выпуклые функции. Свойства выпуклых функций

Определение 1:

Пусть x,yЄЕn. Множество {z}ЄЕn точек

вида z=x+(1-)y, Є[0,1] (1)

называется отрезком, соединяющим точки x и y.

В пространстве Еn, n3 соотношение (1) определяет обычный отрезок, соединяющий точки х и у. Для точки z, прямой, проходящей через точки х и у, справедливо представление: z=y+(x-y), которое отличается от (1) лишь формой записи. При =0 точки z совпадает с одним из концов отрезка (z=y), а при =1 с другим (z=x). При изменении от 0 до 1 точка z пробегает отрезок от точки у до точки х.

Определение 2:

Множество UЄEn называется вынужденным, если вместе с любыми точками ХиY Є U оно содержит и весь отрезок (1).

Очевидно, Еn – выпуклое множество.

Теорема 1: Пересечение выпуклых множествU, i=1,…,m, есть выпуклое множество, если оно содержит более одной точки.

Определение 3:

f(x), заданная на выпуклом множестве UЄEn, называется выпуклой, если для точек ХиYЄU и Є[0,1] выполняется неравенство:

f[х+(1-)у]f(x)+(1-)f(y) (2)

Функция f(x) называется строго выпуклой, если для всех Є(0,1) неравенство (2) выполняется как строгое.

Теорема 2: Линейная комбинация выпуклых на выпуклом множестве U функций f(x), i=с неотрицательными коэффициентами , т.е. f(x)=, , есть выпуклая на множестве U функция.

Теорема 3: Пусть g(х) – выпуклая функция, заданная в пространстве Еn. Тогда множество U точек Х, удовлетворяющих неравенству g(х)в, выпукло.

Приведем свойства выпуклых функций, играющие важную роль в вопросах min-ии:

Теорема 1: Пусть f(x) – выпуклая на выпуклом множестве U функция. Тогда любой ее локальный минимум на множестве U является одновременно и глобальным.

Теорема 2: Глобальный min-м строго выпуклой функции f(x) на выпуклом множестве U может достигаться в единственной точке.

Наличие локальных min-ов функции f(x), не совпадающих с глобальным, сильно затрудняет поиск точки глобального min-ма f(x). Поэтому применение многих методов min-ции обосновано только для функции, не имеющих точек локального min-ма, отличных от глобального. Этим объясняется особая роль свойства выпуклости функции во многих вопросах оптимизации.

Замечание: Отметим, что не всякая выпуклая в Еn функция достигает min-го значения, даже если она ограничена снизу.

Введем класс функций, для которых min-м в Еn обязательно существует.

Определение:

Функция f(x), заданная в Еn, называется сильно выпуклой, если существует такое число >0 (- это константа сильной выпуклости), что для всех ХиYЄЕn и любого Є[0,1] выполняется неравенство:

f[x+(1-)y]f(x)+(1-)f(y)-(1-)||x-y||

Очевидно, сильно выпуклая функция является выпуклой и строго выпуклой.

Замечание: Можно показать, что у сильно выпуклой функции точка глобального min-ма существует и единственна.

- скалярное произведение

Для дифференцированных в Еn функций f(x) выпуклость эквивалентна выполнению неравенства

f(x)f(x), x-x>, (1) – нестрогая выпуклость

f(x)>f(x)+<f(х), x-x>, (2) – строгая выпуклость

f(x)f(x)+<f(х), x-x>+||x-х|| (3) – сильная выпуклость

для любых x,xЄЕn.

Рассмотрим графики этих функций:

а) График функции f(x) не ниже касательной плоскости z=f(x)+<f(х), x-x>, проходящей через произвольную точку поверхности (x,f(x))

б) График функции имеет единственную общую точку с плоскостью z

в) Предположим, что f(x) сильно выпуклая и Х* - точка ее глобального min-а. Тогда f(х*)=0 и неравенство (3) принимает вид f(x)f(x*)+||x-х*||

Поверхность z= f(x*)+||x-х*||представляет собой параболоид вращения с вершиной в точке (x*, f(x*)). Поэтому график сильно выпуклой функции расположен внутри некоторого параболоида вращения.

 

Замечание:

Из неравенства (1) для выпуклой дифференциальной функции f(х) следует, что условие f(х*)=0 является не только необходимым, но и достаточным для того, чтобы х* была точкой глобального min-ма функции f(х).

Дата добавления: 2014-01-07