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

МетодЫ решения оптимизационной задачи.. 2

Методы одномерной минимизации. 2

Метод Свенна. 2

Метод золотого сечения. 2

Метод Фибоначчи. 4

Метод линейной интерполяции (метод секущих) 5

Метод средней точки (метод Больцано) 6

Метод квадратичной интерполяции – экстраполяции. 6

Метод Пауэлла. 7

Метод Давидона. 8

Методы многомерной минимизации. 9

Метод Коши. 9

Метод Циклического покоординатного спуска. 9

Метод параллельных касательных. 10

Метод Гаусса-Зейделя. 11

Метод комплексов Бокса. 11

Метод Хука-Дживса (конфигураций) 13

Метод Хука-Дживса с одномерной минимизацией. 15

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

Метод Зангвилла. 16

Метод Флетчера-Ривса. 17

Метод Пауэлла. 18

МетодЫ решения оптимизационной задачи

Курсовая работа включает в себя подавляющее большинство методов оптимизации, прочитанных в курсах «Методы оптимизации» и «Теория принятия решений». Каждый метод представлен в виде отдельной функции-члена класса. Все однотипные методы (в плане необходимых сведений для поиска) имеют одинаковое число аргументов. В большинстве своём - это начальная точка, погрешность максимальное количество шагов.

В этом разделе представлены краткие описание методов оптимизации и применяемых математических формул. Сначала идут описания одномерных методов поиска, а затем многомерных.

Методы одномерной минимизации

Метод Свенна

Метод Свенна организует начальную локализацию минимума унимодальной функции, т.е. простой одномерный поиск с удвоением шага, критерием окончания которого является появление признака возрастания функции.

Начальный этап
.

(1) задать произвольную начальную точку x0
ÎRn

(2) выбрать начальный шаг h=Dx=0,01

Основной этап

Шаг 1. Установить направление убывания функции. Для этого взять x2
=x1
+h. Если f(x1
) <f(x2
), то поменять направление движения: h1
=-h1
и взять x2
=x1
+h1
.

Шаг 2. Вычислить fk
в точках xk
+1
=xk
+hk
, где k=2,3,4,…,m-1; hk
=2hk
-1
– движение с удвоением шага, до тех пор, пока не придём в точку xm
такую, что f(xm
)<f(xm
-1
).

Шаг 3. Установить начальный интервал локализации минимума

a1
=xm
-2

b1
=xm

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

Метод золотого сечения – это процедура одномерного поиска минимума на интервале [a1
,b1
] или [0,1]. На каждом шаге пробная точка lk
или mk
внутри текущего интервала локализации [ak
,bk
] делит его в отношении, постоянном для всех интервалов - золотое сечение. Можно показать, что , откуда , следовательно , значит . Одним из корней этого уравнения является t1
=0,618 – первое золотое число. Отметим, что t1
2
=0,6182
=0,382 – второе золотое число. Следует отметить, что в методе золотого сечения имеет место правило симметрии (эквидистантности) точек относительно концов интервала, а также правило одного вычисления, т.е. на каждой итерации требуется одно и только одно новое вычисление (кроме первой итерации), т.к. точки на соседних итерациях совпадают.

Алгоритм ЗС-1

Начальный этап

(1) Выбрать погрешность расчёта e=10-3
¸10-7
. Получить начальный интервал методом Свенна.

(2) Вычислить стартовые точки l1
=a1
+0,382L1
, m1
=a1
+0,618L1
(следует отметить, что золотые числа следует вычислять точно)

(3) Принять k=1 – счётчик числа итераций

Основной этап

Шаг 1.Сократить ТИЛ рассмотрением 2-х ситуаций:

(1) Если f(l)<f(m),то

ak+1
=ak

bk+1
=mk

mk+1
=lk

lk
=ak+1
+0,382Lk+1

иначе

ak+1
=lk

bk+1
=bk

lk+1
=mk

mk
=ak+1
+0,618Lk+1

