Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




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

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

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

X = {x ϵ Rn | Ax ≤ b} = {x ϵ Rn | ≤ bi, i = 1,…,m} (1)

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

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

z =a1x1 +a2 x2 +…+amxm , где ai ≥ 0 , i = 1,…,m , и a1 +a2 +…+ am = 1 .

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

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

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

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

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

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

Теорема 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 , то , где xi ϵ x, ai ≥ 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 выпукла на Rn и дифференцируема в точке x* ϵ Rn. Если f '(x*) = 0 , то x* – точка минимума f на Rn .

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

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

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

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

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

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

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

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

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

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

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

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

 


 

 

vikidalka.ru - 2015-2017 год. Все права принадлежат их авторам!