Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

на которых проверяется работоспособность алгоритмов, обычно используются функции со сложной структурой овражного рельефа. Хрестоматийным примером овражной функции двух переменных является функция Розенброка [27, с. 214]

Точка минимума с координатами (1, 1)T расположена на дне узкого крутого ущелья, дно которого к тому же изогнуто по параболе x2 = x21 (рис. 11.3). Из-за своеобразного вида изолиний в окрестности нуля функцию Розенброка иногда называют банановой функцией (banana function).

102 Глава 11. Многомерная оптимизация без ограничений

Задачи оптимизации с подобными функциями принято называть плохо обусловленными (ill-conditioned problems). Для то-

ким образом, целевая функция в данной окрестности аппроксимируется многомерной квадратичной функцией, где в качестве матрицы квадратичной формы выступает матрица Гессе. Как мы знаем (см. с. 33), степень сплющенности эллипсоидов равных уровней для квадратичной функции измеряется числом обусловленности (condition number) cond(H). Если cond(H) ≈ 1, то поверхности равных уровней близки к сферическим и свойство овражности в данной окрестности не наблюдается (см. рис. 11.2, а). Если же cond(H) 1, то матрица относится к классу плохо обусловлен-

Выясним поведение этой функции в окрестности точки оптимума. Подставляя координаты x1 = x2 = 1, получаем

функции Розенброка в окрестности точки минимума представляет собой узкий овраг с такими крутыми склонами, что его трудно изобразить на графике (см. рис. 11.3).

Для решения плохо обусловленных задач изобретен ряд эвристических методов нулевого порядка. Одним из наиболее простых и эффек-

тивных считается метод (деформируемого) многогранника Нелдера — Мида (Nelder — Mead), который в первоначальном варианте назывался симплексным методом. Кроме названия он не имеет ничего общего с симплексным методом в линейном программировании, а назван так потому, что в нем моделируется процесс перекатывания правильного n-мерного многогранника (симплекса) вниз по поверхности целевой функции.

Продемонстрируем симплексный метод на примере функции двух переменных (рис. 11.4). Симплекс в данном случае будет

представлять собой правильный треугольник. Пусть начальное

−→ −→ −→

расположение его вершин есть X 1, X 2, X 3. Вычислим целевую

функцию в каждой из них и найдем вершину с наихудшим (наи-

−→

большим) значением. В нашем случае это будет вершина X 1. Ите-

рация метода состоит в том, что текущий симплекс перемещается в новое положение, при котором все вершины, кроме наихудшей, остаются на своих местах, а последняя отражается в точку, зер-

В описанном варианте метода существует проблема выбора размеров симплекса. Если сделать его большим, то есть опасность проскочить экстремум, а если слишком малым — то замедлится работа. В связи с этим в усовершенствованной модификации симплексного метода предусмотрена подстройка размеров граней в ходе работы, тем самым он превращается в метод деформируемо-

104 Глава 11. Многомерная оптимизация без ограничений

Рис. 11.4. Итерации симплексного метода

го многогранника [27, с. 163]; [21, с. 138].

Вмногомерном случае алгоритм метода следующий.

По д г о т о в и т е л ь н ы й э т а п

Исходный многогранник в n-мерном пространстве, содержащий

ординатный орт, h — предустановленный начальный размер симплекса.

И т е р а ц и я

Каждая итерация может завершиться одним из двух исходов. Либо включается новая вершина, которая замещает самую худшую, при этом происходит перемещение многогранника (шаг 5), либо это невозможно, тогда он сжимается со всех сторон (шаг 6). Выход из итерационного процесса происходит по достижению установленного минимального размера многогранника.

Шаг 1. Оценка. Вычисляются значения целевой функции в вершинах многогранника, затем они упорядочиваются по возрас-

чается в список вершин. Завершение итерации (шаг 5).

Рис. 11.5. Деформирование многогранника

−→ −→

Шаг 3. Растяжение. Если f ( R ) < f (X 1), т. е. результат отражения лучше, чем у самой лучшей вершины, делается попытка

эффициент растяжения у нас равен двум, но возможно и другое значение).

чается в список вершин. Завершение итерации (шаг 5).

• В противном случае попытка растяжения безуспешная, в

→−

список вершин включается отраженная точка R . Завершение итерации (шаг 5).

106 Глава 11. Многомерная оптимизация без ограничений

−→ −→

Шаг 4. Сокращение. Если f ( R ) f (X n), то происходит сокращение (contraction) многогранника с одной стороны, для чего анализируются две возможности.

т. е. производится внутреннее сокращение (contraction inside). Завершение итерации (шаг 5);