(2) Положить k=k+1, Lk+1
=|bk+1
-ak+1
|

Шаг 2. Проверить критерий окончания поиска: если |ak
+1
-bk
+1
|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как . Иначе вернуться на шаг 1.

Алгоритм ЗС-2

Начальный этап

(4) Выбрать погрешность расчёта e=10-3
¸10-7
. Получить начальный интервал методом Свенна.

(5) Вычислить стартовые точки l1
=a1
+0,382L1
, m1
=a1
+0,618L1
(следует отметить, что золотые числа следует вычислять точно)

(6) Принять k=1 – счётчик числа итераций

Основной этап

Шаг 1. Взять очередную пробную точку x2
=ak
+bk
-x1
, симметричную исходной и сократить ТИЛ рассмотрением 4-х возможных ситуаций:

(1) Если (x1
<x2
) и (f(x1
)<f(x2
)) то b=x2
;

(2) Если (x1
<x2
) и (f(x1
)>=f(x2
)) то a=x1
;

(3) Если (x1
>x2
) и (f(x1
)<f(x2
)) a=x2
;

(4) Если (x1
>x2
) и (f(x1
)>=f(x2
)) b=x1
;

Увеличить счётчик числа итераций k=k+1

Шаг 2. Проверить критерий окончания поиска: если |ak
+1
-bk
+1
|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как . Иначе вернуться на шаг 1.

Метод Фибоначчи

Метод Фибоначчи является процедурой линейного поиска минимума унимодальной функции f(x) на замкнутом интервале [a, b], отличающейся от процедуры золотого сечения тем, что очередная пробная точка делит интервал локализации в отношении двух последовательных чисел Фибоначчи. Последовательность чисел Фибоначчи задаётся условиями F0
= F1
= 1, Fk+1
= Fk
+ Fk-1
, k = 1,2,... Начальными членами последовательности будут 1, 1, 2, 3, 5, 8, 13,... Стратегия поиска Фибоначчи требует заранее указать n - число вычислений минимизируемой функции и e - константу различимости двух значений f(x). Рассмотрим один из возможных вариантов метода.

Алгоритм Фибоначчи-1

Начальный этап

(1) Задать константу e, начальный интервал [a1
, b1
], длину конечного интервала Ln
и определить число n так, чтобы выполнялось условие Fn
> (b1
- a1
)/Ln
.

(2) Взять две пробные точки l1
= a1
+ (Fn-2
/Fn
)(b1
- a1
) и m1
= a1
+ (Fn-1
/Fn
)(b1
-a1
). Положить k = 1.

Основной этап

Шаг 1. Сократить текущий интервал локализации:

(1) Если f(lk
) < f(mk
), то положить ak+1
= ak
, bk+1
= mk
,mk+1
=lk
и вычислить новую точку lk+1
= ak+1
+ (Fn-k-2
/Fn-k
)Lk+1
, где Lk+1
= bk+1
- ak+1
; перейти на шаг 2.

(2) Если f(lk
)>> f(mk
),то положить ak+1
=lk
, bk+1
= bk
, lk+1
= mk
и вычислить mk+1
= ak+1
+ (Fn-k-1
/Fn-k
) Lk+1
.

Шаг 2. Проверить критерий окончания поиска:

(1) Заменить k на k+1. (2) Если k = n - 1, перейти на шаг 3, иначе - на шаг 1.

Шаг 3. Найти аппроксимирующий минимум х(*)
:

(1) Положить mk
= lk
+ e.

(2) Если f(lk
) > f(mk
), то x(*)
= (lk
+ bk
)/2. В противном случае - x(*)
= (ak
+ mk
)/2.

Алгоритм Фибоначчи-2

Начальный этап

(1) Задать константу e, начальный интервал [a1
, b1
], длину конечного интервала Ln
и определить число n так, чтобы выполнялось условие Fn
> (b1
- a1
)/Ln
.

(2) Выбрать одну пробную точку . Положить

k = 1.

Основной этап

