Методы оптимизации

Содержание

 

 

 

1. Теоретическая часть

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

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

, .

 

1.1. Стратегия поиска методом  Ньютона

Стратегия метода Ньютона состоит в построении последовательности точек , , таких, что ,

Точки последовательности вычисляются по правилу

, (1)

где точка задается пользователем, а направление спуска определяется для каждого значения по формуле

. (2)

Выбор по формуле (2) гарантирует выполнение требования при условии, что . Формула (2) получена из следующих соображений:

1. Функция  аппроксимируется в каждой точке последовательности квадратичной функцией .

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

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

 

1.2. Алгоритм метода Ньютона

Шаг 1. Задать , , , – предельное число итераций, найти градиент и матрицу Гессе .

Шаг 2. Положить .

Шаг 3. Вычислить .

Шаг 4. Проверить выполнение критерия окончания :

а) если неравенство выполнено, то расчет окончен, ;

б) если нет, то перейти к шагу 5.

Шаг 5. Проверить выполнение неравенства :

а) если неравенство выполнено, то расчет окончен: ;

б) если нет, то перейти к шагу 6.

Шаг 6. Вычислить матрицу .

Шаг 7. Вычислить .

Шаг 8. Проверить выполнение условия :

а) если , то перейти к шагу 9;

б) если нет, то перейти к шагу 10, положив .

Шаг 9. Определить .

Шаг 10. Найти точку ,

положив , если ,

или выбрав из условия , если .

Шаг 11. Проверить выполнение условий:

, :

а) если оба условия выполнены при текущем значении и , то расчет окончен, ;

б) в противном случае положить

и перейти к шагу 3.

 

1.3. Стратегия поиска методом Ньютона - Рафсона

Стратегия метода Ньютона – Рафсона состоит в построении последовательности точек , , таких, что ,

Точки последовательности вычисляются по правилу

, (3)

где точка задается пользователем, а величина шага определяется из условия

. (4)

Задача (4) может решаться либо аналитически с использованием необходимого условия минимума с последующей проверкой достаточного условия , либо численно как задача

,

где интервал задается пользователем.

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

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

Построение последовательности заканчивается в точке , для которой , где – заданное число, или при (М – предельное число итераций), или при двукратном одновременном выполнении двух неравенств , – малое положительное число.

Вопрос о том, может ли точка рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования.

1.4. Алгоритм метода Ньютона – Рафсона

Шаг 1. Задать , , , – предельное число итераций, найти градиент и матрицу Гессе .

Шаг 2. Положить .

Шаг 3. Вычислить .

Шаг 4. Проверить выполнение критерия окончания :

а) если неравенство выполнено, то расчет окончен, ;

б) если нет, то перейти к шагу 5.

Шаг 5. Проверить выполнение неравенства :

а) если неравенство выполнено, то расчет окончен: ;

б) если нет, то перейти к шагу 6.

Шаг 6. Вычислить матрицу .

Шаг 7. Вычислить .

Шаг 8. Проверить выполнение условия :

а) если условие выполняется, то найти ;

б) если нет, то положить .

Шаг 9. Определить .

Шаг 10. Найти шаг из условия .

Шаг 11. Вычислить .

Шаг 12. Проверить выполнение неравенств:

, :

а) если оба условия выполнены при текущем значении и , то расчет окончен, ;

б) в противном случае положить и перейти к шагу 3.

1.5. Стратегия поиска методом  наискорейшего градиентного спуска

Стратегия решения задачи состоит в построении последовательности точек , , таких, что , Точки последовательности вычисляются по правилу

(2)

где точка задается пользователем; величина шага определяется для каждого значения из условия

. (3)

Решение задачи (3) может осуществляться с использованием необходимого условия минимума с последующей проверкой достаточного условия минимума . Такой путь может быть использован либо при достаточно простой минимизируемой функции , либо при предварительной аппроксимации достаточно сложной функции полиномом (как правило, второй или третьей степени), и тогда условие замещается условием , а условие – условием .

Другой путь решения задачи (3) связан с использованием численных методов, когда ищется . Границы интервала задаются пользователем. При этом степень близости найденного значения к оптимальному значению , удовлетворяющему условиям , зависит от задания интервала и точности методов одномерной минимизации.

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

 

1.6. Алгоритм метода наискорейшего  градиентного спуска

Шаг 1. Задать , , , , – предельное число итераций.

Найти градиент функции в произвольной точке .

Шаг 2. Положить .

Шаг 3. Вычислить .

Шаг 4. Проверить выполнение критерия окончания :

а) если критерий выполнен, расчет закончен, ;

б) если критерий не выполнен, то перейти к шагу 5.

Шаг 5. Проверить выполнение неравенства :

а) если неравенство выполнено, то расчет окончен: ;

б) если нет, то перейти к шагу 6.

Шаг 6. Вычислить величину шага из условия

.

Шаг 7. Вычислить .

Шаг 8. Проверить выполнение условий

:

а) если оба условия выполнены при текущем значении и , то расчет окончен, ;

б) если хотя бы одно из условий не выполнено, положить и перейти к шагу 3.

 

2. Постановка задачи

Исследовать численный метод поиска минимума функции многих переменных.

Функция: .

Тестовая функция: Химмельблау

.

Использовать методы:

а) Ньютона;

б) Ньютона-Рафсона с использованием дихотомии и «золотого сечения»;

г) Градиентного спуска с дроблением шага.

Точность вычислений: , , .

 

3. Расчетная часть

3.1. Алгоритм решения задачи

 

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

Блок – схемы методов одномерной минимизации

    

                                            а)                                                            б)      

а) метод дихотомии (diho(xk,dk)); б) метод золотого сечения (zoloto(xk,dk))

Блок – схема метода Ньютона

Блок – схема метода Ньютона - Рафсона

 

Блок – схема метода наискорейшего градиентного спуска

 

3.2. Решение задачи в MathCAD

Выполняем задачу для тестовой функции Химмельблау.

 

 

 

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

Выполняем задачу для заданной функции.

 

 

 

3. Экспериментальная часть

Изменяем значение .

 

Вывод: полученные результаты говорят о том, что при уменьшении решение уточняется.

 

Литература

1. Заварыкин В.М. и др. Численные методы: Учеб. Пособие для студентов пед. ин-в./ В.М. Заварыкин, В.Г. Житомирский, М.П. Лапчик. – М.: Просвещение, 1990.
2. Вычислительная математика: Учеб. Пособие для техникумов/ Данилина Н.И., Дубровская Н.С., Кваша О.П., Смирнов Г.Л. – М.: Высш. шк., 1985.
3. Амосов А.А, Дубянский Ю.А., Копченов Н.В. Вычислительные методы для инженеров: Учеб. пособие. — М.: Высш. шк., 1994.
4. Кирьянов Д.В. Самоучитель MathCAD 2001. – СПб.: БХВ –Петербург, 2001.
5. Макаров Е.Г. Инженерные расчеты в MathCAD. Учебный курс. – СПб.: Питер, 2005.
6. Дьяконов В.П. MathCAD 2001. Специальный справочник. – СПб.: Питер, 2002.