mo_in_exercises

Фибоначчи Fk : Fk = Fk −1 + Fk −2 , F0 = F1 =1. Метод является ε -оптималь- ным на множестве AN всех последовательных N -шаговых методов для класса

унимодальных функций Φu .

Метод Фибоначчи обладает симметрией при размещении всех точек измерений, кроме последнего N -го. На всех итерациях используются

оптимальные пропорции λ*k в размещении точек, удовлетворяющие (4.3) и подобранные из условия наилучшего гарантированного сжатия исходного

интервала за N измерений. Значения λ*	= F	F	.
k	N −k +1	N −k +2

При этом λ*N =12 , что не позволяет разместить последнее измерение симметрично к имеющемуся (в силу λ*N =12 оно обязательно окажется в

центре текущего интервала), поскольку это вызвало бы наложение двух точек измерений. Чтобы избежать повторного вычисления в имеющейся точке, последнее измерение смещают от него на малое ε > 0 .

Гарантированная эффективность метода Фибоначчи d*(αNФиб) =

=(b −a)	F	+ε < d*(αз.с.) при достаточно малом ε .	Известно, что	при
N → ∞	N	N
	гарантированная эффективность метода золотого сечения достаточно
близка к эффективности метода Фибоначчи, а именно F			(1 τ)N −1 ≈1.17 при
		N
N → ∞. Это соотношение выполняется уже начиная с семи измерений.
Для применения метода Фибоначчи необходимо заранее определить
значение	N . При решении задачи с заданной точностью δ > 0 величину			N

вычисляют, исходя из условия d*(αNФиб) ≤δ . Описание алгоритма

(a) Задать δ > 0 - точность решения и ε , 0 < ε << δ .

(b) Определить N := min{n : (b − a)Fn +ε ≤δ}.

(c) Провести измерение в двух первых точках x = b − (b − a) FN −1 FN ,

y= a + (b − a) FN −1 FN , принять Qx = Q(x) и Qy = Q( y) ; k = 2 .

(d)При k = 2,K, N − 2, выполнить пункт (e), при k = N −1 перейти к пункту (f).

(e) Если Qx < Qy ,	то положить		b := y , y := x ,	Qy := Qx	и провести
новое испытание в точке	x = y − ( y − a) FN −k −2 FN −k , Qx := Q(x) ; иначе,
при Qx > Qy , положить a := x ,		x := y , Qx := Qy , провести новое испытание
y = x + (b − x) FN −k −2	FN −k ,	Qy := Q( y) . Увеличить счетчик k := k +1 и
вернуться к пункту (d).			b := y , y := x ,
(f) Если Qx < Qy ,	то положить			Qy := Qx	и провести
новое испытание в точке x = y −ε ,			Qx := Q(x) ;	иначе, при	Qx > Qy ,

51

положить a := x , x := y , Qx := Qy , провести новое испытание y = x +ε , Qy := Q( y) . Положить k = N , перейти на пункт (g).

(g) Если Qx < Qy , положить b := y , иначе, при Qx > Qy , положить a := x . Принять интервал [a,b] в качестве интервальной оценки решения.

Иллюстрация размещения точек испытаний для метода Фибоначчи приведена на рис. 4.3.

Рис. 4.3. Сокращение интервала и размещение испытаний в методе Фибоначчи на первых итерациях при N =6 для некоторого варианта значений функции (указаны доли длин отрезков в текущем [a,b])

4.3. Поиск минимума выпуклой дифференцируемой функции

Пусть в точке xs проведено испытание первого порядка функции Q с вычислением Qs и Qs . Используя критерий выпуклости дифференцируемой

функции, получим оценку снизу в виде Q(x) ≥ Qs + ( Qs , x − xs ) . Если проведено k испытаний, оценка принимает вид Q(x) ≥ Qk−(x) , где

Qk−(x) = max{Qs + ( Qs , x − xs ): s =1,K, k}.

Пусть для выпуклой дифференцируемой функции Q поставлена задача с

ограниченной допустимой областью, описанной системой линейных неравенств:

min{Q(x): A x ≤ b}.

Описание алгоритма

