- •А.В. Аттетков, С.В. Галкин, В.С. Зарубин
- •ПРЕДИСЛОВИЕ
- •Задания для самопроверки
- •ОСНОВНЫЕ ОБОЗНАЧЕНИЯ
- •Буквы латинского алфавита
- •Буквы греческого алфавита
- •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
- •Аттетков Александр Владимирович Галкин Сергей Владимирович Зарубин Владимир Степанович
- •МЕТОДЫ ОПТИМИЗАЦИИ
где е\, еп — стандартный базис в Rn, находим точку
|
~к |
i l l < fi » H i < i - p |
|
Щ + bjej, |
|
X |
Xk |
fij<H и Hi<Hi; |
J'+1 |
j ~ bjej> |
|
|
Ха, |
во всех остальных случаях, |
полагаем /*+1 = f ( x k+1) и переходим к п. 2.
2.Если j < п, то принимаем j := j +1 и переходим к п. 1. В противном случае переходим к п. 3.
3.Если ж£+1 ^ х к, то переходим к п. 4. В противном случае уменьшаем длину вектора Ь, полагая Ь:= Ь/у, где 7 > 1 — коэффициент дробления шага исследующего поиска, и, полагая
j = 1 , x k = x k, fj = f ( x k), возвращаемся к п. 1 .
4. Если |®£+ 1 — х к\< е, то дальнейший поиск точки мини мума прекращаем, полагая х* « х к~1 и f(x*) « /(® fc_1). В противном случае полагаем х к+г = ®£+1 и переходим на к-м шаге поиска к этапу спуска в направлении вектора x k+l —х к, имея при этом f ( x k+1) < f { x k) ^ /(а:*-1).
На этапе спуска по формуле |
|
х к = х к + ак(хк+1 - х к), |
(6.13) |
подбирая так называемый ускоряющий множитель ак > О, находим такую точку х к, чтобы f ( x k) < f ( x k+1). С увели чением ак увеличивается длина ak\xk+l —х к\ шага спуска в направлении вектора x k + 1 — x k. Значение ak можно подобрать из условия минимума функции /(аз) при смещении точки х к в направлении этого вектора. Может оказаться, что ак £ (0,1]. После нахождения точки х к переходим к следующему шагу поиска (к п. 1 этапа исследующего поиска), полагая j = 1, x k + 1 = = x k + 1 = х к, f k + 1 = f { x k) и затем к := к + 1 .
Впростейшем варианте метода Хука — Дживса значение ак
в(6.13) не подбирают, а задают постоянным, причем обычно полагают ак —2. На рис. 6.16 иллюстрируются этапы исследу-
ющего поиска и спуска для первых двух шагов поиска точки х* минимума целевой функции двух переменных при а\ = <22 = 2, 7 = 2 и начальной точке х°.
Известно много модификаций метода Хука — Дживса. Од на из модификаций связана с введением дополнительных правил выбора точки х к на каждом А;-м шаге при проведении этапа ис следующего поиска. Например, координаты этой точки можно выбирать, используя модифицированный метод циклического покоординатного спуска*. На рис. 6.17 иллюстрируется первый шаг поиска точки х* минимума целевой функции двух перемен ных с применением на этапе исследующего поиска модифици рованного метода циклического покоординатного спуска, а на этапе спуска — процедуры подбора ускоряющего множителя аь = а\ > 0 в формуле (6.13), исходя из условия минимума целе вой функции в направлении вектора х 2 —х 1.
Для определения точки х кна к-и шаге при проведении этапа исследующего поиска можно также использовать процедуры случайного поиска**.
*См.: Базара М., Ш ет т и К . **См.: Васильев Ф .П .
Другой путь повышения эффективности поиска точки ми нимума функции состоит в выполнении на каждом шаге по вторного этапа исследующего поиска* В случае квадратич ной целевой функции f(x) = i (Q®, ®) + (с, х) с положительно определенной матрицей Q порядка п эта модификация метода Хука — Дживса позволяет получить точку минимума за один шаг, если на этапах исследующего поиска использовать моди фицированный метод циклического покоординатного спуска, а выбор ускоряющего множителя на этапе спуска осуществлять исходя из условия минимума целевой функции в установленном направлении спуска.
Пример 6.5. Используем метод Хука-— Дживса для мини мизации функции из примера 6.1. Выберем начальную точку х° = (—2, 1) и положим е —0,01, аь = 2, 7 = 2. На рис. 6.18 представлена графическая иллюстрация процесса поиска точки минимума этой функции для различных начальных векторов Ъ. Результаты поиска приведены в табл. 6.4.
Таблица 6.4
Вариант |
ъ |
X* |
Я **) |
N |
|
а |
(1 , 1 ) |
(-2,234, -4,473) |
-28,0 |
16 |
|
б |
(1, 0,5) |
(—2,234, -4,469) |
-28,0 |
20 |
|
в |
(0,5, 1) |
(-2,234, |
-4,473) |
-28,0 |
17 |
г |
(0,5, 0,5) |
(-2,234, |
-4,433) |
-28,0 |
18 |
Из табл. 6.4 видно, что изменение начальной длины вектора Ьв два раза практически не повлияло на точность нахождения точки х* и значения /(®*), но привело к уменьшению необхо димого числа N шагов поиска. При заданной начальной длине вектора Ь уменьшения необходимого числа N шагов поиска можно также достичь, изменив коэффициент дробления ша га 7 > 1 на этапе исследующего поиска. Так, например, при
*См.: Лесин В .В ., Л исовец Ю .П .
a |
б |
в |
г |
Рис. 6.18
6 = (1 , 1 )т (вариант а) наименьшее количество шагов iV = 1 1 достигается при у = 5, в то время как при у = 4 и у = 20 имеем N = 12, а при 7 = 10 имеем N = 15.
Рассмотрим некоторые модификации метода Хука — Дживса, позволяющие повысить эффективность поиска. В табл. 6.5 приведены результаты поиска, в котором на каждом к-м шаге используется не постоянное значение ускоряющего множителя, равное двум, а переменное, выбираемое из условия минимума целевой функции в направлении вектора x k+l — х к.
Таблица 6.5
Вариант |
ь1 |
X* |
/(*• ) |
N |
|
а |
(1 , 1 ) |
(-2,235, -4,468) |
-28,0 |
14 |
|
б |
(1, 0,5) |
(—2,236, |
-4,471) |
-28,0 |
19 |
в |
(0,5, 1) |
(—2,239, |
-4,474) |
-28,0 |
16 |
г |
(0,5, 0,5) |
(—2,234, |
—4,468) |
-28,0 |
16 |
Из табл. 6.5 видно, что рассмотренный способ выбора уско ряющего множителя позволяет уменьшить необходимое число N шагов поиска.
На рис. 6.19 дана графическая иллюстрация первых двух шагов поиска точки минимума функции, в котором на этапе исследующего поиска использован модифицированный метод циклического покоординатного спуска, а ускоряющий множи тель на этапе спуска выбирался двумя способами: в варианте а он постоянный и равен двум, а в варианте б он определяется исходя из условия минимума целевой функции в направлении вектора х к+1 — х к. Соответствующие результаты приведены в табл. 6.6.
Таблица 6 .6
Вариант |
х * |
А * -) |
N |
а |
(-2,238, -4,476) |
-28,0 |
6 |
б |
(—2,236, -4,473) |
-28,0 |
6 |
a |
б |
Рис. 6.19
Рис. 6.20