Построение единой программной среды для решения задач глобальной оптимизации (стр. 3 из 9)

где 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_nx_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_ne_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_ke_k, где x₀ = (b+a)/2, x_k = (b-a)/2. Поскольку входные интервалы обычно представляют независимые переменные, то для каждого входного интервала должен быть использован новый символ шума e_k. Обратно, значение величины, представленной аффинной формой

= x₀ + x₁e₁ + x₂e₂ + … + x_ne_n, гарантированно будет лежать в интервале [x₀ - x, x₀ + x], где x = ||

|| = å|x_i|. Заметим, что [x₀ - x, x₀ + x] – самый маленький интервал, содержащий все возможные значения

, в предположении, что каждый e_i изменяется независимо в интервале [-1, 1].

Для оценки функции ¦ в AA, мы должны заменить каждую примитивную операцию Ф, которая появляется в выражении ¦ на эквивалентную операцию

над аффинными формами, как это сделано в IA для интервалов. Для линейных операций z = Ф(x, y) соответствующая аффинная форма

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

и

. Т.е. если