1.2.4. Понятия выпуклого множества и выпуклой функции

Множество Х  Rⁿ называется выпуклым, если при всех х¹, х²  X,   [0, 1]. Иными словами, множество Х выпукло, если оно вместе с любыми своими двумя точками х¹ и х² содержит соединяющий их отрезок, т. е. множество вида

[x¹, x²] = {x  Rⁿ | x = x² + (x¹ - x²), 0    1}

(рис. 1.4).

Рис.1.4. а) Выпуклое множество; б) невыпуклое множество

На числовой прямой R выпуклыми множествами являются все­возможные промежутки, т.е. одноточечные множества, интервалы, полуинтервалы, отрезки, полупрямые и, наконец, сама. прямая. При­мерами выпуклых множеств в пространстве Rⁿ служат само прост­ранство, любое его линейное подпространство, одноточечное множе­ство, шар, отрезок, а также следующие множества:

– прямая, проходящая через точку х⁰ в направлении вектора h;

– луч, выходящий из точки х⁰ в направлении h;

(1.15)

– гиперплоскость с нормалью р;

, (1.16)

– порождаемые ею полупространства.

Все перечисленные множества, кроме шара, являются частными случаями выпуклого множества вида

X = {x  Rⁿ | Ax  b} = { x  Rⁿ |  ai, x  b_i, i = 1,…, m}, (1.17)

где A – некоторая матрица размера т  п со строками a₁, …, a_m, b = (b₁, …, b_m)  R^m (т = 1, 2, ...). Множества вида (1.17) принято называть полиэдральными или просто полиэдрами. Таким образом, полиэдр — это множество решений некоторой системы конечного числа линейных неравенств, или, что то же самое, пересечение конечного числа полупространств.

Функция f, определенная на выпуклом множестве , называется выпуклой на X, если

(1.18)

при всех х¹, х²  Х,   [0, 1]. Если при всех х¹, х²  Х, x¹  x²,   [0, 1] неравенство (1.18) выполняется как строгое, то f называется строго выпуклой на X. Функция f назы­вается (строго) вогнутой, если функция – f (строго) выпукла.

Геометрически выпуклость функции f означает, что любая точка произвольной хорды графика f располагается не ниже соответствую­щей точки самого графика (рис.1.6, а). Для вогнутой функции взаимное расположение хорды и графика обратно (рис.1.6, б). Функции f (х) = х², f(x) = e^x выпуклы на R; f(x) = ln x вогнута на множестве положительных чисел; f(x) = sin x вогнута на [0, ] и выпукла на [, 2]. Отметим, что указанные функции, в самом деле, строго выпуклы или вогнуты. Функция f(x)= ||x|| выпукла, f(x) = ||x||² строго выпукла на Rⁿ. Функцию вида

f(x)= a, x + b, (1.19)

где a  Rⁿ, b  R, будем называть линейной. Ясно, что для линей­ной функции неравенство (1.18) выполняется как равенство. Поэтому она одновременно выпукла и вогнута на Rⁿ, но не строго.

Рис. 1.6. а) Выпуклая функция; б) вогнутая функция

1.2.5. Выпуклая задача оптимизации

Задача (1.1) называется выпуклой, если X – выпуклое множество, f – выпуклая функция на X.

Теорема 1.8. Если задача (1.1) выпукла, то любое ее локаль­ное решение является также глобальным.

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

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

Теорема 1.9. Пусть функция f выпукла на Rⁿ и дифференци­руема в точке х*  Rⁿ. Если f'(х*) = 0, то х* – точка минимума f на X, т. е. решение задачи (1.5).

Полученные свойства выпуклых задач имеют важное значение не только в теории, но и в численных методах оптимизации. Дело в том, что большинство существующих численных методов позво­ляет, вообще говоря, находить лишь локальные решения, а точнее, стационарные точки задачи. Теоремы 1.8, 1.9 говорят о том, что для выпуклой задачи отыскание стационарной точки автоматически означает отыскание решения, причем глобального.

Укажем еще одно полезное свойство выпуклых задач.

Теорема 1.10. Пусть задача (1.1) выпукла и имеет решение. Тогда множество ее решений выпукло (рис. 1.7, а). Если при этом f строго выпукла на X, то решение задачи единст­венно, т. е. X* состоит из одной точки (рис. 1.7, б).

Рис.1.7. Выпуклость множества решений выпуклой задачи оптимизации