Шаг 1. Проверить критерий окончания поиска: если k=n, то остановиться и положить x*=x2
.

Шаг 2. Сократить текущий интервал локализации рассмотрением 4-х ситуаций, аналогично методу золотого сечения-2.

Метод линейной интерполяции (метод секущих)

Метод секущих предлагает заменить вторую производную f ''(xk
)
в ньютоновской формуле её линейной аппроксимацией (f '(xk
)-f '(xk-1
))/(xk
-xk-1
)
.

Тем самым очередное приближение хk+1
к стационарной точке х*
задаётся формулой вида

xk+1
= xk
- f '(xk
) * (xk
- xk-1
) / ( f '(xk
) - f '(xk-1
)).

Легко видеть, что хk+1
- точка пересечения с осью абсцисс секущей прямой, проходящей через точки хk
и хk-1
.

В отличие от метода Ньютона метод секущих гарантирует сходимость точек {xk
}
к стационарной точке х*
, однако, сходимость метода достигается ценой потери быстродейсвия. Как правило, метод дихотомии оказывается эффективнее метода секущих, хотя последний и получен из более быстродействующей схемы.

Начальный этап
. Пусть методом Свенна получен интервал неопределённости [a1
,b1
]
, границы которого удовлетворяют неравенству f'(a1
)f '(b1
) < 0
. Задать e - погрешность вычисления минимума и принять k=
1.

Основной этап

Шаг 1. Найти очередное приближение хk+1
к минимуму х* и проверить условие окончания поиска:

(1) xk+1
= bk
- f '(bk
)*(bk
- ak
)/(f '(bk
) - f '(ak
));

(2) если ½f '(xk+1
)
½ <<
e
,
то остановиться.

Шаг 2. Уменьшить интервал поиска минимума:

(1) если f '(xk+1
) > 0
, то a
k
+1
= ak, bk+1
= xk+1
, в противном случае принять ak+1
= xk+1
, bk+1
= bk
;

(2) положить k = k + 1 и перейти на шаг 1.

Метод средней точки (метод Больцано)

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

Начальный этап
. Для запуска метода необходимо:

(1) задать [a1
,b1
]- начальный интервал локализации минимума, на границах которого знаки производных различны, т.е. f'¢(a1
)f'¢(b1
)<0; e - малое положительное число;

(2) положить к=1 и перейти к основному этапу.

Основной этап

Шаг 1. Взять пробную точку хk
в центре текущего интервала и проверить критерий окончания поиска: (1) xk
= (ak
+ bk
)/2; (2) если ½f'¢(xk
)½ ≤ e и Lk
= ½bk
- ak
½≤ e, то остановиться (хk
= х* -аппроксимирующий минимум).

Шаг 2. Сократить текущий интервал:

(1) Если f ¢(xk
) > 0, то положить ak+1
= ak
и bk+1
=xk
, в противном случае - ak+1
=xk
, bk+1
=bk
;

(2) заменить k на k+1 и вернуться на шаг 1.

Метод квадратичной интерполяции – экстраполяции

Данный метод относится к классу прямых методов, опирающихся на идею построения аппроксимирующего полинома второго порядка на основании информации о значениях функции в n+1 точке – узлах интерполяции.

Начальный этап

1. Выбрать произвольную точку x1
ÎRn

2. Задаться величиной шага h=0.001

3. Определить погрешность

4. Положить счётчик числа итераций равным 1, а также b=x1

Основной этап

Шаг 1. Вычислить fi
в 3-х точках: a, b и с – центральной (b) и двух соседних: a=b-h, c=b+h. Затем, по формуле

(1)

или

(2)

найти аппроксимирующий минимум d

Шаг 2. Проверить критерий близости 2-х точек b и d

и

Если оба условия выполняются – фиксируем аппроксимирующий минимум

и останавливаемся. Если оба критерия не выполняются, полагаем b=d и возвращаемся на шаг 1.

Метод Пауэлла