(a) Задать δ > 0 - точность поиска по значению функции.

52

(b) Выбрать		k0 ≥1 начальных точек в области					A x ≤ b ,		провести
испытания и положить k = k0 .
(c) Получить очередную точку xk +1 = arg min { Q−(x) : Ax ≤ b }.
					k
(d) Проверить критерий останова: вычислить Q* = min{ Q : s =1,..., k }
					k			s
- текущую оценку глобально-оптимального значения. Если							Q* −Q−(xk +1) ≤δ ,
							k	k
остановить вычисления и перейти к пункту (f), иначе – к пункту (e).
(e) Провести		испытание	в	точке xk +1 :	Q	=Q(xk +1),			Q		=
					k +1				k +1
= Q(xk +1) . Увеличить счетчик k := k +1 и вернуться к пункту (c).
(f)	В качестве оценки решения принять точку					x*		{x1,K, xk },		для
которой Q(x* ) = Q* .						k
	k	k	xk +1
Замечание: выбор точки				в пункте (c)	алгоритмически сводится к
решению	задачи	линейного	программирования		в пространстве				векторов
(z; x) R1+n :

(z k +1; xk +1 ) = arg min z

Q1 +( Q1, x − x1 )≤ z ;

………………………………….

Qk +( Qk , x − xk )≤ z ;

A x ≤ b

4.4. Поиск локального минимума в задачах без ограничений

Рассмотрим задачу	min{Q(x) : x Rn }. Большинство	методов
локальной оптимизации имеют вид итерационных процедур
	xk +1 = xk +tk d k	(4.4)
где d k - направление шага,	определяемое по результатам испытаний Jk в

основных точках поиска xk , а tk - скалярный шаговый множитель [8-10],

[13, 17, 18]. Его величина определяется с использованием дополнительных испытаний, порядок которых может быть ниже, чем у основных.

Критерии и алгоритмы выбора шагового множителя

		Функцию Q будем считать по крайней мере гладкой, а d k – направле-
нием ее строгого локального убывания в точке xk .
		Критерий 1 (существенности убывания функции):
t	k	Π	1	(μ) := {t ≥ 0 : Q(xk + t d k ) ≤ Q + μ ( Q , d k )t }, 0 < μ <1.
				k	k

53

t = 0 ,

Критерий

2 (близость к минимуму по направлению):

t

k

Π

2

(η) := {t ≥ 0 :

( Q(xk + t d k ), d k )

≤η

( Q , d k )

}, 0 <η <1.

k

Критерий

3

(η) := {t ≥ 0 : ( Q(xk + t d k ), d k )≥η ( Q , d k )}.

t

k

Π

3

k

Критерии 2 и 3 используются совместно с критерием 1. Ниже приведено алгоритмическое описание трех способов выбора шагового множителя: правило Армихо, правило одномерной минимизации и правило Вулфа.

Правило Армихо

(a)Задать параметры: μ, 0 < μ <1 - параметр критерия 1; α > 0 - начальное значение шагового множителя; γ , 0 < γ <1 - коэффициент сжатия.

(b)Положить t =α .

(c)Пока t Π1(μ) , корректировать t := γ t .

(d)При первом выполнении условия t Π1(μ) принять tk = t .

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

выбора направлений d k .

Правило одномерной минимизации
Согласно этому правилу, выбор		tk должен удовлетворять требованию
tk Π1(μ) ∩Π2 (η) .	Непустота	пересечения	гарантируется	при

0 < μ <η <1. Выбор подходящего tk происходит в два этапа. На первом этапе определяется отрезок [0,T ], содержащий точку t* первого локального минимума функции ϕ(t) = Q(xk + t d k ) на луче t ≥ 0 . На втором этапе, в предположении унимодальности функции ϕ(t) на [0,T ], выполняется

процедура поиска ее минимума (например, методом золотого сечения) до первого обнаружения значения t , удовлетворяющего заданным условиям.

Этап 1. Сканирование луча с удвоением шага

(a) Задать начальное значение шага 0 < <<1. Положить

ϕt

=ϕ(t) .

(b)

Перейти к следующей точке

t

= t +

