Методы оптимизации - Харчистов Б.Ф.

Поскольку i = 6 = N1 , то вычисления завершаются. В итоге получаем

x6(1) = x4(1) = 1,5, f6 (1) = −0,375.

Второй этап

Определяем ∆(1) = [x3(1) , x5(1) ] = [0,5; 2,5].

Полагаем x0*(2) = 1,5, f0*(2) = −0,375.

Определяем xi(2) с помощью следующего соотношения:

Результаты вычислений заносим в табл. 5.3.

Поскольку i=4= N2 , то вычисления завершаются.

Ответ: x* 2,25, f * −1,62 .

52

Развитием и обобщением поиска с уточнением является поиск с разведкой. В этом случае исходный отрезок локализации

На первом этапе в каждой из зон проводится разведка. Для этого из общего количества вычислений N выделяется N0 вычис-

лений (в каждой из зон выполняется по N0 / 2 вычислений). Цель

разведки состоит в выборе одной из зон для дальнейших исследований.

Разведка заключается в сканировании каждой из зон. Обо-

Если M1 < M 2 , то для дальнейших исследований выбирается зона D1 , в противном случае − зона D2 .

На втором этапе осуществляется сканирование выбранного отрезка ( D1 или D2 ), при этом выполняется N−N0 вычислений.

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

53

В результате определяются x*N −N0 и fN*− N0 = f (x*N − N0 ) , которые считаются оценками искомых величин, т.е.

Пример. Определить с помощью поиска с разведкой минимум функции f (x) = 2x4 − 8x3 + 8x2 − x , заданной на отрезке

∆ = [−2,4], при N=10, N0 =6.

Поскольку i=3= N0 / 2 , то вычисления завершаются. В итоге получаем

Второй этап

Полагаем x0* = 1,5, f0* = −0,375.

Определяем xi с помощью следующего соотношения:

Результаты вычислений заносим в табл. 5.6.

Поскольку i=4= N − N0 , то вычисления завершаются.

Ответ: x* 2,125, f * −1,98.

Задачи

1. Определить с помощью сканирования минимум функ-

ции f (x) = −exp {−2(x −1)2} − 2 exp{−4(x − 3,2)2 }, заданной на отрезке ∆ = [0, 4] , при N=10.

на отрезке ∆ = [0, 4] , при N=10, N0=6.

56

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

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

f (x) → min, x Rn .

Исходя из заданной начальной точки x(0) , методы спуска

позволяют строить последовательность точек x(1) , x(2) ,…, удовлетворяющих условию

Вобщей схеме методов спуска последовательность x(0) ,

x(1) , x(2) ,… приближений к точке минимума x* выбирается по

правилу

x(k ) = x(k −1) + λk h(k ) , k = 1,2,...,

где h(k ) − вектор, определяющий направление убывания функции f (x) (направление спуска) в точке x(k−1) ;

λk − скаляр, определяющий длину шага вдоль h(k ) .

Обычно название метода спуска определяется способом выбора h(k ) , а его различные варианты связываются с различными способами выбора λk .

Градиентные методы основаны на идее замены минимизи-

руемой функции в окрестности очередной точки x(k ) линейной частью ее разложения в ряд Тейлора. В градиентных методах в

Таким образом, данные методы относятся к методам первого порядка.

Градиентные методы отличаются друг от друга способами

57

выбора параметра λk . На практическом занятии рассматриваются

два способа: первый называется методом с дроблением шага, второй – методом наискорейшего спуска.

.

Метод с дроблением шага

Величина λk выбирается так, чтобы выполнялось условие (6.1). Процесс выбора λk осуществляется следующим образом.

Выбираются некоторые константы α > 0 и 0<β<1 (часто β = 12 ).

На k-й, k=1,2,…, итерации проверяется выполнение условия (6.1) при λk =α. Если оно не выполняется, то производится дробление

шага, т.е. полагается λk =αβ и вновь проверяется выполнение условия (6.1). Процесс дробления, т.е. умножение текущего значения λk на β, продолжается до тех пор, пока условие (6.1) не ока-

жется выполненным.

Алгоритм решения задачи безусловной минимизации методом с дроблением шага заключается в следующем.

1. Задаются α, β, ε, x(0) ; вычисляются f (x(0) ) , f ′(x(0) ) , f ′(x(0) ) , полагается k=1.

2. Полагается λk =α.

+ ∆x(k} , f (x(k ) ).

Если условие не выполняется, то полагается k=k+1 и осуществляется переход к п.2.

Отметим, что помимо рассмотренного применяется алгоритм, в котором в качестве начального значения λk используется

конечное значение λk −1 . При этом в п.1 рассмотренного алгоритма добавляется определение λ0 : полагается λ0 = α ; в п.2 алгоритма заменяется определение λk : полагается λk = λk −1.

Пример. Решить методом с дроблением шага задачу безусловной минимизации

f (x) = x12 + 2x22 − 4x1 + 2x2 → min при α = 1, β = 12 , ε = 0,3, x(0) = (1, 0).

Решение.

Находим первые частные производные f (x) :

Используем второй (упрощенный) вариант метода с дроблением шага.

Результаты вычислений заносим в табл. 6.1.

59

Таблица 6.1

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

В данном случае на каждой итерации шаг λk выбирается из условия минимума функции f (x) в направлении движения, т.е.

f(x(k −1) − λk f ′(x(k −1) )) = min ϕ(λ),

λ>0

где ϕ(λ) = f (x(k −1) − λf ′(x(k −1) )).

Такой способ выбора λk требует меньшего числа итера-

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