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

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

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

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

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

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

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

Метод ветвей и границ (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 не содержит даже локального минимума. Аналогично, подобласть может быть отброшена, если матрица Гессе (гессиан) ¦ ни в одной точке этой подобласти не является положительно определенной.

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

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

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

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

Ограничение, основанное на константах Липшица

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

B_{L , W} ¦ = ¦(x ^* ) – L w (W) £ ¦(x ) £ ¦(x ^* ) + L w (W) = B^{L , W} ¦,

где x^* Î W, а L есть константа Липшица для функции ¦ на W, и w (W) служит верхней границей диаметра области W. Такая оценка имеет то преимущество, что она проста для вычисления, когда известна константа Липшица. Дополнительно она имеет следующее свойство

lim (B^{L , W} ¦ - B_{L , W} ¦) = 0 при w (W)® 0.

В то же время, главным недостатком этого метода является то, что если константа L велика, то оценка является недопустимо неточной. Также здесь не используется тот факт, что для данной функции константа Липшица сильно меняется на различных областях.

Интервальная арифметика

Интервальная арифметика (IA – interval arithmetic ) – естественная тех­ника для оценки границ изменения функции. IA была введена Муром [2] с целью улучшения надежности численных вычислений. С тех пор она успешно приме­нялась для решения многих вычислительных задач, таких как обыкновенные дифференциальные уравнения, системы линейных уравнений и глобальная оптимизация.

В IA вещественное число x представимо парой чисел с плавающей точ­кой (a , b ), соответствующих интервалу X = [a , b ], гарантированно содержащему x , т.е. такому, что a £ x £ b . Таким образом, IA обеспечивает не только оценку для значения x , но и говорит о том, насколько хороша эта оценка. Реальная сила IA состоит в том, что мы можем оперировать интервалами, как если бы они были числами, и получать надежные оценки для результатов числовых вычислений.

Простые формулы легко получены для выполнения примитивных ариф­метических операций над интервалами. Интервальные расширения для сложных функций могут быть вычислены путем составления этих примитивных формул в том же порядке, в каком они составлены при вычислении непосредственно самой функции. Другими словами, любой алгоритм для вычисления функции, использующий примитивные операции может быть легко (и автоматически) пе­реведен в алгоритм для вычисления интервального расширения для этой же функции. Это особенно удобно выполнять в языках программирования, кото­рые поддерживают перегрузку операторов, но может быть выполнено в любом языке программирования, либо вручную, либо при помощи предварительной компиляции. Поскольку также относительно легко найти интервальное расши­рение для элементарных трансцендентных функций, таких как sin , cos , log и exp , класс функций, для которых интервальное расширение может быть легко (и ав­томатически) вычислено гораздо больше, чем класс рациональных полиноми­альных функций. Эти наблюдения иногда объединяют в Фундаментальную Теорему Интервальной Арифметики: каждая вычислимая функция имеет интервальное расширение, т.е. для любой вещественной функции ¦, заданной алгоритмом, существует интервальная функция F , такая, что F (X ) Ê ¦(C ) = {¦(x ): x ÎX } для каждого параллелепипеда X в области определения ¦. Причем lim F (X ) = ¦(x ), при сужении параллелепипеда X к любой точки x из области определения ¦.

Основной недостаток IA в том, что оценки диапазона могут быть намного шире, чем точные границы, иногда по сути бесполезные. Это в основном возникает из-за неявного предположения о том, что операнды в примитивных операциях взаимно независимы. Если это предположение ложно, то не все комбинации значений в интервалах-операндах будут достигнуты, и результирующий интервал, вычисленный в IA , может быть намного шире, чем реальный диапазон результирующей величины. В качестве критического примера рассмотрим расчет функции y(x) = x – x , где x Î [1, 5]. IA правила дают [-4, 4], в то время как реальный диапазон [0, 0]. Это иногда называется “проблемой зависимости” в IA .

Данный недостаток IA особенно сильно проявляется в длинных вычислительных цепях, где часто наблюдается “взрыв ошибки”: поскольку оценка продвигается ниже по цепи, относительная точность вычисленных интервалов уменьшается экспоненциально, и они вскоре становятся слишком широкими для использования. Подходы к решению проблемы зависимости в IA включают использование центрированных форм, обобщенной интервальной арифметики Хансена, и более новой – аффинной арифметики [5].

Обобщенная интервальная арифметика

Работая над проблемой зависимости в IA , Хансен [11] изобрел новую вычислительную модель, которая называется обобщенной интервальной арифметикой (GIA – generalized interval arithmetic ). В этой модели, каждая входная переменная x_i представлена интервалом, как в IA , и каждая промежуточная величина z , вычисленная в процессе оценки ¦(x_1,…, x_n ) представлена как линейная комбинация входных переменных:

= z₀ + z₁ x₁ +…+ z_n x_n ,

где каждый коэффициент z_i сам является интервалом. Только коэффициенты z_i записываются для каждой величины z ; переменные x_i подразумеваются. Т.о. GIA представляет величины многочленами первой степени с интервальными коэффициентами.

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

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

= [5, 7] x₁ + [3, 4] x₂ ,

= [4, 6] x₁ + [4, 5] x₂ ,

где переменные x₁ и x₂ имеют диапазоны [-10, 10]. Из этих данных мы можем вывести, что y и z содержатся в интервале [-110, 110]. В GIA модели разность = – оценивается

= [-1, 3] x₁ + [-2, 0] x_{2 .}

Это означает, что w находится в [-30, 30], в то время как IA дает [-220, 220].

Аффинная арифметика

Другая модель, применяемая к проблеме зависимости – аффинная арифметика (AA – affine arithmetic ) [4]. В AA каждая величина x представлена аффинной формой

= x₀ + x₁ e₁ + x₂ e₂ + … + x_n e_n ,

где x₀ – центр формы, x_i (i = 1 ,..,n ) – известные вещественные коэффициенты (записанные как числа с плавающей точкой), называемые частичными отклонениями, и e_i – символьные переменные, называемые символами шума, чьи значения могут произвольно изменяться в интервале [-1, 1]. Т.о. AA поверхностно подобна GIA в том, что обе они представляют величины полиномами первой степени от символьных переменных. Тем не менее, как мы увидим ниже, число членов используемых в AA растет при выполнении вычисления, в то время как число членов используемых в GIA фиксировано и равно числу входных переменных.

Аффинные формы неявно представляют частичные зависимости между операндами: когда две аффинные формы совместно используют общие символы шума, величины, ими представленные, по крайней мере, частично зависят одна от другой. Как и в GIA , принятие таких зависимостей во внимание позволяет AA обеспечивать намного более точные оценки диапазонов, чем в IA , особенно в длинных вычислительных цепях. Другая основная польза, которая связана с этим, – то, что ошибка аффинного представления квадратично зависит от размера W, а не линейно.

AA используется в диапазонном анализе следующим образом. Вначале преобразовываем все входные интервалы к аффинным формам. Затем оперируем этими аффинными формами с помощью AA для вычисления желаемой функции. Окончательно, преобразовываем результат назад в интервал. Преобразования между IA и AA представлениями очевидны. Данный интервал = [a , b ] представляет некоторую величину x эквивалентной аффинной формой = x₀ + x_k e_{k ,} где x₀ = (b+a) /2, x_k = (b-a) /2. Поскольку входные интервалы обычно представляют независимые переменные, то для каждого входного интервала должен быть использован новый символ шума e_k . Обратно, значение величины, представленной аффинной формой = x₀ + x₁ e₁ + x₂ e₂ + … + x_n e_n , гарантированно будет лежать в интервале [x₀ - x , x₀ + x ], где x = || || = å|x_i |. Заметим, что [x₀ - x , x₀ + x ] – самый маленький интервал, содержащий все возможные значения , в предположении, что каждый e_i изменяется независимо в интервале [-1, 1].

Для оценки функции ¦ в AA , мы должны заменить каждую примитивную операцию Ф , которая появляется в выражении ¦ на эквивалентную операцию над аффинными формами, как это сделано в IA для интервалов. Для линейных операций z = Ф (x, y) соответствующая аффинная форма может быть выражена точно, как линейная комбинация символов шума, присутствующих в формах и . Т.е. если

= x₀ + x₁ e₁ + x₂ e₂ + … + x_n e_{n ,}

= y₀ + y₁ e₁ + y₂ e₂ + … + y_n e_{n ,} и a ÎR , то:

± = (x₀ ± y₀ ) + (x₁ ± y₁ ) e₁ + (x₂ ± y₂ ) e₂ + … + (x_n ± y_n ) e_{n ,}

a = ( a x₀ ) + ( a x₁ ) e₁ + ( a x₂ ) e₂ + … + ( a x_n ) e_{n ,}

± a = (x₀ + a ) + x₁ e₁ + x₂ e₂ + … + x_n e_n

Заметим, что разность – равна 0, – полезное свойство, которое не верно в IA (или даже в GIA ). Отсутствие таких тривиальных сокращений в IA является одним из источников взрыва ошибки.

Когда примитивная операция Ф нелинейна, значение не может быть выражено непосредственно как линейная комбинация e_i . В этом случае, мы подбираем хорошую линейную аппроксимацию для Ф (“хорошую” в чебышевском смысле минимизации максимальной ошибки), и добавляем дополнительный член z_k e_k для представления ошибки этой аппроксимации:

= z₀ + z₁ e₁ + z₂ e₂ + … + z_n e_n + z_k e_k .

Здесь e_k – новый шумовой символ и z_k – верхняя граница ошибки аппроксимации. Выбор линейной аппроксимации должен принимать во внимание диапазоны операндов, которые подразумеваются аффинными формами и , и, возможно, также их взаимосвязь. Отметим, что в отличие от GIA , число членов, используемых в аффинных формах, растет во время оценки формулы. (При необходимости, лишние члены могут быть объединены и заменены новыми шумовыми символами ценою некоторой потери точности)

Важно заметить, что для дифференцируемой операции Ф граница ошибки z _k хорошей чебышевской аппроксимации зависит квадратично от диапазонов операндов || || и || ||. Т.о., если функция ¦ использует только дифференцируемые операции, то различие между действительным диапазоном ¦ и диапазоном, вычисленном в AA стремится к нулю в относительном смысле при сужении области. Напротив, внутренние ошибки IA (следствие неучтенных взаимосвязей) зависят линейно от размеров области; поэтому различие будет уменьшаться только в абсолютном смысле.

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

z₀ = x₀ y₀ , z_i = x₀ y_i + y₀ x_i , z_k = || ||×|| ||.

Граница ошибки || ||×|| || не точна, а более чем в два раза больше максимальной ошибки. Для получения более точной границы, мы должны принять во внимание связь x и y , следующую из их аффинных форм, но еще не ясно, получим ли мы от этого выигрыш.

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

В качестве простого примера того, как AA обрабатывает проблему зависимости, рассмотрим оценку z = x(10 – x) в AA для x в интервале [4, 6]:

= 5 + 1e₁

10 – = 5 - 1e₁

= (10 – ) = 25 + 0e₁ + 1e₂

[ ] = [25 - 1, 25 + 1] = [24,26].

Т.о. AA вычисляет оценку очень близкую к [24, 25] – действительному диапазону z . С другой стороны, IA оценка есть [16, 36]. Если выражение x (10 – x ) раскрыто в 10x – x ² , то IA оценка становится значительно хуже, [4, 44], в то время как оценка в AA точна – [24, 25].

Смешанная интервально-аффинная арифметика

Преимущество аффинной арифметики над интервальной арифметикой всецело зависит от ее способности определить и использовать зависимости между операндами. Когда такая зависимость отсутствует, или случайно согласуется с консервативными предположениями IA , AA оценки могут быть шире, чем в IA – даже не смотря на то, что аффинная арифметика более точна, чем интервальная.

Объяснением этого парадоксального факта служит то, что IA пытается окружить график каждой элементарной функции ортогональным параллелепипедом минимального вертикального размера, в то время как AA ищет наклонный параллелепипед минимального объема. Например, рассмотрим операцию возведения в квадрат z = x ² , для x Î[1, 3]. IA дает (узкий) диапазон [1, 9] для z ; а AA представляет x как = 2+1e₁ , и производит = 4.5 + 4e₁ + 0.5e₂ , чей диапазон [0, 9]. Заметим, что IA говорит только то, что пара (x , z ) лежит в прямоугольнике площади 2 * 8 = 16, в то время как результат AA ограничен параллелограммом площади 2 * 1 = 2.

Этот недостаток оценок диапазонов в AA, к сожалению, имеет тенденцию проявляться, когда в функции ¦ преобладают члены, подобные квадрату, оцениваемые возле своего минимума – именно там, где нам нужны точные нижние границы.

Эта проблема может быть решена путем объединения IA с AA . В этой смешанной модели каждая величина x представлена и аффинной формой и стандартным интервалом [x ]. Каждая операция z = Ф (x, y) выполняется в обеих вычислительных моделях . Интервальная часть [z ] результата – это множество, являющееся пересечением диапазонов, вычисленных в IA и в AA ; и AA- процедура использует интервалы [x ] и [y ] при выборе чебышевской аппроксимации для Ф . Таким образом, IA и AA находятся во взаимодействии на каждом шаге: явные интервалы, полученные IA, приводят к лучшим выборам для самых лучших линейных аппроксимаций и к меньшим значениям для члена ошибки z _k ; в то время как аффинные формы в AA позволяют сокращать связанные ошибки, и, следовательно, приводить к более узким интервалам. В частности, смешанная AAIA (affine arithmetic – interval arithmetic ) схема вычисляет неотрицательные диапазоны для Ф (x) = x ² , без потери информации о зависимости, обеспеченной AA .

Управление ошибкой округления

Когда используется точная арифметика, IA и AA всегда вычисляют математически допустимые границы для диапазона значений последовательности операций. Эти границы могут включать реальный диапазон, но они всегда правильны. Однако IA и AA , будут выполняться на цифровом компьютере, который использует арифметику с плавающей точкой, которая подвержена ошибкам округления. Но все же IA и AA способны произвести математически допустимые границы на любом вычислительном устройстве, поддерживающем контроль над округлением. Наиболее современные вычислительные архитектуры обеспечивают контроль над ошибками округления, реализуя IEEE стандарт чисел с плавающей точкой [4].

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

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

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

Оценка границ значений функций посредством

интервального разложения в ряд Тейлора

Любую n +1 раз непрерывно дифференцируемую функцию ¦ в окрестности точки x ^* можно разложить в ряд Тейлора

¦(x ) = + R_n (x , x ),

где

R_n (x , x ) = ,

и x лежит на отрезке, соединяющим точки x и x ^* . Отсюда следует, что для любого x из интервала X значение ¦(x ) будет принадлежать интервалу

T_n (X) = + ,

где вещественные операции заменены на соответствующие им интервальные операции и x ^* ÎX . T_n (X) называется интервальным многочленом Тейлора n -го порядка. Как и для других методов, для T_n (X) справедливо условие

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

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

Схемы разбиения

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

Способы определения того, как разбивать данный параллелепипед сильно варьируются. Параллелепипед можно делить пополам вдоль самого длинного ребра, делить пополам вдоль наиболее перспективного направления, или разбивать в соответствии с длиной градиента. Можно также разбивать на k частей, где k некоторое положительное число большее, либо равное 2. Выбор конкретного разбиения определяется из условия задачи, причем для теоретической сходимости алгоритма нужно гарантировать то, что длина при таком разбиении самого длинного ребра стремится к 0.

Ускорение интервальных методов ветвей и границ

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

Если целевая функция ¦ дифференцируема достаточное количество раз, то простой способ ускорить метод ветвей и границ состоит в использовании одного из многих быстрых методов локальной оптимизации [10]. Локальная оптимизация может быть совмещена с интервальными проверками для градиента или гессиана: если интервальная оценка для градиента Ñ ¦ на подобласти D не содержит 0, то D не может содержать локальный минимизатор. Если интервальная оценка для гессиана показывает, что он положительно определен на D, то D также не может содержать локальный минимизатор.

Back-Boxing

Back-Boxing [1] – методика ускорения для алгоритмов ветвей и границ, объединяющая процедуры быстрого локального поиска с результатом проверяющих методов для устранения и уменьшения большого объема выполненной работы, когда она выполняется вблизи локального минимума. Цель Back-Boxing ’а состоит в том, чтобы определить большие области в W, где целевая функция ¦ гарантированно имеет один локальный минимум. Если только такие области известны, их локальный минимум может быть вычислен эффективно и затем проверен, является ли он глобальным минимумом.

Back-Boxing первоначально локализует минимум x ^* в некоторой подобласти D. Затем ищется наибольший параллелепипед B ÍD, такой, что x ^* - уникальный локальный минимум для B ; область D\B затем помещается в список L для дальнейшей обработки. Поскольку мы теперь знаем, что параллелепипед B имеет уникальный минимум, нам в дальнейшем не нужно делить B , в попытке найти меньшее значение функции.

Аффинное оценивание элементарных функций

Для эффективного и широкого применения рассмотренных выше алгоритмов нужно уметь находить интервальные и аффинные оценки всех входящих в целевую функцию элементарных функций. В то время как задача получения интервальных оценок хорошо изучена и проста в реализации на вычислительном устройстве, аффинное оценивание является процессом значительно более сложным и мало изученным [5]. Автором данной работы были детально исследованы и усовершенствованы способы аффинного оценивания функций, и разработаны соответствующие алгоритмы. Некоторые результаты этого исследования мы рассмотрим ниже.

Как уже было сказано, чтобы оценить формулу в AA мы должны заменить каждую из элементарных операций z = ¦(x , y ) на вещественных числах эквивалентной операцией = ( , ) над аффинными формами [4,7], где - процедура, вычисляющая аффинную форму z = ¦(x , y ), которая соответствует , .

По определению

x = x ₀ + x ₁ e₁ + … + x _n e_n (1)

y = y ₀ + y ₁ e₁ + …+ y _n e_n (2)

для некоторых (неизвестных) значений (e₁ , …, e_n) ÎUⁿ , где Uⁿ есть декартово произведение n вещественных интервалов [-1, 1]. Поэтому величина z есть функция e_i , а именно

z = ¦(x , y ) = ¦(x ₀ + x ₁ e₁ + … + x _n e_n , y ₀ + y ₁ e₁ + …+ y _n e_n ) = ¦*(e₁ ,…,e_n ) (3)

Процедура теперь должна заменить ¦*(e₁ ,…,e_n ) аффинной формой

= z ₀ + z ₁ e₁ + …+ z _n e_n,

которая сохраняет столько информации, сколько возможно из соотношений между x , y и z , вытекающих из (1-3), но без использования других ограничений, которые не могут быть выведены из начальных данных.

В общем случае, когда ¦ является нелинейной операцией, функция ¦*(e₁ ,…,e_n ) = ¦(x , y ) из (3) не может быть выражена как линейная комбинация e_i . В этом случае мы можем подобрать некоторую линейную функцию

¦^a (e₁ ,…,e_n ) = z ₀ + z ₁ e₁ + …+ z _n e_n , (4)

которая аппроксимирует ¦*(e₁ ,…,e_n ) равномерно на области Uⁿ , и затем добавить к ней дополнительный член z _k e_k , представляющий ошибку аппроксимации. Таким образом,

z = ¦^a (e₁ ,…,e_n ) + z _k e_k = z ₀ + z ₁ e₁ + …+ z _n e_n + z _k e_k.

Здесь e_k должен быть новым символом шума (отличным от всех других символов шума в одном вычислении) и величина z _k должна быть верхней границей модуля разницы между ¦^a и ¦* для всех возможных значений e₁ ,…,e_n ; т.е.

max { | ¦*(e₁ ,…,e_n ) - ¦^a (e₁ ,…,e_n ) | : (e₁ ,…,e_n )ÎUⁿ }

Заметим, что замена ¦* на ¦^a + z _k e_k частично отходит от основной цели AA : символ шума e_k принимается независимым от e₁ ,…,e_n , в то время как фактически это функция от них. Любые последующие операции, использующие z в качестве входного значения, не имеют сведений о взаимосвязи между e_k и e₁ ,…,e_n и поэтому могут возвращать аффинную форму, которая менее точна, чем необходимо.

Для минимизации потерянной информации мы должны выбрать коэффициенты z ₀ , z ₁ ,…, z _n таким образом, чтобы сделать новый член ошибки как можно меньше.

Другими словами ¦^a должна быть многочленом первой степени, который наилучшим образом аппроксимирует ¦* на Uⁿ в смысле Чебышева минимизации максимальной ошибки.

Отметим одно свойство, которое окажется нам полезным в дальнейшем. Пусть нам надо найти наилучшую линейную аппроксимацию для функции ¦(x (e₁ ,…,e_n )), где x (e₁ ,…,e_n ) = x ₀ + x ₁ e₁ + … + x _n e_n , тогда ¦*(e₁ ,…,e_n ) = ¦(x ₀ + x ₁ e₁ + … + x _n e_n ) аппроксимируется на гиперкубе Uⁿ некоторой функцией ¦^a (e₁ ,…,e_n ) = z ₀ + z ₁ e₁ + …+ z _n e_n . Заметим, что функция ¦*(e₁ ,…,e_n ) – константа на любой гиперплоскости из Uⁿ , ортогональной вектору (x ₁ ,…, x _n ). Нетрудно показать, что наилучшая (по Чебышеву) линейная аппроксимация ¦* также должна обладать этим свойством. Т.е. нам нужно рассматривать только аппроксимации ¦^a (e₁ ,…,e_n ) вида

¦^a (e₁ ,…,e_n ) = a + b = a( x ₀ + x ₁ e₁ + … + x _n e_n ) + b.

Также легко показать, что значения a и b, которые минимизируют максимальную ошибку ¦^a – ¦* есть в точности коэффициенты наилучшей линейной аппроксимации функции ¦(t ) функцией at + b на интервале [ ]. Таким образом, задача аппроксимации исходной функции n переменных редуцируется в задачу аппроксимации функции одной переменной. Можно показать (см. [16]), что для функции одной переменной прямая at + b будет наилучшей линейной аппроксимацией на отрезке [a , b ], если

a = , b = (5)

Далее мы построим линейное приближение для конкретных функций: и e^x . Техника, иллюстрируемая этими примерами, может быть легко распространена на большинство других элементарных операций и функций.

Аффинная оценка функции

Итак, рассмотрим аффинную оценку функции [8]. Нам нужно аппроксимировать функцию ¦*(e₁ ,…,e_n ) = на гиперкубе Uⁿ некоторой функцией ¦^a (e₁ ,…,e_n ) = z ₀ + z ₁ e₁ + …+ z _n e_n и затем добавить к последней дополнительный член z _k e_k для учета ошибки аппроксимации, где e_k вновь созданный символ шума.

Как показано ранее, нам нужно рассматривать только аппроксимации вида ¦^a (e₁ ,…,e_n ) = a + b = a( x ₀ + x ₁ e₁ + … + x _n e_n ) + b.

Если [a , b ] – интервал [ ], то оптимальные чебышевские коэффициенты a и b есть

a =

b =

и максимальная ошибка аппроксимации d =

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

После того как a, b и d получены, мы можем вычислить

z ₀ = ax ₀ + b

z _i = ax _i (i = 1,…,n)

z _k = d

Этот анализ подразумевает, что мы можем вычислить a, b и d точно. На практике же, вычисление a может выйти за пределы машинно-представимых чисел с плавающей точкой и, таким образом, мы получим только приближение a¢ к оптимальному наклону a. Затем мы должны выбрать b так, чтобы минимизировать максимум |a¢x + b - | вместо |ax + b - |. И опять мы сможем только вычислить приближение b¢ к оптимальному b. Ошибка аппроксимации d тогда будет максимумом |a¢x + b¢ - |; и снова мы способны вычислить только верхнюю границу d¢ для нее.

После этого формулы для расчета z _i должны быть изменены для использования a¢, b¢ и d¢ вместо a, b и d. В действительности, вычисление z ₀ , z ₁ ,…, z _n по этим формулам будет ухудшено ошибкой округления; поэтому мы должны будем определить верхние границы d¢₀ , d¢₁ ,…, d¢_n для этих ошибок и добавить их к ошибке аппроксимации d¢, всегда округляемой вверх, для получения ошибочного члена z _k .

Аффинная оценка функции e ^x

Найдем линейную аппроксимацию ¦^a (e₁ ,…,e_n ) = z ₀ + z ₁ e₁ + …+ z _n e_n для функции ¦(x ) = e^x . Пусть a, b и d имеют тот же смысл, что и в предыдущей части, [ ] = [a , b ]. Тогда из (5) следует, что a = . Для вычисления b нам нужно знать максимум и минимум функции d (x ) = e^x - ax на [a , b ]. Производная d (x ) равна d ¢ (x ) = e^x – a. Следовательно, d ¢ (x ) = 0 при x * = ln (a)Î[a , b ]. Но d ¢¢ (x* ) = e^x > 0, то есть x* есть точка, в которой достигается минимум функции d (x ) на [a , b ]. Очевидно, что максимум достигается в точках a или b (причем из определения a имеем d (a ) = d (b )). Таким образом, b = (d (a ) + d (ln(a)))/2 и d = (d (a ) – d (ln(a)))/2.

Как и в случае квадратного корня, мы сможем лишь получить верхние и нижние границы для величин a, b и d (здесь можно воспользоваться механизмом интервальной арифметики). После этого остается только немного перестроить формулы, по которым вычисляются z _i , чтобы получить ¦^a .

Представление аффинных форм на ЭВМ

Описанный выше математический аппарат был применен автором в разработке конкретных библиотек на языке программирования C++. В них описаны такие классы, как интервал (interval), аффинная форма (affine_form) и смешанная аффинно-интервальная форма (mixed_form). Класс affine_form представляет аффинную форму , зависящую от m символов шума. Он содержит такие поля как количество символов шума в форме, центр формы (т.е. x ₀ ) и массив из m членов, состоящих из частичного отклонения x _i и соответствующего индекса i – целого числа, которое уникально определяет символ e_i . Обозначения символа шума требуется записывать потому, что аффинная форма достаточно разрежена: поскольку данная программа может генерировать миллиард символов шума, каждая аффинная форма будет обычно зависеть от малого их подмножества. Поэтому ясно, что имеет смысл для каждой аффинной формы записывать только ненулевые члены x _i e_i .

Обычно любая аффинная форма, появляющаяся в вычислении будет иметь различное число членов с различным множеством индексов символов шума. Две аффинные формы зависимы тогда и только тогда, когда они включают члены с одинаковыми индексами i .

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

Общие подформулы

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

Практическая реализация алгоритмов

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

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

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

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

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

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

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

Автором разработаны соответствующие алгоритмы на языке программирования C++ для решения проблем 1 – 4, причем главная цель, которая здесь преследовалась, состояла не в реализации отдельных методов, а в построении общей вычислительной среды или системы, основанной на самых современных принципах программирования, в которой разработка конкретных методов оказалась бы тривиальной задачей. В качестве примера, демонстрирующего возможности этой системы, с помощью нее разработан алгоритм, реализующий метод ветвей и границ с градиентной проверкой, и протестирован на нескольких тестовых задачах.

Автоматический анализ функций

Пусть целевая функция подается на вход оптимизатора в виде символьной строки и списка имен переменных, от которых она зависит (для простоты здесь полагается, что функция задана в виде суперпозиции известных элементарных функций, а не алгоритмически). Если полученные данные корректны, то, производя лексический и синтаксический разбор входной символьной строки эту функцию всегда можно представить в виде дерева, с узлами, содержащими данные трех типов: константы (t_constant_data), переменные (t_variable_data) и операторы (t_operator_data). Как известно, между обычными и бинарными деревьями существует взаимно однозначное соответствие. Поэтому обычные деревья удобнее обрабатывать и хранить именно в виде право-прошитых бинарных деревьев [15], которые во всех дальнейших рассуждениях, для краткости, называются просто деревьями. На C++ такое дерево может быть описано в виде класса t_function_node, определив операции над объектами которого (по сути операции над деревьями) можно строить сколь угодно сложные суперпозиции функций. Например, если T ₁ и T ₂ деревья (или объекты класса t_function_node), то T ₁ + T ₂ есть дерево с корнем, содержащем данные типа “binary_plus_operator” и имеющее в качестве левого поддерева дерево T ₁ , а в качестве правого подде
рева дерево T ₂ (см. рис. 2).