реферат черномор


СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ЗАДАЧА БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

2. ГРАДИЕНТНЫЕ МЕТОДЫ

2.1. Общие соображения и определения

2.2. Эвристические соображения, приводящие к градиентным методам

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

2.4. Один пример исследования сходимости

2.5. Теорема об условной сходимости градиентного метода с постоянным шагом

2.6. Замечания о сходимости

2.7. Теорема о линейной сходимости градиентного метода с постоянным шагом

2.8. Об оптимальном выборе шага

2.9. Градиентный метод с дроблением шага

2.10. Метод наискорейшего спуска

3. МЕТОД НЬЮТОНА

3.1. Эвристические соображения, приводящие к методу Ньютона безусловной оптимизации

3.2. Теорема о локальной сверхлинейной сходимости метода Ньютона

3.3. Обсуждение метода Ньютона

3.4. Теорема о квадратичной сходимости метода Ньютона

3.5. Продолжение обсуждения метода Ньютона

3.6. Методы Ньютона с регулировкой шага

3.7. Метод Левенберга — Маркардта

3.8. Еще один недостаток метода Ньютона. Модифицированный метод Ньютона

3.9. Метод секущих

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ВВЕДЕНИЕ

Оптимизация как раздел математики существует достаточно давно. Оптимизация — это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином «оптимизация» в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или «оптимального» решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

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

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

1. ЗАДАЧА БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Итак, мы будем рассматривать задачу безусловной оптимизации

f(x)  min,

(1)

где fRm  R. Точка x*  Rm называется решением задачи (1) (или точкой глобального безусловного минимума функции f), если

f(x*)  f(x)

(2)

при всех x  Rm. Если неравенство (2) выполнено лишь для x, лежащих в некоторой окрестности Vx* точки x*, то точка x* называется локальным решением задачи (1), или точкой локального безусловного минимума функции f. Если неравенство (2) строгое при всех x  x*, то говорят о строгом глобальном и, соответственно, строгом локальном минимумах. Решение задачи (1) иногда обозначают argmin f(x) (или, более полно, argminxRm f(x); когда речь идет о задачах безусловной оптимизации в обозначениях argminxRm f(x) и minxRm f(x) мы будем всегда опускать индекс »x  Rm«). Обычно из контекста ясно о каком минимуме (локальном, глобальном и т. д.) идет речь.

Аналогичные понятия (максимумов) определяются для задачи

f(x)  max.

2. ГРАДИЕНТНЫЕ МЕТОДЫ

2.1. Общие соображения и определения.

Градиентные методы оптимизации относятся к численным методам поискового типа. Они универсальны, хорошо приспособлены для работы с современными цифровыми вычислительными машинами и в большинстве случаев весьма эффективны при поиске экстремального значения нелинейных функций с ограничениями и без них, а также тогда, когда аналитический вид функции вообще неизвестен. Вследствие этого градиентные, или поисковые, методы широко применяются на практике.Сущность указанных методов заключается в определении значений независимых переменных, дающих наибольшие изменения целевой функции. Обычно для этого двигаются вдоль градиента, ортогонального к контурной поверхности в данной точке. Различные поисковые методы в основном отличаются один от другого способом определения направления движения к оптимуму, размером шага и продолжительностью поиска вдоль найденного направления, критериями окончания поиска, простотой алгоритмизации и применимостью для различных ЭВМ. Техника поиска экстремума основана на расчетах, которые позволяют определить направление наиболее быстрого изменения оптимизируемого критерия.

Наиболее распространенные и эффективные методы приближенного решения задачи безусловной оптимизации

f(x)  min,

(1)

где fRm  R, укладываются в следующую грубую схему. Начиная с некоторого x0  Rm, строится последовательность {xn}  Rm такая, что

f(xn+1) < f(xn)

(2)

при всех n  N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей — итерационными методами или методами спуска. Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xn к xn+1) значение функции, мы приближаемся к минимуму (по крайней мере, локальному).

Мы будем говорить, что метод, начиная с данного x0  Rm,

а) условно сходится, если последовательность {xnрелаксационна и

f (xn)   при n  ;

б) сходится, если

xn  x* = argmin f(x) при n  ;

в) линейно сходится (или сходится со скоростью геометрической прогрессии, или имеет первый порядок сходимости), если при некоторых C > 0 и q  [0, 1)

||xn  x*||  Cqn;

(3)

