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

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

Шаг 1. Найти очередное приближение х_k+1 к минимуму х* и проверить условие окончания поиска:

(1) x_k+1 = b_k - f '(b_k)*(b_k - a_k)/(f '(b_k) - f '(a_k));

(2) если ½f '(x_k+1)½ << e, то остановиться.

Шаг 2. Уменьшить интервал поиска минимума:

(1) если f '(x_k+1) > 0, то a_k+1 = ak, b_k+1 = x_k+1, в противном случае принять a_k+1 = x_k+1, b_k+1 = b_k;

(2) положить k = k + 1 и перейти на шаг 1.

Метод средней точки (метод Больцано)

Данный метод является вариантом метода деления интервала пополам. Последовательные сокращения интервала неопределенности производятся на основе оценки производной минимизируемой функции в центре текущего интервала.

Начальный этап. Для запуска метода необходимо:

(1) задать [a₁,b₁]- начальный интервал локализации минимума, на границах которого знаки производных различны, т.е. f'¢(a₁)f'¢(b₁)<0; e - малое положительное число;

(2) положить к=1 и перейти к основному этапу.

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

Шаг 1. Взять пробную точку х_k в центре текущего интервала и проверить критерий окончания поиска: (1) x_k = (a_k + b_k)/2; (2) если ½f'¢(x_k)½ ≤ e и L_k= ½b_k - a_k½≤ e, то остановиться (х_k = х* -аппроксимирующий минимум).

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

(1) Если f ¢(x_k) > 0, то положить a_k+1 = a_k и b_k+1 =x_k, в противном случае - a_k+1 =x_k, b_k+1 =b_k;

(2) заменить k на k+1 и вернуться на шаг 1.

Метод квадратичной интерполяции – экстраполяции

Данный метод относится к классу прямых методов, опирающихся на идею построения аппроксимирующего полинома второго порядка на основании информации о значениях функции в n+1 точке – узлах интерполяции.

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

1. Выбрать произвольную точку x¹ÎRⁿ

2. Задаться величиной шага h=0.001

3. Определить погрешность

4. Положить счётчик числа итераций равным 1, а также b=x¹

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

Шаг 1. Вычислить f_i в 3-х точках: a, b и с – центральной (b) и двух соседних: a=b-h, c=b+h. Затем, по формуле

(1)

или

(2)

найти аппроксимирующий минимум d

Шаг 2. Проверить критерий близости 2-х точек b и d

и

Если оба условия выполняются – фиксируем аппроксимирующий минимум

и останавливаемся. Если оба критерия не выполняются, полагаем b=d и возвращаемся на шаг 1.

Метод Пауэлла

Метод Пауэлла является одним из самых популярных методов. Эффективен как и рассмотренный ранее алгоритм квадратичной интерполяции – экстраполяции, если начальная точка x¹Îd(x*).

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

1. Выбрать ε₁, ε₂, h.

2. Взять 3 точки a, b, c на равных на равных интервалах. Предполагается, что сработал метод Свенна и получен интервал [a, b].

a=a;

c=b;

b=(a+c)/2;

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

1. Найти аппроксимирующий минимум на 1-й итерации по формуле:

на последующих итерациях по формуле:

2. Проверить критерии близости двух точек:

;

Если он выполняется, принять

и остановиться.

Если не выполняется, то из 2-х точек b и d выбрать «лучшую» - в которой наименьшее значение функции, обозначить её как b, а 2 соседние с ней – a и c. Далее рассмотреть 4 ситуации аналогично ЗС-2.

3. Положить k=k+1 и вернуться на шаг 1.

Метод Давидона

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

1. Выбрать ε, x⁰, p, α₁

2. Предполагается, что сработал метод Свенна и получен интервал [a, b].

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

1. Найти аппроксимирующий минимум, т.е. точку d по формулам:

2. Проверить КОП: если y`<sub>r</sub>≤ ε, то остановиться, х=a+α<sub>r</sub>p. Иначе: сократить ТИЛ: если y`_r <0, то [r,b], если y`_r >0, то [a,r].

Положить k=k+1 и вернуться на шаг 1.

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

Здесь имеет смысл упомянуть о поиске минимума функции многих переменных по направлению, так как этом используется во многих методах описываемых далее. Поиск минимума по направлению производится с использованием одномерных методов, т.е. сначала многомерная функция сводится к одномерной функции зависящей от смещения по заданному направлению из заданной точки, а потом для неё вызывается один из методов одномерной минимизации:

x – вектор от которого зависит функция

x0 – стартовая точка

p – направление

L – смещение по направлению

Метод Коши

Метод Коши относится к группе методов градиентного спуска. Градиентные методы – это методы, где на каждом шаге выбирается антиградиентное направление спуска.

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

Выбрать x1, e, k.

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

Шаг 1

Шаг 2

(1) Найти L как результат минимизации функции по направлению p.

(2)

Шаг 3

(1) Вычислить новое значение градиента

(2) Проверить КОП: если

, то , иначе на Шаг 1.

Метод Циклического покоординатного спуска

В данном методе на каждой итерации выполняется n(количество координат) одномерных минимизаций (спусков) вдоль единичных орт. Этот метод работает особенно хорошо, если линии равного уровня расположены вдоль координатный осей.

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

Выбрать x1, e, k=1, l=1.

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

Шаг 1

(1) В качестве направления p выбрать

, где ненулевая позиция имеет индекс l.

(2) Найти L как результат минимизации функции по направлению p.

(3)

(4) Если l<n то Шаг 2, иначе повторить Шаг 1 с l = l+1.

Шаг 2

(1) Вычислить

(2) Проверить КОП: если

, то , иначе , l=1 и на Шаг 1.

Метод параллельных касательных

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

Выбрать х1, ε = 10^-4 – 10^-8 установить k = 1;

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

Шаг 1.

Из точки x¹ выполнить антиградиентный в точку x²= x¹+α₁р¹, где p¹=-Ñу¹.

Шаг 2.

Последовательно выполнить две операции:

1. Антиградиентный спуск в точку x³.

2. Вычислить ускоряющее направление d=x³-x¹ и, не останавливаясь совершить ускоряющий шаг в точку x⁴=x³+α₃d.

Шаг 3.

Проверить КОП:

- остановиться x*=x⁴.

Иначе:

1. Обозначить x² как новую начальную x¹=x², а точку x⁴ как новую точку ускорения x²=x⁴.

Перейти к шагу 2.

Метод Гаусса-Зейделя

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

Выбрать х1, ε = 10^-4 – 10^-8 установить k = 1;

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

Шаг 1.

Выполнить серию одномерных поисков вдоль координатных орт

Шаг 2.

Вычислить ускоряющее направление и проверить КОП:

, если выполняется, минимум найден: x*=xⁿ⁺¹.

Иначе:

1. Выполнить ускоряющий шаг в новую точку хⁿ⁺²

2. Обозначить последнюю точку как начальную и вернуться на шаг 1.

Метод комплексов Бокса

Комплекс-метод предназначен для отыскания условного экстремума непрерывной целевой функции (1) в выпуклой допустимой области.

При использовании метода принимаются следующие предположения:

1. Задача поиска экстремума функционала (1) решается при наличии ограничений 1-го и 2-го рода.

2. Значения целевой функции и функций ограничений могут быть вычислены в любой точке допустимой области изменения независимых переменных.

3. Допустимая область выпукла.