, ϕt

=ϕ(t )

и удвоить шаг

:= 2 .

обнаружено

возрастание

функции

ϕ (например,

(c)

Если в точке t

>ϕt

′

ϕt

или ϕ (t ) > 0 , если значение производной вычисляется), то положить

T = t

и

завершить этап

1; иначе положить

t := t ,

ϕt :=ϕt

и вернуться к

пункту (b).

54

Этап 2. Минимизация на [0,T ]с целью определения tk

(a)Задать параметры 0 < μ <η <1.

(b)Выполнить одним из методов поиск минимума ϕ(t) на отрезке [0,T ],

считая ее унимодальной, до момента первого испытания в точке t Π1(μ) ∩Π2 (η) , после чего поиск остановить.

(c) Положить tk = t .

Правило одномерной минимизации требует вычисления градиента функции для каждого t , проверяемого на этапе 2. Это может приводить к гораздо большим затратам, чем при использовании правила Армихо. Однако

выбор tk по правилу одномерной минимизации (по крайней мере при η <<1) обеспечивает сходимость процесса поиска локального минимума для всех распространенных вариантов выбора направлений d k .

Правило	одномерной	минимизации	при 0 < μ <η <<1 называют
аккуратным одномерным поиском.
Правило Вулфа			условия tk Π1(μ) ∩Π3 (η) ,
Шаговый	множитель	выбирается из
0 < μ <η <1.

Алгоритмизация правила [9]

(a) Задать 0 < μ <η <1 – параметры критериев 1 и 2; α > 0 – начальное пробное значение; 0 < γ <1 – коэффициент «интерполяции»; r >1 – коэффициент «экстраполяции». Положить t =α и α =α = 0 .

(b) Если t Π1(μ) ∩Π3 (η) , перейти к пункту (e), иначе – к пункту (c).

(c) Если t Π1(μ) , положить a = t и перейти к пункту (d), иначе, если t Π2 (η) , положить a = t . Если при этом a ≠ 0, перейти к пункту (d), а при a = 0 выполнить «экстраполяцию», положив t := a r и вернуться к пункту (b).

(d) Выполнить	«интерполяцию»: t :=α γ +α (1 −γ ) и вернуться к
пункту (b).
(e) Положить tk	= t .

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

Методы градиентного поиска

К этой группе относятся методы, использующие итерационное соотношение (4.4), в котором направление шага d k = − Qk . Шаговый

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

любой начальной точки при весьма слабых требованиях на Q . Если

55

используется правило одномерной минимизации в варианте «аккуратного» одномерного поиска (η <<1), то его можно рассматривать как

вычислительную реализацию правила

tk = arg min{Q(xk + t d k ) : t ≥ 0}.	(4.5)
Градиентный поиск в сочетании с правилом (4.5) называют	методом

наискорейшего градиентного спуском. Для него направления d k , полученные на двух последовательных итерациях, всегда ортогональны, т.е. (d k +1, d k )= 0 . Для квадратичных функций Q(x) с положительно определенной матрицей

Гессе, имеющей разброс собственных чисел от λmin							до	λmax , справедливы
следующие оценки скорости сходимости:
	k =0		1	− λmin		2
					/ λmax			и C > 0,
a(x		) [0, q], q =	1	+ λ	/ λ		<1
				min	max

что

Q −Q* ≤ (a(x0 ))k (Q −Q* ) ,

xk − x*

≤ C (a(x0 ))k 2

x0 − x*

.

k

0

Таким

образом,

обеспечивается сходимость со скоростью геометрической

прогрессии,

при

этом величины

xk +1 − x*

и

xk − x*

имеют одинаковый

порядок малости. Такая сходимость называется линейной. В качестве критерия

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

Qk +1

≤ δ .

Метод Ньютона и его модификации

Метод Ньютона предполагает, что функция Q по крайней мере дважды

непрерывно

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

Проводятся испытания

второго

порядка

J

k

= (Q , Q , 2Q

k

). Точка

xk +1 размещается в стационарной точке

k

k

квадратичной аппроксимации, построенной по результату k -го испытания. Шаговый множитель выбирается равным единице, т.е. tk =1. В методе Ньютона

