Лекция: СВОЙСТВА ВЫПУКЛЫХ ФУНКЦИЙ

Определение 3.1.Пусть х, у Î Еn . Множество {z} Ì Еn точек вида

z = ax + (1 — a)y, aÎ[0; 1] (3.16)

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

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

Определение 3.2. Множество U Ì Еn называется выпуклым, если с любыми точками х и у ÎU оно содержит и весь отрезок (3.16). Очевидно, Еn — выпуклое множество.

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

Пусть U= . Рассмотрим произвольные точки х1 и x2ÎU.

Очевидно, х1 и x2ÎU2при любом i = 1, .., т и, так как все Ui — выпуклы, отрезок [х1, x2]Í Uiдля всех i. Следовательно, он целиком принадлежит и множеству U.

Определение 3.3. Функция f(х), заданная на выпукломмножестве U Ì Еn называется выпуклой, если для любых точек x, yÎ U любого a Î [0; 1] выполняется неравенство

f[ax + (1- a)y] £ af(x) + (1-a)f(y). (3.17)

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

Теорема 3.2. Линейнaя комбинaция выпуклых нa выпуклом мно­жестве Uфункций fi(х), i = 1, .., т,с неотрицaтельными коэффициентами li, т.е., li ³ 0 естьвыпуклaя нa множестве U функция.

При li ³ 0 функции lifi(х), выпуклы, поэтому для них выполня­ются неравенства (3.17). Складывая эти неравенства, получаем:

, x,y Î U, aÎ [0; 1].

Теорема 3.3 — Пусть g(x) — выпуклaя функция,зaдaннaя в про­стрaнстве Еn, Тогда множество U точек х,удовлетворяющих не­равенству g(x) £ b,выпукло.

Пусть х и y Î U и z = aх + (1 — a)у, a Î [0; 1]. Из выпуклости функции g(x) следует, что g(z) £ ag(x) + (l — a)g(y) и, следовательно, g(z)£ b, т.е. точка z ÎU и множество U — выпукло.

Следствие. Пусть gi(x), i=l, .., m, — выпуклые функции в Еn .

Тогда множество точек х, удовлетворяющих системе неравенств

gi(x) £ bi i = 1, …, m, выпукло.

Это следует из теорем 3.1 и 3.3.

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

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

Предположим противное, т.е. пусть х0— точка локального, а х* — точка глобального минимума f(х) на множестве U, х*¹х0и f(х0) > f(х*). Отсюда с учетом выпуклости функции имеем:

f[ax*+(1- a)x0] £ af(x*) + (1- a)f(х0)<f(х0).

При a® +0 точка х = aх* + (1-a)х0попадет в сколь угодно малую окрестность точки х0. Поэтому полученное неравенство f(х) < f(х0) противоречит предположению о том, что х0— точка локального минимума.

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

Предположим, что х1 и х2— две различные точки глобального минимума. Из строгой выпуклости f(х) следует, что для всех a Î (0; 1) выполняется строгое неравенство f[ax1+(1- a)x2] < af(x1) + (1-a)f(х2) = f * = f(x), что противоречит предположению о том, что х1 и х2 —точки глобального минимума.

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

Замечание. Отметим, что не всякая выпуклая в En функция достигает минимального значения, даже если она ограничена снизу. Например, функция f(x) = exявляется выпуклой в пространстве E1, но достигает минимума

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

Определение 3.4. Функция f(х), заданная в En, называется сильно выпуклой, если существует такое число l > 0 (константа сильной вы­пуклости), что для всех х и у ÎEn и любого a Î [0; 1] выполняется не­равенство:

.

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

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

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

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

f(x) ³ f(x0) + < f ¢(x0), x — x0>, (3.18)

строгая выпуклость —

f(x) > f(x0) + < f ¢(x0), x — x0>, (3.19)

сильная выпуклость —

f(x) ³ f(x0) + < f ¢(x0), x — x0> + (3.18)

для любыхх, х0Î En

На рис. 3.1 приведена иллюстрация неравенств (3.18)—(3.20) для пространства E2. График выпуклой, но не строго выпуклой функции f=f(х) (рис. 3.1, а) расположен не ниже касательной плос­кости z = f(х0) + < f '(х0), х- х0>, проходящей через произвольную точку поверхности (х0, f(х0)). График строго выпуклой функции (рис. 3.1,6) имеет единственную общую точку с этой плоскостью. Подобное свойство для выпуклой функции одной переменной было рассмотрено в разд. 2.3.3.

Предположим теперь, что f(х) сильно выпуклаих* — точка ее глобального минимума. Тогда f '(x*)=0 и неравенство (3.20) принимает вид f(x) ³ f(x*) + + .

Рис. 3.1. Геометрическая иллюстрация неравенств (3.18) — (3.20) для функции f(x) двух переменных: A — выпуклaя,но не строго выпуклaя; б — строго выпуклaя; в — сильно выпуклaя.

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

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

Приведем критерии строгой и сильной выпуклости для дважды дифференцируемых в Еn функций. Достаточным условием строгой выпуклости функции f(х) является положительная определенность при x Î Еn ее матрицы Гессе f"(х), а сильной выпуклости — положительная определенность матрицы f"(х) — lЕ, где Е— единичная матрица, а l > 0. Эти критерии в комбинации с критерием Сильвестра (3.5) составляют во многих случаях удобный аппарат для проверки выпуклости функций небольшого числа переменных.