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

Страницы работы

Фрагмент текста работы

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

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

2.  f : XR1 - целевая функция.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть:

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

f(x)=0, где

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

df / d x1

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

                           

df / d xn

   

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

1)  xiX,i;

2)  f(x0)>f(x1)>...;

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

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

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

xR

xk+1 = xk+ tkSk , где Sk -вектор, определяющий направление изменения xk                                tk - скаляр, определяющий длину шага.

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

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

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

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

Пусть Sk = -f(xk), tk - длина шага.

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

Пусть tk = t (т.е. не зависит от к-пост.) xk+1 = xk -  tf(xk)

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

Пример: 

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

xk+1=xk - 2taxk = (1- 2at)xk

Отсюда

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

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

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

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

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

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

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

1

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

0

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

1

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

0

1

 f(xk)-t+Lt2||f(xk) ||2 TdT =f(xk)-t(1-Lt/2) ||f(xk) ||2

0

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

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

Выразим f(xk+1) через f(x0)

Пусть k=0: f(x1) f(x0)- a||f(x0) ||2

2                                                 2                                 2

k=1: f(x2) f(x1)- a||f(x1) ||  f(x0)- a||f(x0) || - a||f(x1) || .........

S


f(xk+1) f(x0)- a|| f(x )|| k 2 так как a>0, то 2 a-1(f(x0)-f(xs+1)) a-1(f(x0)-f*), для любого S

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

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

Замечание:

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

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

Похожие материалы

Информация о работе