close

Вход

Забыли?

вход по аккаунту

?

65

код для вставкиСкачать
Министерство образования и науки Российского Федерации
Сибирский федеральный университет
МЕТОДЫ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
Красноярск
СФУ
2011
УДК 517.977.5
ББК 22.193.1я73
С 32 Методы многомерной оптимизации: методические указания/ сост.
Н. А. Сергеева.– Красноярск: Сиб. федер. ун-т, 2011.– с. 92
Приведены методы многомерной оптимизации с примерами численного
моделирования поиска экстремума, изложены особенности поведения алгоритмов, их классификация в зависимости от использования априорной информации. Изложен порядок оформления работ, приведены варианты заданий.
Предназначен для студентов направлений подготовки 230000 –
"Информатика и вычислительная техника" (230104.65), 220100 – "Системный
анализ и управление" (220100.62, 220100.68).
УДК 517.977.5
ББК 22.193.1я73
© СФУ, 2011
© Оформление Н.А.Сергеевой
ПРЕДИСЛОВИЕ
Теория оптимизации представляет собой совокупность фундаментальных
математических результатов и численных методов, ориентированных на
нахождение наилучших вариантов из множества возможных. Перед инженером
ставится задача, которая заключается в том, чтобы, с одной стороны, проектировать более эффективные и менее дорогостоящие системы и, с другой стороны, разрабатывать методы повышения качества работы уже функционирующих
систем.
Методические указания посвящены лишь одному классу задач, а именно
нелинейной оптимизации с непрерывными переменными и действительной целевой функцией. Изучение этих методов является начальным этапом освоения
теории оптимизации, и без их знания невозможным является изучение некоторых более сложных алгоритмов и направлений современной теории.
В работе рассматриваются три основных класса методов многомерной
безусловной оптимизации: нулевого, первого и второго порядка, т.к. методы
этих групп требуется реализовать программно на практике.
Методические указания имеют то преимущество, что наряду с общим изложением методов, пошагово описаны алгоритмы их реализации и представлены результаты численного моделирования, целью которых является не только
проиллюстрировать работоспособность алгоритмов на конкретных примерах
для лучшего понимания стратегии поиска решений, но и привести примеры, когда алгоритмы заканчиваю расчет преждевременно или сходятся к минимуму
за большее количество шагов, нежели оговаривается в теории. Обсуждаются
причины такого поведения. А студентам предлагается самостоятельно провести
подобные эксперименты для того, чтобы лучше прочувствовать характерные
особенности в поведении каждого алгоритма.
При проведении численного моделирования необходимо поварьировать
различные значения входных параметров алгоритмов, чтобы уяснить степень
влияния того или иного параметра на сходимость и поведение алгоритма, или,
другими словами, выяснить чувствительность алгоритма к значениям параметров. Следует также использовать функции с ярко выраженной овражной структурой в качестве целевых функций для более качественного освоения данного
материала, и как следствие, понимания проблем оптимизации в целом.
Автор выражает благодарность за подготовку иллюстративных примеров
студентам специальностей "Информатика и вычислительная техника" и "Системный анализ и управление".
3
ВВЕДЕНИЕ
Будем рассматривать задачу, относящуюся к классу многомерной оптимизации функций действительных переменных без учета ограничений.
Разнообразные методы многомерной оптимизации различают обычно по
виду информации, которая необходима им в процессе поиска экстремума:
- методы прямого поиска (методы нулевого порядка), которые используют для нахождения экстремума только значения целевой функции;
- градиентные методы (методы первого порядка), которые дополнительно используют частные производные первого порядка целевой функции;
- ньютоновские методы (методы второго порядка), которые используют
частные производные первого и второго порядка.
Исторически первыми подходами были прямые обобщения одномерных
методов поиска экстремума унимодальной функции (например, метод дихотомии, поиск Фибоначчи, метод золотого сечения или интерполяционные методы) на многомерные задачи. Эти подходы не были особенно удачными в связи
с тем, что их трудоемкость росла экспоненциально с ростом размерности задачи, и они требовали введения границ значений переменных.
Рекуррентная схема большинства методов многомерной оптимизации основана на выражении
x k 1  x k   k S k .
Они отличаются друг от друга способом выбора длины шага  k и
направления поиска S k . Шаг  k является скаляром, S k – вектором.
Выбор шага может быть различным. В одних методах используется пропорциональный подход, в других шаг подбирается оптимальным образом. В
этом случае используются методы одномерной оптимизации. Мы не будем
здесь их рассматривать, укажем только некоторых авторов, в чьих работах они
подробно излагаются [2,3,4,5].
Все обсуждаемые ниже методы предполагают ту или иную степень гладкости целевой функции. Основная задача касается нахождения минимума
функции, ниже покажем, как быть в случае, если требуется найти максимум.
Методы имеют локальный характер, то есть для многоэкстремальных функций
методы "скатываются" в ближайший экстремум. Поэтому в изложенных ниже
алгоритмах будем считать, что поиск экстремума ведется в области, где можно
не учитывать ограничения, накладываемые на аргумент целевой функции, которая также предполагается унимодальной, т.е. имеет единственный экстремум.
4
1. ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Задача многомерной оптимизации, которую решают ниже изложенные
методы, состоит в нахождении экстремума в смысле минимума или максимума функции при отсутствии каких-либо ограничений на аргументы функции
[3,6,10]. То есть можно говорить о безусловной оптимизации в некотором локальном смысле.
Ниже введем лишь некоторые, наиболее необходимые обозначения, без
которых дальнейшее изложение материала не представляется возможным.
Общая постановка задачи нахождения экстремума функции многих переменных без ограничений содержит:
– целевую функцию f (x) , где x  ( x1 ,..., xn )T , определенную на n - мерном Евклидовом пространстве R n . Ее значения характеризуют степень достижения цели, ради которой и решается задача;
Требуется найти такой вектор x * из множества допустимых решений, которому соответствует минимальное значение целевой функции на этом множестве:
f ( x* )  min f ( x) .
(1.1)
Задача поиска максимума сводится к задаче нахождения минимума путем
замены знака перед целевой функцией на противоположный:
f ( x* )  max f ( x)   min(  f ( x)).
(1.2)
*
*
Решением задачи поиска экстремума является пара чисел ( x , f ( x )) , со*
держащая точку x и значение функции в ней.
Множество точек минимума (максимума) целевой функции f (x) обозначим X * . Оно может содержать конечное множество точек (в том числе одну)
или бесконечное число.
Точка x * называется точкой локального (относительного) минимума
функции
f (x) , если существует такое   0 , что x x  x*   , то
f ( x* )  f ( x) . Здесь x  x12  x22  ...  xn2 – евклидова норма вектора x .
Точка x * называется точкой глобального минимума функции f (x) , если
f ( x* )  f ( x) x  R n .
Точка x * называется точкой относительного (локального) максимума
5
*
функции f (x) , если найдется   0 , что x x  x*   , то f ( x )  f ( x) .
Точка x * называется точкой глобального максимума функции f (x) , если
f ( x* )  f ( x) x  R n .
Поверхностью уровня функции f (x) называется множество точек, в которых функция принимает постоянное значение, т.е. f ( x)  Const . При n  2
поверхность уровня изображается линией уровня на плоскости R 2 .
Предположим, что функция f (x) имеет частные производные в точке x *
вплоть до второго порядка включительно.
Тогда обозначим
 f ( x) f ( x)
f ( x) 

f ( x* )  
,
,...,
x2
xn 
 x1
T
– градиент f (x) в точке x  .
x  x*
Матрица Гессе является матрицей вторых частных производных размерности
n  n . Матрица является симметрической ввиду инвариантности оператора
дифференцирования по переменным x .
  2 f x   2 f x 
 2 f x  


2

x

x

x

x

x

1
2
1
n 
1
2
  2 f x   2 f x 
 f x  

2
H x    x2 x1

x

x

x
– матрица Гессе в точке x  .
2
n 
2




2
2
2
  f x   f x 
 f x  


2

x

x

x

x

x
n
2
 n 1
 x x*
n
 
Обозначим элемент матрицы Гессе через hij , то есть:
 2 f ( x)
hij 
xi x j .
Сформулируем необходимые условия существования экстремума [3]:
Теорема 1 ( необходимое условие существования экстремума первого
порядка)
6
Пусть f (x) дифференцируемая функция в точке x * . Если x * является
локальным решением задачи (1.1), то
 
f x  0.
f ( x* )
 0, i  1,..., n .
xi
или
(1.3)
Точки x * , удовлетворяющие условию (1.3), называются стационарными.
Теорема 2. (необходимые условия экстремума второго порядка)
Пусть f (x) – дважды дифференцируемая функция в точке x * . Если x *

является решением задачи (1.1), то матрица Гессе H ( x* ) в точке x неотрицательно определена:
H ( x* )  0 , т.е. найдется произвольный вектор
h  0, h  R n , что
hT H ( x * ) h  0 .
(1.4)
Сформулируем достаточные условия существования минимума:
Теорема 3. (достаточные условия минимума второго порядка)
Пусть
 
f (x) – дважды дифференцируемая функция в точке x*  R n и
f x  0 , а матрица Гессе положительно определена, т.е. H ( x* )  0 . Тогда

точка x является точкой минимума.
Замечание 1. (Критерий Сильвестра)
Необходимым и достаточным условием положительной определенности
матрицы Гессе H (x) в точке x  является выполнение следующих неравенств:
1  h11  0,  2 
h11
h12
h21 h22
h11
h12
 0,  3  h21 h22
h31 h32
h13
h23  0, ... .
h33
(1.5)
Определители  i называются угловыми минорами матрицы Гессе.
Если некоторые из определителей в точке x  равны нулю, то матрица Гессе является положительно полуопределенной.
Замечание 2.
7
В случае решения задачи на максимум, матрица Гессе H(x) должна быть
отрицательно определена (отрицательно полуопределена), т.е. в условии (1.5)
знаки последовательности должны чередоваться по правилу: –,+,–,+, …,
Критерием Сильвестра удобно пользоваться на практике при классификации точек экстремума по типу.
2. МЕТОДЫ НУЛЕВОГО ПОРЯДКА
2.1. МЕТОД ПОКООРДИНАТНОГО СПУСКА
Метод покоординатного спуска нулевого порядка является самым
простым в программной реализации и алгоритмическом представлении.
Причиной является отсутствие итерационного поиска по общеустановленной
формуле, используемой в остальных методах. Алгоритм выстраивает
последовательность точек, используя одномерный поиск [2,5]. В качестве
базисных направлений в методе берутся направления координатных осей.
Пусть e1 , e2 , ..., en - единичные векторы в n -мерном пространстве. Сначала минимизация функции f (x) осуществляется по направлению e1 . Происходит минимизация по одному направлению следующим образом: фиксируются координаты текущей (начальной) точки начиная с e2 , ..., en , то есть в исходную целевую функцию подставляются координаты текущей точки x2 , ..., xn , а
x1 принимается переменной, значение которой необходимо определить исходя
из условия
min ( x1 )  min f ( x1 , x2 , ..., xn ) .
(2.1)
После того как будет найдено минимальное значение в этом направлении,
осуществляется поиск по направлению e2 и т.д. После определения точки минимума по направлению en , процесс повторяется, начинается с e1 .
Таким образом поиск минимума многомерной функции сводится к последовательной реализации алгоритмов одномерной оптимизации. Перечислим
некоторые алгоритмы: метод дихотомии (половинного деления), золотого сечения, Фибоначчи, квадратичной интерполяции и прочие. Алгоритмы методов
одномерной минимизации широко освещены в специальной литературе,
например [8,9,10].
Процесс поиска заканчивается, если нормы приращения функции и аргумента достигнут заданной точности.
8
Необходимо отметить особенность одномерного поиска, который может
резко повлиять на скорость сходимости алгоритма. Он касается функций гладких, для которых можно выписать частные производные первого порядка. Если
целевая функция гладкая, то минимум по текущему направлению (координате)
можно найти, используя выражение первой производной по данной координате.
Если такой подход реализовать программно, расчет координат будет намного
точнее из-за того, что уравнение напрямую выражает решение одномерной задачи, и скорость сходимости существенно вырастет. Тем не менее, данный
подход не совсем согласуется с исходным условиям задачи, а именно использованием только значений функции в точках. Метод относится к группе алгоритмов 0-го порядка, не использующих вычисления производных, поэтому применение аналитического выражения производных для вычисления координат выглядит сомнительным, хотя и привлекательным. Алгоритмом разрешается
только использовать информацию о значении функции в точке.
Алгоритм
0
0
0
0
Шаг 1: Задается исходная точка x ( x1 , x2 , ..., xn ), i  1, k  0 , 1  0,  2  0,
здесь i – индекс компоненты точки x , k – номер итерации.
Шаг 2: В исходной точке все координаты, кроме i , фиксируются и осуществляется минимизация по координате xi :
min ( xi )  min f ( x1k 1 , x 2k 1 , ..., xi , ..., x nk ) .
В результате одномерной минимизации по xi получаем новое приближение
xik 1 координаты. Переходим к шагу 3.
Шаг 3: Проверяем:
а) если i  n , тогда i  i  1, шаг 2.
б) если i  n , то перебор всех компонент точки завершен, шаг 4.
Шаг 4. Проверка условий выхода:
f ( x k 1 )  f ( x k )  1 ,
x k 1  x k   2 .
(2.2)
а) если условия выполняются, то x*  x k 1 .
б) если условия (2.2) не выполняются, то i  1, k  k  1, шаг 2.
Задаваемые точности вычисления 1 ,  2 задаются разными по значению,
но могут быть взяты и одинаковыми.
9
Алгоритм покоординатного спуска обладает невысокой скоростью сходимости, однако уверенно сходится к точке минимума. Тем не менее, встречаются случаи так называемого "застревания" на функциях, линии уровня которых сильно вытянуты, т.е. функция, имеющих сильно овражную структуру.
Рисунок 1 – Ситуация преждевременной остановки алгоритма
Здесь точка X 0 – начальная точка работы алгоритма, по направлению e1
найдена точка X 1 , лучшая в смысле уменьшения значения функции. Увидеть
данный факт помогают линии уровня целевой функции. Согласно рисунку видно, что в направлении e2 не удается сделать улучшающий шаг, происходит
преждевременная остановка работы алгоритма.
Следует учитывать эту особенность при выборе данного метода минимизации для конкретной функции.
Численный пример
Требуется минимизировать целевую функцию:
x12  x1 x2  x22
f ( x1 , x2 ) 
 min .