г) сверхлинейно сходится, если для любого q  (0, 1) и некоторого (зависящего от qC выполнено неравенство (3);

д) квадратично сходится (или имеет второй порядок сходимости), если при некоторых C > 0 и q  [0, 1) и всех n  N

||xn  x*||  Cq2n.

Если эти свойства выполняются только для x0 достаточно близких к x*, то как всегда добавляется эпитет «локально».

2.2. Эвристические соображения, приводящие к градиентным методам.

Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции. Этот факт позволяет надеяться, что последовательность {xn}, рекуррентно определяемая формулой

xn+1 = xn  f (xn),

(4)

где  - некоторое положительное число, будет релаксационной.

К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xn. Заменим в шаре B(xn, ) с центром в точке xn функцию fее линейным (вернее, афинным) приближением:

f(x)  (x) def= f(xn) + (f (xn), x  xn)

(функция  аппроксимирует f в окрестности точки xn с точностью o(x - xn)). Разумеется, (линейная) безусловная задача (x)  min неразрешима, еслиf (xn)   (см. задачу 1.3). В окрестности же B(xn, ) функция  имеет точку минимума. Эту точку естественно взять за следующее приближение xn+1.

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

В общем случае число  в формуле (4) может на каждом шаге (т. е. для каждого n) выбираться заново:

xn+1 = xn  nf (xn).

(5)

Именно методы, задаваемые формулой (5), называются градентными. Если n =  при всех n, то получающийся метод называется градиентным методом с постоянным шагом (с шагом .)

Поясним геометрическую суть градиентного метода. Для этого мы выберем способ изображения функции с помощью линий уровня. Линией уровня функции f(изолинией) называется любое множество вида {x  Rmf(x) = c}. Каждому значению c отвечает своя линия уровня (см. рис. 5).

Рис. 5.

Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. 6. На каждом шаге мы сдвигаемся по вектору антиградиента, «уменьшенному в  раз».

Рис. 6.

2.4. Один пример исследования сходимости.

Изучим сходимость градиентного метода с постоянным шагом на примере функции

f(x) = |x|p,

где p > 1 (случай p  1 мы не рассматриваем, поскольку тогда функция f не будет гладкой, а мы такой случай не исследуем). Очевидно, задача (1) с такой функцией f имеет единственное решение x* = 0. Для этой функции приближения xn градиентного метода имеют вид:

xn+1 = xn  p|xn|p1sign xn.

(6)

Пределом этой последовательности может быть только 0. Действительно, если x** = limn xn  0, то, переходя к пределу в (6) при n  , получаем противоречащее предположению x**  0 равенство

x** = x**  p|x**|p1sign  x**,

откуда x** = 0. Очевидно также, что если x0 = 0, то и xn = 0 при всех n.

Покажем, что если p < 2, то при любом шаге  > 0 и любом начальном приближении x0 (за исключением не более чем счетного числа точек) приближения (6)не являются сходящимися. Для этого заметим, что если 0 < |xn| < (2/p)1/2(2p), то

|xn+1| > |xn|.

(7)

Поэтому, если xn не обращается в нуль, то она не может сходиться к нулю и, следовательно, не может сходиться вообще.

Таким образом, осталось доказать (7). В силу (6)

|xn+1| = |xn  p|xn|p1 ·sign xn| = |xn|·| 1 p|xn|p2·sign xn|.

Остается заметить, что если 0 < |xn| < (2/p)1/(2p), то, как нетрудно видеть, |1  p|xn|p2·sign  xn| > 1, что и требовалось.

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

2.5. Теорема об условной сходимости градиентного метода с постоянным шагом.

Пусть в задаче (1) функция f ограничена снизу, непрерывно дифференцируема и, более того, f  удовлетворяет условию Липшица:

||f (x)  f (y)||   ||x  y|| при всех x, y  Rm.

Тогда при   (0, 2/) градиентный метод с постоянным шагом условно сходится.

Д о к а з а т е л ь с т в о.  Положим zn = f (xn) и обозначим f(xn + tzn) через (t). Тогда, как легко видеть,

(t) = (f (xn + tzn), zn)

и поэтому по формуле Ньютона — Лейбница для функции 

f(xn+1)  f(xn) = f(xn + zn)  f(xn) = (1)  (0) =

10

