- •А.В. Аттетков, С.В. Галкин, В.С. Зарубин
- •ПРЕДИСЛОВИЕ
- •Задания для самопроверки
- •ОСНОВНЫЕ ОБОЗНАЧЕНИЯ
- •Буквы латинского алфавита
- •Буквы греческого алфавита
- •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.3 |
|
к |
х к |
f ( x k) |
к |
х к |
f { x k) |
||
1 |
(-0,412, -3,259) |
-12,482 |
4 |
(-2,218, |
-4,462) |
-27,998 |
|
2 |
(-1,833, |
-4,206) |
-27,243 |
5 |
(-2,232, |
-4,470) |
-27,999 |
3 |
(-2,149, |
-4,416) |
-27,965 |
6 |
(—2,238, -4,476) |
-28,000 |
6.5. Метод Хука — Дживса
Эффективность прямого поиска точки минимума ограни ченной снизу целевой функции можно повысить, если на ка ждом k-м шаге поиска соответствующим образом выбирать направление спуска. Для этого на каждом fc-м шаге выделяют предварительный этап исследующего поиска. Целью этого этапа является выбор направления спуска путем исследования поведения целевой функции /(ж) в окрестности точки ж*” 1, найденной на предыдущем шаге. В результате выполнения этапа исследующего поиска находится точка ж*, для которой / ( х к) < /(ж**"1). Направление спуска, завершающего fc-й шаг поиска, определяется вектором х к —х к~1. Такая стратегия поиска, предложенная в 1961 году, получила название метода Хука — Дживса*
Опишем один из алгоритмов исследующего поиска. Пусть выбрана начальная точка х° и вектор Ъ= (Ь\ Ьп) , удовле творяющий условию |Ь ^ £, где е > 0 — заданный параметр точности исследующего поиска. Координаты вектора 6, назы ваемого вектором перемещений, определяют приращения координат точки ж0 на этапе исследующего поиска. Полага ем k = j = 1, х к = х к = ж0, f k —/ (ж0) и переходим к основной части алгоритма исследующего поиска.
1. Вычисляем
f + j = / ( * ? + ьз е з) и f - j = f ( * j ~ fei e i)>
*См.: Базара М., Шеттпи К .