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

Золотое сечение, открытое Евклидом, состоит в разбиении интервала [a,b] на 2 части точкой x₁ таким образом, чтобы отношение длины всего отрезка к большей части было равно отношению большей части к меньшей.

Коэффициент дробления отрезка [ a, b ]:

x₁=b+(1-k)(b-a)

x₂=b+k(b-a)

a x₁ x₂ b

 

 

Алгоритм:

1) вычисляем значения x₁, x₂

2) вычисляем значения f(x₁), f(x₂)

3) проверяем условия:

- если f(x₁)≤ f(x₂), то для дальнейшего деления оставляют интервал [a,x₂]

- если f(x₁)> f(x₂), то для дальнейшего деления оставляют интервал [x₁,b]

Процесс деления продолжают до тех пор, пока длина интервала неопределенности не станет меньше заданной точности ε.Замечание: x₁ производит золотое сечение интервала [a,x₂], x₂ – золотое сечение отрезка [x₁,b].

14. Многомерные задачи оптимизации.

Пусть f(x₁, x₂,…, x_n) – целевая функция. Задача поиска максимума этой функции сводится к минимизации функции - f(x₁, x₂,…, x_n), поэтому будем рассматривать задачу поиска минимума. Наибольшие трудности поиска минимума f(x) возникают, когда размерность n вектора x велика, поэтому важнейшей проблемой является уменьшение размерности вектора целевой функции на этапе построения математической модели. В модели следует сохранить только те x_i, которые сильнее других влияют на изменение целевой функции.

Линиями уровня f(x₁, x₂) называют семейство линий плоскости R², на которых функция принимает постоянное значение.

Неявным уравнением линии уровня является уравнение вида f(x₁, x₂)=с.

Если функция f(x) имеет единственную точку минимума x^*(x₁^*, x₂^*), то функция называется мономодальной и линии уровня имеют следующий вид: