«Методы оптимизации» (стр. 1 из 4)

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

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

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

Метод Свенна

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

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

(1) задать произвольную начальную точку x₀ÎRⁿ

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

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

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

Шаг 2. Вычислить f_k в точках x_k₊₁=x_k+h_k, где k=2,3,4,…,m-1; h_k=2h_k_-1 – движение с удвоением шага, до тех пор, пока не придём в точку x_m такую, что f(x_m)<f(x_m_-1).

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

a₁=x_m_-2

b₁=x_m

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

Метод золотого сечения – это процедура одномерного поиска минимума на интервале [a₁,b₁] или [0,1]. На каждом шаге пробная точка l_k или m_k внутри текущего интервала локализации [a_k,b_k] делит его в отношении, постоянном для всех интервалов

- золотое сечение. Можно показать, что

, откуда

, следовательно

, значит

. Одним из корней этого уравнения является t₁=0,618 – первое золотое число. Отметим, что t₁²=0,618²=0,382 – второе золотое число. Следует отметить, что в методе золотого сечения имеет место правило симметрии (эквидистантности) точек относительно концов интервала, а также правило одного вычисления, т.е. на каждой итерации требуется одно и только одно новое вычисление (кроме первой итерации), т.к. точки на соседних итерациях совпадают.

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

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

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

(2) Вычислить стартовые точки l₁=a₁+0,382L₁, m₁=a₁+0,618L₁ (следует отметить, что золотые числа следует вычислять точно)

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

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

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

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

a_k+1=a_k

b_k+1=m_k

m_k+1=l_k

l_k=a_k+1+0,382L_k+1

иначе

a_k+1=l_k

b_k+1=b_k

l_k+1=m_k

m_k=a_k+1+0,618L_k+1

(2) Положить k=k+1, L_k+1=|b_k+1-a_k+1|

Шаг 2. Проверить критерий окончания поиска: если |a_k₊₁-b_k₊₁|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как

. Иначе вернуться на шаг 1.

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

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

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

(5) Вычислить стартовые точки l₁=a₁+0,382L₁, m₁=a₁+0,618L₁ (следует отметить, что золотые числа следует вычислять точно)

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

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

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

(1) Если (x₁<x₂) и (f(x₁)<f(x₂)) то b=x₂;

(2) Если (x₁<x₂) и (f(x₁)>=f(x₂)) то a=x₁;

(3) Если (x₁>x₂) и (f(x₁)<f(x₂)) a=x₂;

(4) Если (x₁>x₂) и (f(x₁)>=f(x₂)) b=x₁;

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

. Иначе вернуться на шаг 1.

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

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

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

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

(1) Задать константу e, начальный интервал [a₁, b₁], длину конечного интервала L_n и определить число n так, чтобы выполнялось условие F_n > (b₁ - a₁)/L_n.

(2) Взять две пробные точки l₁ = a₁ + (F_n-2/F_n)(b₁ - a₁) и m₁ = a₁ + (F_n-1/F_n)(b₁-a₁). Положить k = 1.

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

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

(1) Если f(l_k) < f(m_k), то положить a_k+1 = a_k, b_k+1 = m_k,m_k+1 =l_k и вычислить новую точку l_k+1 = a_k+1 + (F_n-k-2/F_n-k)L_k+1, где L_k+1 = b_k+1 - a_k+1; перейти на шаг 2.

(2) Если f(l_k)>> f(m_k),то положить a_k+1 =l_k, b_k+1 = b_k, l_k+1 = m_k и вычислить m_k+1 = a_k+1 + (F_n-k-1/F_n-k) L_k+1.

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

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

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

(1) Положить m_k = l_k + e.

(2) Если f(l_k) > f(m_k), то x^(*) = (l_k + b_k)/2. В противном случае - x^(*) = (a_k + m_k)/2.

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

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

(2) Выбрать одну пробную точку

. Положить

k = 1.

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

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

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

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

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

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

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

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

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

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