(sds = 

10

(f (xnszn), znds. 

Добавив и отняв (f (xn), zn) = 01(f (xn), zndsи воспользовавшись неравенством (xy)  ||x|| · ||y||, получим

f(xn+1)  f(xn) = (f (xn), zn) + 

10

(f (xn + szn)  f (xn), znds  

 (f (xn), f (xn)) + 

10

||f (xn + szn)  f (xn)|| · ||zn|| ds. 

Учитывая условие Липшица для f , эту цепочку можно продолжить:

 f(xn+1)  f(xn)  ||f (xn)||2 +  ||zn||2

10

s ds =

=  ||f (xn)||2 + 

2

2

||f (xn)||2 = ||f (xn)||2



1  



2



.

(8)

Поскольку 1  /2 > 0, последовательность {f(xn)} не возрастает и, следовательно, релаксационность {xn} доказана. А так как в силу условий теоремы f еще и ограничена снизу, последовательность {f(xn)} сходится. Поэтому, в частности, f(xn+1)  f(xn)  0 при n  . Отсюда и из (8) получаем

 ||f (xn)||2  1



1 – 



2



–1

[f(xn)  f(xn+1)]  0 при n  . 

2.6. Замечания о сходимости.

Подчеркнем, что теорема 3.5 не гарантирует сходимости метода, но лишь его условную сходимость, причем, локальную. Например, для функции f(x) =(1 + x2)1 на R последовательность {xnградиентного метода с постоянным шагом, начинающаяся с произвольного x0 стремится к .

Поскольку в теореме 3.5 градиент непрерывен, любая предельная точка последовательности {xn} является стационарной. Однако эта точка вовсе не обязана быть точкой минимума, даже локального. Например, рассмотрим для функции f(x) = x2sign x градиентный метод с шагом   (0, 1/2). Тогда, как легко видеть, если x0 > 0, то xn  0 при n  . Точка же x = 0 не является локальным минимумом функции f.

Заметим также, что описанный метод не различает точек локального и глобального минимумов. Поэтому для того, чтобы сделать заключение о сходимости xnк точке x* = argmin f(x) приходится налагать дополнительные ограничения, гарантирующие, в частности, существование и единственность решения задачи (1). Один вариант таких ограничений описывается ниже.

2.7. Теорема о линейной сходимости градиентного метода с постоянным шагом.

Пусть выполнены условия теоремы 3.5 и, кроме того, f дважды непрерывно дифференцируема и сильно выпукла с константой . Тогда при   (0, 2/)градиентный метод с шагом  сходится со скоростью геометрической прогрессии со знаменателем q = max{|1  |, |1   |}:

||xn  x*||  qn||x0  x*||.

Д о к а з а т е л ь с т в о. Решение x* = argmin  f(x) существует и единственно в силу теорем 2.9 и 2.10. Для функции F(x) = f (x) воспользуемся аналогом формулы Ньютона — Лейбница

F(y) = F(x) + 

10

F [x + s(y  x)](y xds,

или, для x = x* и y = xn, учитывая, что f (x*) = Q,

f (xn) = 

10

f [x* + s(xn  x*)](xn  x*) ds 

(9)

(здесь мы, как и выше, воспользовались задачей 2.3). Далее, в силу утверждения (2.5) из п. 2.3 f (x)   при всех x  Rm. Кроме того по условию f (x)   при тех же x. Поэтому, так как

||h||2  (f [x* + s(xn x*)]hh)   ||h||2,

выполнено неравенство

||h||2  





10

f [x* + s(xn x*)] ds



hh



   ||h||2.

(10)

Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор на Rm, обозначим его Ln. Неравенство (10)означает, что   Ln  . В силу (9) градиентный метод (4) записывается в виде

xn+1 = xn  Ln(xn  x*).

Но тогда ||xn+1  xn|| = ||xn  x* Ln(xn  x*)|| == ||(I  Ln)(xn  x*)||  ||I  Ln|| · ||xn  x*||.

Спектр (I  Ln) оператора I  Ln состоит из чисел вида i = 1 i, где i  (Ln). В силу (10) и неравенства (2.3),

1    i  1  ,

и следовательно ||I  Ln||  max{|1 |, |1   |} = q.

Таким образом, ||xn+1  xn||  q||xn  x*||.

2.8. Об оптимальном выборе шага.

Константа q, фигурирующая в теореме 2.7 и характеризующая скорость сходимости метода, зависит от шага . Нетрудно видеть, что величина

q = q() = max{|1  |, |1   |}

минимальна, если шаг  выбирается из условия |1  | = |1   | (см. рис. 7), т. е. если  = * = 2/(+ ). При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной

q = q* = 

  

 + 



Страницы: Первая | 1 | 2 | 3 | Вперед → | Последняя | Весь текст


Предыдущий:

Следующий: