5.2. Общие принципы многомерной минимизации

Для численного решения задач безусловной минимизации f (x) → min ,

x En

разработано много алгоритмов, использующих итерационные процедуры вида

xk +1 = Φ(xk , xk −1 , ..., x0 ) , x0 En .

(5.3)

lim f (xk ) = f = min

f (x), если U ≠ Ø

(5.4а)

k →∞

En

(5.4б)

lim f (xk ) = f = inf

f (x), если U = Ø

k →∞

En

где U − множество

точек

глобального

минимума

функции

f (x) .

Последовательность

{xk },

удовлетворяющая

требованию

(5.4), называется

минимизирующей для

функции f (x) . Если, кроме того, для случая

U ≠ Ø

дополнительно выполняется условие

lim ρ (xk , U ) = 0 ,

(5.5)

k

→∞

то говорят, что минимизирующая последовательность сходится к множеству U .

Если множество U состоит из единственной точки

x , то для сходящейся к U

минимизирующей последовательности lim xk = x .

k→∞

Необходимо отметить, что

1. ρ (x, U ) = inf ρ(x, y) есть расстояние от точки x до множества U .

y U

2. Минимизирующая последовательность может и не

сходиться к точке

минимума. Например, для функции

f (x) =

x2

,

x E ,

последовательность

1 + x4

1

xk

= k является минимизирующей, но не сходится к единственной точке минимума

x

= 0 . Напротив, минимизирующая последовательность xk =1/ k

сходится к точке

минимума x = 0 .

Вопрос о существовании точки минимума обычно решается с помощью

теоремы Вейерштрасса: если функция

f (x)

непрерывна

в

En и множество

q (0, 1) ,

что

выполняется

неравенство

ρ (xk , x ) ≤ q ρ (xk −1 , x ) ,

т.е.

ρ (xk , x ) ≤ qk ρ (x0 , x ) .

Сходимость

называется сверхлинейной, если

ρ (xk , x ) ≤ qk ρ (xk −1 , x ) , и

qk → +0 при k → ∞.

Наконец,

термин

квадратичная

сходимость

используется,

если

f (xk +1 ) − f (xk )

< ε2

(5.6)

f (xk )

< ε3

xk +1 = xk +αk

pk , k = 0, 1, ... ,

(5.7)

где вектор

pk − направление поиска из точки

xk в точку xk +1 ,

а число αk −

величина

шага,

которая

выбирается

так,

чтобы

выполнялось

Φ

α

→

min ,

Φ

α

=

f (x

k +α

p

k

) .

(5.8)

k ( )

k ( )

α

реализуется возможность уменьшить значение целевой функции

f (x) при

перемещении из точки

xk в направлении, коллинеарном вектору pk .

Величина

шага αk может быть

найдена с помощью рассмотренных ранее

методов

Теорема. Если функция

f (x)

дифференцируема

в En , то в

итерационном

процессе (5.7) с выбором шага с исчерпывающим

спуском для

любого k ≥1

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

f (x

k +1

), p

k

)

=

0 .

(5.9)

(

d Φk (α)

n

∂ f (xk +1 ) d xkj +1

= ∑

= 0 .

d α

∂ x j

d α

j=1

d xk +1

Учитывая, что xkj +1 = xkj +α pkj

, поэтому

j

= pkj

. Отсюда получаем условие

dα

(5.9). ■

Геометрическая иллюстрация

соотношения

(5.9)

в E2 выглядит так. При

убывания функции,

происходит пересечение линий уровня функции f (x) . Это

происходит до тех

пор, пока

либо не

будет достигнута стационарная

точка

( f (xk +1 ) = 0 ), либо

прямая не

коснется

в точке xk +1 некоторой линии

уровня