100
Очевидно, что решением является точка с координатами (0,0). Начальная
точка задана координатами: x 0  (100 , 100 ) , точность поиска 1   2  0.01 .
Минимум найден за 9 итераций. Результаты расчетов на каждой итерации с
10
учетом направлений сведены в таблицу. Следует обратить внимание на характерное изменение координат в порядке перебора направлений.
Таблица 2.1 – Результаты численного эксперимента методом покоординатного спуска
Направление
поиска
Номер
итерации
Норма
невязки
по x
x1
x2
Норма невязки
по f (x)
e1
1
-50.02
100.00
49.981
24.9999964861
e2
1
-50.02
25.01
90.118
81.2359382447
e1
2
-12.51
25.01
37.509
14.0721818210
e2
2
-12.51
6.26
41.937
17.5904526898
e1
3
-3.13
6.26
9.3809
0.8801623239
e2
3
-3.13
1.56
10.488
1.1002110468
e1
4
-0.78
1.56
2.3458
0.0550395461
e2
4
-0.78
0.39
2.6229
0.0688065819
e1
5
-0.20
0.39
0.5868
0.0034431309
e2
5
-0.20
0.10
0.6561
0.0043044324
e1
6
-0.05
0.10
0.1466
0.0002152681
e2
6
-0.05
0.02
0.1640
0.0002690364
e1
7
-0.01
0.02
0.0366
0.0000134927
e2
7
-0.01
0.01
0.0410
0.0000168426
e1
8
-0.00
0.01
0.0092
0.0000008438
e2
8
-0.00
0.00
0.0102
0.0000010558
11
Направление
поиска
Номер
итерации
Норма
невязки
по x
x1
x2
Норма невязки
по f (x)
e1
9
-0.00
0.00
0.0022
0.0000000516
e2
9
-0.00
0.00
0.0024
0.0000000645
Рисунок 2 – Иллюстрация работы алгоритма покоординатного спуска
На рисунке, приведенном выше, видно характерное поведение данного
алгоритма на функциях параболического типа.
Теоретически метод покоординатного спуска эффективен для унимодальной функции, но на практике он оказывается слишком медленным. Метод
хорошо работает на гладких функциях с неярко выраженной овражной структурой. Метод прост для практической реализации. Были сделаны многочисленные попытки улучшить его сходимость в общем случае, которые не привели
к большим успехам. Поэтому были разработаны более сложные методы, использующие больше информации на основании уже полученных значений
функции. Одной из таких модификаций покоординатного спуска является поиск по образцу, разрешающий шаги по диагонали координатной плоскости.
12
2.2. МЕТОД КОНФИГУРАЦИЙ
(ХУКА-ДЖИВСА)
Метод конфигураций (Хука-Дживса) [R.Hooke, T.A.Jeeves] представляет
собой сочетание двух этапов: исследующий поиск и поиск по образцу.
Исследующий поиск ориентирован на выявление характера локального
поведения целевой функции и определение направления вдоль "оврагов" [1,9].
На основании исследующего поиска строится направление убывания функции
и осуществляется так называемый ускоряющий поиск по образцу.
Исследующий поиск начинается в некоторой начальной точке x 0 , называемой старым базисом. В качестве множества направлений поиска выбираются
координатные оси. Задается величина шага  , которая может быть различной
для разных координатных направлений и переменной в процессе поиска. Далее
фиксируется первое координатное направление и рассматривается пробная точка ( x10  1 , x20 , ..., xn0 ) , здесь 1 – шаг по первому координатному направлению.
Рисунок 3 – Поведение алгоритма Хука-Дживса
Если значение функции в пробной точке меньше значения функции в исходной точке, шаг считается удачным. В противном случае шаг неудачен, возвращаемся в исходную точку и делаем шаг в противоположном выбранному
направлению, т.е. рассматриваем точку с координатами: ( x10  1 , x20 , ..., xn0 ) .
Снова сравниваем значения функции в полученной точке с исходной, если зна-
13
чение функции меньше, значит следующий шаг делаем из новой точки, если
улучшения не произошло, то возвращаемся в исходную точку. Далее, первое
координатное направление пройдено (удачно или неудачно), переходим к следующему координатному направлению. И так далее, до тех пор, пока не переберем все n направлений. На этом исследующий поиск заканчивается. Согласно рисунку, исследующий поиск заканчивается в точке 5, которая далее обозначается через x1 (рисунок 3). По окончании исследующего поиска возможны
2 варианта исхода: либо получена новая точка, ее координаты отличаются от
старого базиса, тогда следует ее объявить новым базисом и осуществить ускоряющий поиск по образцу, т.е. перейти ко второму этапу. Либо, после перебора
всех направлений точка не изменила своих координат, то есть ни по одному из
направлений не произошло движения из точки старого базиса. Тогда следует
уменьшить размер шага по каждому из направлений по пропорциональному закону и снова повторить исследующий поиск.
Отсюда следует основное условие выхода из алгоритма поиска экстремума метода Хука-Дживса, а именно экстремум достигнут, когда  i  , i  1, n .
Когда определена точка нового базиса, осуществляется поиск по образцу.
Это есть движение по направлению из старого базиса к новому. На рисунке поиск по образцу осуществляется по прямой, построенной через точки x 0 и
x1  т.5 . Значение ускоряющего шага задается ускоряющим множителем  .
На рисунке точка, полученная в результате поиска по образцу, будет т.6. Успех
поиска по образцу определяется с помощью исследующего поиска из полученной точки 6. Так как в результате исследующего поиска из точки 6 была получена точка 10, отличная от т.6, то поиск по образцу ( x 0 , x1 ) был успешен. Следует обратить внимание, что сравнение значений функции в точках ( x1 ,6) не
происходит. А сравниваться будут точки 10 (как точка нового базиса) и т. 6
(как точка старого базиса).
При этом значение в наилучшей точке 10 оказалось меньше (теперь это
уже точка нового базиса), чем в точке предыдущего базиса x1 . На рисунке т. 11
– точка удачного поиска по образцу, т.15 – неудачного. Если поиск по образцу
оказался неудачен, то происходит возврат в новый базис, т.е. в т.6, где продолжается исследующий поиск с уменьшенным шагом. На рисунке удачный поиск
отображается сплошными линиями, неудачный – пунктирными.
Обозначим через (d1 , ...d n ) – координатные направления
14
1
 0
 0
 
 
 
0
1
 
 
 0
d1   , d 2   , ..., d n    .



 
 
 
 0
 0
1
(2.3)
При поиске по направлению d i меняется только переменная xi , остальные остаются фиксированными.
Алгоритм
Шаг 1. Задать начальную точку x 0 , число   0 для остановки алгоритма,
начальные величины шагов по координатным направлениям  i  , i  1, n ,
ускоряющий множитель   0 , коэффициент уменьшения шага   1. Положить y1  x 0 , i  1, k  0 . Здесь i – индекс, перебирающий координатные
направления, k – номер итерации.
Шаг 2. Осуществить исследующий поиск по выбранному координатному
направлению:
а) если f ( y i   i d i )  f ( y i ) , т.е.
f ( y1i ,..., yii  i ,..., yni )  f ( y1i ,..., yii ,..., yni ) , шаг считается удачным. В
этом случае следует положить y i1  y i   i d i и перейти к шагу 3;
б) если в п. "а" шаг неудачен, то делается шаг в противоположном
направлении. Если f ( y i   i di )  f ( y i ) , т.е.
f ( y1i ,..., yii  i ,..., yni )  f ( y1i ,..., yii ,..., yni ) , шаг считается удачным. В
этом случае положить y i1  y i   i d i и перейти к шагу 3;
в) если в пп. "а" и "б" шаги неудачны, положить y i 1  y i .
Шаг 3. Проверить условия:
а) если i  n , то положить i  i  1, и перейти к шагу 2 (продолжить
исследование по следующему направлению);
б) если i  n , проверить успешность исследующего поиска:
– если f ( y n1 )  f ( x k ) , перейти к шагу 4;
– если f ( y n1 )  f ( x k ) , перейти к шагу 5.
Шаг 4. Провести поиск по образцу:
– положить x k 1  y n1 ;
15
– y l  x k 1  ( x k 1  x k ), i  1, k  k  1 ,
– перейти к шагу 2.
Шаг 5. Проверить условие окончания:
а) если все  i  , i  1, n , то поиск завершить: x  x k ;
б) для тех i , для которых  i  , уменьшить величину шага:  i 
i
.

Положить y l  x k , x k 1  x k , k  k  1, i  1 и перейти к шагу 2.
Рекомендуемые значения ускоряющего множителя   2 , значение
  1.5 , начальные шаги по координатным направлениям  i  1, i  1, n .
Численные примеры отыскания экстремума методом конфигураций
Начальная величина шага по координатным направлениям 1   2  10 ,
ускоряющий множитель   2 , коэффициент уменьшения шага   2 , точность
  0.01 . Целевая функция квадратичного вида:
f ( x1 , x2 )  25 x12  5x22  x1 x2 ,
начальная точка (начальный базис) ( x10 , x20 )  (50,50) .
Решение задачи нашлось за 11 шагов, что демонстрирует неплохую скорость для прямого метода.
Таблица 2.2 – Результаты численного решения методом Хука-Дживса
№ итерации
x1
x2
1
2
3
4
5
6
7
8
9
10
11
-20
-5
2,5
-1,25
0,625
-0,312
0,156
-0,078
0,039
-0,019
0,009
-20
-5
2,5
-1,25
0,625
-0,312
0,156
-0,078
0,039
-0,019
0,009
16
На рисунке 4 изображены линии уровня целевой функции и значения решения на каждой итерации. Здесь начальная точка оказалась выбрана настолько
удачно, что направление поиска решения фактически не меняется на всем протяжении всей работы алгоритма.
Рисунок 4 – Иллюстрация работы алгоритма Хука-Дживса
В следующем примере исследовалась более сложная функция:
f ( x1 , x2 )  e
 x1 
 
8
2
  x2  2 
1     .
 3 


(2.4)
Точкой минимума исследуемой функции является x  (0,0) . Начальная
точка задавалась координатами x 0  (19,17 ) , точность   0.01 . Метод сошелся
в точку минимума за 16 итераций. Здесь можно заметить изменение направления поиска.
Строгое доказательство сходимости метода Хука-Дживса было дано
только в случае строгой выпуклости и непрерывной дифференцируемости целевой функции.
Надо указать одну особенность поведения данного метода, с которой
можно столкнуться при оптимизации на сильно овражных функциях. Если
начальная точка попадает на излом оврага, если направление оврага окажется
не параллельным осям координат, то алгоритм заканчивает свою работу преж17
девременно, т.к. исследующий поиск не дает улучшения ни по одному направлению. Эта особенность является недостатком метода.
Были разработаны многие модификации метода поиска по образцу, но все
они не являются столь популярными, как оригинальный алгоритм.
Рисунок 5 – Иллюстрация работы алгоритма Хука-Дживса функции (2.4)
Преимуществом метода может служить простота алгоритма и сравнительно небольшое количество вычислений.
Достоинством алгоритма является то, что его операции очень просты и
даже в случае непредвиденных обстоятельств не приводят к запрещенным
арифметическим операциям (типа деления на ноль). Еще одним достоинством
является то, что алгоритм требует очень мало (порядка n) памяти компьютера.
Поиск по образцу ускоряет продвижение алгоритма по дну оврага, а шаги исследующего поиска позволяют приблизительно определить направление градиента.
18
2.3. МЕТОД ДЕФОРМИРУЕМОГО МНОГОГРАННИКА
(НЕЛДЕРА-МИДА)
В 1962 году Спендли, Хекст и Химсворт предложили метод поиска по
симплексу, разработанный ими в связи со статистическим планированием эксперимента [Spendly W., Hert G.R., Himsworth F.R. Sequential application of simplex deigns in optimization and evolutionary operation // Texnometrics. 1962. V.4.
Pp. 441–461]. Этот метод получил название симплексного, т.к. в основе алгоритма используются геометрические объекты, именуемые симплексами, при
построении траектории поиска [10,11]. Обсудим основные идеи этого метода.
Определение. Регулярным многогранником (симплексом) в n-мерном
пространстве называется множество из (n+1) равноудаленной точки. На плоскости симплексом является равносторонний треугольник, в пространстве – правильный тетраэдр.
Из аналитической геометрии известно, что координаты вершин регулярного симплекса определяются следующей матрицей размерности n(n+1):
0 d1
0 d
2
D
. .

0 d 2
d2
d1
.
d2
d 2 ... d 2 
t
d1 
( n  1  n  1),

d 2 ... d 2
n
2
,
. . .
t
 d 2  n 2 ( n  1  1).
d 2 ... d1 
(2.5)
Здесь столбцы есть координаты вершин, а строки дают номера координат,
t – расстояние между вершинами.
При n=2 и t=1 получим треугольник с координатами:
0 0,956 0,259 
D
.
0 0,259 0,956 
При поиска экстремума этим методом целевая функция вычисляется в
каждой из вершин регулярного симплекса. Из вершины, где целевая функция
максимальна, проводится проектирующая прямая через центр тяжести симплекса, затем вершина с максимальным значением функции отбрасывается и
строится новый отраженный симплекс из оставшихся прежних точек и одной
новой точки, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести.
Продолжение этой процедуры, в которой каждый раз отбрасывается точка с максимальным значением целевой функции, а также использование правил
уменьшения размера многогранника позволяют осуществить поиск, в котором
19
величина шага на любом шаге фиксирована, а направление поиска можно менять (производная не используется).
Определенные трудности, встречающиеся при использовании этого метода, а именно отсутствие ускорения поиска в "хорошем" направлении и трудности при поиске на искривленных "оврагах" и "хребтах", привели к необходимости улучшений.
В 1964 году Нелдер и Мид предложили модификацию, в которой симплекс может изменять свою форму [Nelder J.A., Mead R. A simplex method for
function minimization // Computer J. 1965. V. 7. Pp. 308 – 313]. Так как в этом
случае симплекс не будет уже регулярным, метод назвали поиском по деформируемому многограннику [1,6,10].
Минимизируется функция независимых переменных с использованием
(n+1) вершин многогранника. Вершина, в которой значение целевой функции
наибольшее, проектируется через центр тяжести остальных вершин. Улучшенные значения целевой функции находятся последовательной заменой точки с
наибольшим значением на более "хорошие" точки, пока не будет найден минимум. При этом многогранник может вытягиваться или сжиматься по выбранному направлению.
Деформируемый многогранник в противоположность жесткому симплексу
адаптируется к топографии целевой функции, вытягиваясь вдоль длинных
наклонных поверхностей, изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума, что достигается выбором коэффициентов сжатия,
растяжения и отражения.
Обозначим вершины выпуклого многогранника x i (k ), i  1,..., n  1 ( k –
номер итерации). Деформирование многогранника зависит от структуры линий
целевой функции. Задается точность оценивания точки минимума   0 .
Алгоритм
Шаг 1. Задать вершины многогранника x1 ,..., x n1 ; Параметры отражения
 , сжатия  , растяжения  , число   0 для остановки алгоритма. Положить
k  0 (последующие шаги 2-6 соответствуют текущему номеру k системы точек).
l
h
Шаг 2. Среди вершин найти «наилучшую» x и «наихудшую» x , соответствующие минимальному и максимальному значениям функции:
f ( x l )  min f ( x j ) , f ( x h )  max f ( x j ) ,
j 1,..., n1
j 1,..., n1
20
а также точку x s , в которой достигается второе по величине после максимального значение f ( x s ) .
Шаг 3. Найти «центр тяжести» всех вершин многогранника за исключением наихудшей x h :
1 n1
 1 n1
x n 2    x j  x h    x j .
n  j 1
 n j 1
j h
Шаг 4. Проверить условие окончания:
 1 n1
j
n 2 
f
(
x
)

f
(
x
)
a) если   


 n  1  j 1

2
1
2

   , процесс поиска можно

