- •Аннотация
- •Оглавление
- •Предисловие
- •ГЛАВА 1. Задачи оптимизации. Основные определения
- •1.1. Задачи оптимизации
- •1.2. Минимум функции одной переменной
- •1.3. Унимодальные функции
- •1.4. Выпуклые функции
- •1.5. Условие Липшица
- •1.6. Классическая минимизация функции одной переменной
- •Вопросы и задания для самоконтроля
- •ГЛАВА 2. Одномерная минимизация функций. Прямые методы
- •2.1. О прямых методах
- •2.2. Метод перебора
- •2.3. Метод поразрядного поиска
- •2.4. Метод дихотомии
- •2.5. Метод золотого сечения
- •2.6. Сравнение методов перебора, дихотомии и золотого сечения
- •2.7. Метод парабол
- •Вопросы и задания для самоконтроля
- •Задание для численной реализации в среде программирования MATLAB
- •ГЛАВА 3. Одномерная минимизация. Методы, использующие информацию о производных целевой функции
- •3.1. Метод средней точки
- •3.2. Метод хорд
- •3.3. Метод Ньютона
- •3.4. Возможные модификации метода Ньютона
- •3.5. Методы минимизации многомодальных функций
- •Вопросы и задания для самоконтроля
- •Задание для численной реализации в среде программирования MATLAB
- •ГЛАВА 4. Задача минимизации функции многих переменных. Необходимые и достаточные условия безусловного экстремума
- •4.1. Постановка задачи и определения
- •4.2. Свойства выпуклых множеств и выпуклых функций
- •4.3. Необходимые и достаточные условия безусловного экстремума
- •Вопросы и задания для самоконтроля
- •5.1. Выпуклые квадратичные функции
- •5.2. Общие принципы многомерной минимизации
- •5.3. Метод градиентного спуска
- •5.4. Метод наискорейшего спуска
- •5.5. Метод сопряженных направлений
- •5.6. Метод сопряженных градиентов
- •5.7. Метод Ньютона
- •5.8. Квазиньютоновские методы
- •Вопросы и задания для самопроверки
- •Задание для численной реализации в среде программирования MATLAB
- •ГЛАВА 6. Прямые методы безусловной минимизации многомерных задач
- •6.1. Проблема минимизации многомерных задач
- •6.2. Минимизация функций по правильному (регулярному) симплексу
- •6.3. Минимизация функций при помощи нерегулярного симплекса
- •6.4. Метод циклического покоординатного спуска
- •6.5. Метод Хука–Дживса
- •6.6. Методы случайного поиска
- •Вопросы и задания для самопроверки
- •Задание для численной реализации в среде программирования MATLAB
- •7.1. Условный экстремум при ограничениях типа равенств
- •7.2. Условный экстремум при ограничениях типа неравенств
- •Вопросы и задания для самопроверки
- •ГЛАВА 8. Линейное программирование
- •8.1. Определения. Примеры задач линейного программирования
- •8.2. Общая и каноническая задачи линейного программирования
- •8.3. Геометрическое истолкование задач линейного программирования
- •8.4. Аналитическое решение задач линейного программирования
- •Вопросы и задания для самоконтроля
- •Литература
6.5. Метод Хука–Дживса
Эффективность прямого поиска точки минимума ограниченной снизу целевой функции можно повысить, если на каждом k -м шаге поиска последовательно выбирать направление спуска. Для этого на каждом k -м шаге выделяют предварительный этап исследующего поиска. Целью этого этапа является выбор
направления спуска |
путем исследования |
поведения |
целевой функции f (x) в |
||||||
окрестности |
точки |
xk −1 , найденной на |
предыдущем |
шаге. |
В |
результате |
|||
исследующего |
поиска находится |
точка |
x k , |
для |
которой |
f (x k ) < f (xk −1 ) . |
|||
Направление |
спуска, |
завершающего |
k -й |
шаг |
поиска, |
определяется |
вектором |
||
x k − xk −1 . Такая стратегия поиска, предложенная в |
1961г., получила название |
||||||||
метода Хука–Дживса. Это один из наиболее эффективных прямых методов. |
Алгоритм метода Хука–Дживса на каждом шаге содержит две основные процедуры:
а) исследующий поиск в окрестности данной точки x для определения направления убывания функции f (x) . В результате получим точку x ;
б) перемещение в направлении убывания (x − x) .
Поиск завершается, если после шага "а" получено, что x = x .
Опишем один из возможных алгоритмов исследующего поиска −
покоординатный поиск. Пусть задана |
точка x |
с |
приращениями по каждой |
|
координате j , j =1, ..., n . |
|
|
|
|
Шаг 1. |
Положить x = x, j =1. Перейти к шагу 2. |
|
|
|
Шаг 2. Сделать пробный шаг y = x − |
j e j , где e j − |
j -й базисный вектор. Если |
||
f (x) ≤ f ( y) , то перейти к шагу 3, иначе − к шагу 4. |
|
|
||
Шаг 3. |
Сделать пробный шаг y = x + |
j e j . Если |
f (x) ≤ f ( y) , то прейти к шагу 5, |
|
иначе − к шагу 4. |
|
|
|
|
Шаг 4. |
Положить x = y . Перейти к шагу 5. |
|
|
|
Шаг 5. |
Положить j = j +1 . Если j ≤ n , то перейти к шагу 2, иначе исследующий |
поиск окончен, т.е. получена точка x , для которой f (x) < f (x) , если В результате исследующего поиска может оказаться, что
исследующий поиск считается неудачным. Если при этом норма приращения
117
= ( 1 ,..., n ) мала, т.е. |
|
|
|
|
|
|
|
< ε , где ε |
− заданная точность, |
то полагают |
|||
|
|
|
|
||||||||||
x = x, |
f (x ) = f (x) . Если заданная точность не достигнута, то полагают |
= |
/ γ |
||||||||||
(где коэффициент дробления шага γ >1) и повторяют исследующий поиск. |
|
|
|||||||||||
Полный алгоритм метода Хука – Дживса следующий. |
|
|
|
||||||||||
Шаг |
1. Выбрать начальную точку |
x0 , вектор приращений |
= ( |
1 , ..., |
n ) , |
коэффициент дробления шага γ >1, параметр окончания поиска ε > 0 . Перейти к
шагу 2. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг |
2. |
Провести исследующий покоординатный поиск из точки x0 , |
т.е. найти |
||||||||||
точку x 0 . Если x 0 ≠ x0 , то перейти к шагу 4, иначе к шагу 3. |
|
||||||||||||
Шаг |
3. |
Проверка окончания поиска. Если |
|
|
|
|
|
|
|
< ε , то прекратить |
поиск и |
||
|
|
|
|
||||||||||
положить x = x0 . Иначе − положить = |
/ γ |
и перейти к шагу 2. |
|
||||||||||
Шаг |
4. |
Осуществить перемещение |
из |
точки |
|
x 0 в направлении |
убывания |
||||||
( x 0 − x0 ) в точку x1 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
x1 = x0 + ak (x0 − x0 ) , |
|
|
|
и подобрать так называемый ускоряющий множитель ak > 0 , чтобы f (x1 ) < f (x 0 ) .
Часто ak (0,1]. С увеличением ak увеличивается длина ak x 0 − x0 шага спуска в направлении вектора x 0 − x0 . Значение ak можно подбирать из условия минимума функции f (x) при смещении точки x 0 в направлении этого вектора. В простейшем варианте метода Хука–Дживса значение ak выбирают постоянным, обычно ak = 2 .
В этом случае формула, по которой осуществляется спуск, имеет вид
x1 = x0 +2(x 0 − x0 ) = 2x 0 − x0 .
6.6. Методы случайного поиска
Основой для этих методов служит итерационный процесс
|
xk +1 = xk +αk |
|
|
|
ξ |
|
|
, k = 0,1,... |
|
(6.8) |
|||||
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
ξ |
|
|
|
|
|
|||||
|
|
|
|
|
|
||||||||||
где αk > 0 |
− величина |
шага, ξ = (ξ1 , ..., ξn ) - |
некоторая |
реализация |
n -мерного |
||||||||||
случайного вектора ξ . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Будем |
считать, что |
координаты |
|
|
вектора |
ξ − это независимые |
случайные |
||||||||
величины, |
равномерно распределенные на отрезке [−1, 1] . |
На текущей итерации |
118
при помощи генерирования случайных векторов ξ получаются точки, лежащие на гиперсфере радиуса αk с центром в точке xk . Если значение функции в полученной точке не меньше, чем в центре сферы, шаг считается неудачным. Если число неудачных шагов из данной точки достигает заданного числа M , поиск повторяется из той же точки с уменьшенным шагом до тех пор, пока шаг не станет меньше заданной точности. Если же значение функции в полученной точке меньше, чем в центре, шаг считается удачным и полученное значение выбирается за новый центр поиска.
Приведем два возможных алгоритма метода случайного поиска. Они могут использоваться как самостоятельные минимизирующие процедуры, или входить в состав других алгоритмов, например, использоваться для исследующего поиска в методе Хука-Дживса.
Алгоритм поиска с возвратом при неудачном шаге следующий.
Шаг 1. Выбрать параметр точности ε > 0 , начальный шаг α > 0 , коэффициент уменьшения шага γ >1, предельное число попыток M , точку x . Вычислить f (x) .
Перейти к шагу 2.
Шаг 2. Положить счетчик числа неудачных попыток j =1. Перейти к шагу 3.
Шаг 3. Получить реализацию случайного вектора ξ . Перейти к шагу 4.
Шаг 4. Найти пробную точку y = x +α ξξ , вычислить f ( y) . Перейти к шагу 5.
Шаг 5. Если f ( y) < f (x) , то положить x = y, f (x) = f ( y) и перейти к шагу 4.
Иначе − перейти к шагу 6.
Шаг 6. Положить j = j +1. Если j ≤ M , то перейти к шагу 3, иначе − к шагу 7.
Шаг 7. Если α < ε , то поиск завершить, полагая x = x, f = f (x) . Иначе – положить α =α / γ и прейти к шагу 2.
Иллюстрация построения последовательности (6.8) с помощью описанного алгоритма для функции двух переменных приведена на рис. 6.10, где пунктиром показаны неудачные попытки определения точки xk +1 из (6.8), не приводящие к уменьшению f (x) .
На практике предельное число неудачных попыток M обычно полагают равным 3n , где n − число переменных целевой функции.
119
x0 |
f(x)=C2 |
|
|
x2 |
x* f(x)=C1 |
|
f(x)=C3
C1 < C2 < C3 < C4
f(x)=C4
Рис. 6.10. Иллюстрация работы алгоритма с возвратом при неудачном шаге в E2
Алгоритм метода случайного поиска наилучшей пробы следующий. Этот алгоритм отличается от предыдущего только шагами 3 и 4.
Шаг 3. |
Получить m реализаций случайного вектора ξ : ξ1 , ..., ξm . |
||||
Шаг 4. |
Найти пробные точки yi = x +α |
|
ξi |
, i =1, ..., m , вычислить f ( yi ) . |
|
|
ξi |
|
|||
|
|
|
|
|
Найти yk из условия f ( yk ) = min f ( yi ) и положить y = yk .
i
Вопросы и задания для самопроверки
1.Сформулировать стратегию построения алгоритма симплексного поиска.
2.Какая нумерация вершин симплекса называется правильной?
3.Описать алгоритм отражения вершины в методе правильного симплекса.
4.Зачем необходима и в чем заключается редукция правильного симплекса?
5.Сформулировать теоретическое обоснование минимизации целевой функции методом правильного симплекса.
6.В задачах минимизации с какими целевыми функциями метод правильного симплекса не может обеспечить высокой точности?
7.Сформулировать особенности минимизации целевой функции методом Нелдера-Мида по сравнению с ее минимизацией методом правильного симплекса.
120