xk +1 = xk +1 dньютk ,

где dньютk определяют из решения линейной системы

2Qk dньютk = − Qk .

В явной форме

xk +1 = xk + ( 2Qk )−1(− Qk ).

Однако при вычислениях этот вид записи не применяется, за исключением одномерного случая ( n =1), когда

xk +1 = xk −Qk′ Qk′′.

56

Сходимость метода Ньютона к стационарной точке x* функции Q обеспечивается для функций Q C2 (Rn ) при условии det( 2Q(x* ))≠ 0 только лишь в некоторой окрестности x* . Сходимость является сверхлинейной, т.е. xk +1 − x* = o( xk − x* ) , следовательно, ошибка убывает быстрее, чем

любая геометрическая прогрессия. Если у функции существуют третьи производные и они ограничены в области сходимости, то сходимость по крайней мере квадратична, т.е. существует C ≥ 0 такая, что с некоторого шага

xk +1 − x* ≤ C xk − x* 2 .

Расширение области сходимости метода Ньютона может быть достигнуто за счёт введения шагового множителя tk , выбираемого по правилу Армихо,

Вулфа или одномерной минимизации. В первых двух случаях следует выбирать значения параметра α =1.

Заметим, что в методе Ньютона направление dньютk будет являться направлением локального убывания только в случае выполнения очевидного условия ( ( 2Qk )−1(− Qk ), Qk ) < 0. Оно может нарушаться, если матрица2Qk не будет являться положительно определённой, что говорит о

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

быть модифицирован путем замены матрицы 2Qk на близкую к ней положи-

тельно определённую. Обычно для этого используется модифицированное преобразование Холесского [18].

В качестве основного критерия останова в методе Ньютона используется останов по малости нормы градиента: Qk ≤δ .

Метод сопряжённых градиентов Флетчера-Ривса

Для дважды непрерывно дифференцируемых функций Q можно

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

Описание метода

(a) Задать δ > 0 – параметр останова, 0 < μ <η <1 – параметры одномерной минимизации, x0 - начальную точку.

(b)ВычислитьQ0 =Q(x0 ) , Q0 = Q(x0). Положить p0 =− Q0 и k = 0 .

(c)Если ( Qk , pk ) ≥ 0 (т.е. pk – не направление строгого локального

убывания), то выполнить замену pk = −Qk , x0 = xk и положить k = 0 ; иначе не изменять pk .

57

(d) Принять d k = pk и определить шаговый множитель tk по алгоритму «аккуратной» одномерной минимизации, вычислить xk +1 = xk + tk d k , Qk +1 = Q(xk +1) , Qk +1 = Q(xk +1) , увеличить счетчик k := k +1.

(e)Проверить критерий останова: при Qk ≤ δ остановить вычисления

ипринять за оценку решения xk . При Qk > δ перейти к пункту (f).

(f)Если k = N , то положить x0 = xN , p0 = − QN и k = 0 , вернуться к пункту (d); иначе определить

pk = − Qk + βk pk +1 ,

где βk = ( Qk , Qk − Qk −1)|| Qk −1 ||2 , вернуться к пункту (d).

Укажем на некоторые дополнительные свойства метода в случае его применения к квадратичной функции Q(x) с положительно определенной

матрицей	Гессе 2Q = A.	Для таких функций метод строит систему
направлений p0 , p1,K, p N −1 , которая будет являться			A-сопряженной, т.е.
i ≠ j	( pi , A p j ) = 0 при	нетривиальности самих	векторов. При этом

глобальный минимум квадратичной функции будет найден (если не учитывать

критерий останова) не более, чем за	N шагов	(где N –	размерность
пространства переменных x ), а система	градиентов	Q0 , Q1,K, QN −1
окажется взаимно ортогональной.
Для функции Q(x) общего вида метод за N		итераций	в точку её

минимума, естественно, не попадет и будет выполнен рестарт из последней найденной точки. Кроме того, для функции общего вида очередной вектор pk

может не являться направлением строгого локального убывания. Это проверяется в пункте (c). В случае нарушения данного условия выполняется рестарт из последней точки.