завершить и в качестве приближенного решения взять наилучшую
точку текущего многогранника: x*  x l ;
b) если    , продолжать процесс.
Шаг 5. Выполнить операцию отражения наихудшей вершины через центр
тяжести x n2 (рисунок 6, а):
x n3  x n2  ( x n2  x h ) .
Шаг 6. Проверить выполнение условий:
a) если f ( x n3 )  f ( x l ) , выполнить операцию растяжения (рисунок 6,
б):
x n4  x n2  ( x n3  x n2 ) .
Найти вершины нового многогранника:
 если f ( x n4 )  f ( x l ) , то вершина x h заменяется на x n4 (при
n  2 многогранник будет содержать вершины x1 , x 3 , x 6 ).
Затем следует положить k  k  1 и перейти к шагу 2;
h
n 3
 если f ( x n4 )  f ( x l ) , то вершина x заменяется на x (при
n  2 многогранник будет содержать вершины x1 , x 3 , x 5 ).
Далее следует положить k  k  1 и перейти к шагу 2;
21
б) если f ( x l )  f ( x n3 )  f ( x h ) , выполнить операцию сжатия
(рисунок 6, в):
x n5  x n2  ( x h  x n2 ) .
Следует заменить вершину x h на x n5 , положить k  k  1 и
перейти к шагу 2 (при n  2 многогранник будет содержать вершины x1 , x 3 , x 7 );
в) если f ( x l )  f ( x n3 )  f ( x s ) , то вершина x h заменяется на x n3 .
При этом положить k  k  1 и перейти к шагу 2;
г) если f ( x n3 )  f ( x h ) , выполнить операцию редукции (рисунок 6, г).
Формируется новый многогранник с уменьшенными вдвое
Рисунок 6 – Этапы изменения многогранника
l
сторонами и вершиной x :
x j  x l  0,5( x j  x l ), j  1,..., n  1 .
При этом следует положить k  k  1 и перейти к шагу 2.
22
В результате численного исследования поведения алгоритма для оптимизации целевых функций разных типов были установлены предпочтительные
диапазоны задания параметров   1, 0.4    0.6 , 2.8    3.0 . Данные рекомендации являются общими и значения параметров могут отличаться от
каждого конкретного случая.
Численные примеры поиска безусловного экстремума
методом Нелдера-Мида
Требуется найти минимум функции:
f ( x1 , x2 )  100  ( x1  x2 ) 2  1  10  ( x1  x2 ) 2  1
(2.5)
Аналитическое решение:
1. Составим необходимое условие существования экстремума:
20  x`1  20  x2
200  x1  200  x2
 f ( x1 , x2 )


 0,
 x
2
2
2  100  ( x1  x2 )  1 2  10  ( x1  x2 )  1
1


20  x1  20  x2
 f ( x1 , x2 )  200  x1  200  x2 
 0.
2
2
 x2
2  100  ( x1  x2 )  1 2  10  ( x1  x2 )  1

Получаем стационарную точку ( x1 , x2 )  (0,0) подозрительную на экстремум.
2. Проверим выполнение достаточного условия:
 2 f ( x1 , x2 )
10
(20  x1  20  x2 ) 2



3
2
x12
10  ( x1  x2 )  1 4  10  ( x  x ) 2  1 2


100
100  ( x1  x2 )  1
2
 2 f ( x1 , x2 )

x1x2




4  100  ( x1  x2 ) 2  1


4  10  ( x1  x2 ) 2  1
100  ( x1  x2 ) 2  1

3
2

;
10  ( x1  x2 )  1
2

4  100  ( x1  x2 )  1
2
23
3
2
10
(200  x  200  y ) 2


2
(200  x1  200  x2 ) 2
(20  x1  20  x2 ) 2
100
1
3
2

 2 f ( x1 , x2 )

;
x2 x1
 2 f ( x1 , x2 )
10
(20  x1  20  x2 ) 2



3
2
x22
10  ( x1  x2 )  1 4  10  ( x  x ) 2  1 2


100

100  ( x1  x2 )  1
2
1
2
(200  x1  200  x2 ) 2


4  100  ( x1  x2 ) 2  1
3
2

.
Составим матрицу Гессе в особой точке :
  2 f ( x1 , x2 )

x12

  2 f ( x1 , x2 )

 x1x2
 2 f ( x1 , x2 ) 

xy 
2
 f ( x1 , x2 ) 

x22
 ( x ,x
1
110 90 
 ,
 
90
110


2 ) ( 0 , 0 )
далее определим значения угловых миноров:
1  110  0,  2 
110
90
90
110
 4000  0.
Полученный знаковый ряд угловых миноров соответствует точке минимума,
таким образом, ( x1* , x2* )  (0,0) , f ( x1* , x2* )  2 .
Таблица 2.3 – Параметры метода деформируемого многогранника
x10
x20




0
5
1
0,5
2
0,01
Таблица 2.4 – Результат вычислений
(для каждой k -ой итерации приводится только лучшая вершина)
k
x1k
x2k
f ( x1k , x2k )
0
0
5
65,8529785
1
0,9312505
3,4563769
51,9351928
2
-0,5349756
2,1669272
24,9526132
3
0,5944124
-1,5650437
16,6593202
4
0,5944124
-1,5650437
16,6593202
24
Окончание таблицы 2.4
k
x1k
x2k
f ( x1k , x2k )
5
0,5944124
-1,5650437
16,6593202
6
0,0297183
0,3009417
4,7719363
7
0,0297183
0,3009417
4,7719363
8
0,0297183
0,3009417
4,7719363
9
0,1708919
-0,1655545
2,4615474
10
0,0439593
-0,129521
2,4566793
11
0,1074256
-0,1475378
2,3619982
12
0,0721322
-0,0309137
2,1333708
13
0,0721322
-0,0309137
2,1333708
14
0,0721322
-0,0309137
2,1333708
15
0,0739123
-0,0847216
2,1245954
16
0,039509
0,0049985
2,1005115
17
0,0258676
-0,057757
2,0839905
18
-0,0085356
0,031963
2,035243
19
0,008666
-0,0128969
2,0032167
20
0,008666
-0,0128969
2,0032167
21
0,008666
-0,0128969
2,0032167
На рисунке 7 представлены линии уровня и поведение многогранника, в
таблице 2.4 содержатся значения лучшей вершины симплекса и значение функции в этих вершинах.
Приведенный далее пример иллюстрирует движение многогранника
вдоль хребта, что является довольно характерным для данного метода поведением.
Вид функции:
f ( x1 , x2 )  100  ( x1  x2 ) 2  1  100  ( x1  x2 ) 2  1
25
(2.6)
Таблица 2.5 – Параметры метода деформируемого многогранника
x10
x20




15
20
1
0,5
2
0,01
Рисунок 7 – Иллюстрация алгоритма Нелдера-Мида для функции (2.5)
Рисунок 8 – Поведение алгоритма Нелдера-Мида для функции (2.6)
26
Ниже приводятся результаты численных исследований для одной и той
же начальной точки и различных показателях , ,  , значения которых были
взяты за рамками рекомендуемых пределов. Для ниже представленных в таблице результатов бралась единая начальная точка x 0 =3, y 0 =5.
Таблица 2.6 – Изменение значения  (коэффициента растяжения)



k
x1k
x2k
f ( x1k , x2k )
1
0,5
2
55
0,0005929
-0,0007432
2,00001
1
0.5
3
30
0,0018341
-0,0012106
2,0000657
1
0.5
4
64
0,000499
-0,0014348
2,0000624
1
0.5
5
26
0,0004451
0,0001408
2,0000176
1
0.5
6
75
-0,0001931
-0,0003221
2,0000133
Лучший результат выделен: 4-я строка. Строка соответствует наименьшему количеству итераций, достигнутой точности вычислений.
Таблица 2.7 – Изменение значения  (коэффициента сжатия)



k
x1k
x2k
f ( x1k , x2k )
1
0,1
2
54
0,0107456
-0,0088395
2,0020976
1
0.2
2
54
0,0003881
-0,0011777
2,0000434
1
0.3
2
22
0,6477317
-0,6383733
5,1925268
1
0.4
2
43
0,0030362
-0,002935
2,0001787
1
0.5
2
55
0,0005929
-0,0007432
2,00001
Данное обследование не выявило улучшения сходимости. Удалось получили вариант, когда остановка работы алгоритма произошла преждевременно,
минимум не достигнут (3-я строка). Наилучший результат показан в последней
строке таблицы 2.7.
В таблице 2.8 исследовались различные значения коэффициента отражения. Замечено, что, взяв растяжение вместо отражения, получаем наилучшую
скорость сходимости при коэффициенте   2 , что подтвердило общие рекомендации выбора параметров метода.
27
Таблица 2.8 – Изменение значения  (коэффициента отражение)



k
x1k
x2k
f ( x1k , x2k )
1
0,5
2
63
-0,0001395
-0,0001749
2,0000049
2
0.5
2
55
-0,0017661
0,0017037
2,0000603
3
0.5
2
65
-0,0000585
-0,001504
2,0001325
Подытоживая результаты численного обследования, получаем следующую наилучшую комбинацию коэффициентов для данной целевой функции с
точки зрения точности вычислений, сведенных в таблицу 2.9.
Таблица 2.9 – Значения параметров метода Нелдера-Мида



k
x*
y*
f ( x* , y * )
1
0,5
2
21
-0,0009254
0,0005397
2,0000049
Следующий численный пример иллюстрирует преждевременную остановку поиска минимума функции:
f ( x1 , x2 )  2 x12  x1 x2  x22 .
Таблица 2.10 – Значения параметров при преждевременной остановке
Нач. точка
Коэф. отражения, 
Коэф. сжатия, 
Коэф. растяжение, 
Норма, 
(4, 4)
4
0,2
2
0,01
Конечным результатом будет точка x =(4.58, 0.19), поскольку выполнено
условие выхода из алгоритма поиска. Точность метода достигнута, однако решение не найдено (рисунок 9), что является прямым следствием влияния выбранного коэффициентов отражения и сжатия. Вообще метод более чувствителен к выбору коэффициента отражения, нежели растяжения.
Все примеры были взяты для наглядной демонстрации того факта,
насколько существенно влияние значений коэффициентов метода на скорость
его сходимости алгоритма, поведение и конечный результат. Чтобы получить
данную иллюстрацию пришлось выйти за пределы рекомендованных значений
и принять   5 .
28
Рисунок 9 – Преждевременная остановка алгоритма Нелдера-Мида
Легко увидеть даже на примере небольшой размерности, что  – коэффициент растяжения влияет на поведение алгоритма сильнее, чем ,  .
Можно привести результаты исследований параметров следующими учеными: Нелдер и Мид рекомендуют использовать значения   1,   0.5,   2 ;
Павиани (D.Paviani):   1, 0.4    0.6, 2.8    3.0 ; Паркинсон и Хадчинсон
(J.M.Parkinson, D.Hutchinson):   2,   0.25,   2.5 .
Для задач с небольшим числом переменных метод деформируемого многогранника известен как надежный и робастный метод, который, однако, является и относительно дорогостоящим. Для работы алгоритма необходимо хранить n+1 векторов, а операция отображения требует порядка n2 операций. Нелдер и Мид эмпирически обосновали утверждение, что с ростом размерности n
количество обращений к целевой функции растет примерно как n2.11, однако
это обоснование проведено на размерности меньше десяти и вряд ли будет в
силе для много большего числа переменных.
29
2.4. МЕТОД ВРАЩАЮЩИХСЯ КООРДИНАТ
(РОЗЕНБРОКА)
Пусть требуется найти безусловный минимум функции многих переменных, т.е. найти точку
x * , для которой выполняется соотношение:
f ( x* )  min f ( x) .
(2.7)
Пусть d1 , d 2 , ..., d n – линейно независимые векторы и d i  1, i  1, n . Если (d i , d j )  0, i  j, i, j  1, n , тогда система векторов d1 , d 2 , ..., d n является
T
взаимно ортогональной.
Суть метода Розенброка состоит в следующем: задаѐтся исходная точка,
из неѐ осуществляется итеративный поиск направления убывания функции с
помощью изменяемых дискретных шагов вдоль линейно независимых и ортогональных направлений [2,3,6,9].
В случае удачного шага в исследуемом направлении его значение на следующей итерации увеличивается с помощью коэффициента растяжения, а в
случае неудачи уменьшается за счѐт умножения на коэффициент сжатия (при
этом направление поиска изменяется на противоположное). Поиск в системе
текущих направлений проводится до тех пор, пока все возможности уменьшения функции не будут исчерпаны.
Рисунок 10 – Поведение метода Розенброка
Если по каждому направлению поиска имеет место неудача, строится новое множество линейно независимых и ортогональных направлений и цикличе-
30
ский поиск по отдельным направлениям продолжается. Новые направления поворачиваются по отношению к предыдущим так, что они оказываются вытянутыми вдоль оврага.
Алгоритм:
Шаг 1. Задать начальную точку x , число   0 для остановки алгоритма, коэффициент расширения   1 , коэффициент сжатия  1    0 . В каче0
стве начальных линейно независимых и ортогональных направлений выбрать
координатные направления
1
 0
 0
 
 
 
0
1
 
 
 0
d1   , d 2   , ..., d n    .



 
 
 
 0
 0
1
(2.8)
Начальная величина шага вдоль направлений 01 ,...0n  0 , N – максимальное число неудачных серий шагов по всем направлениям на одной итерации. Положить y1  x 0 , k  0, i  1,  i  0i для всех i .
Шаг 2. Сделать шаг по i -му направлению:
а) если f ( y i   i d i )  f ( y i ) , шаг считается удачным. В этом случае следует положить y i1  y i   i d i ,  i   i и перейти к шагу 3;
б) если
f ( y i   i di )  f ( y i ) , шаг считается неудачным. Тогда следует
i 1
i
положить y  y ,  i   i и перейти к шагу 3.
Шаг 3. Проверить выполнение условий:
а) если i  n , то положить i  i  1 и перейти к шагу 2;
б) если i  n , проверить успешность поиска по текущим ортогональным
направлениям:
– если
f ( y n1 )  f ( y1 ) , т.е. хотя бы 1 спуск по направлению на шаге 2
был успешным, положить y  y
1
– если f ( y
n1
n1
, i  1 и перейти к шагу 2;
)  f ( y1 ) , т.е. каждый из n последних шагов был неудач-
ным, оценить успешность поиска на текущей итерации:
– если f ( y
n1
)  f ( x k ) , т.е. на k-й итерации хотя бы 1 шаг удачный, то
перейти к шагу 4;
31
– если f ( y
n1
)  f ( x k ) , т.е. не было ни одного удачного шага на k-й
итерации, процесс поиска приостановить. Если число l последовательно неудачных серий шагов по всем направлениям на текущей итерации не превышает
N , проверить условие окончания, иначе перейти к шагу 4. Если
 i   для
всех i , то найдено приближенное решение задачи: x*  x k . Если  i   хотя
бы для одного i , то положить y  y
1
Шаг 4. Положить
а) если x
k 1
б) если x
n1
,
i  1 и перейти к шагу 2.
x k 1  y n1 и проверить условие окончания:
 x k   , то поиск завершить: x*  x k .
k 1
 x k   , вычислить длины шагов по каждому направле-
нию поиска на k -й итерации 1 , ...,  n из соотношения
n
x k 1  x k    i d i .
(2.9)
i 1
Далее построить новый набор линейно независимых и взаимно ортогональных направлений поиска d1 , d 2 , ..., d n с помощью процедуры ГраммаШмидта:
 i  0,
ai ,
i  1,
 ai ,

bi
n

i 1
d

ai  
b

.
T
i

 j d j ,  i  0; i
ai   (ai d j )d j , i  2;

b
i


j 1
 j 1

(2.10)
Если  i  0 , то d i  d i , т.е. новые направления следует вычислять
только для тех индексов, для которых  i  0 . После нахождения новых направлений следует положить: d i  d i ,  i  0i для всех i  1,..., n , k  k  1 ,
, i  1, и перейти к шагу 2.
Так же, как и поиск по образцу, метод Розенброка не требует информации
о производных, но в процессе вращения осей координат отслеживает положение градиента функции. Это позволяет ему двигаться вдоль дна оврага и преодолевать повороты. Метод также не использует одномерную оптимизацию
вдоль выбранных осей. Это делает процедуру устойчивой (робастной).
Однако имеется дополнительный недостаток – процедура ортогонализации очень дорого стоит и в смысле количества операций, производимых с си-
32
стемой координат, и в смысле необходимой памяти, которой требуется уже по2
рядка n , а не n, как в методе Хука-Дживса. Это значит, что даже в случае относительно “дешевой” целевой функции вычислительные затраты на ортогонализацию оказываются значительными в сравнении с общими затратами. Кроме
того, размерность решаемых задач ограничивается требуемым объемом памяти.
Существует несколько модификаций алгоритма Розенброка, главная из
которых состоит в отказе от постоянной длины шага и замене на процедуру
масштабирования длины шага в зависимости от успешности поиска в данном
направлении.
Численные примеры нахождения минимума
с помощью метода Розенброка
На приведенных ниже графиках отражена работа алгоритма поиска экстремума функций квадратичного и общего вида. Первой функции соответствует уравнение:
f ( x1 , x2 )  2 x12  x1 x2  x22 .
Нетрудно видеть, что минимум этой функции
(2.11)
достигается в точке
( x1 , x2 )  (0,0) .
*
*
Численное решение задачи минимизации функции линейного вида методом Розенброка отражено в таблицах.
Таблица 2.11 – Начальные данные поиска минимума функции (2.11) методом Розенброка
Коэффициент расширения   1
Коэффициент сжатия
1,5
-0,5
1    0
Нач. шаг
вдоль 1
направления 1
0,6
Нач. шаг
вдоль 2
направления  2
1
Малое положительное
число   0
Начальная точка
0,1
(4;3)
( x10 , x20 )
Рисунок отражает линии уровня с нанесенными значениями квадратичной функции и точки, получившиеся в результате работы алгоритма.
Таблица 2.12 – Результаты работы алгоритма Розенброка для функции
(2.11)
Номер итерации
x1
x2
1
2
0,043750
-0,078734
0,203125
0,058809
33
Рисунок 11 – Реализация метода Розенброка для функции (2.11)
Таблица 2.13 – Начальные данные для метода Розенброка
Коэффициент расширения   1
Коэффициент сжатия
1,8
-0,8
1    0
Нач. шаг
вдоль 1
направления 1
1,2
Нач. шаг
вдоль 2
направления  2
1
Малое положительное
число   0
Начальная точка
0,1
(5;-4)
( x10 , x20 )
Рисунок 12 – Реализация метода Розенброка для функции (2.11)
34
Таблица 2.14 – Таблица численных результатов для функции (2.11)
Номер итерации
x1
x2
1
2
-0,7984
-0,063507
0,8736
0,0358864
Численное решение задачи минимизации функции общего вида методом
вращающихся координат.
Вторая функция записывается соотношением:
x12
40
 x22 
f ( x1 , x2 )  e   1 .
 10 
(2.12)
Таблица 2.15 – Начальные данные для функции (2.12)
Коэффициент расширения   1
Коэффициент сжатия
1,3
-0,4
1    0
Нач. шаг
вдоль 1
направления 1
0,6
Нач. шаг
вдоль 2
направления  2
0,6
Малое положительное
число   0
Начальная точка
0,1
(5;6)
( x10 , x20 )
Рисунок 13 – Реализация метода Розенброка для функции (2.12)
35
Таблица 2.16 – Таблица результатов работы алгоритма Розенброка для
функции (2.12)
Номер итерации
x
x
1
1
2
2
-0,725845
-0,0101368
0, 274155
-0,031746
2.5. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ
(ПАУЭЛЛА)
В основе метода сопряженных направлений (методе Пауэлла [Powell
M.J.D.] лежит результат математического анализа, который можно сформулировать следующим образом: минимум квадратической функции может быть
найден не более чем за n шагов, где n – размерность пространства переменных, при условии, что поиск ведется вдоль сопряженных относительно матрицы Гессе направлениях [3,5,9].
Дадим определение:
Пусть H – симметрическая матрица размера n n . Векторы d1 , d 2 , ...d n
называются H -сопряженными или просто сопряженными, если d Tj Hdi  0
при всех i  j .
Поиск минимума функции вдоль сопряженных относительно матрицы
Гессе направлениях обеспечивает высокую скорость сходимости, близкую к
размерности пространства. При этом метод использует только знание о значении функции в точках. Этот метод хорошо работает и для функций общего вида, которые хорошо аппроксимируются квадратическими функциями в области
экстремума. Число итераций возрастет незначительно, вполне сравнимо с размерность пространства переменных.
Задается начальная точка и направления d1 , d 2 , ...d n , совпадающие с координатными. Находится минимум f (x) при последовательном движении по
n  1 направлениям поиска с помощью одного из методов одномерной минимизации.
При этом полученная ранее точка минимума берется в качестве исходной
для поиска по следующему направлению, а направление d n используется как
при первом d 0  d n , так и последнем поиске. Находится новое направление поиска, сопряженное с d n . Оно проходит через точки при первом и последнем
поиске. Заменяется d1 на d 2 , d 2 на d 3 и т.д. Направление d n заменяется со-
36
пряженным направлением, после чего повторяется поиск по ( n  1 ) направлениям, уже не содержащим старого направления d1 .
Рисунок 14 – Поведение метода Пауэлла
Для квадратичных функций последовательность n 2 одномерных поисков
приводит к точке минимума (при условии точности расчетов). Построение сопряженного направления при n  2 проиллюстрировано на рисунке 14. Проходит это направление через точки 1 и 3, здесь нужно пояснить, что одна итерация включает в себя шаги построенные по всем ( n  1 ) направлениям, то есть в
случае размерности n  2 это будут точки 1, 2, 3.
Алгоритм Пауэлла, приведенный в этом параграфе, может быть отнесен к
методам нулевого порядка, т.к. не использует производных в явном виде, но он
же может быть отнесен и к градиентным алгоритмам, т.к. неявно формирует
оценку матрицы Гессе и использует информацию о поведении производных.
Более того, как метод квадратичной аппроксимации целевой функции, он может даже рассматриваться как метод Ньютоновского типа. Метод, по существу,
занимает некоторое промежуточное положение, имея черты нескольких групп
методов, тем не менее изложим его в группе методов нулевого порядка, ссылаясь на то, что в явном виде нигде градиенты не используются.
Утверждение 2.1. Если используются сопряженные направления, то любая
квадратичная функция n переменных, имеющая минимум, может быть минимизирована за n шагов, по одному в каждом из сопряженных направлений. Порядок использования сопряженных направлений не имеет значения.
Так как методы прямого поиска не используют производные, то матрица
Гессе не известна и нужно другое правило определения подходящих сопряженных направлений.
37
Теорема 2.1. Если при начальной точке x 0 поиска в направлении S минимум f (x) находится в некоторой точке x a и, если при начальной точке поиска x1  x 0 в том же самом направлении S минимум f (x) находится в точке
x b , то при f ( x b )  f ( x a ) направление x b  x a  сопряжено с направлением S
по отношению к матрице Гессе функции f (x) .
Эта теорема может быть расширена на случай нескольких сопряженных
направлений.
Теорема 2.2. Если, начиная из x 0 , после использования p сопряженных
направлений (p < n) определяется точка x a и если, начиная из x1 , после использования этих же направлений определяется точка x b , функция f (x) ми-


нимизируется на каждом шаге, то вектор x b  x a сопряжен ко всем p направлениям.
Утверждение 2.2. Пусть S1 , S 2 , . . . , S n – некоторые направления оптимизирующего поиска функции f (x) в R n , A – матрица, столбцы которой есть S1 ,
S 2 , . . . , S n . Тогда определитель матрицы A принимает максимальное значение
тогда и только тогда, когда S1 , S 2 , . . . , S n сопряжены относительно матрицы
Гессе функции f (x) .
Идея алгоритма Пауэлла состоит в том, что на каждом этапе поиска определяется минимум квадратичной функции, которой аппроксимируется целевая
функция, вдоль каждого из сопряженных ко всем предыдущим (см. теоремы 2.1
и 2.2). Затем выбирается новая система направлений с использованием результатов поиска и утверждения 2.2.
Увеличению количества итераций могут способствовать некоторые факторы вычислительного характера, как например использование численных алгоритмов одномерного поиска. Результат их вычислений будет соотноситься с
точность работы алгоритма, задаваемой исследователем. Причем влиять будет
как высокая точность в алгоритме Пауэлла, так и более грубая (низкая) в работе
одномерного алгоритма.
Алгоритм
0
Шаг 1. Задать начальную точку x ( x1 , x2 ) . В качестве начальных линейно независимых ортогональных направлений выбираются координатные направления
38
1
 0
 0
 
 
 
0
1
 
 

d1    , d 2   ,  , d n    .


0
 
 
 
 0
 0
1
Положить y 0  x 0 ; k  0 ; i  0 ; d 0  d n ;
Шаг 2. Найти y i1  y i  ti d i , где шаг t i находится в результате поиска минимума функции f ( y i  ti d i ) по t i методами одномерной минимизации (методом
дихотомии, золотого сечения, Фибоначчи, квадратичной интерполяции и др.)
Шаг 3. Проверить выполнение условий:
а) если i  n , i  i  1 положить и перейти к шагу 2;
б) если i  n , проверить успешность поиска по первым n направле*
n
ниям. Если y  y , то поиск завершить: x  y , иначе положить
i  i  1 и перейти к шагу 2.
в) если i  n , проверить успешность поиска по n последним
n
0
направлениям. Если y
n1
 y n , поиск завершить: x*  y n1 , иначе пе-
рейти к шагу 4 для построения сопряженного направления.
Шаг 4. Положить x
k 1
 y n1 и проверить условие окончания:
*
k 1
k 1
k
а) если x  x   , то поиск завершить: x  x ;
б) иначе положить d 0  d n  y n1  y1 : (новое направление);
d i  d i1 (исключается старое направление).
Если при этом rang(d1 , ..., d n )  n то новая система направлений
линейно независима. В этом случае положить: d i  d i , k  k  1 , i  0 ,
y 0  y k 1 и перейти к шагу 2.
Если rang(d1 , ..., d n )  n , то новая система линейно зависима. Тогда следует продолжить поиск в старых направлениях. Для этого положить: d i  d i , k  k  1 , i  0 , y 0  y k 1 и перейти к шагу 2.
Далее приводится численный пример, демонстрирующий работу алгоритма сопряженных направлений.
39
Численные примеры нахождения минимума
с помощью метода Пауэлла
В качестве целевой функции квадратичного вида:
f ( x1 , x2 )  2( x1 ) 2  x1 x2  ( x2 ) 2 .
(2.13)
Численные результаты работы алгоритма сопряженных направлений
Пауэлла приведена в таблице 2.17 и на рисунке 15. Здесь указаны точки, полученные при движении вдоль сопряженных направлений, величина оптимального шага t i , рассчитанного методом одномерной оптимизации, в данном случае
был использован метод золотого сечения.
При анализе работы алгоритма видно, что самое удачное направление на
текущей итерации отбрасывается на каждой последующей, а новое перспективное ставится на место последнего. Является ли это целесообразным? Повидимому да, так как наилучшее направление уже выработало свой ресурс (это
обеспечивается движением с оптимальным шагом), а перспективное служило
для нахождения оптимального шага при одномерном поиске и, следовательно,
применять его на следующем шаге нецелесообразно.
Таблица 2.17 – Численные результаты работы алгоритма Пауэлла для
функции (2.13)
№ итерации
x1
x2
f ( x1 , x2 )
t
1
8
-4
48
-13
2
2
-4
12
-6
3
2
-1
3
3
4
0
0
0
-0,333
5
0
0
0
0
40
Рисунок 15 – Реализация метода Пауэлла для функции (2.13)
На количество итераций отразились точность одномерного поиска
(0.1) и более высокая точность самого метода Пауэлла (0.01).
Пауэлл доказал, что определитель матрицы направлений принимает
свое максимальное значение тогда и только тогда, когда направления сопряжены относительно матрицы Гессе. Он сделал вывод о том, что
направление полного перемещения должно заменять предыдущее только
в том случае, когда это направление увеличивает определитель матрицы
направлений, так как только тогда такой набор будет являться эффективным.
Метод Пауэлла очень чувствителен к способу построения сопряженных направлений, сильно зависит от точности одномерного поиска.
Сам Пауэлл рекомендовал использовать метод квадратичной интерполяции со специальной процедурой настройки параметров этого поиска. Тем
не менее численные исследования показали, что с размерностью выше 20
данный метод использовать не рекомендуется.
2.6. МЕТОДЫ СЛУЧАЙНОГО ПОИСКА
Адаптивный метод случайного поиска
Задается начальная точка x 0 . Каждая последующая точка находится по
формуле: x k 1  x k  t k  k , t k  0 – величина шага;  k – случайный вектор еди-
41
ничной длины, определяющий направление поиска; k – номер итерации. На
текущей итерации при помощи генерирования случайных векторов  k
Рисунок 16 – Поведение адаптивного алгоритма случайного поиска
получаются точки, лежащие на гиперсфере радиуса t k с центром в точке x k .
Если значение функции в полученной точке не меньше, чем в центре, шаг
считается неудачным (точки y1 , y 2 при поиске из x 0 ; y1 , y 3 при поиске из x1 .
Если число неудачных шагов из текущей точки достигает некоторого
числа M , дальнейший поиск продолжается из той же точки, но с меньшим шагом до тех пор, пока он не станет меньше заранее заданной величины R . Если
же значение функции в полученной точке меньше, чем в центре, шаг считается
удачным и в найденном направлении делается увеличенный шаг, играющий
роль ускоряющего шага (аналогично поиску по образцу в методе конфигураций). Если при этом значение функции снова меньше, чем в центре, направление считается удачным и дальнейший поиск продолжается из этой точки (точки
z 3  x1 при поиске из x 0 , z 4  x 2 при поиске из x1 ). Если же значение функции стало не меньше, чем в центре, направление считается неудачным и поиск
продолжается из старого центра (в точке y 2 при поиске из x1 функция меньше,
чем в x1 , а в точке z 2 уже не меньше, поэтому направление ( z 2  x1 ) неудачное) [10, 11]
42
Алгоритм
Шаг 1. Задать начальную точку x 0 , коэффициент растяжения   1, коэффициент сжатия 0    1, M – максимальное число неудачно выполненных
испытаний на текущей итерации, t0  1 – начальную величину шага, R – минимальную величину шага, N – максимальное число итераций. Положить
k  0, j  1 .
Шаг 2. Получить случайный вектор  j  (1j ,...,  nj )T , где  ij – случайная
величина, равномерно распределенная на интервале [-1;1].
Шаг 3. Вычислить y  x  t k
j
k
j
j
.
Шаг 4. Проверить выполнение условий:
а) если f ( y j )  f ( x k ) , шаг удачный. Положить z j  x k  ( y j  x k ) .
Определить, является ли текущее направление ( y j  x k ) удачным:
– если f ( z j )  f ( x k ) , направление поиска удачное. Положить
x k 1  z j , t k 1  tk , k  k  1 и проверить условие окончания. Если k  N , положить j  1 и перейти к шагу 2. Если k  N , поиск завершить: x*  x k ;
– если f ( z j )  f ( x k ) , направление поиска неудачное, перейти к шагу
5;
б) если f ( y j )  f ( x k ) , шаг неудачный и перейти к шагу 5.
Шаг 5. Оценить число неудачных шагов из текущей точки:
а) если j  M , следует положить j  j  1 и перейти к шагу 2;
б) если j  M , проверить условие окончания:
– если t k  R , процесс закончить: x*  x k , f ( x* )  f ( x k ) ;
– если t k  R , положить t k  t k , j  1 и перейти к шагу 2.
Замечания.
1. Величина  ij , распределенная равномерно на интервале [-1;1], генерируется обычно с помощью датчиков псевдослучайных чисел. Вырабатывается
случайная величина ij , равномерно распределенная на [0;1], а затем используется линейное преобразование ij  2ij  1 . Другой вариант генерирования
случайных точек через выбор величины угла. С помощью случайной величины
43
 j , равномерно распределенной в интервале [0;1], можно определить угол:
  360   далее перевести в радианы  
j
i
j
i ,
j
j
180
  . Координаты угла подста-
вить в выражение для определения точек y j , причем нормировка не требуется.
2. Шумер и Стейглиц [Schumer M.A., Steiglitz K.] рекомендуют следующие параметры алгоритма:   1,618 ;   0,618 ; M  3n . При   1 точка z j
на шаге 4 совпадает с y j , т.е. аналог поиска по образцу не производится.
Начальный шаг t0  R можно задать произвольно.
Рисунок 17 – Разброс случайных точек
3. Если выполнено условие окончания t k  R , то в качестве ответа можно
использовать любую точку внутри шара радиусом t k и центром в точке x k .
4. Есть варианты алгоритма, содержащие элементы обучения, при котором направления убывания функции становятся более вероятными, а другие –
нет.
На рисунке представлено графическое изображение поведения алгоритма
с нанесенными вариантами случайных точек. Можно заметить увеличение радиуса, пока поиск ведется в удачном направлении, и его уменьшении, когда
точка минимума оказывается внутри сферы.
Численные исследования показывают очень разную скорость сходимости,
в целом метод медленно сходится, однако очень хорошо подходит для любого
самого сложного рельефа.
44
В качестве примера приведем численные данные расчетов точки минимума для двух функций параболического (2.14) и общего вида (2.15):
f1 ( x1 , x2 )  2 x12  x1 x2  x22 ,
(2.14)
x12
40
 x22 
(2.15)
f 2 ( x1 , x2 )  e   1 .
10


Начальные данные сведены в таблицу, обозначения приняты в соответствии с алгоритмом:
Таблица 2.18 – Начальные данные для алгоритма случайного поиска
 1
0   1
M
tk
R
N
x0
1,5
0,5
3
1
0,01
10
(4;5)
В таблице указаны значения центров сфер, ответом была принята точка
последнего центра сферы.
Таблица 2.19 – Результат работы адаптивного алгоритма случайного поиска
№ итерации
x1
x2
1
3,4467
3,6057
2
1,7781
2,0963
3
-0,9982
0,1779
4
-0,0043
-0,0124
5
-0,0031
0,0023
В данном случае количество итераций небольшое, однако при каждом
новом запуске метода для одних и тех же исходных данных количество итераций может весьма существенно меняться, если говорить о данном случае, до
нескольких десятков.
45
Рисунок 18 – Реализация работы адаптивного алгоритма случайного поиска
Полученный график показан на рисунке 18. Можно наблюдать рост радиуса сфер в начале работы алгоритма и существенное его уменьшение в области
минимума.
Рисунок 19 – Иллюстрация случайного характера поведения алгоритма
46
Второй пример (рисунок 19) иллюстрирует как раз особенности поведения алгоритма, которое связано с определением "случайный".
На графике очень хорошо видно влияние случайных чисел на выбор
направления движения в область оптимума, что явилось причиной изгиба траектории и, как следствие, увеличение числа итераций. Следует также отметить,
что исследовалась на минимум функция (2.15). Функция f 2 ( x1 , x2 ) имеет области сильно изогнутого рельефа и участки пологие, где искривления поверхности незначительные или медленные. Начальные данные аналогичны тем, что
приведены в предыдущем примере, только начальная точка x 0  (8,8) .
Метод случайного поиска с возвратом при неудачном шаге
Задается начальная точка x 0 . Каждая последующая точка находится по
формуле:
x k 1  x k  tk  k ,
(2.16)
где t k  0 – величина шага;  k – случайный вектор единичной длины, определяющий направление поиска; k – номер итерации. На текущей итерации при
помощи генерирования случайных векторов  k получаются точки, лежащие на
гиперсфере радиуса t k с центром в точке x k . Если значение функции в полученной точке не меньше, чем в центре, шаг считается неудачным (точки y1 , y 2
при поиске из x 0 ; y1 , y 2 , y 3 при поиске из x1 .
Рисунок 20 – Стратегия поиска минимума методом случайного поиска с возвратом при неудачном шаге
47
Если число неудачных шагов из текущей точки достигает некоторого
числа M , дальнейший поиск продолжается из той же точки, но с меньшим шагом до тех пор, пока он не станет меньше заранее заданной величины R . Если
же значение функции в полученной точке меньше, чем в центре, шаг считается
удачным и дальнейший поиск продолжается из этой точки.
Алгоритм
Шаг 1. Задать начальную точку x 0 , коэффициент сжатия 0    1, M –
максимальное число неудачно выполненных испытаний на текущей итерации,
t 0 – начальную величину шага, R – минимальную величину шага, N – максимальное число итераций. Положить k  0, j  1 .
Шаг 2. Получить случайный вектор  j  (1j , ...,  nj )T , где  ij – случайная
величина, равномерно распределенная на интервале [-1;1].
Шаг 3. Вычислить y  x  t k
j
k
j
j
.
Шаг 4. Проверить выполнение условий:
а) если f ( y j )  f ( x k ) , шаг удачный. Положить x k 1  y j , t k 1 t k ,
k  k  1 и проверить условие окончания. Если k  N , положить j  1 и перейти к шагу 2. Если k  N , поиск завершить: x*  x k .
б) если f ( y j )  f ( x k ) , шаг неудачный и перейти к шагу 5.
Шаг 5. Оценить число неудачных шагов из текущей точки:
а) если j  M , следует положить j  j  1 и перейти к шагу 2;
б) если j  M , проверить условие окончания:
– если t k  R , процесс закончить: x*  x k , f ( x* )  f ( x k ) ;
– если t k  R , положить t k  t k , j  1 и перейти к шагу 2.
Метод наилучшей пробы
Задается начальная точка x 0 . Каждая последующая точка находится по
формуле:
x k 1  x k  tk  k ,
где t k  0 – величина шага;  k – случайный вектор единичной длины, определяющий направление поиска; k – номер итерации. На текущей итерации при
48
помощи
генерирования
случайных
векторов
k
получается
M точек
y1 , y 2 , ...y M , лежащие на гиперсфере радиуса t k с центром в точке x k . Среди
полученных точек выбирается одна y m , в которой значение функции наименьшее. Если в выбранной точке значение функции меньше, чем в центре, то дальнейший поиск продолжается из этой точки. Иначе поиск продолжается из старого центра, но с меньшим шагом до тех пор, пока он не станет меньше заранее
заданной величины R .
Рисунок 21 – Стратегия поиска минимума методом наилучшей пробы
Алгоритм
Шаг 1. Задать начальную точку x 0 , коэффициент сжатия 0    1, M –
число испытаний на текущей итерации, t0  1 – начальную величину шага, R –
минимальную величину шага, N – максимальное число итераций. Положить
k  0, j  1 .
Шаг 2. Получить M реализаций случайного вектора  j  (1j , ...,  nj )T ,
где j  1, ..., М ,  ij – случайная величина, равномерно распределенная на интервале [-1;1].
Шаг 3. Вычислить y  x  t k
j
k
j
j
49
, j  1, ..., М .
Шаг 4. Найти y m из условия y m  min f ( y j ) .
1 j  M
Проверить выполнение условий:
а) если f ( y m )  f ( x k ) , шаг удачный. Положить x k 1  y m , t k 1 t k ,
k  k  1 и проверить условие окончания. Если k  N , положить j  1 и перейти к шагу 2. Если k  N , поиск завершить: x*  x k .
б) если f ( y m )  f ( x k ) , шаг неудачный и перейти к шагу 5.
Шаг 5. Оценить число неудачных шагов из текущей точки:
– если t k  R , процесс закончить: x*  x k , f ( x* )  f ( x k ) ;
– если t k  R , положить t k  t k , j  1 и перейти к шагу 2.
Замечания.
1. Данный метод позволяет преодолевать локальные экстремумы при поиске глобального.
2. К недостаткам можно отнести тот факт учитывается только самая
удачная точка, а остальная информация остается невостребованной. Хотя она
содержит знание о поведении целевой функции.
3. Существует модификация метода, которая учитывает информацию, содержащуюся во всех сгенерированных точках и носит название алгоритма
статистического градиента. Для каждой из M реализаций 1 ,  2 , ...,  M случайного вектора, полученных в точке x k , вычисляются разности
f j  f ( x k  tпр k )  f ( x k ) ,
где t пр – пробное значение шага. В качестве направления поиска используют
вектор статистического антиградиента
dk
1 M j j
d     f или вектор k
t пр j 1
d
k
.
Далее алгоритм решения совпадает с описанным выше.
Алгоритмы случайного поиска оказываются очень полезны при сложной
структуре целевой функции, когда невозможно заранее установить какие-либо
ее свойства, позволяющие правильно выбирать направления поиска. Методы
случайного поиска позволяют оптимизировать любую функцию хотя и с различной эффективностью, иногда очень низкой, в смысле скорости сходимости.
Чаще всего эти методы применяют в комбинации с одним или несколькими алгоритмами других поисковых процедур.
50
3. МЕТОДЫ ПЕРВОГО ПОРЯДКА
Группа методов, использующая для поиска безусловного экстремума
производные первого порядка, объединена под общим названием методов первого порядка или методов спуска. Использование методов первого порядка
возможно, когда целевая функция непрерывно дифференцируема и производные можно выразить аналитически. Скорость сходимости градиентных методов
выше, так как при поиске учитываются производные, которые характеризуют
направление наиболее быстрого убывания функции [1,2,4].
Постановка задачи поиска безусловного экстремума может быть сформулирована следующим образом.
Пусть дана функция f (x) , ограниченная снизу на множестве R n и имеющая непрерывные частные производные во всех точках.
Требуется найти локальный минимум x * функции f (x) на множестве допустимых решений, т.е.
f ( x* )  min f ( x) .
(2.17)
Ниже приводятся наиболее широко известные алгоритмы градиентного
поиска. Численные примеры ярко иллюстрируют локальный характер алгоритмов. Несколько алгоритмов содержат этапы одномерной оптимизации по шагу.
Автор не приводит этих алгоритмов, давая возможность читателю освоить их
самостоятельно.
3.1. МЕТОД ГРАДИЕНТНОГО СПУСКА
С ПОСТОЯННЫМ ШАГОМ
Стратегия решения задачи состоит в построении последовательности точек {x k }, k  0,1, ... таких, что f ( x k 1 )  f ( x k ), k  0,1, ... . Точки последовательности {x k } вычисляются по правилу:
x k 1  x k  tk f ( x k ), k  0,1,... ,
(3.1)
0
где точка x задаѐтся пользователем; f ( x k ) – градиент функции f (x) вы-
численный в точке x k ; величина шага t k задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, что
контролируется путем проверки выполнения условия: f ( x k 1 )  f ( x k )  0 или
51
2
f ( x k 1 )  f ( x k )   f ( x k ) , 0    1 . Построение последовательности {x k }
заканчивается в точке
2
x k , для которой f ( x k )  1 , где 1
– заданное малое
положительное число, или k  M , где M – предельное число итераций, или
при двукратном одновременном выполнении двух неравенств x k 1  x k   2 ,
f ( x k 1 )  f ( x k )   2 , где  2 – малое положительное число. Далее исследуется
вопрос о том, может ли полученная точка быть принята как точка минимума
целевой функции [4,6].
Алгоритм:
Шаг 1: Выбираем начальную точку x 0 , 0    1, 1  0 ,  2  0 , M – предельное число итераций. Найти градиент функции в произвольной точке
 f ( x)
f ( x) 

f ( x )  
, ...,

x

x

1
n 
T
k
.
x xk
Шаг 2: Положить k  0 .
Шаг 3: Вычислить f ( x k ) .
2
Шаг 4: Проверить выполнение критерия окончания f ( x k )  1 :
а) если критерий выполнен, расчет закончен, x*  x k ;
б) если критерий не выполнен, то перейти к шагу 5.
Шаг 5: Проверить выполнение неравенства k  M :
а) если неравенство выполнено, то расчет окончен x*  x k ;
б) если нет, то перейти к шагу 6.
Шаг 6: Задать величину шага
tk .
k 1
k
k
Шаг 7: Вычислить x  x  t k f ( x ) .
Шаг 8: Проверить выполнение условий:
2
f ( x k 1 )  f ( x k )  0 или f ( x k 1 )  f ( x k )   f ( x k ) :
а) если условие выполнено, то перейти к шагу 9;
б) если условие не выполнено, положить t k 
tk
и перейти к шагу 7.
2
Шаг 9: Проверить выполнение условий:
x k 1  x k   2 , f ( x k 1 )  f ( x k )   2 :
52
а) если оба условия выполнены при текущем значении k и k  k  1 , то расчет
окончен, x*  x k 1 .
б) если хотя бы одно из условий не выполнено, положить k  k  1 и перейти к
шагу 3.
Геометрическая интерпретация поведения алгоритма проиллюстрирована
на рисунке 21 при n  2 .
Рисунок 21 – Поиск минимума методом градиентного спуска с постоянным шагом
Анализ сходимости метода подробно описан в [1], сформулированы
условия нахождения глобального экстремума. Последовательность точек {x k }
сходится к стационарной точке x * , где f ( x* )  0 . Следовательно, найденная в
результате работы алгоритма точка x * нуждается в дополнительном исследовании с целью ее классификации.
Процедура решения задачи
1. Используя алгоритм градиентного спуска с постоянным шагом, найти
точку x k , в которой выполнен по крайней мере одно условие окончания расчетов.
2. Провести анализ точки x k с целью установить, является ли точка x k
найденным приближенным решением задачи. Если целевая функция имеет непрерывные вторые частные производные, то есть f ( x)  С
верить, является ли
2
,
то следует про-
матрица Гессе положительно определенной, т.е.
H ( x k )  0 . Если неравенство верно, тогда точка x k является искомой точкой
53
минимума. Если f ( x)  C1 , то следует провести проверку функции f (x) на
выпуклость в окрестности точки x k . Критерий проверки выпуклости в этом
случае таков: функция f (x) выпукла (строго выпукла) тогда и только тогда,
когда
f ( x  y)  f ( x)  (f ( x), y), x, y из
окрестности
xk
точки
( f ( x  y)  f ( x)  (f ( x), y)) . Если функция f (x) выпукла (строго выпукла), то x k есть найденное приближение точки x * .
Численный пример работы метода градиентного спуска
с постоянным шагом
Целевая функция была взята в виде: f ( x1 , x2 )  x12  x1 x2  x22 , точность
вычислений
  1   2  0.001 , начальная точка x 0  (0.5,1) , шаг t0  0.5 ,
предельное число итераций М=10. В результате работы алгоритма была получена точка x * =(-0,022, 0,055). Поведение алгоритма отражено на рисунке 22.
Решение было найдено за 8 итераций.
Рисунок 22 – Результат работы алгоритма градиентного спуска с постоянным шагом
Вторая функция была задана уравнением:
x12
40
 x22 
f 2 ( x1 , x2 )  e   1 .
 10 
54
(3.2)
Таблица 3.1 – Начальные значения для работы метода градиентного спуска с постоянным шагом
Начальная
точка
1  0
2  0
(8;4)
0,1
0,15
Предельное
число итераций M
10
Величина шага t 0
2,5
Таблица 3.2 – Результат вычислений методом градиентного спуска с постоянным шагом
№ итерации
1
2
3
x1
-4,877
0,082
0,072
x2
-5,906
-0,552
-0,276
Рисунок 23 – Графическое представление работы градиентного алгоритма с постоянным шагом
В таблице 3.2 представлены точки, полученные в результате работы алгоритма, интересно, что их количество (то есть количество итераций) довольно
мало, метод сошелся быстро. В сравнении с предыдущим методом здесь существенно увеличен шаг t 0 .
Следующая иллюстрация демонстрирует ситуацию, довольно часто
встречающуюся при поиске минимума градиентным алгоритмом, его скачкообразное поведение по берегам оврага.
55
Таблица 3.3 – Начальные значения для градиентного метода с постоянным шагом
Исходная
точка
Предельное
количество
шагов, M
Норма, 1
Норма,
(7, 5)
10
0.01
2
Величина
шага, t k
Величина
уменьшения
шага, t k
0.015
0.5
0.75
x2
Рисунок 24 – Случай преждевременно остановки градиентного метода поиска
минимума с постоянным шагом
Здесь была взята квадратичная функция с неярко выраженной овражной
структурой. Точка минимума имеет координаты x*  (0, 0) .
Результатом стала точка: x*  (0.195, 0.287 ) f ( x* )  0.214 , f ( x* )  1.264 .
Положение начальной точки оказало влияние на поведение алгоритма,
который не смог сойтись за указанное ограничение по количеству итераций, в
результате решение получилось достаточно грубым. Отсюда можно сделать
вывод о том, что метод чувствителен к выбору начальной точки.
56
3.2. МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКА
Стратегия поиска состоит в построении последовательности точек
{x k }, k  0,1, ... таких, что f ( x k 1 )  f ( x k ), k  0,1, ... . Точки последовательности {x k } вычисляются по правилу:
x k 1  x k  tk f ( x k ), k  0,1,... ,
0
где точка x задаѐтся пользователем; величина шага
(3.2)
t k определяется для каж-
дого значения k из условия:
(t k )  f ( x k  t k f ( x k ))  min .
(3.3)
tk
Оптимизация по шагу основана на использовании численных методов одномерной оптимизации, когда ищется
min (tk )  min f ( x k  t k f ( x k )) .
tk [ a ,b ]
(3.4)
tk [ a ,b ]
Границы интервала поиска [a, b] задаются пользователем. При этом степень близости найденного значения
tk
к оптимальному значению
tk
*
, удовле-
d(t k )
d 2 (t k )
творяющему условиям
 0, зависит от задания интервала
 0,
dtk
dtk2
[a, b] и точности методов одномерной оптимизации.
Построение последовательности {x k } заканчивается в точке
x k , для ко-
2
торой f ( x k )  1 , где 1 – заданное малое положительное число, или
k  M , где M – предельное число итераций, или при двукратном одновременном выполнении двух неравенств x k 1  x k   2 , f ( x k 1 )  f ( x k )   2 , где  2 –
малое положительное число. Далее требуется провести дополнительные исследования, чтобы ответить на вопрос о том, может ли полученная точка быть
принята как найденное приближение точки локального минимума x * целевой
функции [2,3].
57
Алгоритм
Шаг 1: Выбираем начальную точку x 0 , 1  0 ,  2  0 , M – предельное число
итераций. Найти градиент функции в произвольной точке
 f ( x)
f ( x) 

f ( x )  
,...,

x

x

1
n 
T
k
.
x xk
Шаг 2: Положить k  0 .
Шаг 3: Вычислить f ( x k ) .
2
Шаг 4: Проверить выполнение критерия окончания f ( x k )  1 :
а) если критерий выполнен, расчет закончен, x*  x k ;
б) если критерий не выполнен, то перейти к шагу 5.
Шаг 5: Проверить выполнение неравенства k  M :
а) если неравенство выполнено, то расчет окончен x*  x k ;
б) если нет, то перейти к шагу 6.
Шаг 6: Вычислить величину шага t k* из условия
(t k )  f ( x k  t k f ( x k ))  min .
tk
Рисунок 25 – Поведение алгоритма наискорейшего градиентного спуска
Шаг 7: Вычислить x k 1  x k  tk f ( x k ) .
Шаг 8: Проверить выполнение условий:
58
x k 1  x k   2 ,
f ( x k 1 )  f ( x k )   2
а) если оба условия выполнены при текущем значении k и k  k  1 , то
расчет окончен x*  x k 1 .
б) если хотя бы одно из условий не выполнено, положить k  k  1 и перейти к шагу 3.
Скорость сходимости подробно исследовалась в работах [1,4], при определенных условиях метод сходится со скоростью геометрической прогрессии,
для сильно выпуклых функции с применением данного алгоритма может быть
достигнут глобальный минимум.
Для реализации метода наискорейшего градиентного спуска использовалась функция (2.4). На работе алгоритма сказывается более сложное выражение
для градиента, здесь овражность имеет более сложный рельеф.
Рисунок 26 – Результат поиска минимума методом наискорейшего градиентного спуска
59
Алгоритм нашел решение за 8 итераций, в целом показав высокую скорость сходимости, особенно если учесть точность 1   2  10 6 . Точка минимума x * =(0.01692;2.00331e-07).
3.3. ГРАДИЕНТНЫЙ МЕТОД ПОКООРДИНАТНОГО СПУСКА
Стратегия решения задачи состоит в построении последовательности точек {x k }, k  0,1,... таких, что f ( x k 1 )  f ( x k ) , k  0,1,... . Точки последовательности x k вычисляются по циклам в соответствии с правилом:
 f ( x) 
x jk1  x jk  t k 
 ek 1 ,
(3.5)

 x  x x jk
где j – номер цикла вычислений; j  0,1, ..., k – номер итерации внутри цикла
k  0,1, ..., n  1 ; ek 1 , k  0,1, ..., n  1 – единичный вектор, ( k  1 )-я проекция которого равна 1; точка x 00 задается пользователем, величина шага t k выбирается
из условия:


 f ( x) 

f  x jk  t k 
 ek 1   f ( x jk )  0 ,
 x 



 x x jk


или
2
f ( x jk1 )  f ( x jk )   f ( x jk ) .
(3.6)
Если выбранное условие при текущем t k не выполняется, шаг уменьша-
 f ( x) 

ется вдвое и точка x jk  t k 
 ek 1 вычисляется заново. Заметим, что
 x 

 x x jk
при фиксированном j за одну итерацию с номером k изменится только одна
проекция точки x jk , имеющая номер k  1 , а в течение всего цикла с номером j,
т.е. начиная с k=0 и кончая k  n  1, изменяются все n проекций точки x j 0 .
После этого точке x jn присваивается номер x j 1,0 и она берется за начальную
точку для вычислений в j  1 цикле. Расчет заканчивается в точке x jk , при выполнении по крайней мере одного из трех критериев окончания счета:
f ( x jk )  1 , или j  M , или двукратного выполнения неравенств
x jk1  x jk   2 , f ( x jk1 )  f ( x jk )   2 .
60
(3.7)
Полученные в результате вычислений точки могут быть записаны как
элементы последовательности x l , где l  n  j  k – порядковый номер точки,
 
 
т.е. x  {x  x , x  x ,..., x n  x 0 n  x10 , x n1  x11, x n2  x12 ,...} .
l
0
00
1
01
Алгоритм
Шаг 1. Задать x 00 ,   0, 1  0,  2  0 , предельное число М, циклов счета,
кратное n, где n – размерность вектора x. Найти градиент f (x) .
Шаг 2. Задать номер цикла j=0.
Шаг 3. Проверить выполнение неравенства j  M :
а) если неравенство выполнено, то x*  x jk , расчет окончен;
б) если нет, то перейти к шагу 4.
Шаг 4. Задать k=0.
Шаг 5. Проверить условие k  n  1 :
а) если k  n  1 , то перейти к шагу 6;
б) если k=n, то положить j=j+1 и
Шаг 6. Вычислить f ( x jk ).
x j 1,k  x jn
и перейти к шагу 3.
Шаг 7. Проверить выполнение критерия окончания f ( x jk )  1 :
а) если критерий выполнен, то x*  x jk , расчет окончен;
б) если нет, то перейти к шагу 8.
Шаг 8. Задать
tk .
 f ( x) 

 ek 1 .
 x 

 x x jk
Шаг 9. Вычислить точку x jk 1 : x jk1  x jk  t k 
Шаг 10. Проверить выполнение условия
2
f ( x jk1 )  f ( x jk )  0 или f ( x jk1 )  f ( x jk )   f ( x jk ) .
а) если условие выполнено, то перейти к шагу 11;
б) если нет, то положить t k 
tk
и перейти к шагу 9.
2
Шаг 11. Проверить выполнение условий
x jk1  x jk   2 , f ( x jk1 )  f ( x jk )   2 ;
а) если оба условия выполнены в двух последних циклах с номерами j и
j-1, то расчет окончен, x*  x jk1 ;
б) Если хотя бы одно из условий не выполнено, то положить k=k+1 и перейти к шагу 5.
61
Рисунок 27 – Поведение метода покоординатного градиентного спуска
Найденная в результате работы алгоритма точка нуждается в дополнительном исследовании для определения ее типа [6,9].
Ниже приведены результаты численного моделирования, иллюстрирующие поведение алгоритма. Целевая функция имела параболический вид, унимодальная, точка минимума находится в начале координат.
Таблица 3.4 – Начальные данные для расчетов по методу покоординатного градиентного спуска
Началь
ная
точка
Малое положительное число
x0
0
(5;5)
0,01
Малое положительное число
1  0
0,1
Малое положительное число
2  0
0,15
Предельное
число M
циклов
счѐта
10
n – раз-
Велимерность чина
вектора
шага
x
tk
2
1
Таблица результатов содержит значения точек, для нахождения минимума потребовалось 2 итерации.
Таблица 3.5 – Результаты расчетов методом покоординатного градиентного спуска
№ итераx1
x2
ции
1
-1,25
5
1
-1,25
0,625
2
0
0,625
2
0
0
62
Рисунок 28 – Поиск по методу покординатного градиентного спуска
График демонстрирует весьма характерное поведение алгоритма, в котором поиск минимума осуществляется вдоль координатных осей.
3.4. МЕТОД НАИСКОРЕЙШЕГО ПОКООРДИНАТНОГО
ГРАДИЕНТНОГО СПУСКА
(ГАУССА-ЗЕЙДЕЛЯ)
Стратегия метода Гаусса-Зейделя (Gauss-Seidel) решения задачи нахождения минимума состоит в построении последовательности точек
{x k }, k  0,1, ... таких, что f ( x k 1 )  f ( x k ), k  0,1, ... . Точки последовательно-
 
сти x k вычисляются по циклам в соответствии с правилом:
 f ( x) 

x jk1  x jk  t k 
 ek 1 ,
 x 

 x x jk
(3.7)
где j – номер цикла вычислений; j  0,1,...; k – номер итерации внутри цикла
k  0,1, ..., n  1 ; ek 1 , k  0,1, ..., n  1 – единичный вектор, ( k  1 )-я проекция
которого равна 1; точка x 00 задается пользователем, величина шага t k выбирается из условия:
 jk

 f ( x) 



(t k )  f x  t k
 ek 1   min .
 x  jk
tk



 x x


63
(3.8)
Эта задача является задачей одномерной минимизации функции (t k ) и может
 (t k )
(t k )
быть решена либо с использованием условий
 0 , либо чис 0,
2
t k
t k
ленно с использованием методов одномерной минимизации, как задача
(t k )  min .
2
tk [ a ,b ]
Рисунок 29 – Поиск минимума методом Гаусса-Зейделя
(t k )
 0 имеет высокую степень и корни его трудно
t k
определить, можно аппроксимировать функцию (t k ) полиномом P(t k ) второй
Если уравнение
P(t k )
 2 P(t k )
или третьей степени и определить t из условий:
 0,
 0.
2
t k
t k
При численном решении задачи определения величины шага степень близости найденного значения t k к оптимальному значению t k* , удовлетворяюще*
k
 2 (t k )
(t k )
 0,
му условиям
 0 , зависит от задания интервала [a, b] и
2
t k
t k
точности метода одномерной оптимизации.
Заметим, что при фиксированном j за одну итерацию с номером k изменится только одна проекция точки x jk , имеющая номер k  1 , а в течение всего
цикла с номером j, т.е. начиная с k=0 и кончая k  n  1 , изменяются все n проекций точки x j 0 . После этого точке x jn присваивается номер x j 1,0 и она берется за начальную точку для вычислений в j  1 цикле [1,3,6].
64
Расчет заканчивается в точке x jk , при выполнении по крайней мере одного из трех критериев окончания счета: f ( x jk )  1 , или j  M , или двукратного выполнения неравенств
x jk1  x jk   2 , f ( x jk1 )  f ( x jk )   2 .
Здесь 1 , 2 – малые положительные числа, задаваемые пользователем,
характеризующие точность вычислений, M – предельное число циклов итераций.
Полученные в результате вычислений точки могут быть записаны как
элементы последовательности x l , где l  n  j  k – порядковый номер точки,
 
 
т.е. x l  {x 0  x 00 , x1  x 01,..., x n  x 0 n  x10 , x n1  x11, x n2  x12 ,...} .
Алгоритм
Шаг 1. Задать x 00 , 1  0,  2  0 , предельное число М, циклов счета, кратное n, где n – размерность вектора x. Найти градиент f (x) .
Шаг 2. Задать номер цикла j=0.
Шаг 3. Проверить выполнение неравенства j  M :
а) если неравенство выполнено, то x*  x jk , расчет окончен;
б) если нет, то перейти к шагу 4.
Шаг 4. Задать k=0.
Шаг 5. Проверить условие k  n  1:
а) если k  n  1 , то перейти к шагу 6;
б) если k=n, то положить j=j+1 и
Шаг 6. Вычислить f ( x jk ).
x j 1,k  x jn
и перейти к шагу 3.
Шаг 7. Проверить выполнение критерия окончания f ( x jk )  1 :
а) если критерий выполнен, то x*  x jk , расчет окончен;
б) если нет, то перейти к шагу 8.
Шаг 8. Вычислить t k из условия:


 f ( x) 

(t k )  f  x jk  t k 
 ek 1   min .
 x  jk
tk



 x x


 f ( x) 

Шаг 9. Вычислить точку x jk 1 : x jk1  x jk  t k* 
 ek 1 .
 x 

 jk
x x
Шаг 10. Проверить выполнение условий
65
x jk1  x jk   2 , f ( x jk1 )  f ( x jk )   2 ;
а) если оба условия выполнены в двух последних циклах с номерами j и
j-1, то расчет окончен, x*  x jk1 ;
б) Если хотя бы одно из условий не выполнено, то положить k=k+1 и перейти к шагу 5.
Фактически задачей нахождения оптимального шага решается задача
отыскания минимальной по своему значению линии уровня в направлении по
конкретной координате.
Функция: f ( x1 , x2 )  10 x12  x1 x2  10 x22  2 x1  2 x2  7
(3.9)
Начальные координаты (20,15) . Точность   0.01 .
Рисунок 30 – Результат поиска минимума методом Гаусса-Зейделя
Численные примеры иллюстрируют поведение алгоритма на разных рельефах, и рисунок 30 содержит изображение линий уровня квадратичной
функции, не имеющей овражной структуры, и результат поиска минимума методом Гаусса-Зейделя.
Таблица 3.7 – Численные результаты методом Гаусса-Зейделя для функ-15
ции (3.9)
№ итерации
x1jk
x2jk
f ( x1jk , x 2jk ) Шаг
tk
1
1,164
-15
2280
0,05
1
1,164
-0,205
18,8
0,05
66
Окончание таблицы 3.7.
№ итерации
f ( x1jk , x 2jk ) Шаг
tk
x1jk
x2jk
2
0,128
-0,205
7,71
0,05
2
0,128
0,089
6,82
0,05
3
0,096
0,089
6,8
0,05
3
0,096
0,095
6,8
0,05
Точность в примере была одинакова для различных 1 , 2 . Шаг найден
методом золотого сечения, точность метода 0.1.
Метод сошелся за 3 итерации. Таблица 3.7 содержит численные расчеты
методом Гаусса-Зейделя. В ней содержатся расчеты по каждой координате,
итерация заканчивается, когда заканчивается внутренний цикл: перебор всех
координатных направлений. Поэтому в указанной таблице 6 измерений. Скорость сходимости метода подробно исследовалась в работах [2,3]. Минимум
достигается в точке x*  (0.096 , 0.095 ) , f ( x* )  6.8 .
3.5. МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ
(ФЛЕТЧЕРА-РИВСА)
Стратегия метода Флетчера-Ривса [Fletcher R., Reeves C.M.] состоит в поk
строении последовательности точек {x }, k  0,1,... таких, что f ( x k 1 )  f ( x k ) ,
k  0,1,... . Точки последовательности x k  вычисляются по циклам в соответ-
ствии с правилом:
x k 1  x k  tk d k , k  0,1, ...;
d k  f ( x k )  k 1d k 1 ;
d 0  f ( x 0 );
k 
f ( x k )
f ( x
67
k 1
)
(3.10)
2
2
.
(3.11)
t k определяется на каждой
Точка x 0 задается пользователем, величина шага
итерации из условия
(t k )  f ( x k  t k d k )  min .
tk [ a ,b ]
Решение задачи одномерной минимизации может осуществляться либо из
(t k )
 2 (t k )

0
условия
,
 0 , либо численно с использованием методов од2
t k
t k
номерной минимизации (t k )  min .
tk [ a ,b ]
При численном решении задачи определения величины шага степень близости найденного значения t k к оптимальному значению t k* , удовлетворяюще-
 2 (t k )
(t k )
му условиям
 0 , зависит от задания интервала [a, b] и
 0,
2
t k
t k
точности метода одномерной оптимизации.
Вычисление величины  k 1 по формуле (3.9) обеспечивает для квадратичной
формы
n
n
f ( x)   aij xi x j
построение
последовательности
Н-
i 1 j 1
сопряженных
направлений
d 0 , d 1 , ..., d k ,...,
для
которых
d j Hd i  0 ,
i, j  0,1, ..., i  j . При этом в точках последовательности x k  градиенты
функции f (x) взаимно перпендикулярны, т.е. f ( x k 1 ), f ( x k )   0 ,
k  0,1, ....
Для квадратичных функций f (x) с матрицей H  0 метод ФлетчераРивса является конечным и сходится за число шагов, не превышающее размерность пространства переменных [3,4,10].
При минимизации неквадратичных функций метод не является конечным,
при этом отметим наличие погрешностей вычислений в решении задачи нахождения оптимального шага. Это может стать причиной нарушения условия перпендикулярности векторов-градиентов и H -сопряженности направлений. Для
неквадратичных функций используют алгоритм Полака-Рибьера [Polak E.,
Ribiere G], когда в величина  k 1 вычисляется следующим образом:
 k 1
 f ( x k ), [f ( x k )  f ( x k 1 )]
, k  J;

k 1 2

f ( x )

0,
k  J,

68
(3.12)
где J  {0, n, 2n, ...}. В отличие от алгоритма Флетчера-Ривса алгоритм Полака-Рибьера предусматривает использование итерации наискорейшего градиентного спуска через каждые n шагов [7,8]. Построение последовательности {x k }
заканчивается в точке, для которой выполняется неравенство:
f ( x k 1 )  1 ,
где 1 – заданное число, или при k  M , M – предельное число итераций, или
при двукратном одновременном выполнении двух неравенств:
x k 1  x k   2 , f ( x k 1 )  f ( x k )   2 .
где  2 – малое положительное число. Вопрос о том, может ли точка x рассматриваться как найденное приближение истинной точки минимума, решается
путем проведения дополнительного исследования.
k
Алгоритм
Шаг 1. Задать x 0 , 1  0,  2  0 , предельное число М. Найти градиент
f (x) .
Шаг 2. Задать номер цикла k=0.
Шаг 3. Вычислить f ( x k ) .
Шаг 4. Проверить выполнение критерия окончания работы:
f ( x k 1 )  1 :
а) если критерий выполняется, то расчет окончен. Принять x  x ;
б) если нет, то перейти к шагу 5.
Шаг 5. Проверить условие k  M :
*
k
а) если неравенство выполняется, то расчет окончен и x  x ;
б) если нет, то при k=0 перейти к шагу 6, а при k  1 перейти к шагу 7.
*
k
0
0
Шаг 6. Определить d  f ( x ); перейти к шагу 9.
Шаг 7. Определить:




 f ( x k ), [f ( x k )  f ( x k 1 )]

f
(
x
)
,
k

J
;



k 1 2
;  k 1  
k 

f
(
x
)
2
.
k 1
f ( x )


0,
k  J ,


k
2
Шаг 8. Вычислить d  f ( x )  k 1d
k
k
Шаг 9. Вычислить t k* из условия:
69
k 1
;.
(t k )  f ( x k  t k d k )  min .
tk [ a ,b ]
Шаг 10. Вычислить точку
x k 1 : x k 1  x k  tk *d k .
Шаг 11. Проверить выполнение условий
x k 1  x k   2 , f ( x k 1 )  f ( x k )   2 ;
а) если оба условия выполнены в двух последних циклах с номерами k и
k  1 , то расчет окончен, x  x
*
k 1
;
б) Если хотя бы одно из условий не выполнено, то положить k  k  1 и
перейти к шагу 3.
Рисунок 31 – Поведение алгоритма Флетчера-Ривса
Метод сопряженных градиентов обеспечивает сходимость не более чем за
n шагов для квадратичных функций с неотрицательно определенной матрицей
Гессе (вторых частных производных). Доказана сходимость нормы градиента
целевой функции к нулю для ограниченных снизу функций, удовлетворяющих
условию Липшица в алгоритме Полака-Рибьера.
Ниже приводятся результаты численного моделирования поиска минимума методом сопряженных градиентов. В первом случае минимизирована
функция
f ( x1 , x2 )  4 x1  5x2  4 x1 x2  2 x1  2 x2  10 .
2
2
70
(3.13)
Рисунок 32 – Результат работы алгоритма сопряженных градиентов
Начальная точка (20,-20).
Таблица 3.8 – Результаты расчетов методом Флетчера-Ривса для минимизации функции
№ итерации
f (x)
1
2
3
4
5
2010
199
9,7
9,689
9,688
9,688
Текущая
точка
Шаг
*
f ( x)
x1
f ( x)
x2
(20,-20)
(6.474, 1.554)
(0.185, 0.176)
(0.169, 0.135)
(0.187, 0.125)
(0.187, 0.124)
0,8
0,1734
0,0897
0,0806
0,1967
0,0785
-78
-70,1
-0,19
0,093
-0,001
122
-10,909
-0,509
-0,054
-0,0009
t
Метод сошелся за 5 итераций, здесь сказывается влияние вычислительной
ошибки при нахождении оптимального значения шага. Фактически в окрестность экстремума алгоритм выходит на 3 итерации, следующие шаги уточняющие.
Преимуществом алгоритма Флетчера-Ривса является то, что он прост в реализации и при этом почти столь же эффективен как квази-Ньютоновские алгоритмы.
71
3.6. МЕТОД ДЭВИДОНА-ФЛНТЧЕРА-ПАУЭЛЛА
Стратегия решения задачи состоит в построении последовательности точек {x k }, k  0,1, ... таких, что f ( x k 1 )  f ( x k ), k  0,1, ... . Точки последователь-
 
ности x k вычисляются по правилу
x k 1  x k  tk Аk f ( x k ) ,
(3.14)
k
где A есть матрица размера n n , которая вычисляется по правилу
Ak 1  Ak  Ack , A0  E ,
x k (x k )T Ak g k (g k )T Ak
k
Ac 

,
k T
k
(x ) g
(g k )T Ak g k
где x  x
k
k 1
(3.15)
 x k , g k  f ( x k 1 )  f ( x k ) .
Точка x 0 , задается пользователем, величина шага t k* определяется из
условия
(t k )  f ( x k  t k d k )  min
tk [ a ,b ]
Задача одномерной минимизации функции (t k ) может быть решена ли-
 2 (t k )
(t k )
бо с использованием условий
 0 , либо численно с исполь 0,
2
t k
t k
зованием методов одномерной минимизации, как задача (t k )  min .
tk [ a ,b ]
(t k )
 0 имеет высокую степень и нахождение корней
t k
затруднено, можно аппроксимировать функцию (t k ) полиномом P(t k ) второй
P(t k )
*
 2 P(t k )
или третьей степени и определить t k из условий:
 0,
 0.
2
t k
t k
При численном решении задачи определения величины шага степень блиЕсли уравнение
зости найденного значения
t k к оптимальному значению t k* , удовлетворяюще-
(t k )
 2 (t k )
му условиям
 0,
 0 , зависит от задания интервала [a, b] и
2
t k
t k
точности метода одномерной оптимизации.
Расчет матриц позволяет сформировать такую последовательность { Ak }
положительно определенных матриц, таких, что
Ak  H 1 ( x* ) .
k 
72
(3.16)
Доказано, что для квадратичных функций алгоритм сходится не более
чем за n шагов [5,9,10].
Для функций общего вида алгоритм перестает быть конечным, сильное
влияние оказывает погрешность вычисления задачи оптимизации по шагу.
Сходимость метода можно гарантировать при его обновлении через каждые n шагов, т.е.
E,
k  J , J  {0, n,2n,...},

Ak   k 1
k 1
k  J.
 A  Ac ,
(3.17)
Построение последовательности {x k }, k  0,1, ... , заканчивается в точке
x k , для которой f ( x k )  1 , где 1 - заданное малое положительное число,
или при k  M , M – предельное число итераций, или при двукратном одновременном выполнении неравенств x k 1  x k   2 , f ( x k 1 )  f ( x k )   2 , где  2 малое положительное число. И в заключении решается вопрос о том, может ли
полученная точка рассматриваться как искомая точка минимума.
Алгоритм
Шаг 1. Задать x 0 , 1  0,  2  0 , предельное число итераций М. Найти
градиент f (x) .
Шаг 2. Положить k=0, A0  E .
Шаг 3. Вычислить f ( x k ) .
Шаг 4. Проверить выполнение критерия окончания f ( x k )  1 ;
а) если критерий выполнен, то x*  x k , расчет закончен;
б) если нет, то перейти к шагу 5.
Шаг 5. Проверить выполнение неравенства k  M :
*
k
а) если неравенство выполнено, то x  x , расчет закончен;
б) если нет, то перейти при k=0 к шагу 10, а при k  1 к шагу 6.
k
k 1
k
Шаг 6. Вычислить g  f ( x )  f ( x ) .
Шаг 7. Вычислить x  x
Шаг 8. Вычислить
k
k 1
 xk .
x k (x k )T Ak g k (g k )T Ak
A 

(x k )T g k
(g k )T Ak g k
Шаг 9. Ak 1  Ak  Ack .
Шаг 10. d k   Ak f ( x k ) .
k
c
73
Шаг 11. Вычислить
t k* из условия (tk )  f ( xk  tk Ak f ( x k ))  min .
tk
k 1
Шаг 12. Вычислить x  x  t k А f ( x ) .
Шаг 13. Проверить выполнение условий:
x k 1  x k   2 , f ( x k 1 )  f ( x k )   2 ;
k
k
k
а) если оба условия выполнены при текущем значении k и k  1 , то рас*
k 1
чет окончен, x  x ;
б) Если хотя бы одно из условий не выполнено, то положить k  1 и перейти к шагу 3.
Численное моделирование работы алгоритма проводилось для функций
квадратического и общего вида.
На первом графике представлен поиск минимума для функции
f ( x1 , x2 )  2 x12  x1 x2  x12 .
(3.18)
Начальные данные были следующие: x 0  (10,10), 1  0.1,  2  0.15 .
Максимальное количество итераций 10.
Рисунок 33 – Графическое представление минимизации методом Девидона-Флетчера-Пауэлла
Решение найдено за 2 итерации, производилась довольно точная настройка по шагу методом золотого сечения.
74
Таблица 3.9 – Таблица результатов.
№ итерации
x1
x2
Норма
градиента
0
10
10
58,309
1
-1,764
2,491
5,823
2
0
0
0
Следует отметить, что метод сопряженных градиентов может быть использован при минимизации функций с разрывными производными. Поиск "не
зависает" на изломе, а идет вдоль линии, соединяющей точки изломов линий
уровня, которая как правило, проходит через точку минимума.
4. МЕТОДЫ ВТОРОГО ПОРЯДКА
4.1. МЕТОД НЬЮТОНА
В результате работы метода
строится последовательность точек
{x k }, k  0,1, ... таких, что f ( x k 1 )  f ( x k ), k  0,1, ... . Точки последовательности {x k } вычисляются по правилу:
x k 1  x k  d k , k  0,1,... ,
(4.1)
0
где точка x задаѐтся пользователем, а направление спуска d k определяется
по правилу:
d k   H 1 ( x k )f ( x k ) .
(4.2)
Выбор d k гарантирует выполнение требования f ( x k 1 )  f ( x k ) при условии,
что матрица Гессе положительно определена, т.е. H ( x k )  0 . Формула расчета
последовательности {x k } основана на разложении в ряд Тейлора функции
1
f ( x)  f ( x k )  T f ( x k )( x  x k )  ( x  x k )T H ( x k )( x  x k ) ,
2
75
(4.3)
с точностью до второго члена ряда. Учтем, что в точке минимума градиент
функции равен нулю, получаем:
T f ( x k )  H ( x k )( x  x k )  0 ,
(4.4)
тогда и получаем формулу итерационного расчета.
В задачах поиска минимума произвольной квадратичной функции с положительной матрицей вторых частных производных метод Ньютона дает решение за одну итерацию независимо от выбора начальной точки. В этом случае
метод Ньютона является прямым решением задачи [1,2,6].
В случае функции общего вида сходимость метода можно гарантировать
только в малой окрестности точки минимума, при этом матрица Гессе должна
быть хорошо обусловлена. По этой причине метод чаще используется в комбинации с методами, быстро сходящимися вдали от точки экстремума.
k 1
k
Чтобы обеспечить выполнение требования f ( x )  f ( x ) даже в тех
случаях, когда для каких-либо значений матрица Гессе не окажется положительно определенной, рекомендуется для соответствующих значений k вычисk 1
k
k
лить точку x k 1 по методу градиентного спуска x  x  t k f ( x ) , шаг вы-
бирается из условия f ( x k  tk f ( x k ))  f ( x k ) .
Построение последовательности {x k } заканчивается в точке x k , для кото2
рой выполняется f ( x k )  1 , где 1 – заданное малое положительное число,
или k  M , где M – предельное число итераций, или при двукратном одновременном выполнении двух неравенств x k 1  x k   2 , f ( x k 1 )  f ( x k )   2 ,
где  2 – малое положительное число. Дополнительно исследуется вопрос о том,
может ли полученная точка быть принята как точка минимума целевой функции.
Алгоритм
Шаг 1: Выбираем начальную точку x 0 , 0    1, 1  0 ,  2  0 , M – предельное число итераций. Найти градиент функции в произвольной точке
 f ( x)
f ( x) 

f ( x k )  
, ...,
x
x
 1

n
T
и матрицу Гессе H (x) .
x xk
Шаг 2: Положить k  0 .
76
Шаг 3: Вычислить f ( x k ) .
2
Шаг 4: Проверить выполнение критерия окончания f ( x k )  1 :
а) если критерий выполнен, расчет закончен, x*  x k ;
б) если критерий не выполнен, то перейти к шагу 5.
Шаг 5: Проверить выполнение неравенства k  M :
а) если неравенство выполнено, то расчет окончен x*  x k ;
б) если нет, то перейти к шагу 6.
Шаг 6: Вычислить матрицу H ( x k ) .
Шаг 7: Вычислить H 1 ( x k ) .
Шаг8: Проверить выполнение условия H 1 ( x k )  0 :
а) если неравенство верно, то перейти к шагу 9;
k
k
б) если нет, то перейти к шагу 10, положив d  f ( x ) .
Шаг 9: Определить d k   H 1 ( x k )f ( x k ) .
Шаг 10: Найти точку x
k 1
 x k  tk d k , положив t k  1 , если
d k   H 1 ( x k )f ( x k ) , или выбрав
tk
из условия f ( x k 1 )  f ( x k ) , если
d k  f ( x k ) .
Шаг 11: Проверить выполнение условий:
x k 1  x k   2 , f ( x k 1 )  f ( x k )   2 :
а) если оба условия выполнены при текущем значении k и k  k  1, то расчет
окончен, x*  x k 1 .
б) если хотя бы одно из условий не выполнено, положить k  k  1 и перейти к
шагу 3.
Сходимость метода доказана для сильно выпуклых функций, предварительно необходимо исследовать матрицу Гессе на выполнение условия положительной определенности, и в случае невыполнения этого условия на текущей
итерации использовать градиентный спуск.
77
Рисунок 34 – Принцип поиска минимума методом Ньютона
Метод может применяться и для нахождения максимума, причем в силу
того, что H ( x k )  0 , формула для вычисления последовательности точек не
меняется.
Таким образом, решение задачи безусловной минимизации методом
Ньютона состоит из двух подзадач.:
1. Найти решение методом Ньютона;
2. Исследовать матрицу Гессе на положительную определенность, можно
заменить проверкой на выпуклость минимизируемой функции.
Рисунок 35 – Поиск минимума квадратичной функции методом Ньютона
Для квадратичной функции минимум находится за одну итерацию, поскольку метод Ньютона фактически является прямым решением задачи минимизации для такого типа функций. Рисунок 35 наглядно демонстрирует этот
78
факт. Начальная точка имеет координаты (20, 20) , точность метода составила
10 6 .
Следующий пример представляет результат работы алгоритма для функции заданной уравнением:
2
2
f ( x1 , x2 )  e x1  e x2
(4.5)
Начальные данные содержат сведения о координатах начальной точки
( x10 , x20 )  (1; 0.7) , точности вычислений по нормам градиента, точки и функ-
ции 1  0.1 ,  2  0.5 , предельное количество итераций М=10.
Таблица 4.1 – Решение методом Ньютона для функции общего вида
Номер
итерац.
Норма
градиента
x1
x2
1
-0,666
0,346
2,221
2
-0,313
0,067
0,705
3
-0,051
0,0005
0,103
4
-0,0002
4,2Е-10
0,000
79
Рисунок 36 – Результат работы метода Ньютона для функции (4.5)
Поведение алгоритма Ньютона характерен для функции общего вида,
здесь влияние оказывает то, что функция сильно выпуклая и недостаточно
хорошо аппроксимируется квадратичной функцией, что даже от сравнительно
недалеко выбранной начальной точки методу потребовалось несколько
итераций. Хотя в целом для сильно выпуклых функций количество итераций
сравнительно небольшое, по отношению к другим алгоритмам.
Однако есть еще одна причина, по которой алгоритм Ньютона стараются
применять реже. Это задача связанная с обращением матрицы, особенно
высоких порядков, когда размерность значительно усложняет вычислительный
процесс.
4.2. МЕТОД НЬЮТОНА С ПЕРЕМЕННЫМ ШАГОМ
(НЬЮТОНА-РАФСОНА)
В результате работы метода строится последовательность точек
{x }, k  0,1, ... таких, что f ( x k 1 )  f ( x k ), k  0,1, ... . Точки последовательноk
сти {x k } вычисляются по правилу:
x k 1  x k  tk H 1 ( x k )f ( x k ), k  0,1, ...,
0
(4.6)
где точка x задаѐтся пользователем, а величина шага t k определяется по правилу:
(t k )  f ( xk  tk H 1 ( x k )f ( x k ))  min .
tk
80
Рисунок 37 – Поведение алгоритма Ньютона-Рафсона
Задача нахождения оптимального шага решена либо с использованием
(t k )
 2 (t k )
условий
 0,
 0 , либо численно с использованием методов од2
t k
t k
номерной минимизации, как задача (t k )  min .
tk [ a ,b ]
При численном решении задачи определения величины шага степень близости найденного значения t k к оптимальному значению t k* , удовлетворяющему
(t k )
 2 (t k )
условиям
 0,
 0 , зависит от задания интервала [a, b] и точно2
t k
t k
сти метода одномерной оптимизации.
k
Построение последовательности {x } заканчивается в точке
x k , для ко-
2
торой выполняется f ( x k )  1 , где 1 – заданное малое положительное число, или k  M , где M – предельное число итераций, или при двукратном одновременном
выполнении
двух
x k 1  x k   2 ,
неравенств
f ( x k 1 )  f ( x k )   2 , где  2 – малое положительное число. Дополнительно исследуется вопрос о том, может ли полученная точка быть принята как точка
минимума целевой функции [4,5].
Алгоритм
Шаг 1: Выбираем начальную точку x 0 , 0    1, 1  0 ,  2  0 , M – предельное число итераций. Найти градиент функции в произвольной точке
 f ( x)
f ( x) 

f ( x )  
,...,
x
x
 1

n
T
и матрицу Гессе H (x) .
k
x xk
Шаг 2: Положить k  0 .
Шаг 3: Вычислить f ( x k ) .
2
Шаг 4: Проверить выполнение критерия окончания f ( x k )  1 :
а) если критерий выполнен, расчет закончен, x*  x k ;
б) если критерий не выполнен, то перейти к шагу 5.
Шаг 5: Проверить выполнение неравенства k  M :
а) если неравенство выполнено, то расчет окончен x*  x k ;
81
б) если нет, то перейти к шагу 6.
Шаг 6: Вычислить матрицу H ( x k ) .
Шаг 7: Вычислить H 1 ( x k ) .
Шаг8: Проверить выполнение условия H 1 ( x k )  0 :
а) если неравенство верно, то найти d k   H 1 ( x k )f ( x k ) ;
k
k
б) если нет, то положить d  f ( x ) .
Шаг 9: Определить x
k 1
 x k  tk d k .
Шаг 10: Шаг найти из условия:
(t k )  f ( xk  tk H 1 ( x k )f ( x k ))  min .
tk
Шаг 11: Проверить выполнение условий:
x k 1  x k   2 , f ( x k 1 )  f ( x k )   2 :
а) если оба условия выполнены при текущем значении k и k  k  1, то расчет
окончен, x*  x k 1 .
б) если хотя бы одно из условий не выполнено, положить k  k  1и перейти к
шагу 3.
На следующем рисунке представлен результат работы алгоритма для
функции неквадратического вида.
Начальные данные содержат сведения о координатах начальной точки
( x10 , x20 )  (100;100 ) , точности вычислений по нормам градиента, точки и
функции 1  0.1 ,  2  0.5 , предельное количество итераций М=10.
Таблица 4.2 – Решение методом Ньютона-Рафсона для функции неквадратического вида
№ итерации
f ( x1 , x2 )
Текущая точка
Шаг
Градиент
0
-108.13
(80;100)
0.64
(0,84;0,84)
1
-200.00
(0,46;0,29)
0.92
(0,0)
2
-200.00
(0,11;0,02)
0.92
(0,0)
82
Рисунок 38 – Результаты поиска минимума методом Ньютона-Рафсона
Количество итераций сравнительно невелико, лучше чем в методе
Ньютона, за счет оптимального выбора шага. Метод учитывает рельеф,
ориентирован в большей степени на неквадратичные выпуклые функции, что и
демонстирует данный рисунок.
Сходимость метода обладает теми же особенностями, что и метод Ньютона, однако для неквадратических функций может сходиться за меньшее число шагов. Тем не менее, метод чувствителен к точности настройки одномерного
поиска оптимального шага.
5. СОДЕРЖАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ ПО ТЕМЕ
"ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ"
Работа состоит в программной реализации численных алгоритмов безусловной оптимизации. Методы выбираются из каждой группы: нулевого порядка и градиентных, не менее двух методов каждой группы.
Целевых функций использовать не менее двух, разных по виду: квадратического типа и общего (более высокого порядка, с использованием экспоненциальной, логарифмической тригонометрической функций). Далее приводятся
примеры с указанием ограничений для квадратической функции и некоторые
функции общего вида.
Необходимо провести несколько экспериментов, чтобы изучить влияние
начальных условий и типа функции на поведение алгоритма, скорость сходимости, чувствительность к значениям параметров, определить недостатки и достоинства, подтвердить результатами численного моделирования.
83
Сделать выводы об эффективности работы алгоритмов, дать оценку возможных трудностей реализации, связанных с увеличением размерности, свойствами целевой функции и значениями параметров.
Подготовить отчет с анализом полученных результатов.
Порядок защиты лабораторной работы включает 2 этапа: тестирование
программы в присутствии преподавателя и защита теоретической части работы
в соответствии с отчетом.
6. ПРАВИЛА ОФОРМЛЕНИЯ ОТЧЕТА К ЛАБОРАТОРНОЙ РАБОТЕ
Перечислим общие требования, предъявляемые к выполняемым работам.
6.1. Требования по оформлению
Отчет о выполненной работе должен содержать следующие части:
 Титульный лист. Титульный лист содержит наименование темы лабораторной работы, данные о студенте, оформляется в соответствии с текущими требованиями, принятыми в ВУЗе.
 Основной текст документа. Основной текст имеет формат Microsoft
Word, формулы набраны вручную, пронумерованы, шрифт Times New
Roman 12pt.
 Постановка задачи. Содержимое этого раздела должно быть конкретизировано под выполняемый вариант работы с указанием реализованных
методов и вариантов целевой функции.
 Теоретические сведения. Теоретические сведения должны соответствовать методам, определенным постановкой задачи. Обязательно должно
присутствовать аналитическое решение задачи с описанием необходимых и достаточных условий существования экстремума, классификацию
полученных точек.
 Описание программной реализации метода. В этом разделе приводится
описание в виде текста или блок схем реализуемых алгоритмов поиска
безусловного минимума.
 Тестирование реализованного метода. В этом разделе приводятся результаты работы реализованного в виде программы поиска безусловного
минимума. Результаты необходимо представить в виде таблиц, графиков
или снимков экрана.
 Выводы. В этом разделе должны быть представлены выводы об обнаруженных особенностях поведения реализованных алгоритмов, дан срав-
84
нительный анализ их работы, указаны недостатки и преимущества алгоритмов.
 Список литературы. Приводится список литературы, оформленный в соответствии с текущими требованиями, принятыми в ВУЗе.
Примечание. Исходные тексты программы не надо включать в отчет. Они
должны быть предоставлены в электронном виде вместе с исполняемым файлом программы реализующей выданный вариант работы.
6.2. Требования к реализации
 Используемый язык программирования. Язык по выбору студента. Желательно использовать современные языки и платформы программирования: C++, Delphi, Java, C# и т.д.
 Интерфейс пользователя. Интерфейс должен быть достаточно "дружественным", удобным для тестирования, лучше всего в виде диалоговых
окон. Это ускоряет и упрощает процедуру тестирования программы
преподавателем. Консольный вариант интерфейса программы так же
допустим, хотя и не желателен, так как на сегодняшний день современные инструментальные средства разработки (такие как Borland Delphi,
Visual Studio, Eclipse и т.д.) позволяют создавать удобные визуальные
диалоговые окна «в несколько щелчков мышкой», вырабатывая соответствующие навыки у студентов.
 Программа не должна выдавать таких возможных ситуаций, как «Деление на ноль», «Переполнение» и т.п. При возникновении таких ошибок
программы будут отправляться на доработку.
 Тестирование программы проходит во время занятий в компьютерном
классе. Если тестирование проводится на компьютере преподавателя, то
программа должна быть предоставлена в виде исполняемого модуля,
при необходимости укомплектованная всеми нужными внешними библиотеками, так как на компьютере преподавателя может не быть той инструментальной среды, которую выбрал студент для реализации работы.
 Исходные тексты программы должны быть отформатированы и содержать достаточное для понимания логики программы количество комментариев.
85
 Исполняемый модуль и носитель (USB-носитель, CD диск и т.п.) на котором он предоставляется для проверки преподавателю, должны быть
предварительно проверены на вирусы.
6.3 Пример интерфейса пользователя
На рисунке 39 приведен примерный интерфейс пользователя.
Рисунок 48 – Примерный вид интерфейса пользователя.
Рекомендуется при выполнении заданий стремиться делать примерно такой же
интерфейс, так как в таком случае удобно и наглядно представлена вся входная
и вся выходная информация.
Программа должна выполнять элементарные проверки на корректность
вводимых данных, например, ввод строковых данных вместо числовых и т.п.
6.4 Получение и прием заданий
Темы лабораторных работ даются в рамках изложенного на лекциях теоретического материала. Студент должен реализовать методы безусловной минимизации действительной функции двух переменных, изложенные в рамках
86
лекций, в виде программы на любом языке программирования (по выбору студента).
Студенты получают варианты заданий на практических занятиях. Так как
общее число методов довольное большое, их количество для программной реализации оговаривается отдельно, в зависимости от уровня подготовки студентов. Общие рекомендации следующие. Рассмотреть методы поиска безусловного минимума из основных групп: нулевого порядка и градиентных методов
(первого и второго порядков). Минимальное число: 2 метода в каждой группе.
Необходимо сравнить методы между собой в каждой группе по разным показателям (быстродействие, чувствительность к выбору начальной точке и параметрам, трудоемкость алгоритма, сложность реализации и т.д.). Методы выбираются после прочтения лекционного материала, утверждаются преподавателем и не подлежат замене. Соответствие заданию строго контролируется.
Требования к выполнению лабораторных работ:
1. Строгое соответствие программы и результатов ее работы с полученным заданием.
2. Самостоятельные тестирование и отладка программы.
3. Устойчивость работы программы при любых значениях параметров,
задаваемых пользователем через интерфейс программы.
4. Предоставление демонстрационных примеров и исходного текста программы для защиты лабораторных работ. Привести наиболее интересные графики из численного моделирования. Отдельно рассмотреть ситуации, когда метод не сходится к решению, если удается получить такой пример. Объяснить
причины подобного поведения алгоритма.
5. Графики должны быть легко читаемы, нумерация координатных осей
обязательна, на одном графике представлен один вариант вычисления.
6. Таблицы должны содержать значения всех переменных метода, которые
подлежат пересчету на каждой итерации. Обязательно указывать значения критериев выхода из итерационной процедуры. Для методов покоординатного
спуска указывать результаты по каждой координате. В дальнейшем учесть количество промежуточных вычислений при подсчете количества итераций.
7. Выводы: дать сравнительный анализ методов между основными группами и внутри каждой группы. Особенно уделить внимание на специализацию
методов, т.е. ответить на вопрос – как поведение целевой функции отражается
на работе алгоритма (метода). Поскольку у каждого метода есть свой класс
функций, для которого данный метод и был разработан. Объяснить, почему на
одних функциях результаты хорошие, на других сходимость медленнее. Ука87
зать алгоритмы, которые одинаково хорошо работают на функциях любого вида.
8. Работу выполнить для функций 2 типов: параболического (квадратичного) типа и общего типа.
Условия сдачи лабораторных работ:
Знание теории по сдаваемой теме. Умение объяснить полученные результаты. Способность быстро продемонстрировать владение предметной областью.
7. ВАРИАНТЫ ФУНКЦИЙ
7.1. ФУНКЦИЯ КВАДРАТИЧНОГО ТИПА
Рассмотрим квадратичную функцию в общем виде:
f ( x)  ax12  bx1 x2  cx22  dx1  kx2  l .
(7.1)
Коэффициенты уравнения очень сильно влияют на поведение вид функции,
наличие у нее точек экстремума, их тип. Получим условия существования минимума у функции квадратичного типа. Выпишем матрице Гессе:
 2a b 
 ,
H ( x)  
 b 2c 
(7.2)
далее выпишем угловые миноры и воспользуемся критерием Сильвестра:
1  2a  0  a  0,  2 
2a
b
b
 4ac  b 2  0 .
2c
При соблюдении свойств (7.3) функция (7.1) имеет глобальный минимум.
7.2. ФУНКЦИИ ОБЩЕГО ВИДА
Варианты функций:
x  50  

 x 
1. f ( x1 , x2 )  100  sin  1
  cos 2  
 100  
  100 
2. f ( x1 , x2 )  e
 x1 
 
a
2
  x2  2 
1    , a  0, b  0
 b 


2
2
3. f ( x1 , x2 )  a  ( x1  x2 )  1  b  ( x1  x2 )  1, a  0, b  0
4. f ( x1 , x2 )  e
x12
2
 e x2
88
(7.3)
5. f ( x1 , x2 )  e
6. f ( x1 , x2 )  e
7.
x12
 x22
( x1 a )2
f ( x1 , x2 )  e
(1  ( x2  b) 2 )
( x1 a )2 ( x2 b )2
8. f ( x1 , x2 )  ( x1  x2 ) sin x1
2
2
2
f ( x1 , x2 )  a | x1 | b | x2 |, a  0, b  0
10. f ( x1 , x2 )  a | x1  x2 | b | x1  x2 |, a  0, b  0
9.
11.
f ( x1 , x2 )  a( x1  x2 ) 2  x22 , a  0
12.
f ( x1 , x2 )  x13  x1 x2  x22  2 x1  3x2  4
13.
f ( x1 , x2 )  ( x2  x12 ) 2  (1  x1 ) 2
14.
f ( x1 , x2 )  x14  x24  ( x1  x2 ) 2
15.
f ( x1 , x2 )  2 x13  4 x1 x22  10 x1 x2  x22
16. Функция Химмельблау:
f ( x1 , x2 )  ( x12  x2  11) 2  ( x1  x22  7) 2
89
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Акулич, И.Л. Математическое программирование в примерах и задачах.–М.:Высш. шк., 1986.–312с.
2. Базара, М. Нелинейное программирование. Теория и алгоритмы /М. Базара, К.Шетти.–М.: Мир, 1982. 583с.
3. Банди, Б. Методы оптимизации. Вводный курс.–М.: Радио и связь,
1988. – 128с.
4. Дэннис, Дж. Численные методы безусловной оптимизации и решения
нелинейных уравнений / Дж. Дэннис, Р.Шнабель.– М.: Мир,1988. 440с.
5.Мину, М. Математическое программирование. Теория и алгоритмы /
М.Мину. – М.: Наука, 1990. 488с.
6. Пантелеев, А.В. Методы оптимизации в примерах и задачах: учеб.метод. пособие/. А.В. Пантелеев, Т.А. Летова.–М.: Высш. шк., 2005.–544с.
7. Полак, Б.Т. Введение в оптимизацию / Б.Т. Полак.– М.: Наука, 1983.
384с.
8. Полак, З. Численные методы оптимизации (единый подход) / З.Полак. –
М.: Мир, 1972. 240с.
9. Пшеничный, Б.Н. Численные методы в экстремальных задачах Б.Н.
Пшеничный, Ю.М. Данилин. – М.: Наука, 1975. 319с.
10. Рубан, А.И. Методы оптимизации: учеб. пособие. 3-е изд., испр. и
доп./ А.И. Рубан. Красноярск: ИПЦ КГТУ, 2004.– 528с.
11. Химмельблау, Д. Прикладное нелинейное программирование. – М.:
Мир, 1975.–534с.
90
СОДЕРЖАНИЕ
Предисловие.......................................................................................................3
Введение.............................................................................................................4
1. Постановка задачи и основные определения..............................................5
2. Методы нулевого порядка............................................................................8
2.1. Метод покоординатного спуска............................................................8
2.2. Метод конфигураций (Хука-Дживса).................................................13
2.3. Метод деформированного многогранника
(Нелдера-Мида).....................................................................................19
2.4. Метод вращающихся координат (Розенброка).................................30
2.5. Метод сопряженных направлений (Пауэлла)....................................36
2.6. Метод случайного поиска....................................................................41
3. Методы первого порядка...........................................................................51
3.1. Метод градиентного спуска с постоянным шагом...........................51
3.2. Метод наискорейшего градиентного спуска.....................................57
3.3. Градиентный метод покоординатного спуска...................................60
3.4. Метод наискорейшего покоординатного
градиентного спуска (Гаусса-Зейделя)..............................................63
3.5. Метод сопряженных градиентов (Флетчера-Ривса).........................67
3.6. Метод Девидона-Флетчера-Пауэлла..................................................72
4. Методы второго порядка...........................................................................75
4.1. Метод Ньютона....................................................................................75
4.2. Метод Ньютона-Рафсона.....................................................................80
5. Содержание лабораторной работы по теме
"Численные методы многомерной оптимизации"...................................83
6. Правила оформления отчета к лабораторной работе .............................84
6.1. Требования по оформлению...............................................................84
6.2. Требования к реализации....................................................................85
6.3. Пример интерфейса пользователя......................................................86
6.4. Получение и прием заданий................................................................86
7. Варианты функций.....................................................................................88
7.1. Функция квадратического типа..........................................................88
7.2. Функция общего вида..........................................................................88
Библиографический список...........................................................................90
91
Учебное издание
Методы многомерной оптимизации:
методические указания
Составитель Н. А. Сергеева
Редактор О. Ф. Александрова
Компьютерная верстка Н. А. Сергеева
Подписано в печать 16.05.2011. Печать плоская.
Формат 60×84/16. Бумага офсетная.
Усл. печ. л. 5.75. Тираж 100. Заказ 3616.
Редакционно-издательский отдел
Библиотечно-издательского комплекса
Сибирского федерального университета
660041, г. Красноярск, пр. Свободный, 79
Тел/факс (391) 206-21-49, 206-26-57 206-26-55,
е-mail: [email protected]
Отпечатано полиграфическим центром
Библиотечно-издательского комплекса
Сибирского федерального университета
660041, г. Красноярск, пр. Свободный, 82а
Тел. (391)206-26-58, 206-26-49, 206-26-67
e-mail: [email protected]
Документ
Категория
Без категории
Просмотров
59
Размер файла
3 500 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа