учебники / osnovy-informacionnyh-tehnologiy

многогранник, с которым повторяется описанная процедура. В про-

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

меры, что и обусловило название метода.

У

Т

А

Г

Рис. 7.4. Прямой поиск: невозможность продвижения к минимуму:

Б

а – С1 > C2 > C3; б – С1 > C2

Рис. 7.5. Геометрическая интерпретация метода деформируемого многогранника

Напомним,

что поверхностью

уровня

(на плоскости –

линией

й

уровня) является поверхность, получаемая приравниванием выра-

и

Введем следующие обозначения:

жения функции f(х) некоторой постоянной величине С, т. е. f(х) =

x[i, k] =(x1[i, k], …, xj[i, k], …, xn[i, k])

T

С . Во всех

точках этой

поверхности

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

и то же значение С. Давая величине С различные значения С1, ...,

р

где i = 1, ..., п + 1; k = 0, 1, ..., – i-я вершина многогранника на k-м

Сn, получают ряд поверхностей, геометрически иллюстрирующих

этапе поиска; х[h, k] — вершина, в которой значение целевой

характер функции.

функции максимально, т. е. f(х[h, k] = max{f(x[1, k]), …, f(x[n + 1,

одно

k])}; х[l, k] – вершина, в которой значение целевой функции ми-

7.1.1.5. Метод деформируемого многогранн ка

нимально, т. е. f(х[l, k]) =min {f(x[1, k]), …, f(x [n + 1, k])};

х [п + 2, k]- центр тяжести всех вершин, за исключением х[h, k].

(метод Нелдера – Мида)

т

Координаты центра тяжести вычисляются по формуле:

Данный метод

состоит в

том,

что для

мин м ац функц и

xj [n

+ 2,k]=

1

n+1

[i,k]− xj

п переменных f(х)

в n-мерном пространстве стро тся многогранн к,

n

∑xj

[h,k] , j =1,…,n

содержащий (п + 1) вершину. Очевидно, что каждая вершинасоответ-

i=1

ствует некоторому вектору х. Вычисляются

начения целевой функ-

ции f(х) в каждой из вершин мног гранника,зпределяются макси-

Алгоритм

метода деформируемого

многогранника состоит

мальное из этих значений и соответствующая ему вершина х[h]. Через

в следующем:

эту вершину и центр тяжести остальных вершин проводится проеци-

1. Осуществляют проецирование точки х[h, k] через центр тяжести:

рующая прямая, на которой находится точках[q] с меньшим значени-

x[n + 3, k] =x[n + 2, k] + a(x[n + 2, k] – x[h, k]) ,

ем целевой функции, чем в в

х[h] (рис. 7.5). Затем исключается

где а > 0 – некоторая константа. Обычно а = 1.

вершина х[h]. Из оставшихся в ршин и точки x[q] строится новый

п

341

342

ршине

Р

2. Выполняют операцию растяжения вектора х[n+3, k] – х[n+2, k]:

7.1.1.6. Метод вращающихся координат (метод Розенброка)

x[n + 4, k] =x[n + 2, k] + γ(x[n + 3, k] – x[n + 2, k]),

Суть метода состоит во вращении системы координат в соответ-

ствии с изменением скорости убывания целевой функции. Новые

где γ > 1 – коэффициент растяжения. Наиболее удовлетворительные

У

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

результаты получают при 2,8 <= γ <= 3.

бы одна из них соответствовала направлению наиболее быстрого

Если f(x[n + 4, k]) < f(х[l, k]), то х[h , k] заменяют на x[n + 4, k]

Т

убывания целевой функции, а остальные находятся из условия ор-

и продолжают вычисления с п. 1 при k = k + 1. В противном случае

тогональности. Идея метода состоит в следующем (рис. 7.6).

х[h, k] заменяют на х[n + 3, k] и переходят к п. 1 при k = k + 1.

А

3. Если f(x[n + 3, k]) > f(х[i, k]) для всех i, не равных

h, то сжи-

мают вектор x[h, k] – x[n+2, k]:

Г

x[n+ 5, k] =x[n + 2, k] + β (х[h, k] – x[n + 2, k] ),

Б

где β > 0 – коэффициент сжатия. Наиболее хорошие результаты по-

лучают при 0,4 <= β <= 0,6.

й

Затем точку х[h, k] заменяют на х[n + 5, k] и переходят к п. 1 при k =

= k + 1.

4. Если f(x[n + 3, k])> f(x[h, k]),

то все векторы х[i,

k] –

х[l, k].

и

i= 1,..., п + 1, уменьшают в два раза:

x[i, k] = x[l, k] + 0,5(x[i, k] – x[l, k]) .

р

Затем переходят к п. 1 при k = k + 1.

Рис. 7.6. Геометрическая интерпретация метода Розенброка

В диалоговой системе оптимизации выход из подпрограммы,

Из начальной точки х[0] осуществляют спуск в точку х[1] по на-

реализующей метод деформируемого многогранника,

-

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

вляется при предельном сжатии

многогранн ка, т. е.

вы-

итерации одна из осей должна проходить в направлении y1 = х[1] ––

полнении условия:

о

осущест

х[0], а другая – в направлении, перпендикулярном к у1 . Спуск

n

2,k])