Метод Хука-Дживса

Этот метод прямого поиска, т.е. измеряются только значения функции, а гладкость и даже непрерывность Q(x) не предполагаются. Направление

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

Пусть e1, e2 ,K, eN – координатные орты, а h – параметр конфигурации. Алгоритм построения конфигурации x = F(z) .

(a)Положить x = z , i =1.

(b)Для i ≤ N выполнить пункт (c); при i > N завершить построение конфигурации.

58

(c) Если Q(x + h ei ) < Q(x) , положить x := x + h ei ;	иначе, если
Q(x − h ei ) < Q(x) , положить x := x − h ei ; иначе сохранить	прежнее x .
Увеличить номер координаты i := i +1 и вернуться к пункту (b).

Основной алгоритм

(a)Задать начальную точку x0 , параметр останова δ > 0 и параметр конфигурации h >> δ .

(b)Положить z1 = x0 , k = 0 .

(c)Построить конфигурацию xk +1 = F (zk +1)

(d) Если Q(xk +1) < Q(xk ) , то положить k := k +1 и перейти к пункту (e); иначе, если h < δ , остановить вычисления, приняв за оценку решения значение xk ; если же h > δ , то перейти к пункту (f).

(e)Выполнить шаг по образцу: zk +1 = xk + 2(xk − xk −1) , и перейти к пункту (c).

(f)Если k > 0 , положить x0 := xk , k = 0 и перейти к пункту (b); если же k = 0 , то уменьшить параметр конфигурации h := h2 и перейти к пункту (b).

4.5. Вычислительные методы решения задач с ограничениями

Рассмотрим задачи общего вида (4.1)-(4.2) и приведем описание двух общих методов: метода внешнего штрафа и метода модифицированных множителей Лагранжа. Оба метода строят последовательность вспомогательных оптимизационных задач. Минимизируемые функции этих задач зависят от настраиваемых параметров. Решения исходной задачи можно получить как предельные точки последовательностей решения вспомогательных задач.

Метод внешнего степенного штрафа [8, 9, 10, 13]

Функция H (x) , определенная на множестве x E , называется функ-

цией штрафа в задаче (4.1)-(4.2), если
0,	x D,
H (x) =	x D.
> 0,

Одним из конкретных видов функции штрафа является степенной штраф:

H (x) = ∑N	(max{0; c g	(x)}) p + ∑M		C	h	(x)		p ,
i=1	i i	j=1		j	j

где c1,K, cN ; C1,K, CM - положительные нормировочные коэффициенты, а показатель степени p > 0 .

59

Заметим, что при достаточной гладкости функций gi и hj порядок гладкости функции штрафа определяется значением p следующим образом:

(a)при 0 < p ≤1 негладкий штраф;

(b)при 1 < p ≤ 2 гладкость до первого порядка;

(c)при 2 < p ≤ 3 гладкость до второго порядка.

Построим вспомогательную функцию для задачи со штрафом

Sγ (x) = Q(x) +γ H (x) ,

где γ > 0 – коэффициент штрафа. Заметим, что в допустимой области x D функция Sγ (x) = Q(x) , а вне этой области Sγ (x) > Q(x) за счет присутствия

положительной штрафной добавки за нарушение ограничений. Вспомогательные задачи со штрафом будут иметь вид:

		min{Sγk (x) : x E ,			(4.6)
где выбирается γk		→ ∞ при k → ∞. Предполагается,			что при больших γk
решения x*	этих задач существуют и не покидают некоторой ограниченной и
γ k
замкнутой области. Если E - компактно,			то последнее предположение будет
всегда выполнено.		Можно доказать, что при		непрерывности Q и H все
предельные	точки	последовательности	x*	будут	являться решениями
			γ k

исходной задачи (4.1)-(4.2). Структуру задачи со штрафом при некотором коэффициенте штрафа γk иллюстрирует рис. 4.4.

Рис. 4.4. Пример поведения функции задачи со штрафом при гладкой функции штрафа

Заметим, что при гладкости штрафа в случае положения x* (решения исходной задачи) на границе допустимой области D сходящаяся к x*

60