Построение единой программной среды для решения задач глобальной оптимизации (стр. 5 из 9)
Надежное функционирование IA должно использовать направленные округления для вычисления результата каждой примитивной операции: нижняя граница результирующего интервала должна быть округлена вниз и верхняя граница должна быть округлена вверх.
Контроль ошибки округления в AA не так прост для реализации. Один путь для выполнения этого контроля в AA – иметь специальный член шума, отвечающий только за ошибки округления. Этот член ведет себя отлично от других ошибочных членов, в том, что он всегда неотрицателен, никогда не уменьшается и обрабатывается по аналогии с другими членами ошибки, но с везде принятым абсолютным значением и все его вычитания заменяются сложением.
В IA много дополнительной работы требуется для направленного округления переменных. Для AA количество требуемой работы более чем удвоено для разных примитивных операций. К счастью, это не верно для алгоритма в целом, исключая случай, когда окончательная точность решения недостижима из-за машинной точности.
Оценка границ значений функций посредством
интервального разложения в ряд Тейлора
Любую n+1 раз непрерывно дифференцируемую функцию ¦ в окрестности точки x* можно разложить в ряд Тейлора
¦(x) =
+ Rn(x, x),где
Rn(x, x) =
,и x лежит на отрезке, соединяющим точки x и x*. Отсюда следует, что для любого x из интервала X значение ¦(x) будет принадлежать интервалу
Tn(X) =
+ 
,где вещественные операции заменены на соответствующие им интервальные операции и x*ÎX. Tn(X) называется интервальным многочленом Тейлора n-го порядка. Как и для других методов, для Tn(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 = x0 + x1e1 + … + xnen (1)
y = y0 + y1e1 + …+ ynen (2)
для некоторых (неизвестных) значений (e1, …, en)ÎUn, где Un есть декартово произведение n вещественных интервалов [-1, 1]. Поэтому величина z есть функция ei, а именно
z = ¦(x, y) = ¦(x0 + x1e1 + … + xnen, y0 + y1e1 + …+ ynen) = ¦*(e1,…,en) (3)
Процедура
теперь должна заменить ¦*(e1,…,en) аффинной формой = z0 + z1e1 + …+ znen,которая сохраняет столько информации, сколько возможно из соотношений между x, y и z, вытекающих из (1-3), но без использования других ограничений, которые не могут быть выведены из начальных данных.
В общем случае, когда ¦ является нелинейной операцией, функция ¦*(e1,…,en) = ¦(x, y) из (3) не может быть выражена как линейная комбинация ei. В этом случае мы можем подобрать некоторую линейную функцию
¦a(e1,…,en) = z0 + z1e1 + …+ znen, (4)
которая аппроксимирует ¦*(e1,…,en) равномерно на области Un, и затем добавить к ней дополнительный член zkek, представляющий ошибку аппроксимации. Таким образом,
z = ¦a(e1,…,en) + zkek = z0 + z1e1 + …+ znen + zkek.
Здесь ek должен быть новым символом шума (отличным от всех других символов шума в одном вычислении) и величина zk должна быть верхней границей модуля разницы между ¦a и ¦* для всех возможных значений e1,…,en; т.е.
max { | ¦*(e1,…,en) - ¦a(e1,…,en) | : (e1,…,en)ÎUn }
Заметим, что замена ¦* на ¦a + zkek частично отходит от основной цели AA: символ шума ek принимается независимым от e1,…,en, в то время как фактически это функция от них. Любые последующие операции, использующие z в качестве входного значения, не имеют сведений о взаимосвязи между ek и e1,…,en и поэтому могут возвращать аффинную форму, которая менее точна, чем необходимо.