Выпуклые функции

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

Числовую функцию f, определенную на выпуклом множестве X, X Ì Eⁿ, называют выпуклой, если для любых двух точек x ₁, x ₂Î X и произвольного числа l Î[0;1] выполняется неравенство

f (l x ₁+(1- l) x ₂) £ l f (x ₁)+(1- l) f (x ₂). (3.1)

Неравенство противоположного смысла определяет вогнутую функцию, причем часто используются термины «выпуклая вниз» (1) «выпуклая вверх» (2) (рис. 3.6.).

Рис. 3.6. Выпуклая (выпуклая вниз) функция (1), вогнутая (выпуклая вверх) функция (2)

Геометрически выпуклость функции f означает, что любая точка произвольной хорды графика f располагается не ниже соответствующей точки самого графика (лежит ниже хорды, соединяющей две точки ее графика) (рис. 3.6, кривая 1).

Простейшими примерами выпуклых функций одной переменной служат парабола y = x ² и экспонента y = e ^x. Функции y = - x ² и y = -e ^x являются вогнутыми.

Если при всех x _1, x ₂Î X x ₁ ¹ x ₂ и l Î[0,1] неравенство (3.1) выполняется как строгое (<), то f называется строго выпуклой на X (рис. 3.7,а). Функция называется (строго) вогнутой, если - f (строго) выпукла (рис. 3.7, б).

О выпуклости или вогнутости целевой функции можно судить также по характеру изменения ее частных производных ¶ f /¶ x. В случае строго выпуклой функции эта производная по мере увеличения аргумента возрастает (рис. 3.7, а), а для строго вогнутой падает (рис. 3.7, б). При наличии линейного участка целевой функции указанная производная на этом участке постоянна.

Рис. 3.7. Строго выпуклая (а) и строго вогнутая функции, их производные (пунктир) и функция, имеющая линейный участок (в)

Определение. Функция f (x), определенная на выпуклом множестве Х, называется сильно выпуклой с константой l > 0, если

f (λ x ₁)+(1- λ) x ₂≤ λ f (x ₁)+ (1- λ) f (x ₂)- λ (1- λ) ,

0 ≤ λ ≤1 (3.2)

Дадим геометрическую интерпретацию определения (3.2), рассмотрев функцию y= f (x ) одного переменного. Зафиксировав x ₁ и x ₂ из области определения функции и обозначив х (λ) = λ х ₁+(1 - λ) х ₂, будем изменять l от 0 до 1. Ясно, что тогда значение x (l), будет изменяться от x ₁ до х ₂, а точка (х, f (x)) пройдет по графику функции y= f (x) от точки B = (x ₂, f (x ₂)) до точки А = (х ₁, f (x ₁)) (рис. 3.8).

Рис. 3.8. График сильно выпуклой функции

Уравнения

в плоскости x O y описывают прямую L (секущую), соединяющую точки А и В, а уравнения

задают параболу Р вида , которая проходит через точки А и В. Неравенство (3.2) в этом случае означает, что график функции y = f (x) на плоскости х 0 у расположен ниже не только секущей, соединяющей точки А и В, но и параболы Р, прогиб которой определяется параметром l и его можно выбрать сколь угодно малым. Другими словами, в области, ограниченной секущей и графиком функции, можно построить параболу, соединяющую точки А и В.

Теорема 3.1. Непрерывно дифференцируемая на выпуклом множестве X функция f выпукла на этом множестве тогда и только тогда, когда для любых x ₁, x ₂Î X верно неравенство

f (x ₂) ³ f (x ₁) + <Ñ f (x ₁, x ₂ - x ₁)>, (3.3)

получаемое из разложения функции f (x) в ряд Тейлора в точке x ₁ путем исключения членов второго и более высокого порядка разложения

f (x ₁+ h) = f (x ₁) + hf ¢(x ₁) + h ²/2∙ f ¢¢(x ₁) +...,

где h достаточно малое число, | h | < d. Известно, что если функция f дифференцируема в точке x ₁, то она в этой точке непрерывна и

Ñ f (x ₁) = (¶ f /¶ x ₁, ¶ f /¶ x ₂,…, ¶ f /¶ x _n)^т,

т.е. представляет собой вектор частных производных первого порядка, вычисленных в точке x ₁ и называется градиентом функции f в точке x ₁. Каждая частная производная ¶ f /¶ x_i определяет проекцию градиента на ось x_i в евклидовом пространстве Eⁿ. В любой точке градиент показывает направление наибольшей скорости возрастания функции, а проекции дают составляющие этой скорости. Антиградиент –Ñ f (x ₁) указывает направление наибольшей скорости убывания функции.

Теорема 3.2. Пусть функция f дважды непрерывно дифференцируема на выпуклом множестве X, содержащем хотя бы одну внутреннюю точку, и Ѳ f (x) – ее гессиан. Тогда для выпуклости f на множестве X необходимо и достаточно, чтобы матрица Ѳ f (x) была неотрицательно определена при всех x Î X, т.е. чтобы неравенство

<Ѳ f (x) h, h > ³ 0 (3.4)

выполнялось для всех точек x Î X, h Î E. Здесь числовая матрица Ѳ f (x) называется гессианом (или матрицей Гессе). Если функция f имеет непрерывные частные производные второго порядка (дважды непрерывно дифференцируема) в точке x ₁, то она дважды дифференцируема в x ₁ и обладает матрицей Гессе вида

,

причем эта матрица симметрична, т.е. .

Аналогичные утверждения имеют место и для вогнутых функций. При этом в формулах (3.3) и (3.4) знак неравенства ³ следует заменить на £.

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

Выпуклое множество вида

X = { x Î Eⁿ } | Аx £ b} = { x Î Eⁿ | < a_i, x > £ b_i, i = 1: m },

где А – некоторая матрица размера m х m со строками a ₁,.., a_m, b = (b ₁,.., b_m) Î Eⁿ (m = 1,2,…) принято называть полиэдральным или просто полиэдром. Таким образом, полиэдр − это множество решений некоторой системы конечного числа линейных неравенств, или, что то же самое, пересечение конечного числа полупространств (рис. 3.9).

Отметим важное свойство выпуклой функции. Если функция f выпукла на множестве X, то для любых точек x ₁, x ₂,..., x_m Î X и произвольных неотрицательных чисел l₁+l₂+...l _m = 1 имеет место неравенство Иенcена

f (l₁ x ₁ + l₂ x ₂ +...+ l _mx_m) £ l₁ f (x ₁) + l₂ f (x ₂) +...+ l _mf (x_m).

При m = 2 это неравенство совпадает с неравенством (3.1) из определения выпуклой функции.

< a 1, x>= b 1

< a 4, x>= b 4

< a 3, x>= b 3

< a 2, x>= b 2

Рис. 3.9. Полиэдральное множество (полиэдр)