Метод Пауэлла является одним из самых популярных методов. Эффективен как и рассмотренный ранее алгоритм квадратичной интерполяции – экстраполяции, если начальная точка x1
Îd(x*).

Начальный этап

1. Выбрать ε1
, ε2
, h.

2. Взять 3 точки a, b, c на равных на равных интервалах. Предполагается, что сработал метод Свенна и получен интервал [a, b].

a=a;

c=b;

b=(a+c)/2;

Основной этап

1. Найти аппроксимирующий минимум на 1-й итерации по формуле:

на последующих итерациях по формуле:

2. Проверить критерии близости двух точек:

;

Если он выполняется, принять и остановиться.

Если не выполняется, то из 2-х точек b и d выбрать «лучшую» - в которой наименьшее значение функции, обозначить её как b, а 2 соседние с ней – a и c. Далее рассмотреть 4 ситуации аналогично ЗС-2.

3. Положить k=k+1 и вернуться на шаг 1.

Метод Давидона

Начальный этап

1. Выбрать ε, x0
, p, α1

2. Предполагается, что сработал метод Свенна и получен интервал [a, b].

Основной этап

1. Найти аппроксимирующий минимум, т.е. точку d по формулам:

2. Проверить КОП: если y
`
r
≤ ε
, то остановиться, х=a+αr
p
. Иначе: сократить ТИЛ: если y
`
r
<0, то [r,b], если y
`
r
>0, то [a,r].

Положить k=k+1 и вернуться на шаг 1.

Методы многомерной минимизации

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

x – вектор от которого зависит функция

x0 – стартовая точка

p – направление

L – смещение по направлению

Метод Коши

Метод Коши относится к группе методов градиентного спуска. Градиентные методы – это методы, где на каждом шаге выбирается антиградиентное направление спуска.

Начальный этап

Выбрать x1, e, k.

Основной этап

Шаг 1

Шаг 2

(1) Найти L как результат минимизации функции по направлению p.

(2)

Шаг 3

(1) Вычислить новое значение градиента

(2) Проверить КОП: если , то , иначе на Шаг 1.

Метод Циклического покоординатного спуска

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

Начальный этап

Выбрать x1, e, k=1, l=1.

Основной этап

Шаг 1

(1) В качестве направления p выбрать , где ненулевая позиция имеет индекс l.

(2) Найти L как результат минимизации функции по направлению p.

(3)

(4) Если l<n то Шаг 2, иначе повторить Шаг 1 с l = l+1.

Шаг 2

(1) Вычислить

(2) Проверить КОП:

если , то , иначе , l=1 и на Шаг 1.

Метод параллельных касательных

Начальный этап:

Выбрать х1, ε = 10-4
– 10-8
установить k = 1;

Основной этап:

Шаг 1.

Из точки x1
выполнить антиградиентный в точку x2
= x1
+α1
р1
, где p1
=-Ñу1
.

Шаг 2.

Последовательно выполнить две операции:

1. Антиградиентный спуск в точку x3
.

2. Вычислить ускоряющее направление d=x3
-x1
и, не останавливаясь совершить ускоряющий шаг в точку x4
=x3
+α3
d.

Шаг 3.

Проверить КОП: - остановиться x*=x4
.

Иначе:

1. Обозначить x2
как новую начальную x1
=x2
, а точку x4
как новую точку ускорения x2
=x4
.

Перейти к шагу 2.

Метод Гаусса-Зейделя

Начальный этап

Выбрать х1, ε = 10-4
– 10-8
установить k = 1;

Основной этап:

Шаг 1.

Выполнить серию одномерных поисков вдоль координатных орт

Шаг 2.

Вычислить ускоряющее направление и проверить КОП: , если выполняется, минимум найден: x*=xn+1
.

Иначе:

1. Выполнить ускоряющий шаг в новую точку хn+2

2. Обозначить последнюю точку как начальную и вернуться на шаг 1.

Метод комплексов Бокса

Комплекс-метод предназначен для отыскания условного экстремума непрерывной целевой функции (1) в выпуклой допустимой области.

При использовании метода принимаются следующие предпо­ложения:

1. Задача поиска экстремума функционала (1) решается при наличии ограничений 1-го и 2-го рода.

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

3. Допустимая область выпукла.

4. Значения целевой функции и функций ограничений вычисляются без ошибок.

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

В отличие от симплексного метода, в комплексе-методе используется случайный набор N точек – Комплекс, а число точек Комплекса определяется по правилу:

(5)

где n – число независимых переменных.

Вычислительная последовательность (алгоритм) комплекс-метода включает в себя следующие этапы.

1) Формируется исходный комплекс. Координаты вершин исходного Комплекса хij вычисляются последовательно с помощью равномерно распределенных на интервале (0;1) псевдослучайных чисел rij:

(6)

x
ij
=g
i
+r
ij
(h
i
- g
i
), i=1, 2,…,n, j=1, 2, ,N.

В каждой вершине с номером j проверяется выполнение ограничений 2-го рода (ограничения 1-го рода выполняются автоматически).

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

Пусть число точек, удовлетворяющих ограничениям 2-го рода Р
(Р≥1),
тогда (
N
–
P
)
– число точек, в которых ограничения нарушены.

Далее для каждой из еще незафиксированных вершин выполняется операция по ее смещению к центру Р
вершин Комплекса, при этом новые координаты точки х*
ij
вычисляются по формуле

(7)

, i
=1, 2,…,
n
,
j
=
P
+1,
P
+2,…,
N
.

Процесс смещения j
-й точки продолжается до тех пор, пока для нее не будут выполнены все ограничения. Такой момент обязательно наступит, поскольку допустимая область выпукла. Точка фиксируется как новая вершина Комплекса (Р
увеличивается на единицу), после чего операция смещения повторяется для очередной вершины.

(8)

2) Для всех N вершин Комплекса вычисляются значения целевой функции F
i
:

F
j
=
F
(
x
j
)
, , j
=1, 2,…,
N
.

(9)

3) Выбираются наилучшее R
и наихудшее S
(с точки зрения экстремума) значения из массива F
i
:

R
=
F
G
;
S
=
F
D
.

где G
– номер самой «хорошей»; а D
– самой «плохой» вершины.

4) Определяются координаты C
i
центра Комплекса с отброшенной «наихудшей» вершиной:

(10)

, i=1, 2,…,n.

5) Проверяется условие окончания поиска. Для этого вычисляется величина В
:

(11)

.

Если В<ε
(ε
– заданная точность вычисления), т.е. среднее расстояние от центра Комплекса до худшей (D
) и лучшей (G
) вершин меньше ε
, то поиск заканчивают, считая экстремум найденным.

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

(12)

6) взамен наихудшей вычисляются координаты новой точки Комплекса:

x
i
0
=2,3
C
i
– 1,3
x
iD
,
i
=1, 2,…,
n
.

В этой новой точке проверяется выполнение ограничений 1-го рода. В случае, если ограничения нарушаются, x
i
0
принимает значения g
i
+
ε
или h
i
–
ε
в зависимости от того, в какую сторону i
-е
ограничение нарушено;

(13)

7) для новой точки проверяется выполнение ограничение 2-го рода. Если хотя бы одно из ограничений нарушено, то новую точку смещают к центру Комплекса на половину расстояния:

.

Процесс смещения продолжают до тех пор, пока все ограничения 2-го рода не будут соблюдены.

8) В новой точке вычисляют значения целевой функции F
0
:

(14)

.

(15)

9) Если F
0
оказывается хуже S
(значение целевой функции в наихудшей точке D
предыдущего комплекса), т.е. новая точка находится дальше от экстремума, чем вершина с номером D
, то новая вершина находится смещением x
i
0
на половину расстояния к лучшей из вершин комплекса G
:

.

Затем вновь вычисляют значение целевой функции F
0
и сравнивают его с S
. Смещением к лучшей вершине по формуле (15) продолжают до тех пор, пока F
0
не станет лучше S
.

За счет этой процедуры происходит последовательное сжатие комплекса к лучшей вершине.

10) Если вычисленное в новой точке х
0
значение F
0
лучше S
, то в Комплексе на месте наихудшей точки х
D
фиксируется точка х
0
и значение S
заменяется на F
0
.

Затем вычисления повторяются, начиная с п. 3, и продолжаются до тех пор пока не будет выполнено условие остановки, т.е. не будет найден с заданной точностью экстремум целевой функции.

Метод Хука-Дживса (конфигураций)

Эффективность прямого поиска точки минимума можно повысить, если на ка­ждом k-м шаге поиска соответствующим образом выбирать направление спуска. Для этого на каждом k-м шаге выделяют предварительный этап исследующего поиска. Целью этого этапа является выбор направления спуска путем исследования поведения целевой функции f(x) в окрестности точки xk-1, найденной на предыдущем шаге. В результате выполнения этапа исследующего поиска находится точка xk, для которой f(xk
) < f(xk-1
). Направление спуска, завершающего k-w. шаг поиска, определяется вектором xk
- xk-1
. Такая стратегия поиска, получила название метода Хука - Дживса.

Исследующий поиск 1

Вдоль координатных орт выполняют малые шаги. Т.е. локальное обследование точки х1
, для поиска лучшей чем х1
точки. Если шаг удачный то точку фиксируют и продолжают шаги из неё, если не удачный то делают шаг в противоположную сторону, если полученная точка снова хуже, то по этой оси шаг не делается.

Ускоряющий поиск

Выполняем единичный шаг вдоль направления , . Затем производим исследующий поиск в окрестности x3
, в надежде найти точку лучшую чем x2
.

Начальный этап

β = 10, ε = 10-4 – 10-8 , k = 1, х1
, h1
= … =hn
=0.1;

Основной этап

Шаг 1.

Выполнить ИП1 и отыскать т. х2
для которой .

Шаг 2.

Если ИП1 удачен т.е. найдена х2
, то перейти на шаг 3, иначе, но в то же время h<ε необходимо уменьшить шаг в β раз и вернуться на шаг 1. При h<ε остановиться х* = х1
.

Шаг 3.

Выполнить УП в пробную точку

Обозначить

В окрестности х3 попытаться ИП2 найти т. х4
«лучшую» чем х1
.

Шаг 4.

Если ИП2 удачен, то положить и вернуться на шаг 1.

Иначе: уменьшить шаг в β раз и вернуться на шаг 1.

Метод Хука-Дживса с одномерной минимизацией

Данный метод является аналогом метода циклического покооординатного спуска (ЦПС) с ускоряющим шагом. Начиная со второй итерации, устанавливается новый способ построения направления ускоряющего поиска. Организацию итерационной процедуры и отличие метода Хука-Дживса с одномерной минимизацией от метода ЦПС раскрывает представленное ниже пошаговое описание алгоритма.

Начальный этап

(1) Исходные данные - базовая точка x
, погрешность вычисления минимума e, матрица координатных направлений p
= {pi
}, i = 1,2,...,n
, где pi
= ei
- i-ый единичный орт в Rn
, т.е. ei
= 1
и ej
i
= 0
при всех i
¹
j
.

(2) Начальную точку x1
принять равной базовой точке: x1
= x
.

Основнй этап

Шаг 1.

Выполнить ЦПС из начальной точки x1
в конечную точку xn+1
, последовательно решая n-задач одномерной минимизации вдоль координатных направлений p
.

Шаг 2.

Проверить критерий окончания поиска:

(1) построить направление ускоряющего поиска d = xn+1
- x
;

(2) если ½½d
½½ <<
e
, остановиться.

Шаг 3.

Определить начальные условия для очередной итерации:

(1) найти оптимальный шаг a
n+1
в точку xn+2
= xn+1
+
a
n+1
d
;

(2) взять точку xn+2
за новую начальную точку x1
= xn+2
, а точку xn+1
за новую базовую x = xn+1
;

(3) вернуться на шаг 1.

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

Если f(x)
является дважды дифференци­руемой в Rn
, то эффективность процесса поиска точки х*
ее минимума можно повысить, используя информацию не толь­ко о градиенте этой функции, но и о ее матрице Гecce H(x). Алгоритмы такого поиска обычно относят к ме­тоду Ньютона. В простейшем варианте алгоритма на каждой k-й итерации целевая функция аппроксимируется в окрестно­сти точки xk-1
(на первой итерации в окрестности начальной точки х0) квадратичной функцией и затем определяется точка xk
минимума функции . На следующей, (k+
1)-й итерации строится новая квадратичная аппроксимация уже в окрестности точки xk
.

Начальный этап:

Выбрать x0
, e
, k
=1.

Основной этап

Шаг 1

(1) Строится Ньютоновское направление:- градиент в заданной точке, H – матрица Гессе

(2) Найти как результат решения системы уравнений

(3)

(4)

Шаг 3

Проверить КОП: если , то , иначе на Шаг 1.

Метод Зангвилла

Начальный этап

Выбрать константу остановки e
> 0
и начальную точку x
1
. Положить y1
= x1
, k
= j
=1, и перейти к основному этапу.

Основной этап

Шаг 1. Взять в качестве оптимальное решение задачи минимизации при и положить . Если , то перейти к шагу 4; в противном случае перейти к шагу 2.

Шаг 2. Положить и взять в качестве оптимальное решение задачи минимизации при . Положить , и перейти к шагу 3.

Шаг 3. Если , то остановиться; -- оптимальное решение. В противном случае взять в качестве оптимальное решение задачи минимизации при . Положить . Если , то заменить на и повторить шаг 3. В противном случае положить , заменить на и перейти к шагу 1.

Шаг 4. Положить , , заменить на , положить и перейти к шагу 1.

Метод Флетчера-Ривса

Метод сопряжённых направлений основан на свойствах векторов сопряженных относительно некоторой квадратной матрицы. Различие в способах построения системы сопряженных векторов, определяющих сопряжённые направления спуска, порождает несколько алгоритмов этого метода. В качестве матрицы сопряжений берётся матрица Гессе. Особенность алгоритмов метода сопряженных направле­ний состоит в том, что систему сопряженных векторов строят последовательно в процессе выполнения итераций, причем найденный на очередной, k-й итерации вектор pk определяет на этой итерации направление спуска. Для не квадратичных функций получаемые направления, в конце концов, перестают быть взаимносопряженными поэтому, как и в ДФП через n шагов вектор направления делают равным антиградиенту.

Начальный этап

Выбрать x1
, e, k=1.

Основной этап

Шаг 1.

Построить вектор pk:

Шаг 2.

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

Шаг 3.

Проверить КОП: .

Расчетное соотношение Флетчера-Ривса

Метод Пауэлла

Метод достаточно прост в реализации и обладает квадратичной сходимостью вблизи минимума. Стратегия метода базируется на свойстве квадратичных функций параллельного подпространства: если x1
минимум квадратичной функции по вектору p, а x2
минимум этой же функции по вектору параллельному предыдущему, то .

Первый вариант
алгоритма метода Пауэлла

Начальный этап

(1) Выбрать x1, e, k=1.

(2) Положить

Основной этап:

Шаг 1.

(1) Выполнить n переходов по векторам базиса :

(2) Определить новое направление и спуститься вдоль него:

Шаг 2.

Проверить КОП: если ,или k = n (для квадратичных функций) то прекратить поиск, иначе Шаг 3

Шаг 3.

Построить новую поисковую систему: из предыдущей системы удаляется первый вектор, а в конец добавляется вектор d.

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

Второй вариант
алгоритма метода Пауэлла

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

Изменение поисковой системы выглядит так: