Методические указания к лабораторным работам Чебоксары 2006 (стр. 2 из 4)
14. Насколько уменьшается длина интервала в методе дихотомии?
15. Выведите зависимость длины интервала от количества вычислений значения функции.
16. К каким функциям применим метод дихотомии с производной?
17. Обеспечена ли глобальная сходимость для метода дихотомии?
18. Для каких функций применяется кубическая интерполяция?
19. Как применяется кубическая интерполяция для нахождения минимума, для функций нескольких переменных?
20. В каких алгоритмах применяются методы Голдстейна, а в каких метод Вольфе–Пауэлла?
Задания к лабораторной работе
1. Найти минимум функции:
а) F(x) = 2N(x – N)2 + 16(x – N);
б) F(x) = 40 + 90(x – N)2;
в)
с точностями EPS = 1E–3, 1E–10, 1E–15.
2. Построить график функции N = 3 на терминале вблизи точки минимума.
Отчет о работе
1. Титульный лист.
2. Задания к лабораторной работе.
3. Алгоритмы численного нахождения минимума.
4. График зависимостей количества итерации от точности решения.
5. Краткий анализ результата поиска минимума указанных выше функций.
6. Вывод по работе.
Список методов
1. Метод Ньютона.
2. Метод секущих.
3. Метод Фибоначчи.
4. Метод золотого сечения.
5. Квадратичная интерполяция.
6. Метод дихотомии.
7. Метод дихотомии с производной.
8. Кубическая интерполяция.
9. Метод Голдстейна.
10. Метод Вольфе–Пауэлла.
Выбор метода решения
1. Порядковый номер студента в журнале по модулю 10.
2. Номер метода +5 по модулю 10.
Список рекомендуемой литературы
1. Карманов В.Г. Математическое программирование. М.: Наука, 1960.
2. Банди Б. Метод оптимизации: Вводный курс: Пер. с англ. М.: Радио и связь, 1988.
Лабораторная работа 2
Методы прямого поиска оптимума
для функции N переменных
Алгоритмы методов прямого поиска оптимума
для функции N переменных
А. Метод покоординатного спуска.
1. Выбрать точку x0, k = 0.
2. На k-й итерации: из точки xk произвести поиск минимума вдоль направления оси x1 и найти точку xk1. Произвести поиск из точки xk1 в направлении к оси x2 и определить точку xk2. Выполнить эту процедуру по всем координатам.
Б. Симплексный метод.
1. Выбрать базовую точку x0. Задать масштабный множитель a. Вычислить
.Определим остальные вершины симплекса:
i, j =1, 2, …N.2. На k-й итерации: определить
, где x j - вершина с наибольшим значением функции. Отразить x j относительно xc. x = 2xc – x j;3. Тест на остановку: если выполнено, то конец. Если не выполнено условие сходимости или некоторая вершина не исключается на протяжении более чем M = 1,65N + 0,05N 2 итерации, то необходимо уменьшить размеры симплекса, построить новый симплекс, выбрав в качестве базовой точку, которой соответствует минимальное значение целевой функции, и перейти к 2.
В. Метод Нелдера–Мида
1. Выбрать x1, …, xN+1, a, b, g. Вычислить f1, …, fN+1.
2. Найти xh, xg, xz, fh, fg, fz; fh - наибольшее, fg - следующее за ним, fz - наименьшее значение функции.
3. Найти
4. Найти xr, fr, отразив точку xh относительно x0:
xr = (1 + a) x0 – axh.
5. Если fr < fz, то производим растяжение симплекса – находим xe = gxr + (t – g) x0, fe = f(xe).
6. Если fe < fz, то xh := xe.
Проверка на сходимость. Если сходимость достигнута, то конец. В противном случае перейти на шаг 2.
7. Если fe ≥ fz, то xh := xr.
Проверка на сходимость. Если сходимость достигнута, то конец. B противном случае перейти на шаг 3.
8. Если fr > fz, нo fr £ fg, то xh := xr.
Проверка на сходимость. Если сходимость не достигнута, то возвратиться на шаг 2.
9. Если fr > fz и fr > fg, то перейти на шаг 10.
10. Если fr > fh, то перейти к 11.
Если fr < fh, то xh := xr и fh := fr. Перейти к 11.
11. Так как fr > fh, то переходим к шагу сжатия:
xc = b xh + (1 – b)x0.
12. Если fc < fh, то xh := xc, и если сходимость не достигнута, то возвратиться на шаг 2.
13. Если fc > fh, то перейти на шаг 14.
14. Уменьшить размерность симплекса xi := (xi + xz)/2. Вычислить fi для i = 1, N + 1. Проверка на сходимость. Если она не достигнута, возвратиться на шаг 3.Г. Метод Хука–Дживса:
1. Определить начальную точку x0, приращение Di, i = 1, N.Коэффициент уменьшения шага a > 1, параметр окончания поиска E.
2. Провести исследовательский поиск.
3. Если исследовательский поиск удачный (найдена точка с меньшим значением целевой функции), перейти к 5. Иначе перейти к 4.
4. Тест на остановку: если выполнено, то конец. Иначе: уменьшить приращение.
, перейти к шагу 2.5. Провести поиск по образцу
xp(K+1) = xK + (xK – xK–1).
6. Провести исследующий поиск, используя xpK+1 в качестве базовой точки. Пусть xK+1 - полученная в результате точка.
7). Если выполняется неравенство f(xK+1) < f(xK), то положить xK–1 = xK и xK= xK+1. Перейти к 5. Иначе: перейти к 4.
Основные обозначения:
xK - текущая базовая точка;
xK–1 - предыдущая базовая точка;
xpK+1 - точка, построенная при движении по образцу;
xK+1 - следующая (новая) базовая точка.
Критерии проверки сходимости
1.
; 
; s < e (метод Нелдера–Мида).2. h < e (метод Хука–Дживса), h–шаг.
Контрольные вопросы и задания
1. Назовите достоинства и недостатки прямых методов поиска для функций и переменных.
2. В чем преимущество метода Хука–Дживса по сравнению с методом покоординатного спуска?
3. В каких случаях удобно использовать симплексный метод?
4. Обеспечивают ли эти методы глобальную сходимость?
5. Для решения каких задач целесообразно использовать метод Нелдера–Мида?
6. Дайте геометрическую иллюстрацию всех четырех методов оптимизации.
7. Какой из приведенных методов целесообразно использовать для оптимизации технологических процессов в условиях производства?
Задание к лабораторной работе
Найти минимум функций:
1) F(x1, x2) = N(x2 – x12)2 + (N – x1)2
2) F(x1, x2, x3, x4) = (x1 + Nx2)2 + N(x3 – x4)2 + (x2 – Nx3)4 +
+N(x1 – x4)4 с точностями EPS=1E-3, 1E-5, 1E-10, 1E-15.
Отчет о работе
1. Титульный лист.
2. Задание к лабораторной работе.
3. Алгоритмы численного нахождения минимума.
4. Графики зависимости количества итерации от точности решения.
5. Краткий анализ результатов поиска минимума указанных выше функций.
6. Вывод по работе.
Список методов
1. Метод покоординатного спуска.
2. Симплекс метод.
3. Метод Нелдера–Мида.
4. Метод Хука–Дживса.
Выбор метода решения
1. Порядковый номер студента в журнале по модулю 4.
2. Номер первого метода +5 по модулю 4.
Список рекомендуемой литературы
1. Карманов В.Г. Математическое программирование. М.: Наука, 1980.
2. Банди Б. Метод оптимизации: Вводный курс: Пер. с англ. М.: Радио и связь, 1988.
Лабораторная работа 3
Численные методы для оптимизации
дифференцируемых функций
Описание алгоритмов
А. Алгоритм градиента с заранее заданным шагом.
1. Выбрать начальную точку x0 и число l > 0. Положить k = 0.
2. На k-й итерации
, где Ñk; lk > 0.3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k¬k+1 и возвратиться к 2.
Б. Алгоритм наискорейшего спуска.