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

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

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

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

¦^a(e₁,…,e_n) = a

+ b = a( x₀ + x₁e₁ + … + x_ne_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_ne_n и затем добавить к последней дополнительный член z_ke_k для учета ошибки аппроксимации, где e_k вновь созданный символ шума.

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

+ b = a( x₀ + x₁e₁ + … + x_ne_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_ne_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_ie_i.

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

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

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

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

для аффинного оценивания, вдвойне важно определить общие подвыражения, подобно x², и вычислить каждое из них только однажды.

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

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