- •А.В. Аттетков, С.В. Галкин, В.С. Зарубин
- •ПРЕДИСЛОВИЕ
- •Задания для самопроверки
- •ОСНОВНЫЕ ОБОЗНАЧЕНИЯ
- •Буквы латинского алфавита
- •Буквы греческого алфавита
- •1. ЗАДАЧИ ОПТИМИЗАЦИИ
- •1.1. Основные понятия
- •1.2. Некоторые простые примеры
- •1.3. Задачи оптимального проектирования
- •1.4. Задачи оптимального планирования
- •1.5. Классы задач оптимизации
- •Вопросы и задачи
- •2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ
- •2.1. Предварительные замечания
- •2.3. Оптимальный пассивный поиск
- •2.4. Методы последовательного поиска
- •2.5. Сравнение методов последовательного поиска
- •2.6. Методы полиномиальной аппроксимации
- •2.7. Методы с использованием производных
- •Вопросы и задачи
- •3. МИНИМИЗАЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ
- •3.2. Выпуклые функции
- •3.4. Условия минимума выпуклых функций
- •3.5. Сильно выпуклые функции
- •ф{t) = (grad/(а; + th), h)
- •3.6. Примеры минимизации квадратичных функций
- •3.7. Минимизация позиномов
- •Qj = '%2aijci = Q> J = !.*»•
- •Вопросы и задачи
- •4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ
- •4.1. Релаксационная последовательность
- •4.2. Методы спуска
- •4.4. Минимизация квадратичной функции
- •4.5. Сопряженные направления спуска
- •5. АЛГОРИТМЫ МЕТОДОВ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ
- •|iufc|
- •5.3. Метод Ньютона
- •5.4. Модификации метода Ньютона
- •5.5. Квазиньютоновские методы
- •Вопросы и задачи
- •6. АЛГОРИТМЫ ПРЯМОГО ПОИСКА
- •6.1. Особенности прямого поиска минимума
- •6.2. Использование регулярного симплекса
- •6.4. Циклический покоординатный спуск
- •6.5. Метод Хука — Дживса
- •Щ + bjej,
- •6.6. Методы Розенброка и Пауэлла
- •Вопросы и задачи
- •7. АНАЛИТИЧЕСКИЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- •7.2. Минимизация при ограничениях типа равенства
- •7.4. Седловая точка функции Лагранжа
- •7.5. Двойственная функция
- •7.6. Геометрическое программирование
- •Вопросы и задачи
- •8. ЧИСЛЕННЫЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- •8.1. Метод условного градиента
- •8.2. Использование приведенного градиента
- •8.5. Метод проекции антиградиента
- •СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
- •ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
- •ОГЛАВЛЕНИЕ
- •Математика в техническом университете Выпуск XIV
- •Аттетков Александр Владимирович Галкин Сергей Владимирович Зарубин Владимир Степанович
- •МЕТОДЫ ОПТИМИЗАЦИИ
Рис. 6.24 |
Рис. 6.25 |
функции, не являющейся квадратичной, дополнительная итера ция гарантирует линейную независимость векторов, определя ющих направление спуска на каждом fc-м шаге поиска.
Вопросы и задачи
6.1.Перечислите методы прямого поиска, выделите те из них, в которых поиск точки минимума целевой функции про водится в соответствии с рекуррентным соотношением (6.8). Объясните, почему при построении алгоритмов таких мето дов направления поиска должны быть линейно независимыми. Графически проиллюстрируйте на примере решения двумерной задачи минимизации возможные подходы к построению таких направлений поиска.
6.2.В задаче
/(х 1,ггг) = ll^ i + 60:1X2 + 3^2 —2\/l0(xi — ЗХ2) — 22 -» min,
выбрав в качестве начальной точку х° = (\/10, 0), найдите уравнение линии уровня целевой функции, проходящей через точку х°. При помощи ортогонального преобразования при ведите уравнение, описывающее эту линию уровня, к кано ническому виду и постройте эту кривую в исходной системе координат.
6.3. Проведите поиск минимума целевой функции в зада че 6.2 из заданной начальной точки х° с точностью е = 0,01 методами поиска при помощи регулярного и нерегулярного симплексов, циклического покоординатного спуска, методами Хука — Дживса, Розенброка и Пауэлла. Оптимизируйте про цесс поиска при реализации алгоритма метода Нелдера — Ми да путем изменения параметров алгоритма: выбора способа построения исходного симплекса и его размеров, коэффици ентов отражения, растяжения, сжатия и редукции симплекса; при реализации алгоритма метода Хука — Дживса изменени ем вектора перемещений и коэффициента дробления шага на этапе исследующего поиска, а также подбором ускоряющего множителя на этапе спуска. Проведите сравнительный анализ результатов, дайте их графическую интерпретацию. Перечи слите методы, гарантированно приводящие к минимуму целе вой функции за конечное число шагов поиска.
6.4. Решите задачу
f(x 1,ж2) = Ю(ж? - х2 )2 + {xi - I)2 -» min,
выбрав в качестве начальной точку ж0 = (—1, 1) и задав значе ние параметра точности поиска е = 10“ 3. Примените методы циклического покоординатного спуска, Розенброка и Пауэлла. Оптимизируйте процесс поиска точки (1,1) минимума целевой функции, используя различные алгоритмы одномерной мини мизации на каждом шаге покоординатного спуска: дихотомии, золотого сечения, квадратичной и кубической интерполяции.
Проведите сравнительный анализ алгоритмов по числу N ша гов поиска. Дайте графическую интерпретацию полученных результатов.
6.5. Используя методы прямого поиска, минимизируйте функцию Розенброка
/ ( 1 1 ,3:2) = 100(я2 - Х 2 ) 2 + {xi - I)2
с точностью е = 10-3 , выбрав начальную точку яз° = (—1, 1). Установите, какие из примененных алгоритмов не позволяют при заданной точности поиска получить точку минимума (1, 1) вследствие преждевременного окончания процесса поиска.
6.6. Используя различные модификации метода Хука — Дживса, минимизируйте функцию Химмельблау
f{x 1 ,х2) = (я2 + Х 2 - П )2 + (Я1 + х\ - 7)2
с точностью е |
= 10“ 3, выбирая различные начальные точки: |
а) (5, 5); б) (5, |
-5 ); в) (0, 0); г) (-5 , -5 ); д) (5, 0). Оптимизи |
руйте процесс поиска путем изменения параметров алгоритма. Дайте графическую иллюстрацию полученных результатов.
6.7. Минимизируйте функцию Пауэлла
/(Ж1,£2)2?з ,3?4) =
= (xi 4- Юяг)2 + 5(яз - Я4)2 + (х2 - 2хз)4+ 10(xi - Я4)4,
выбрав параметр точности поиска е = 10-3 и начальную точ ку х° = (3, —1, 0, 1). Для этого используйте метод Нелдера — Мида, оптимизируя процесс поиска подбором параметров ал горитма. Установите, можно ли получить точку минимума х * = (0, 0, 0, 0) целевой функции, используя поиск с помощью регулярного симплекса.