– иначе сжатие многогранника (шаг 6).

Шаг 5. Перемещение. Включенная точка замещает верши-

−→

ну X n+1, тем самым многогранник переходит в новое положение. Возврат на начало итерации (шаг 1).

Шаг 6. Сжатие. Происходит сжатие (shrink) многогранни-

ка, например, в два раза, во всех направлениях, при этом лучшая

−→

вершина X 1 остается на месте, остальные пересчитываются по

−→ −→ −→ −→

формуле X i = X 1 + (X i − X 1)/2, i = 2, . . . , n + 1. Возврат на начало итерации (шаг 1).

На рис. 11.6 показаны первые 40 итераций поиска экстрему-

ма функции Розенброка методом деформируемого многогранни-

−→

ка. Исходная точка X 0 = (−0.5, 0.5)T , h = 0.5, начальный симплекс выделен жирными линиями. Легко убедиться, что метод хорошо адаптируется к овражному рельефу целевой функции.

Поиск по

Другой популярный метод прямого поиска был

образцу

предложен Хуком и Дживсом (Hooke — Jeeves) в

1962 г., он называется поиском по образцу (pattern search) или методом конфигураций [27, с. 157]; [21, с. 130].

Алгоритм вначале обследует окрестность текущей точки, из-

→−

меняя на фиксированную величину ± компоненты вектора X k. Эту процедуру можно уподобить действиям путника в темноте, который, прежде чем сделать очередной шаг, ощупывает посохом землю, пытаясь определить направление спуска по склону горы.

После того как будет найдено понижающее направление, в этом направлении производятся дробные шаги при постепенно увеличивающейся длине шага, тем самым устанавливается конфигурация поиска. Это продолжается до тех пор, пока поиск в направлении установленной конфигурации дает уменьшение це-

108 Глава 11. Многомерная оптимизация без ограничений

→−

левой функции f (X ). Если же не удается найти точку с меньшим значением функции, размер шага уменьшается. После нескольких последовательных сокращений размера шага от принятой конфигурации отказываются и предпринимается новое обследование окрестности. Метод позволяет во время фазы обследования восстанавливать направление движения вдоль оврага в тех случаях, когда вследствие искривления его дна установленная ранее конфигурация перестает быть эффективной.

11.3. Градиентные методы

Переходим к рассмотрению типичных методов первого поряд-

ка. Они иначе называются градиентными, потому что предпола-

→−

гают, что в любой точке X k наряду со значением целевой функции

→− →− →−

f (X k) известно направление вектора градиента f (X k).

Поскольку ограничения отсутствуют, а градиент указывает направление скорейшего возрастания целевой функции в данной точке, то самым простым и очевидным способом выбора

понижающего направления на каждом шаге является выбор направления антиградиента. Тогда итеративная процедура поиска минимума будет описываться следующими соотношениями:

где δ — выбранная длина шага. В пределе длину шага δ можно считать бесконечно малой, в этом случае мы будем иметь непрерывную модель скатывания безынерционного (с нулевой массой)

шарика по рельефу целевой функции. Траектория его движения

→−

X (t) описывается дифференциальным уравнением

→− dX (t)

dt

(11.2)

Шарик будет катиться до тех пор, пока есть уклон, и в конце концов остановится в точке, где градиент целевой функции равен нулю, то есть в стационарной точке. Как мы знаем, для выпуклой функции стационарность является необходимым и достаточным условием экстремума.

В принципе, любой численный метод решения уравнения (11.2) даст нам метод нелинейной оптимизации без ограничений, однако на практике это была бы стрельба из пушек по воробьям,

так как методы решения дифференциальных уравнений рассчи-

→−

таны на вычисление формы траектории X (t), а нам нужна только ее конечная точка. Тем не менее с теоретической точки зрения модель движения шарика представляет интерес, на ее основе можно сконструировать оригинальный метод невыпуклой оптимизации, так называемый метод тяжелого шарика, который мы рассмотрим в разд. 11.5..

Более рациональным с практической точки зрения представляется метод, при котором понижающее направление выбирается по антиградиенту, однако шаг совершается на полную длину, то есть до тех пор, пока функция убывает в выбранном

направлении. Это и есть классический метод скорейшего спуска (steepest descent), предложенный в XIX веке французским мате-

Метод скорейшего спуска очень хорошо изучен, прост в реализации, его принципиальная сходимость для выпуклых функций строго доказана. К сожалению, он, как и метод Гаусса — Зайделя, плохо работает на овражных функциях. Причина этого явления та же самая: легко показать, что направления движения на соседних шагах всегда ортогональны друг другу.