Метод золотого сечения
Сравнение
различных процедур
линейного поиска
естественно
производить
в соответствии
со следующим
коэффициентом
сжатия (длина
интервала неопределенности
после k выполненных
наблюдений)/(длина
интервала неопределенности
до выполнения
наблюдений).
Очевидно, что
более эффективные
схемы соответствуют
меньшим значениям
коэффициента
сжатия. В дихотомическом
поиске значение
коэффициента
приблизительно
равно (0.5)^(k/2). Метод
золотого сечения
является более
эффективным,
для него значение
коэффициента
сжатия равно
(0.618)^(k-1).
Рассмотрим
такое симметричное
расположение
точек x1 и x2 на отрезке
[a,b], при котором
одна из них
становится
пробной точкой
и на новом отрезке,
полученном
после исключения
части исходного
отрезка. Использование
таких точек
позволяет, кроме
первой, ограничиться
определением
только одного
значения f(x), так
как другое значение
уже найдено
на одной из
предыдущих итераций.
Для определения
точек x1 и х2 рассмотрим
сначала отрезок
[0,1] и для определенности
положим, что
при уменьшении
исключается
правая часть
этого отрезка.
Пусть х2=q, тогда
симметрично
расположенная
точка x1=1-q. Пробная
точка х1 отрезка
[0,1] перейдет в пробную
точку х1'=1-q нового
отрезка [1,q]. Чтобы
точки x2=q и x2'=1-q делили
отрезоки [0,1] и
[0,q] в одном и том
же отношении,
должно выполняться
равенство
1/q = q/(1-q) или q^2 = 1-q
откуда находим
положительное
значение q = 0.61803...
Таким образом
для произвольного
отрезка [a,b] выражения
для пробных точек
примут вид:
x1=a+(1-q)(b-a) x2=a+q*(b-a)
Алгоритм метода
золотого сечения
Алгоритм метода
золотого сечения
для минимизации
строго квазивыпуклой
фунции на интервале
[a1,b1].
Начальный
этап. Выбрать
допустимую
конечную длину
интервала неопределенности
l>0. Пусть [a1,b1] - начальный
интервал неопределенности.
Положить p1=a1+(1-0.618)(b1-a1)
и q1=a1+0.618(b1-a1). Вычислить
F(p1) и F(q1), положить
k=1 и перейти к
основному этапу.
Основной этап.
Шаг 1. Если bk-ak < l,
то остановиться;
точка минимума
принадлежит
интервалу [ak,bk].
В противном
если F(pk)>F(qk), то перейти
к шагу 2, а если
F(pk)<=F(qk),то к шагу
3.
Шаг2. Положить
a[k+1]=pk, b[k+1]=bk, p[k+1]=qk, q[k+1]=a[k+1]+0.618(b[k+1]-a[k+1]). Вычислить
F(q[k+1]) и перейти к
шагу 4.
Шаг3. Положить
a[k+1]=ak, b[k+1]=qk,q[k+1]=pk, p[k+1]=a[k+1]+(1-0.618)(b[k+1]-a[k+1]).
Вычислить F(p[k+1])
и перейти к шагу
4. Шаг4. Заменить
k на k+1 и перейти
к шагу 1.
