Множество вариантов или допустимое множество. Соответствие методов и множеств. Безусловная оптимизация (многомерные функции)

Основные понятия.

1.  X- множество вариантов или допустимое множество.

2.  f : XR₁ - целевая функция.

3.  Точка x*X - оптимальная, если выполняется f(x*)=min f(x), xX  (*).

Если верно (*) для любого xX, то точка x- точка глобального минимума.

Если нет, но существует R₁,  >0 такое что:

f(x)  f(x*),для любого x из - окрестности, то есть ||x-x*||< , то        x* - точка локального минимума.

Надо найти экстремумы функции f на множестве X.

Содержание курса состоит в поисках экстремумов.

Будем искать min f(x), xX , так как max f(x)= - min(-f(x)), xX.

Множество X бывает:

1.  Конечным (конечное множество элементов, например графы).

2.  Конечномерным (когда совпадает или является подмножеством множества евклидова пространства).

3.  Бесконечномерным (не вкладывается в евклидово пространство ,например множество непрерывных функций на отрезке).

Соответствие методов и множеств.

1.  Методы решения переборных задач (метод ветвей и границ, динамическое        программирование и др.)

2.  Методы решения задач математического программирования 

(условная/безусловная минимизация, нелинейное, выпуклое и линейное      программирование).

3.  Методы вариационного исчисления и методы оптимального управления (уравнение Эйлера-Лагранжа, принцип максимума).

I.  Безусловная оптимизация (многомерные функции). min f(x), x = Rⁿ, то есть минимизация на всем пространстве.

Определение:

Минимизация заданная неравенствами, равенствами и другими             ограничениями называется условной.

Пусть:

1.  x = Rⁿ  (евклидово n-мерное пространство); 2.  Функция f дифференцируема хотя бы один раз,тогда в точке минимума выполняется равенство:

f(x)=0, где

(вектор частных производных по каждому аргументу)

df / d x1

f(x)= ............

                           

df / d xn

   

В большинстве случаев это приводит к решению системы нелинейных уравнений, что само по себе проблема. Существуют релаксационные методы, в основе которых лежит построение релаксационной последовательности со следующими свойствами:

1)  x_iX,i;

2)  f(x₀)>f(x₁)>...;

3)  x_ix* = argmin f(x), i, xX.

Это методы нахождения локального минимума (т.е. корня уравнения f(x) =0). Все рассматриваемые методы делятся на несколько групп в зависимости от того, какой максимальный порядок производной функции f используется для вычисления последовательности. Если производные не используются, то методы нулевого порядка, затем -первого и так далее. Мы будем рассматривать порядок не выше второго.

Общая схема безусловной оптимизации  

xR_n 

x_k+1 = x_k+ t_kS_k , где S_k -вектор, определяющий направление изменения x_k                                t_k - скаляр, определяющий длину шага.

S_k может зависеть от xk: Sk = (x_k), а может от x_k-1. В зависимости от этого критические методы делятся на: n одношаговые ((x_k)); n двухшаговые ((x_k,x_k+1)).

Эти методы имеют основное распространение.

1.1 Методы первого порядка (градиентные методы)

Для вычисления t и S используются значение функции и первая производная. Известно, что градиент функции в точке дает направление наибольшего возрастания функции в точке. Направление наибольшего убывания - это направление антиградиента.

Пусть S_k = -f(x_k), t_k - длина шага.

1.  Градиентный метод с постоянным шагом

Пусть t_k = t (т.е. не зависит от к-пост.) x_k+1 = x_k -  tf(x_k)

Видно, что останавливаемся в любой точке, где f(x_k)=0.

Пример: 

f(x) = ax², a>0, x-скаляр

x_k+1=x_k - 2tax_k = (1- 2at)x_k

Отсюда

1-2at<1 at<1- необходимое и достаточное условие существования предела Если 0<t_k<1/a - сходится,          t_k>1/a -  расходится,

t_k=1/a - зацикливается.( t_k=1/a x₁=x₀-2x₀= -x₀  x₂=x₁-2x₁= -x₁=x₀ и т.д.) Выбор постоянного шага приводит к осложнениям. Оценим сходимость этого метода в общем случае.

Теорема (о сходимости метода градиентов)

Пусть f(x)- дифференцируема на R_n, f(x) удовлетворяет условию Лифшица:

|| f(x)-f(y) || L ||x-y || (*)  (||x²|| = x_i² ), f(x)- ограничена снизу f(x) f* >- (**) и 0< t< 2/L(***), L -const.

Тогда в методе x_k+1= x_k-tf(x_k), градиент стремится к нулю,  т.е. limf(x_k) =0, при k, а функция f(x)  монотонно убывает f(x_k+1)f(x_k). Точнее f(x_k+1)  f(x_k)-t(1-tL/2)||f(x_k) ||²(градиент характеризует скорость убывания и множитель)

Доказательство Известно из мат.анализа:

1

f(x + y) = f(x) + ( f(x),y) +  (f(x + y) -T f(x),y)dT   (1)

0

Пусть x=x_k, y= -tf(x_k)  (2) Подставим (2) в(1):

1

f(x_k+1)=f(x_k)-t||f(x_k) ||²-t (f(x - t f(xk T  k)) -f(x_k),f(x_k))dT 

0

1

 f(x_k)-t+Lt²||f(x_k) ||²  TdT =f(x_k)-t(1-Lt/2) ||f(x_k) ||²

0

Обозначим a = t(1-Lt/2); a>0, так как (***)

Отсюда  f(x_k+1) f(x_k)-a||f(x_k) ||²

Выразим f(x_k+1) через f(x₀)

Пусть k=0: f(x₁) f(x₀)- a||f(x₀) ||²

2                                                 2                                 2

k=1: f(x₂) f(x₁)- a||f(x₁) ||  f(x₀)- a||f(x₀) || - a||f(x₁) || .........

S

f(x_k+1) f(x₀)- a|| f(x )|| k ² так как a>0, то ² a^-1(f(x₀)-f(x_s+1)) a^-1(f(x₀)-f*), для любого S

 то есть || f(x )||          k < ( сумма ограничена) ||f(x_k) ||0, то есть теорема

k0 доказана.

Замечание:

Сходимость градиента к нулю не гарантирует сходимости к минимуму. Пример:

f(x) =  , градиент сходится к нулю, но функция не имеет минимума