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

Золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка.

Золотое сечение отрезка [a, b] производится двумя точками и , где .

Точки x₁ и x₂ расположены симметрично относительно середины отрезка и выполняется

и .

Точка x₁ в свою очередь производит золотое сечение отрезка [a, x₂]. Аналогично точка x₂ производит золотое сечение отрезка [x₁, b].

Опираясь на это свойство золотого сечения, предложен следующий метод минимизации унимодальной функции F(x) на отрезке [a, b]. Его суть - деление интервала поиска минимума по правилу золотого сечения, вычисление значения F(x) в точках деления, сравнение значений и отбрасывание той части интервала, на которой заведомо отсутствует минимум. Точка x₁ производит золотое сечение [a, x₂], точка x₂ - золотое сечение отрезка [x₁, b]. Поэтому на оставшемся интервале нужно определить одну точку, производящую золотое сечение. Процесс деления продолжают до тех пор, пока длина интервала неопределенности не станет меньше заданной точности . На каждом шаге длина нового интервала неопределенности равна 0,618 длины старого интервала и на каждом шаге вычисляется лишь одно значение F(x), а не два, как в методе деления отрезка пополам.

Оптимизация полимодальных одномерных целевых функций. Метод ломаных

Метод ломаных разработан для оптимизации одномерных полимодальных функций. Функция J(U) называется липшицируемой на [a, b], если существует такое число L (константа Липшица), что для любых x, y из [a, b] верно неравенство |f(x)-f(y)| ≤ L·|x-y|. Т.е. постоянная Липшица - положительное число, равное или большее модуля максимального значения производной J^’(U) на [a, b].

Необходимо найти значение управляемого параметра U, доставляющее глобальный экстремум-минимум нелинейной целевой функции с заданной абсолютной погрешностью при заданных ограничениях на управляемый параметр A U  B. Выбирается произвольно начальная поисковая точка U₀ [A,B] и составляется ломаная функция

g (U,U₀)=J(U₀)−L(U-U₀).

Очевидно, функция g(U,U₀) состоит из двух отрезков и расположена ниже J(U), только в точке U = U₀, т.е. g(U₀) = J(U₀). Затем вводится ломанная огибающая по максимуму Р₀(U₁) = g(U,U₀). Следующая поисковая точка U₁ определяется условием P₀ (U₁)= min P₀(U). Для точки U₁ опять рассматривается ломаная g(U,U₁)=J(U₁) − L , и вводится огибающая по максимуму P₁(U) = max {P₀(U), g(U,U₁)} (ломаная FЕСВ на рис.). Следующая поисковая точка U₂ определяется опять по условию P₁(U₂) = min P₁(U) Однако, это будет точка пересечения P₀(U) = g(U,U₀) и g(U,U₁). Значение U₂, следовательно, определяется из уравнения g(U,U₀)= g(U,U₁) и равно

,

Рисунок 1 Метод ломаных

Если J(U₀) > J(U₁), то , то есть следующая поисковая точка смещается относительно середины отрезка в сторону минимума J(U). Затем вводятся ломаная функция для точки U₂ g(U₁,U₂) = J(U₂) −L и огибающая по максимуму P₂(U) = max {P₁(U), g(U,U₂)}. Следующая поисковая точка определяется по условию P₂(U₃) = min P₂(U). Однако в данном случае точек минимума будет две - это точки пересечения g(U,U₂) с P₁(U)

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

, ,

соответствующая меньшему значению целевой функции.

Процесс поиска заканчивается по достижению заданной точности ξ вычисления минимума целевой функции J^*, оцениваемой очевидным графическим соотношением . Решение получено с абсолютной погрешностью вычисления экстремума-минимума целевой функции ξ, если