Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
численные методы оптимизации / Численные методы оптимизации_06.pptx
Скачиваний:
52
Добавлен:
15.04.2015
Размер:
830.64 Кб
Скачать

ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

Константин Ловецкий

Октябрь 2012

1

Кафедра систем

 

телекоммуникаций

Методы оптимизации

Говоря о задачах минимизации выделяют несколько общих моментов: f

Определяют некоторую «скалярную» меру качества –

целевую функцию

Определяют набор независимых переменных и формулируют условия,

которые характеризуют их приемлемые значения (размерность задачи и ее

ограничения).

Решение оптимизационной задачи – это приемлемый набор значений

переменных, которому отвечает оптимальное значение целевой функции.

2Под оптимальностью обычно понимают минимальность

целевой функции.

Методы спуска

Продолжим рассмотрение итерационных методов, являющиеся более

изощренными по сравнению с методами нулевого порядка. Формулируются они следующимx(0) Rn образом:(k 0)

Пусть дан вектор начального приближения

 

,

очередное

 

 

 

 

x

(k 1)

x

(k)

k d

(k)

,

 

 

 

 

k )

 

 

 

 

 

 

 

 

 

 

 

 

 

приближение(

рассчитывается по формуле

k

 

d

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

где

 

k )

 

 

 

 

 

 

 

образом выбранное направление

 

- подходящим(

 

 

 

 

 

 

 

 

 

 

и

d

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

- шаг –

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

d

(k)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

положительное число, определяющее величину

 

смещения вдоль

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

d

(k)T

f (x

(k)

) 0если

(f

(k)

0,

 

 

 

 

 

 

 

 

x )

 

 

направления

 

 

.

(k)

0если

(

)f

(k)

 

 

 

Направление

 

 

d

 

 

x0.

 

 

 

 

 

называется направлением спуска,

 

3если

Методы спуска

Методами спуска называются методы рассмотренного выше типа, вd (k )

которых векторы являются векторами спуска.

Поскольку

k 0

 

 

 

рассматриваются дифференцируемые функции, то для них

всегда

f (x(k) k d(k) ) f (x(k) ),

существует достаточно малое

, такое, что

f (x(k) d (k) ) f (x(k) ) f (x(k) )T d (k) ,

Используя возможностьk разложенияk целевой функции в ряд Тейлора,0при kи ее0.

непрерывность, можно записать:k 0

где

 

Как следствие, при достаточно малых

из

4

последнего равенства

 

Методы спуска

Различные способы выбора направлений спуска приводят к разным методам минимизации:

Метод Ньютона, в котором направление спуска определяется по

формуле

 

d(k) H 1(x(k) ) f (x(k) ),

 

 

 

H

 

 

 

с положительно определенной матрицей

, что обеспечивает

значительную область сходимости;

 

 

 

Приближенный метод Ньютона(k) 1, в(которомk) (k)

),

 

 

d

Bk (x

) f (x

 

B 1

 

 

H 1(x(k) )

;

где k

- подходящая аппроксимация матрицы

5

Методы спуска

Градиентный метод или метод скорейшего спуска,

 

соответствующий

d (k)

f (x(k) )

.

выбору направления спуска по формуле

 

Таким образом,

 

 

Bk I

этот метод является приближенным методом Ньютона, в котором

. d (k)T f (x(k) ) f (x(k) ) 2 .

Он может рассматриваться и как градиентный2 метод, поскольку

 

d(k) f (x(k) ) d(k 1) ,

Метод сопряженных градиентов, для которого

 

 

k

k

 

 

где

- скалярная величина, подбираемая таким образом,

чтобы

d (k)

 

обеспечить взаимную ортогональность направлений

6

Методы спуска

(k )

недостаточен для полного задания

Выбор направленияd

метода спуска. Ведь остается еще проблемаk

определения

 

 

 

так, чтобы шаг метода был не очень мал, что замедлит

скорость сходимости, но в то же время сохранял бы условие

сходимости:

f (x(k) k d(k) ) f (x(k) )

 

k

 

заключается в

Обычно метод выбора параметра

решении одномерной задачи минимизации:

 

 

 

,

(минимизирующееk)

 

Найти значение(k)

функцию

( ) f (x

 

d

).

 

 

 

 

 

 

 

 

Теорема. Если параметр

является решением задачи

 

(k

1) (k)

 

одномерной минимизацииf (наx

каждом)d 0шаге, то метод спуска

обеспечивает сохранение условия ортогональности

7каждом шаге метода.

Методы спуска

Ксожалению, за исключением редких случаев, точное решение задачи

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

нелинейна(

. Одна

f

 

x

k)

d

(k)

 

из возможных стратегий заключается в аппроксимации

функции

 

вдоль

прямой

 

 

 

 

полиномом и минимизации этого

полинома по

переменной .

Квадратичная интерполяция – метод Пауэлла. Кубическая интерполяция – метод Давидона.

8В общем случае процесс решения задачи одномерной

Линейный поиск

Методика линейного поиска

Рассмотрим итеративные методы, останавливающиеся при выполнении некоторого критерия останова итеративного процесса. При этом предполагается, что условия,

определяющие(kнаправление) (

спуска,

 

 

T

 

 

 

k)

 

 

 

(k)

 

d f (x

) 0если

 

0,

 

(f x )

 

d

(k)

0если

(

 

(k)

 

 

 

)f x0.

выполнены.

 

Практика показывает, что искать точное решение задачи о

минимуме функции

( ) f (x(k) d(k) )

 

не обязательно. Кажется, что(

достаточно добиться на каждой

 

f (x

k 1)

) f (x

(k)

)

итерации выполнения условия

 

 

 

d (k )

x(k )

 

 

.

 

 

при фиксированных

и

 

 

 

 

9

 

 

 

 

 

 

Линейный поиск

Однако простейшая процедура, заключающаяся в выборе

достаточно

k

, которое затем

 

 

 

большого начального значения

 

(k)

 

 

 

f (x

(k 1)

) f

(x

)

уменьшается (делением

 

 

 

 

 

 

 

 

пополам) до момента, пока не выполнится условие

,

может привести к совершенно неправильным результатам.

Необходимо использование более строгих правил выбора параметра шага

для обеспечения сходимости метода.

 

k

 

 

M

 

(k 1)

 

1

(k)

(k)

(k)

 

Отметим, что0 приv

выбореx шагаf (xхочется) f (xпреодолетьd )

две

основные проблемы:

 

k

 

 

 

 

 

медленная скорость сходимостиf (xи(k)малая)T d (k) , величина шага.

Первая может(0,1 / 2)быть решена требованием выполнения 10 условия: