Элементы выпуклого анализа.

Множество xϵRⁿ называется выпуклым, если λx₁ + (1 - λ)x₂ ϵ X при всех x1, x2 ϵ X,λ ϵ [0,1]. Иными словами, множество X выпукло, если оно вместе с любыми своими двумя точками x1 и x2 содержит соединяющий их отрезок [x1, x2 ] = {xϵRⁿ | x = x2 +λ (x1 - x2), 0 ≤ λ ≤ 1}.

(выпуклое) (невыпуклое)

На числовой прямой R выпуклыми множествами являются всевозможные промежутки, то есть одноточечные множества, интервалы, полуинтервалы, отрезки, полупрямые, а также сама прямая. Примерами выпуклых множеств в пространстве Rn служат само пространство, любое его линейное подпространство, одноточечное множество, шар, отрезок, а также прямая, проходящая через точку x0 в направлении вектора h, луч, выходящий из точки x0 в направлении вектора h, гиперплоскость с нормалью p и порождаемые ею полупространства. Пустое множество по определению выпуклое. Нетрудно понять, что все перечисленные множества, кроме шара, являются частными случаями выпуклого множества вида

X = {x ϵ Rⁿ | Ax ≤ b} = {x ϵ Rⁿ | ≤ b_i, i = 1,…,m} (1)

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

Выпуклой комбинацией точек x1,…, xm называется точка

z =a₁x₁ +a₂ x₂ +…+a_mx_m, где a_i ≥ 0, i = 1,…,m, и a₁ +a₂ +…+ a_m = 1.

Теорема 2. Выпуклое множество X содержит выпуклые комбинации всех своих точек. Функция f (x), определенная на выпуклом множестве X ϵ Rⁿ, называется выпуклой на X, если f (λx₁ + (1 - λ)x₂) ≤ λ f (x₁) + (1 - λ) f (x₂) (2).

при всех x1, x2 ϵ X, λ ϵ [0,1]. Если при всех x1, x2 ϵ X, x1≠ x2 и λ ϵ (0,1) неравенство (2) выполняется как строгое, то f называется строго выпуклой на X. Функция f называется (строго) вогнутой, если функция (- f) (строго) выпукла.

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

Для вогнутой функции взаимное расположение хорды и графика обратно.

Функцию вида f (x) = + b, где aϵRⁿ, bϵR будем называть линейной. Ясно, что для линейной функции неравенство (2) выполняется как равенство. Поэтому она одновременно выпукла и вогнута на Rⁿ, но не строго.

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

Теорема 3. Выпуклая функция f (x), определенная на выпуклом множестве X, непрерывна в каждой внутренней точке этого множества.

Теорема 4. Функция f(x), дифференцируемая на выпуклом множестве X, выпукла тогда и только тогда, когда для любых x, yϵ X справедливо ≤ f(y) - f(x).

Теорема 5. Функция f(x), определенная и дважды непрерывно дифференцируемая на выпуклом множестве X, (строго) выпукла тогда и только тогда, когда матрица (положительно) неотрицательно определена для любого x ϵ X.

Для исследования матрицы B(x) на знакоопределенность используют, как правило, критерий Сильвестра.

Теорема 6. Для любой выпуклой функции f (x), определенной на выпуклом множестве X, и любого числа λ множество {x ϵ X | f (x) ≤ l} выпукло.

Теорема 7 (неравенство Йенсена). Если функция f (x) выпукла на выпуклом множестве X, то , где x_i ϵ x, a_i ≥ 0, i = 1,…,m, и a1 +a2 +…+am = 1.

Экстремальная задача , φ_i(x) ≤ 0, i = 1 называется выпуклой, если S – выпуклое множество, f, φ_i(x) ≤ 0, i = 1,…,m, – выпуклые функции на S.

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

Теорема 8. Если экстремальная задача выпукла, то любое ее локальное решение

является также глобальным.

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

Теорема 9. Пусть функция f выпукла на Rⁿ и дифференцируема в точке x* ϵ Rⁿ. Если f '(x*) = 0, то x* – точка минимума f на Rⁿ.

Теоремы 8, 9 говорят о том, что для выпуклой задачи отыскание стационарной точки автоматически означает отыскание решения, причем глобального.

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

Теорема 10. Пусть экстремальная задача выпукла и имеет решение. Тогда множество ее решений Q* = Arg min f (x) xϵQ выпукло. Если при этом функция f строго выпукла на множестве Q, то решение задачи единственно.

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

Определение 1. Дифференцируемая функция f называется сильно выпуклой (с константой l > 0), если для любых x и y из Rⁿ справедливо

f (x + y) ≥ f (x) + + l

Лемма 1. Если функция f является сильно выпуклой (с константой l > 0), то она имеет глобальный минимум на Rⁿ .

Лемма 2. Если функция является сильно выпуклой (с константой l > 0) и x* – ее глобальный минимум, то для любого xϵRⁿ выполняется неравенство

≥ 2l(f (x) - f (x*)).

Лемма 3. Пусть f – дважды непрерывно дифференцируемая функция. Если

f – сильно выпуклая функция с константой l, то выполняется неравенство

|| [ f ’’(x)]^-1 ||≤ l ^-1.

Не нашли, что искали? Воспользуйтесь поиском: