Методические указания к лабораторным работам Чебоксары 2006 (стр. 3 из 4)
1. Выбрать начальную точку x0. Положить k = 0.
2. На k-й итерации dk = – Ñf(xk). Найти такое число lk, что f(xk+ lkdk) = min{f(xk+ ldk)}. Положить xk+1 = xk + lkdk;
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k¬k+1 и возвратиться к 2.
В. Алгоритм сопряженного градиента для квадратичных функций.
1. Выбрать начальную точку x0. Определить g = Ñq(x0) = Ax0 + b.
Положить d0 = – g0, k = 0.
2. На k-й итерации определить
, xk+1 = xk + lkdk, gk+1 = Ñq(xk+1), 
, dk = – gkH + bkdk.3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k¬k+1 и возвратиться к 2.
Г. Алгоритм Фленча–Ривза.
1. Выбрать начальную точку x0. Положить d0 = – Ñf(x0), K = 0.
2. На K-й итерации выбрать l, минимизирующую функцию g(l)= =f(xKK + ld), положить xK+1 = xK + lKdK;
;dK = – Ñf(xK+1)+ bKdK.
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k¬k+1 и возвратиться к 2.
Д. Алгоритм метода Ньютона, модифицированного метода Ньютона, метода Марквардта.
1. Выбрать начальную точку x0, K = 0.
2. На K-й итерации для метода Ньютона - xK+1 = xK – [Ñ2f(xK)]–1Ñf(xK);
для модифицированного метода Ньютона xK+1 = xK – lK[Ñ2f(xK)]–1Ñf(xK);
для метода Марквардта xK+1 = xK –[mI + Ñ2f(xK)]2Ñf(xK), где m0 = 104; mK=m0/K.
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k¬k+1 и возвратиться к 2.
Е. Алгоритм Давида–Флетчера–Пауэлла (ДФП).
1. Выбрать начальную точку x0; положить Н0=I, где I- единичная матрица; K=0;
2. На K-й итерации dK = – HKÑf(xK). Найти такое l ³ 0, чтобы
f(xK + lKdK) = min{f(xK + ldK)}.
Положить xK+1 = xK + lKdK; sK = xK+1 – xK; gK = Ñf(xK+1) – Ñf(xK);
.3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k¬k+1 и возвратиться к 2.
Ж. Алгоритм Бройдена–Флетчера–Гольдфарба–Шанно (БФГШ).
1. Выбрать начальную точку x0. Положить Н = I, где I- единичная матрица; K = 0.
2. На K-й итерации dK = – HKÑf(xK).
Найти такое l ³ 0, чтобы f(xK + lKdK) = min{f(xK + ldK)}. Положить xK+1 = xK + lKdK; sK = xK+1 – xK; gK = Ñf(xK+1) – Ñf(xK),
.3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k¬k+1 и возвратиться к 2.
Наиболее употребительные критерии для определения
окончания процесса вычислений
1.
(e > 0 задано).2.
(e > 0 задано).3. |f(xK+1) – f(xK)| < h (h > 0 задано).
Тест должен быть проверен на p последовательных итерациях, в лабораторной работе взять значение p = 3.
Контрольные вопросы и задания
1. В чем основная особенность методов градиента с заданным шагом?
2. Приведите основной недостаток метода наискорейшего спуска на примере некоторых типов функций.
3. Как расположены последовательные направления перемещения метода наискорейшего спуска?
4. Почему метод минимизации должен обеспечить быструю сходимость на квадратичных функциях?
5. Какие направления называются сопряженными?
6. В чем заключается суть методов сопряженных направлений?
7. За какое количество шагов обеспечивается сходимость метода сопряженного градиента для квадратичных функций?
8. В чем отличие метода Флетчера–Ривза от метода сопряженного градиента?
9. Какую информацию необходимо хранить в памяти ЭВМ в методе Флетчера–Ривза?
10. За какое количество итераций сохранится метод Ньютона при применении к строго выпуклой квадратичной функции?
11. Обеспечивается ли метод Ньютона для произвольных функций?
12. Какому требованию должен удовлетворять гессиан в методе Ньютона?
13. Назовите способы получения положительно определенной матрицы в методе Ньютона.
14. Какой общий подход положен в основу квазиньютоновских методов?
15. Какому требованию отвечает аппроксимация обращения гессиана функций в квазиньютоновских методах?
16. Какие формулы коррекции использованы в методах ДФП и БФГШ?
17. Как ведет себя алгоритм ДФП к неточностям в подзадачах одномерной минимизации?
18. В чем отличие алгоритма Бройдена-Флетчера-Гольдфарба-Шанно от алгоритма Давида-Флетчера-Пауэлла?
19. Чему пропорциональна загрузка памяти в квазиньютоновских методах?
20. Оцените объем промежуточных вычислений в квазиньютоновских методах.
Задание к лабораторной работе
Найти минимум функций:
а) F(x1, x2) = N(x2 – x12)2 + (N – x1)2;
б) F(x1, x2, x3, x4) = (x1 + Nx2)2 + N(x3 – x4)2 + (x2 – Nx3)4 +
+N(x1 – x4)4 с точностями Е=10-3,10-5,10-10,10-15.
Отчет о работе
1. Титульный лист.
2. Задание к лабораторной работе.
3. Алгоритмы численного нахождения минимума.
4. Графики зависимости количества итерации от точности решения.
5. Краткий анализ результатов поиска минимума указанных выше функций.
6. Вывод по работе.
Список методов
1. Метод градиента с заранее заданным шагом.
2. Метод наискорейшего спуска.
3. Метод сопряженных направлений.
4. Метод сопряженного градиента для квадратичных функций.
5. Метод Флетчера–Ривза.
6. Метод Ньютона.
7. Метод Давида–Флетчера–Пауэлла.
8. Метод Бройдена–Флетчера–Гольдфарба–Шанно.
Выбор метода решения
1. Порядковый номер студента в журнале по модулю 8.
2. Номер первого метода +5 по модулю 8.
Список рекомендуемой литературы
1. Сухорев А.Г., Тимохов А.В., Федоров В.Б. Курс методов оптимизации. М.: Радио и связь, 1988.
2. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
3. Гуськин С.А., Омельянов Г.А., Резников Г.А., Сироткин В.С. Минимизация в инженерных расчетах на ЭВМ. М.: Машиностроение, 1981.
4. Банди Б. Метод оптимизации: Вводный курс: Пер. с англ. М.: Радио и связь, 1988.
Лабораторная работа 4
Линейное программирование
Алгоритмы симплекс-методов
А. Симплекс-метод.
1. Ввести размерность задачи. Ввести коэффициенты в канонической форме, базисные переменные и задать небазисные переменные.
2. Найти наименьший из коэффициентов C 'm+1, …, C 's, …,C 'n. Пусть это коэффициент C 's. Если C 's ³ 0, то конец, оптимум найден. Иначе: C's<0, и переменная Xs войдет в базис, перейти к 3.
3. Если все a'is £ 0, то конец.
Решение лежит вне заданных границ. Иначе: вычислить B'i / a'is для всех a'is>0 и найти минимум B'i / a'is.
Пусть этот минимум равен br / a'is. Тогда Xs – базисная переменная, а Xr – свободная переменная.
4. Построить новую каноническую форму, изменить базис и перейти к 2.
Б. Двойственный симплекс-метод.
1. Пусть все коэффициенты целевой функции положительны.
2. Найти отрицательную базисную переменную. Если ее нет, то оптимальное решение найдено; если их более чем одна, надо взять из них наименьшую. Пусть эта базисная переменная в r-м ограничении, она является переменной для исключения из базиса.
3. В r-й строке найти отрицательный коэффициент arj.
4. Если такого коэффициента нет, то не существует допустимого решения задачи. Для отрицательных коэффициентов в этой
строке найти
.5. Если этот минимум найден в S-м столбце, переменная Xs должна быть включена в базис.
6. Провести обычные симплекс-преобразования, выбрав в качестве ведущего элемента a'rs.
В. Улучшенный симплекс-алгоритм.
1. Пусть задача представлена в канонической форме. Базисные переменные Xn+1, …, Xn+m равны соответственно b1, …, bm. Обращение базиса есть просто Im – единичная матрица размерностью m´m. Соответствующие симплекс-множители – это p1 = 0, …, pm = 0, поскольку в целевую функцию Z не входят базисные переменные.