Сокращение отрезка проводятся до тех пор, пока не выполнится неравенство n=|bn-an|≤ε.
2.6.2. Метод золотого сечения
Схема алгоритма метода золотого сечения, представленная на рис. 2.6-2, требует дополнения процедуры-функции f(x), в которой вычисляется значение целевой функции.
Рис.2.6-2. Алгоритм метода золотого сечения
В методе дихотомии используется функция f(x), унимодальная на отрезке [a;b] [3].В основу метода положено разбиение отрезка неопределенности [a;b] в соотношении золотого сечения:
x a 0.382(b a) |
|
x1 a k1(b a) |
|
1 |
или |
|
|
x2 a 0.618(b a) |
x2 |
a k2(b a) |
|
,
где k1=0.382, а k2=0.618.
37
Сравнение значений функции в точках х1 и х2 позволяет, в силу унимодальности функции f(x), отбросить ту часть отрезка, где заведомо нет точки минимума. Известно, что и точка х1и точка х2дваждыосуществляет золотое сечение на отрезке[a;b]. Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.
После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Сокращение отрезка проводятся до тех пор, пока не выполнится неравенство n=|bn-an|≤ε.
2.6.3. Метод средней точки
Схема алгоритма метода средней точки, представленная на рис. 2.6-3, требует дополнения процедуры-функции f(x), в которой вычисляется значение целевой функции.
Рис. 2.6-3. Алгоритм метода средней точки Алгоритм метода средней точки [2] основан на сокращении длины
текущего отрезка неопределенности [a;b], путем отбрасывания той половины отрезка, которая не содержит точки минимума. В основу метода положено основное свойство унимодальности функции, то есть, для того чтобы на отрезке [a;b] существовал минимум, необходимо, чтобы первая производная на нем была неубывающей. Выбрав середину текущего отрезка c=(ai+bi)/2),
принимается решение: если |
|
f (c) 0 , то в следствии унимодальности |
|
|
38 |
функции, точка минимума не может лежать левее точки с, переопределяется
левая граница отрезка(ai+1=с), а если |
f (c) 0 |
, то минимум не может лежать |
|
правее точки с и переопределяется правая граница отрезка (bi+1=c). В случае
если |
f (c) 0 |
за точку минимума принимают значение с. |
|
Сокращение отрезка проводятся до тех пор, пока не выполнится неравенство n=|bn-an|≤ε.
После каждой итерации длина отрезка неопределенности сокращается в 2 раза, однако метод имеет существенный недостаток –необходимость вычисление производной от целевой функции.
2.7.Алгоритмы методов многомерной оптимизации
Итерационные методы, применяемые для решения задач минимизации функции нескольких переменных, относятся к классу методов спуска[3]. В них каждая итерация(k) приводит к уменьшению значения целевой функции:
Q(xk+1,yk+1)<Q(xk,yk), для всех k 0.
В качестве начальной точка (x0, y0)выбирается точка, принадлежащая области допустимых значений функции.
Поскольку направление спуска совпадает с направлением вектора антиградиента, то координаты очередной точки траектории спуска вычисляются по формулам:
x |
|
x |
|
λ |
|
|
Q |
|
|
|
; |
|
|
k 1 |
k |
k |
x |
x ,y |
|
||||||||
|
|
|
|
|
|
|
|
k |
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
y |
|
y |
|
λ |
|
|
Q |
|
|
|
|
|
. |
k 1 |
k |
k |
y |
x ,y |
|
||||||||
|
|
|
|
|
|
|
|
|
k |
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
где k - шаг спуска. Способ |
задания шага спуска k определяется |
|||||||||||||
конкретным методом. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Итерации повторяются до тех пор пока не выполняется условие |
||||||||||||||
окончания цикла: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Q |
|
x |
|
,y |
| ε; |
и |
| |
Q |
|
x |
|
,y |
| ε. |
|
|
|
|
|||||||||||
x |
|
|
y |
|
|
|||||||||
|
|
k 1 |
k 1 |
|
|
|
k 1 |
k 1 |
||||||
Схема алгоритма метода градиентного спуска, представленная на рис. 2.7-1, требует дополнения следующих процедур-функций:
Q(x,y) – целевая функции;
g1(x,y) – частная производная по х;
g2(x,y)– частная производная по y.
39
Рис.2.7-1. Алгоритм методов наискорейшего спуска
40
Схемы алгоритмов выбора шага спуска(λ) выбирается в зависимости от используемого метода (рис.2.7-2, рис.2.7-3).
Рис. 2.7-2. Выбор шага в методе ГДШ В методе градиентного спуска с дроблением шага выбор шага спуска
осуществляется следующим образом.
Начальный шаг спуска 0, как правило, задается равным 0,5. На каждой k-й итерации для выбора шага kпроизводится проверка условия:
|
|
|
) Q(x |
|
λ |
p |
|
|
λ |
s |
) |
λ |
|
2 |
s |
2 |
|
Q(x |
,y |
|
|
,y |
|
k |
(p |
). |
|||||||||
k |
k |
k |
|
|
|
||||||||||||
k |
|
|
k |
k |
|
k |
k |
|
2 |
k |
k |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
где p |
Q(x,y) x xk |
s |
|
Q(x,y) x xk |
||
|
|
|
|
|||
k |
x |
y yk |
k |
|
y |
y yk . |
|
|
|
||||
|
|
|
|
|
41 |
|
Если условие выбора шага не выполняется, то шаг полагается равнымk = k/2 и проверка условия возобновляется. При выполнении условия выбора шага его значение передается в процедуру вычисления координат очередной точки спуска.
В методах наискорейшего спуска из выбранной точки (x0,y0) спуск осуществляют в направлении антиградиента до тех пор, пока не будет достигнуто минимальное значение целевой функции Q(x, y) вдоль луча, направление которого определяет вектор антиградиент.
Если выразить целевую функцию Q(x, y) через шаг , то на определенном шаге, при фиксированных значенияхxи y, целевую функцию можно представить как функцию одной переменной:
(λ) Q(x |
k |
λ |
p |
,y |
k |
λ |
s |
). |
|
k |
k |
|
k |
k |
|
Величина шага на каждой итерации определяется из условия минимума функции (λ) :
(λ*)
= min(
( ))
k = *(xk, yk), |
>0. |
Таким образом, выбор шага k на каждой итерации предполагает решение задачи одномерной оптимизации. По способу решения этой задачи различают два метода наискорейшего спуска [3]:
-аналитический метод (НСА);
-численный метод (НСЧ).
В методе НСА[3] формулу для вычисления значения текущего шага спуска получают аналитически перед компьютерной реализацией алгоритма
из условия |
'(λ) 0 . |
В методе НСЧ величину k находят на отрезке [0;1] c заданной точностью, используя один из методов одномерной оптимизации, например, метода золотого сечения (рис. 2.7-3). В качестве целевой функции
используется |
(λ) |
. |
|
|
42
Рис. 2.7-3. Выбор шага в методе НСЧ методом золотого сечения
43