2

n

вдоль этих осей приводит в точку х[2] , что дает возможность по-

max∑(xj [i,k]− xj [n +

< ∑e2j ,

(7.10)

строить новый вектор х[2] – х[1] и на его базе новую систему на-

j=1

j=1

при

правлений поиска. В общем случае данный метод эффективен при

где e = (е1 ,..., еn) – заданный вектор.

минимизации овражных функций, так как результирующее направ-

С помощью операции растяжения и сжатияразмеры и форма

ление поиска стремится расположиться вдоль оси оврага.

Алгоритм метода вращающихся координат состоит в следующем.

деформируемого многогранника ада тируются к т пографии целе-

1. Обозначают через р1[k], ..., рn[k] направления координатных

вой функции. В результате многогранник

вытягивается

вдоль

осей в некоторой точке х[k] (на к-й итерации). Выполняют пробный

о

длинных наклонных пов рхност й, изм няет направление в изогну-

шаг h1 вдоль оси р1[k], т. е.

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

x[kl] = x[k] + h1p1[k].

эффективность рассмотр нного мптода.

343

344

е

Р

Если при этом f(x[kl]) < f(x[k]), то шаг h умножают на величину										У
							функции х*, пересекает под равными углами касательные к поверхно-
β > 1;							стямравногоуровняфункциивточкахпересечения(рис. 7.7):
Если f(x[kl]) > f(x[k]), то на величину (–β), 0 < |β| < 1;								А
x[kl] = x[k] + β h1p1[k].									Т
Полагая β h1 = а1, получают							Г
x[kl] = x[k] + a1p1[k].
2. Из точки х[k1] выполняют шаг h2 вдоль оси р2[k]:
x[k2] = x[k] + a1p1[k] + h2p2[k].							Б
Повторяют операцию п. 1, т. е.
x[k2] =x[k] + а1р1[k] +а2p2[k].
Эту процедуру выполняют для всех остальных координатных
осей. На последнем шаге получают точку
		n
x[kn]= x[k +1]= x[k]+ ∑ai pi [k].
		i=1					й
3. Выбирают новые оси координат p1[k+1], …, рn[k+1]. В каче-					р
стве первой оси принимается вектор							Рис. 7.7. Геометрическая интерпретация метода Пауэлла
р1[k+1] = x[k+l] – x[k].							Суть метода такова. Выбирается некоторая начальная точка х[0]
Остальные оси строят ортагональными к первой оси с помощью							выполняется одномерный поиск вдоль произвольного направле-
процедуры ортогонализации Грама – Шмидта. Повторяют вычис-						иния, приводящий в точку х[1] . Затем выбирается точка х[2], не ле-
ления с п. 1 до удовлетворения условий сходимости.				результа			жащая на прямой х[0] – х[1], и осуществляется одномерный поиск
Коэффициенты β подбираются эмпирически. Хорошие							ствляется во взаимно сопряженных направлениях. В случае неквад-
				-			вдоль прямой, параллельной х[0] – х[1]. Полученная в результате
ты дают значения β = – 0,5 при неудачных пробах (f(x[ki]) > f(x[k]))							точка х[3] вместе с точкой х[1] определяет направление x[1] – х[3]
и β = 3 при удачных пробах (f(x[ki]) < f(x[k])).							одномерного поиска, дающее точку минимума х*. В случае квадра-
В отличие от других методов нулевого порядка алгор				м Розен-			тичной функции n переменных оптимальное значение находится
брока ориентирован на нахождение оптимальной				о
				в каждом			за п итераций. Поиск минимума при этом в конечном счете осуще-
			з
направлении, а не просто на фиксированный сдв г по всем направ-
лениям. Величина шага в процессе поиска непрерывно				меняется			ратичной целевой функции направления поиска оказываются со-
в зависимости от рельефа поверхности			. Сочетание враще-				пряженными относительно матрицы Гессе. Алгоритм метода
ния координат с регулированием шага делает метточкид Ро енброка							параллельных касательных состоит в следующем.
эффективным при решении сложных задач			птими ации.				1. Задаются начальной точкой x[0]. За начальные направления
							поиска р[1], ... , р[0] принимают направления осей координат, т. е.
7.1.1.7. Метод параллельных касательных (мет д Пауэлла)							р [i] = е[i], i = 1, ..., n (здесь e[i]= (0, ..., 0, 1, 0, … 0)T).
е		уровня					2. Выполняют n одномерных поисков вдоль ортогональных на-
Этот метод использу т свойство квадратичной функции, заключаю-							правлений р[i] , i = 1, ..., п. При этом каждый следующий поиск
щееся в том, что любая прямая, которая роходит через точку минимума							производится из точки минимума, полученной на предыдущем ша-
Р	п						ге. Величина шага аk находится из условия:
	345									346

f (x[k]+ ak p[k]) = min f (x[k]+ ap[k

]).

Т

a

А

У

Полученный шаг определяет точку:

х[k+1] = х[k] + аkр[k] .

3. Выбирают новое направление p =–x[n] – х[0] и заменяют на-

Г

правления р[1], ..., р[n] на р[2], ..., р [n], р. Последним присваивают

обозначения р[1], ..., р[n].

вдоль направления р =

4. Осуществляют одномерный

поиск

р[n] = х[n] – х[0]. Заменяют х[0] на х[n+1] = х[n] + аnр[п] и прини-

Б

Рис. 7.8. Градиент

мают эту точку за начальную точку х[0] для следующей итерации.

Вектор-градиент направлен в сторону наискорейшего возраста-

Переходят к п. 1.

Таким образом в результате выполнения рассмотренной проце-

ния функции в данной точке. Вектор, противоположный градиенту

дуры осуществляется поочередная замена принятых вначале на-

( − f ′(х[0])), называется антиградиентом и направлен в сторону

правлений поиска. В итоге после n шагов они окажутся взаимно со-

наискорейшего убывания функции. В точке минимума градиент

пряженными.

р

функции равен нулю. На свойствах градиента основаны методы

йпервого порядка, называемые также градиентными и методами ми-

7.1.2. Численные методы

о

и

н мизации. Использование этих методов в общем случае позволяет

определить точку локального минимума функции.

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

Очевидно, что если нет дополнительной информации, то из на-

точке

чальной точки х[0] разумно перейти в точку х[1],

лежащую в на-

правлении

антиградиента –

наискорейшего

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

7.1.2.1. Минимизация функций многих переменных.

Основные положения

и

Выбирая

в качестве

направления

спуска

р[k]

антиградиент

Градиентом дифференцируемой функции f(x) в точке х[0] назы-

− f ′(х[k]) в точке х[k], получаем итерационный процесс вида

вается n-мерный вектор f(x[0]), компоненты которого являю ся ча-

х[k + 1] = x[k] – akf'(x[k]), аk > 0; k = 0, 1, 2, ...

стными

производными функции

f(х),

вычисленными

в

х[0], т. е.

В координатной форме этот процесс записывается следующим

f'(x[0]) = (дf(х[0])/дх1, …, дf(х[0])/дхn)T.

(7.11)

образом:

о

x

k +1

= x

k

]

− a

df (x[k])

,

k

Этот вектор перпендикулярен к

ск сти, пр веденной через

i [

]

i [

dxi

з

точку х[0] и касательной к оверхн сти ур вня функции f(x),

проходящей через точку х[0]. В кажд й т чке так й поверхности

где i = 1, ..., n; k= 0, 1, 2, ... .

функция

одинаковое

значение.

Приравнивая

f(x) принимает

В качестве критерия останова итерационного процесса исполь-

функцию различным постоянным

личинам С0, С1, ... , получим

зуют либо

выполнение

условия

малости приращения аргумента

Р

серию поверхностей, характ ризующих ее топологию (рис. 7.8).

|| x[k+l] – x[k] || <= ε, либо выполнение условия малости градиента

пл

347

348

f

′

(

x

[

k +1

≤γ,

ϕ(a) = f

(

x[k]− a

k

f ′

(

x

[k]

))

.

])

Алгоритм метода наискорейшегоУспуска состоит в следующем.

где ε и γ – заданные малые величины.

Возможен и комбинированный критерий, состоящий в одновре-

1.

Задаются координаты начальной точки х[0].

2.

В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента

менном выполнении указанных условий. Градиентные методы от-

f'(x[k]).

Т

личаются друг от друга способами выбора величины шага аk.

3.

Определяется величина шага ak, путем одномерной миними-

При методе с постоянным шагом для всех итераций выбирается

зации по а функции ϕ(a) = f(x[k] – af'(x[k])).

некоторая постоянная величина шага. Достаточно малый шаг аk

обеспечит убывание функции, т. е. выполнение неравенства

4.

ОпределяютсяАкоординаты точки х[k + 1]:

5. хi[k+1] = xi[k] – аkf'i(х[k]), i = 1 ,..., п.

f(х[k+1]) = f(x[k] – akf'(x[k])) < f(x[k]).

6.

ПроверяютсяГусловия останова процесса. Если они выполня-

ются, то вычисления прекращаются. В противном случае осущест-

Однако это может привести к необходимости проводить непри-

вляется переход к п. 1.

емлемо большое количество итераций для достижения точки ми-

В рассматриваемом методе направление движения из точки х[k]

нимума. С другой стороны, слишком большой шаг может вызвать

Б

касается линии уровня в точке x[k+1] (рис. 7.9). Траектория спуска

неожиданный рост функции либо привести к колебаниям около

з гзагообразная, причем соседние звенья зигзага ортогональны

точки минимума (зацикливанию). Из-за сложности получения не-

друг другу. Действительно, шаг ak выбирается путем минимизации

обходимой информации для выбора величины шага методы с по-

йпо а функции f(a) = ϕ(x[k] – af'(x[k])). Необходимое условие мини-

стоянным шагом применяются на практике редко.

и

мума функции dϕ(a)/da = 0. Вычислив производную сложной

Более экономичны в смысле количества итераций и надежности

функции, получим условие ортогональности векторов направлений

градиентные методы с переменным шагом, когда в зависим сти

спуска в соседних точках:

р

от результатов вычислений величина шага некоторым образом меня-

dϕ(a)/da = –f' (x[k+1] f

′

(x[k]) = 0.

ется. Рассмотрим применяемые на практике варианты таких ме д в.

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

о

При использовании

метода наискорейшего

спуска на каждой

т

итерации величина шага аk выбирается из услов я м н мума

функции f(x) в направлении спуска, т.е.:

и

f

(

x[k]− a

f ′

x[k]

= min f

(

x

[k]

− a

f ′

(

))

(

x[k]

)).

k

a

>0

k

з

Это условие означает, что движение вд ль антиградиента про-

исходит до тех пор, пока

функции f(x) убывает. С матема-

о

тической точки зрения на каждой ит рации необходимо решать за-

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

о а функции:

Рис. 7.9. Геометрическая интерпретация метода наискорейшего спуска

п

350

349

значение

Р

У

Градиентные методы сходятся к минимуму с высокой скоростью

Т

(со скоростью геометрической прогрессии) для гладких выпуклых

функций. У таких функций наибольшее М и наименьшее m собст-

А

венные значения матрицы вторых производных (матрицы Гессе)

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обуслов-

лена. Напомним, что собственными значениями λi, i = 1, …, n, мат-

рицы являются корни характеристического уравнения

∂2 f (x)

∂2 f (x)

…

∂2 f (x)

Б

∂x ∂x

∂x ∂x

∂x ∂x

…

1

1

1

2

1

n

Г

H (x) =

∂2 f (x)

∂2 f (x)

…

∂2 f (x)

(7.12)

ражной

∂x ∂x

∂x ∂x

∂x ∂x

Рис. 7.10. Овражная функция

2

1

2

…

2

n

2

∂2 f (x)

∂2 f (x)

∂2 f (x)

и

Скорость сходимости градиентных методов существенно зави-

∂xn∂x1

∂xn∂x2

∂xn∂xn

сит также от точности вычислений градиента. Потеря точности,

а это обычно происходит в окрестности точек минимума или в ов-

∂2 f (x)

∂2 f (x)

∂2 f (x)

ситуации, может вообще нарушить сходимость процесса

градиентного спуска. Вследствие перечисленных причин градиент-

∂x1∂x1

∂x1∂x2

∂x1∂xn

о

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

∂2 f (x)

∂2 f (x)

∂2 f (x)

эффективными методами на начальной стадии решения задачи.

…

=

0.

(7.13)

р

В этом случае точка х[0] находится далеко от точки минимума,

∂x ∂x

∂x ∂x

∂x ∂x

т

и шаги в направлении антиградиента позволяют достичь сущест-

2

1

2

2

2

n

венного убывания функции.

∂2 f (x)

∂2 f (x)

…

∂2 f (x)

∂x

∂x

∂x

∂x

∂x

∂x

7.1.2.3. Метод сопряженных градиентов

n

1

n

2

n

n

Однако на практике,

как правило, минимиз руемые функц и

Рассмотренные выше градиентные методы отыскивают точку

минимума функции в общем случае лишь за бесконечное число

имеют плохо обусловленные матрицы вторых про

водных (т/М

итераций. Метод сопряженных градиентов формирует направления

градиента этих функций (см. рис. 7.10)существенно отклоняется от

<< 1). Значения таких функций вдоль некоторых направлен й

з-

меняются гораздо быстрее (иногда на неск лькоипорядков),

чем

поиска, в большей мере соответствующие геометрии минимизи-

в других направлениях. Их поверхн сти ур вня в пр стейшем слу-

руемой функции. Это существенно увеличивает скорость их сходи-

п

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

чае сильно вытягиваются (рис. 7.10), а в б леезсл жных случаях из-

гибаются и представляют собой овраги. Функции,

бладающие та-

функцию

кими свойствами,

е

Направление анти-

f(x) = (х, Нх) + (b, х) + а,

называют

овражными.

направления в точку минимума, что

риводит к замедлению скоро-

с симметрической положительно определенной матрицей Н за ко-

сти сходимости.

Р

нечное число шагов п, равное числу переменных функции. Любая

351

352

f (x[k]+ ak p[k])

У

гладкая функция в окрестности точки минимума хорошо аппрок-

= min f

(x[k]+ ap[k]).

симируется квадратичной, поэтому методы сопряженных гради-

a≥0

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

Для квадратичной функции:

функций. В таком случае они перестают быть конечными и ста-

А

′(x[k], p[k])

новятся итеративными.

ak

= −

f

.

(7.14)

По определению, два n-мерных вектора х и у называют сопря-

Г

Т( [ ]

[ ] )

женными по отношению к матрице H (или H-сопряженными), если

p k , Hp k ,

Алгоритм метода сопряженных градиентов Флетчера – Ривса

скалярное произведение (x, Ну) = 0. Здесь Н – симметрическая по-

ложительно определенная матрица размером п на п.

состоит в следующем:

Одной из наиболее существенных проблем в методах сопряжен-

1.

В точке х[0] вычисляется p[0] = –f’(x[0]).

ных градиентов является проблема эффективного построения на-

2.

На k-м шаге по приведенным выше формулам определяют-

правлений. Метод Флетчера – Ривса решает эту проблему путем

ся шаг аk и точка х[k +1].

преобразования на каждом шаге антиградиента – f(x[k]) в направле-

3.

Вычисляются величины f(x[k + 1]) и f'(x[k + 1]).

ние p[k], H-сопряженное с ранее найденными направлениями р[0],

4.

Если

f

′

(x[k + 1]) = 0,

то точка х[k +

1] является точкой

р[1], ..., р[k – 1]. Рассмотрим сначала этот метод применительно

Б

к задаче минимизации квадратичной функции.

и

минимума функции f(х). В противном случае определяется новое

направление p[k+l] из соотношения:

Направления р[k] вычисляют по формулам:

р

й

(

f ′(x[k +1]), f ′(x[k +1]))

p[k] = –f (x[k]) +`βk–1p[k – l], k > = 1;

p[k +

1]= − f ′(x[k +1])

p[k],

(7.15)

p[0] =

− f ′(x[0]).

( f ′(x[k]), f ′(x[k]))

о

Величины βk–1 выбираются так, чтобы направления p[k], р[k–1]

и осуществляется переход к следующей итерации. Эта процедура

были H-сопряженными:

найдет минимум квадратичной функции не более чем за п шагов.

(p[k], Hp[k – 1]) = 0.

При минимизации неквадратичных функций метод Флетчера –

и

Ривса из конечного становится итеративным. В таком случае по-

т

В результате для квадратичной функции:

сле (п + 1)-й итерации процедуры 1-4 циклически повторяются

з

с заменой

х[0] на х[п + 1], а вычисления

заканчиваются при

f ′(x[k])

< ε, где ε– заданное число. При этом применяют сле-

βk −1 =

( f ′(x[k], f ′(x[k])))

,

(

′

(

[

]

′

(

[

])))

f

x

k

−1 , f

x

k

−1

дующую модификацию метода:

итерационный процесс минимизации имеет вид:

x[k + l] = x[k] +akp[k],

п

x[k + l] =x[k] +akp[k],

p[k] = –f’(x[k])+βk–1p[k – l], k >= 1;

е

p[0] = – f ′(x[0]);

гдер[k] – направлениеспусканаk-мшаге;

аk – величина шага, которая выбираетсяоиз условия минимума

f(х[k] + akp[k]) = min f(x[k] + ap[k]);

функции f(х) по а внаправл нии движения, т. е. в результате реше-

Р

a≥0

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

353

354

( f ′(x[k]), f ′(x[k])− f ′(x[k −1]))

,k I .

7.1.3. Численные методы

f ′(x[k]), f ′

(x[k])

(7.16)

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

βk −1 =

У

0,k I.

7.1.3.1. Особенности методов второго порядка

Здесь I – множество индексов: I

=

{0, n,

2п,

Зп, ...},

т. е. об-

Методы безусловной оптимизации второго порядка используют

Т

новление метода происходит через каждые п шагов.

вторые частные производные минимизируемой функции f(х). Суть

этих методов состоит в следующем.

Геометрический смысл метода сопряженных градиентов со-

Необходимым условием экстремума функции многих перемен-

стоит в следующем (рис. 7.11). Из заданной начальной точки х[0]

ных f(x) в точкеАх* является равенство нулю ее градиента

осуществляется спуск в направлении р[0] = –f'(x[0]). В точке х[1]

в этой точке:

определяется вектор-градиент f'(x [1]). Поскольку х[1]

является

Г

точкой минимума функции в направлении р[0], то f’(х[1]) орто-

f’(х*) 0.

гонален вектору

р[0]. Затем

отыскивается вектор р[1],

H-сопряженный к р [0]. Далее отыскивается минимум функции

Разложение f'(х) в окрестности точки х[k] в ряд Тейлора с точно-

вдоль направления р[1] и т. д.

Б

стью до членов первого порядка позволяет переписать предыдущее

уравнение в виде

й

f'(x) f'(x[k]) + f"(x[k]) (х – х[k]) 0.

и

Здесь f"(x[k]) Н(х[k]) – матрица вторых производных (матрица

Гессе) минимизируемой функции. Следовательно, итерационный

р

процесс для построения последовательных приближений к реше-

нию задачи минимизации функции f(x) описывается выражением:

x[k + l] x[k] – H–1(x[k]) f'(x[k]) ,

о

где H–1(x[k]) – обратная матрица для матрицы Гессе;

H–1(x[k])f'(x[k]) р[k] – направление спуска.

т

Полученный метод минимизации называют методом Ньютона.

Рис. 7.11. Траектория спуска в методе сопряженных град ентов

Очевидно, что в данном методе величина шага вдоль направления

Методы сопряженных направлений являются

и

р[k] полагается равной единице. Последовательность точек {х[k]},

дними из наи-

получаемая в результате применения итерационного процесса, при

более эффективных для решения задач минимизации. Однако

определенных предположениях сходится к некоторой стационар-

следует отметить, что они чувствительны к

шибкам, возникаю-

ной точке х* функции f(x). Если матрица Гессе Н(х*) положительно

щим в процессе счета. При большом числе

еременных погреш-

определена, точка х* будет точкой строгого локального минимума

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

функции f(x). Последовательность x[k] сходится к точке х* только

даже для квадратичной функции, т. .

роцесс для нее не всегда

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

укладывается в п шагов.

п

определена на каждой итерации.

355

356

е

Р

У

Если функция f(x) является квадратичной, то, независимо от на-

Т

7.1.3.2. Метод Ньютона

чального приближения х[0] и степени овражности, с помощью ме-

Алгоритм метода Ньютона состоит в следующем.

тода Ньютона ее минимум находится за один шаг. Это объясняется

1.

А

тем, что направление спуска р[k] H

–1

В начальной точке х [0] вычисляется вектор:

(x[k])f’(x[k]) в любых точках

х[0]

всегда совпадает с направлением в точку минимума х*. Ес-

p[0] – H –1(x[0])f’([0]).

ли же функция f(x) не квадратичная, но выпуклая, метод Ньютона

Г

гарантирует

ее

монотонное убывание от

итерации

к

итерации.

2.

На k-той итерации определяются шаг аk и точка х[k + 1].

При минимизации овражных функций скорость сходимости метода

3.

Вычисляется величина f(х[k + 1]).

Ньютона более высока по сравнению с градиентными методами.

4.

Проверяются условия выхода из подпрограммы,

реализую-

В таком случае вектор р[k]

не указывает направление в точку ми-

щей данный алгоритм. Эти условия аналогичны условиям выхода

нимума функции f(x), однако имеет большую составляющую вдоль

из подпрограммы при методе наискорейшего спуска. Если эти ус-

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

ловия выполняются, осуществляется прекращение вычислений.

антиградиент.

й

Существенным недостатком метода Ньютона является зависи-

В противном случае вычисляется новое направление:

мость сходимости для невыпуклых функций от начального при-

Б

р[k + 1]

–1

ближения х[0]. Если х[0] находится достаточно далеко от точки ми-

–H (x[k])f'([k]) .

нимума, то

метод

может

расходиться,

т. е. при

проведении

р

осуществляется переход к следующей итерации.

итерации каждая следующая точка будет более удаленной от точки

и

Количество вычислений на итерации методом Ньютона, как

минимума, чем предыдущая. Сходимость метода,

независимо

правило, значительно больше,

чем в градиентных методах.

от начального приближения, обеспечивается выбором не только

Это объясняется необходимостью вычисления и обращения мат-

направления спуска р[k]

H –1(x[k])f'(x[k]),

но и величины шага а

рицы

вторых

производных

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

Однако

вдоль этого направления. Соответствующий алгоритм называют

на получение решения с достаточно высокой степенью точности

методом Ньютона с регулировкой шага. Итерационный пр цесс

с помощью метода Ньютона обычно требуется намного меньше

в таком случае определяется выражением

о

итераций, чем при использовании градиентных методов. В силу

–1

этого метод Ньютона существенно более эффективен. Он обладает

x[k + l] x[k] – akH

(x[k])f'(x[k]).

сверхлинейной

или квадратичной скоростью сходимости

Величина шага аk выбирается из условия мин мума функц

f(х)

в зависимости от требований, которым удовлетворяет минимизи-

по а в направлении движения, т. е. в результате решен я

од-

руемая функция f(x). Тем не менее в некоторых задачах трудоем-

номерной минимизации:

т

о

кость итерации методом Ньютона может оказаться очень большой

(

))

(

))

за счет необходимости вычисления матрицы вторых производных

f

k

H −1

(

x[k]

)

f ′

(

x[k]

= min f

k

−1

(

x[k]

)

f ′

(

x[k]

.

x[k] − a

x[k] − a H

минимизируемой функции, что потребует затрат значительного

a≥0

задачи

Вследствие накопления ошибок в

цессезсчета матрица Гессе

количества машинного времени.

В ряде случаев целесообразно комбинированное использование

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

градиентных методов и метода Ньютона. В начале процесса мини-

е

ной или ее нельзя будет обратить. В таких случаях в подпрограм-

мизации, когда точка х[0] находится далеко от точки экстремума х*,

мах оптимизации полага тся H

–1

(x[k]) Е , где Е — единичная мат-

можно применять какой-либо вариант градиентных методов. Далее,

рица. Очевидно,

что ит рация

ри этом осуществляется по методу

при уменьшении скорости сходимости градиентного метода можно

Р

пр

перейти к методу Ньютона.

наискорейшего спуска.

357

358

7.2. Линейное программирование

грани многогранника. В силу изложенного для решения задачу ли-

Под линейным программированием понимается раздел теории

нейного программирования теоретически достаточно вычислить

значения функции в вершинах многогранника и найти среди

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

У

этих значений наибольшее или наименьшее. Однако в практиче-

(или максимизации) линейных функций на множествах, задаваемых

ских задачах количество вершин области G настолько велико, что

системами линейных равенств и неравенств. В общем случае задача

просмотр их даже с использованием ЭВМ невозможен. Поэтому

линейного программирования формулируется следующим образом.

Т

задач ли-

разработаны специальные численные методы решения

Найти вектор х* = (x*1, ..., х*n), определяющий максимум (мини-

нейного программирования, которые ориентируются в основном

мум) линейной форме

на две формы записи задач. Каноническая форма задачи линейного

f(x) с1x1 + с2x2+...+сnxn

(7.17)

программирования:

А

Гf(x) с1х1 + ...+ сnxn →max(min);

(7.19)

при ограничениях (7.18):

Б

a11x1 +… a1nxn b1;

(7.20)

a11x1 + … a1nxn ≤b1;

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

amx1 +… amnxn bm;

am1x1 + … amnxn ≤bm;

xi ≥0; i 1, …, n.

ли в матричной форме:

am+1x1+… am+1,nxn ≥bm+1;

й

(с, х) →max(min);

(7.21)

. . . . . . . . . . . . . . . . . . .

и

Ax b,

akx1 + … aknxn ≥bm;

х ≥0.

ak+1 x1 + … ak+1nxn ≥ bm;

(7.18)

р

Здесь А (аij) – (m на n) – матрица условий. Ее столбцы (a1j, ...,

am+1x1 + … am+1,nxn bm+1;

аmj)T , j 1, ..., п, называются векторами условий. Вектор b (b1, ...,

bm)T носит название вектора правых частей, а с (с1, …, сn) – век-

о

. . . . . . . . . . . . . . . . . .

тора коэффициентов линейной формы.

alx1 + … alnxn bl;

Задача линейного программирования с однотипными условиями:

т

f(x) с1х1 + ...+ сnxn → max(min);

(7.22)

xi 0; i 1, …, n.

a11x1 +… a1nxn ≤ b1;

Каждое из условий-неравенств определяет полупространство,

. . . . . . . . . . . . . . . . . .

amx1 +…amnxn ≤ bm,

и

ограниченное гиперплоскостью. Пересечение п лупространств об-

разует выпуклый п-мерный многогранник Q. Усл вия равенства

или в матричной форме:

з

выделяют из n-мерного пространства ( –l)-мерную плоскость, пе-

(с, х) → max(min);

(7.23)

ресечение которой с областью Q дает вы уклый (n–l)-мерный мно-

Ax ≤ b.

гогранник G. Экстремальное

формы (если оно

линейной

Любую задачу можно привести к каждой из приведенных форм

существует) достигается в н которой вершине многогранника.

При вырождении оно мож т достигаться во всех точках ребра или

с помощью приемов, описанных ниже.

п

359

360

значение

Р