Детерминированные методы

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

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

Метод ветвей и границ

Метод ветвей и границ (branch and bound) принадлежит классу детерминированных методов и может применяться для решения широкого круга задач, в которых информация о минимизируемых функциях мала или отсутствует совсем. Он может быть легко использован для задач с вогнутыми или выпуклыми областями, вогнутыми или выпуклыми целевыми функциями и с функциями, для которых недоступна информация об их непрерывности. В тех случаях, когда для работы алгоритма требуется какая-либо специфическая информация об исследуемой функции, существует две возможности: либо пользователь предоставляет эту информацию на входе, либо алгоритм сам проводит аналитическое исследование функции, вычисляя нужные производные, определяя области непрерывности и т.д. Очевидно, что на практике более удобно работать с вычислителем, основанном на последнем подходе, но бывают случаи, когда получение информации (например, вычисление константы Липшица) аналитическим путем является задачей, плохо поддающейся, или совсем не поддающейся алгоритмизации. В таких случаях получение всей необходимой информации возлагается на пользователя.

Метод ветвей и границ, подобно моделируемому отжигу, первоначально успешно применялся для решения задач целочисленной оптимизации. После этого он был адаптирован для непрерывного случая и для решения задачи поиска min¦(x) при x ÎWÍRⁿ принял следующий канонический вид:

Алгоритм 3: Метод ветвей и границ

Инициализация: Установить i = 1, z^* = + infinite, и список = W.

Шаг 1: Извлечь область W _i из списка.

Шаг 2: Если W _i достаточно мала, занести ее в результирующий список и перейти к шагу 1.

Шаг 3: Вычислить z _-, z ⁺ такие что z _- £ ¦(x)|_{W i} £ z ⁺.

Шаг 4: Если z _- > z^* удалить область W _i и перейти к шагу 1.

Шаг 5: Если z ⁺ £ z^* установить z^* = z ⁺.

Шаг 6: Разбить W _i на k равных частей и добавить их в список.

Шаг 7: Перейти на шаг 1.

Шаг 8: Вернуть список результирующих областей.

Алгоритм 3 разбивает исходную область W на все более и более мелкие части, отбрасывая те, наличие глобального минимума в которых невозможно.

Этот простой алгоритм имеет несколько недостатков. Во-первых, границы значений функции на W _i, вычисленные на шаге 3 потенциально не точны. Если оценка функции проведена с плохой точностью, то алгоритм может потратить большое количество времени, пытаясь отбросить области, не содержащие глобального минимума, на которых целевая функция является достаточно плоской. Во-вторых, на шаге 6, W _i разбивается на k равных частей, причем не принимается в расчет какая-либо информация об локально/глобальном поведении функции на полученных частях. Более интеллектуальный алгоритм должен принять эту информацию во внимание, для определения того, где нужно резать область. Например, возьмем прямоугольник [-1, 1]´[-1, 1] и ¦(x) = x ². Этот прямоугольник можно разбить на четыре части, каждая с углом в (0, 0). Это разбиение не очень хорошее, поскольку каждый прямоугольник все еще содержит глобальный минимум функции. В то же время, если прямоугольник разрезать на части

[- e, e ]´ [- e, e ], [ e, 1]´ [-1, 1], [-1, - e ]´ [-1, 1], [- e, e ]´ [ e, 1], [- e, e ]´ [-1, - e ],

где e достаточно малое положительное число, мы теперь имеем пять прямоугольников, только один из которых содержит глобальный минимум, и другие четыре могут быть легко отброшены.

В-третьих, подобласти могут отбрасываться только на основе информации о значениях функции. Если же функция хотя бы один раз непрерывно дифференцируема и показано, что градиент этой функции не может принимать нулевое значение на W _i, целиком лежащей (т.е. не имеющей общих граничных точек) в исходном W, то W _i не содержит даже локального минимума. Аналогично, подобласть может быть отброшена, если матрица Гессе (гессиан) ¦ ни в одной точке этой подобласти не является положительно определенной.

Канонический метод ветвей и границ позволяет решать задачу глобальной оптимизации также и для случая, когда на переменные задана некоторая система ограничений. Достаточно просто проверить эти ограничения для текущего параллелепипеда и, если они гарантированно не выполнены, то параллелепипед можно выбросить из дальнейшего рассмотрения. Здесь нужно только чтобы ограничения задавали такую область, что при достаточно мелком ее разбиении существовал параллелепипед, целиком лежащий в этой области. Если это условие не выполнено, то данный метод неприменим.

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

Функции ограничения

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