функцию из примера 8.4. В х„=1 алгоритм FD дает для нее Лг= .819х 10-. Если использовать этот интервал для оценки f (х) при Х(,= 10, то относительная погрешность tfp составит .409x10- (значения и f для л-=10 равны .971x10» и .970286 X 10). Пусть теперь алгоритм FD применяется в точке х„=10 (с ед = .5х 10). Тогда получится интервал/if = .lOlx 10- и если использовать его для оценки f (х) при х=1, относительная погрешность ф окажется равной .102x10 Подобная картина типична, хотя, разумеется, нетрудно сконструировать такую f, чтобы «оптимальные» интервалы в разных точках были совершенно разными.

В заключение отметим, что в п-мерном случае наряду с набором конечно-разностных интервалов алгоритм FD выдаст набор оценс к диагональных элементов матрицы Гессе вхо. Для квазиньютоновского метода это - очень полезная дополнительная информация.

8.6.2.5. Конечно-разностные приближения при решении задач с ограничениями. Подход, изложенный в разд. 8.6.2.1, применим и для выбора интервалов при непосредственной аппроксимации спроектированных градиентов Z(x)g(x) в методах поиска условного минимума: прост надо рассматривать приращения х не вдаль координатных осей, а вдоль векторов, являющихся столбцами матрицы Z (х). Никаких осложнений из-за такой модификации ие возникает. Другое дело, что не ясно, как пересчитывать интервалы по ходу оптимизации - ведь в моменты смен рабочего списка матрица Z может полностью изменяться. Многие вопросы касательно эффективной организации вычисления конечно-разностных интервалов при решении задач с ограничениями пока еще открыты.

Иногда считают, что трудности, связанные с потерей относительной точности аппроксимации производных вблизи решения, не возникнут, если при поиске условного оптимума оценивать полный градиент, а не спроектированный. Основанием служттг отличие g(x*) от нуля. Можно, однако, показать, что конечно-разностное приближение градиента в точке х, близкой к х*, будет иметь высокую точность только в той своей составляющей, которая принадлежит ране-пространству А (х) и при умножении g(x) на Z(x)r обнуляется. Для оптимизации же важна точность приближения составляющей g(x) из нуль-пространства Л (xj, т. е. точность оценивания компонент спроектированного градиента (даже если он не строится явно).

Замечания и избранная библиография к разделу 8.6

Ссылки по поводу конечно-разностной аппроксимации производных даны в замечаниях к разд. 4.6.

8.7. ПОДРОБНЕЕ О МАСШТАБИРОВАНИИ В разд. 7.5.1 уже обсуждалась одна из простых форм масштабирования оптимизационных задач, а именно диагональное преобразование переменных с целью добиться, чтобы в представляющей интерес области нх значения стали величинами одного порядка. Ниже идея масштабирования трактуется в более широком плане, причем речь пойдет как о задачах безусловной минимизации, так п о задачах с ограничениями. Все представленные далее приемы предполагают доступность производных.

8.7.1. МАСШТАВИРОВАНИЕ ЗАМЕНОЙ ПЕРЕМЕННЫХ

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

Мы будем рассматривать только линейные замены вида

x=Ly,

(8.49)

где L.- фиксированная невырожденная матрица. (О нелинейных заменах кратко говорилось в разд. 7.4.1.) Обозначим через 3(у) суперпозицию F и (8.49), т. е.

¥{y)F{Ly). (8.50)

Тогда производные ¥ по у будут связаны с производными F по X следующим образом: V„ = ig(x), VyS = LW (х) L.

8.7.1.1. Инвариантность методов относительно замен переменных. Допустим, что некая задача сначала была сформ}Лирована в переменных х, а затем был совершен переход к переменным у, связанным с X преобразованием (8.49). Пусть, далее, к исходной и преобразованной задачам применяется один н тот же метод, причем в ка-честве начальных приближений берутся соответственные точки, т. е. Xo=Li/„. Обозначим через {хд } и {i/t} генерируемые последовательности. Если

Xt-Lyt (8.51)

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

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

тоБ ( И те И другие обеспечивали бы (8.51) при условии, что матрицы Гессе или ее приближения будут положительно определенными на всех итерациях). Однако при машинной реализации методов инва-риатность неизбежно теряется.

Первая причина - неинвариантность вычислений с конечной точностью по отношению к масштабам операндов. Например, ошибки округления при подсчете на машине сумм x,+Xs и axi+fixi будут связаны простым образом только при а=р.

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

8.7.1.2. Обусловленность матрацы Гессе. Важной характеристикой задачи минимизации без ограничений является число обусловленности матрицы Гессе ее целевой функции в точке оптимума. Если оно велико, отклики F на одинаковые по норме, но разные по направлению вариации х* могут быть существенно разными. Эта одна из форм плохой отмасштабированности.

С вычислительной точки зрения большой разброс собственных чисел С{х*) нежелателен ио нескольким причинам. В частности, как следует из разд. 8.2.2.1, чем хуже обусловлена С (х*), тем меньше точность численного решения, на которую можно рассчитывать. К тому же плохая обусловленность С (х*) отрицательно сказывается на характеристиках методов. Например, она может приводить к деградации (утрате сверхлинейной сходимости) алгоритмов, в которых направления спуска определяются решением систем линейных уравнений, включающих матрицы С(х) (нли их аппроксимации).

Один из способов улучшить обусловленность С(х*) - подобрать подхо,цящую замену переменных. При известной (и положительно определенной С(х*)) идеальным было бы преобразование (8.49) с

L = G(x*)-4, (8.52)

после которого матрица Гессе, отвечающая решению, становится единичной. (Некоторые алгоритмы безусловной минимизации можно проинтерпретировать как итерационный попек матрицы (8.52); в частиосги, к таковым относятся квазиньютоновские методы и методы сопряженных градиентов.) Однако, поскольку обычно мы не знаем С(х*), на практике приходится использовать другие L. Если вторые производные доступны п есть основания полагать, что в точках Хи и X* они будут различаться «не слишком сильно», то в качестве L для (8.49) берут С(Хо)-.. Располагая лишь первыми производными, L строят по конечно-разностной аппроксимации G(xJ.

Наконец, не имея возможности вычислять даже градиенты, иногда применяют диагональное масштабирование. Точнее говоря, выполняют преобразование с матрицей L, у которой на диагонали стоят квадратные корни (вычисляемых по значениям F) конечно-разностных оценок в Хо соответствующих вторых производных (процедура построения таких оценок описана в разд. 8.6.2.2), а остальные элементы равны нулю. Еще раз подчеркнем, что все это имеет смысл, только если между матрицами Гессе в хц и в х* нет больших различий.

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

Пример 8.7. Допустим, что требуется найти минимум функции двух переменных

F (x)=x?xS,

где b и с - константы. Матрица Гессе F(x) выглядт так: (Ьф-\)х1 bcxjXj

С(х) = -, .

xixi \trx,Xj

При этом справедливо разложение С(х) =

bcxjXj Л v(c-\)xi)-

(8.53)

, РДГ. О - Vrx. 6х,

с Р==А(6-1), Г=Ьс№ и 6=с(1-c)/(ft-I). Обобусловленности С(х) можно судять (см. разд. 8.3.3.2) по отнонюнию максимальною по модулю диагонального элемента L к минимальному, т. е. в предположении, чго Px,>6xJ,

cond(G) = cond(Z.)=

Отсюда видно, что если Р и 6 - величина одного порядка, то для достижения хорошей обусловленности С(х*) достаточно применить диагональное масштабирование, обеспечивающее примерное равенство оптимальных значений переменных Ху и Xs (к тому же выводу придем и при pxj!6xi).

8.7.1.3. Балансирование производных. В разд. 7.5.1 была рас-смогрена одна из форм плохой отмасштабированности задачи безусловной минимизации, состоящая в большом разбросе характерных значении модулей переменных. Другая (иногда связанная с первой) форма - «несбалансированность» производных мииимизи-руемой функции. Способы ее преодоления, предлагаемые ниже.

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

Масштабирование по первой производной. Ниже речь пойдет о ситуации, когда какие-то ко.мпоненты градиента «малы» относительно погрешности еа вычисления F. Чтобы проиллюстрировать ее, возьмем функцию семи переменных.

Пример 8.8.

F (x) = (аг, -100)» + (x,-1000)» + (х, + х,-1000)» + + (x,- 1000)»-(х. + х,-200)= + + 10-" (x, +2х, + Зх, + 4х, + 5х, + 6х, + 7х,-1900).

Ее точное значение при х = (0. О, 400, 100, 0. О, 0) равно f (х) = .2219973х 10. Если вычислять F на IBM 370 с одинарной точностью (ej„= 16-ё я:;.9537х 10-), то величина в окрестности x будет иметь поря.чок e«F).

Плохая отмасштабированность F по отношению к первой пере менной становится очевидной при подсчете F в x=x+hei, где шаг Л определяется по формуле (8.47). Будь F хорошо отмасштабированной, такое возмущение привело бы к изменению примерно половины значащих разрядов (см. разд. 8.6.1). На самом же деле меняется (на единицу) лишь последняя цифра мантиссы.

Плохая отмасштабированность рассматриваемого типа особенно опасна, когда применяется конечно-разностная аппроксимация производных и, в частности, когда используются «стандартные» конечно-разностные интервалы. Коль скоро численная оценка производной строится по интервалу, на котором F почти постоянна, доверять ей нельзя: полученное значение может восновном определяться ошибкой условий.

Пример 8.9. Рассмотрим конечно-разностную аппроксимацию для функции из примера 8,8, когда вычисления выполняются иа IBM370 (ед,= 16-> «;.9537х 10-") с одинарной точностью. Если взять «стандартный» интервал

то правая конечно-разностная формула даст оценку gt(x), равную -.512000Х10. В то же время истинным значением g,(x) является -.199730Х IO*. Таким образом, из-за плохой отмасштабированности F «стандартны>Ь> способ выбора Л приводит к совершенно неудовлетворительному результату.

Отметим, что тяжесть последствий обсуждаемого дефекта функции зависит от погрешностей, с которыми проводятся вычисления. Если, скажем, считать на IBM 370 с двойной точностью (когда ед1= 16-"«!.222х ЮЧ), то для той же функции

F при том же Л у F(x) н F(x) будут различаться 9 из 14 значащих шестнадЦатернчных цифр. Правда, если использовать интервал h, который формула (8.54) дает при соответствующем Ед, то у численной оценки производной g, (х) верньши окажутся лни[ь 5 (а не 8, как можно было бы ожидать при хорошо отмасштабированной функции) десятичных разрядов, т. е. и здесь плохая отмасштабированность ощутима.

Большая ошибка аппроксимации производной, наблюдаемая в примере 8.9, объясняется тем, что gi (х) имеет порядок

Кед(1-1- F(x)\). Тейлоровское разложение F вдоль Cj в окрестности x выглядит так:

F (X-)-V/)-FM = h,gj (X) -Ь {hJGjj (x) -f О (Л?). (8.55)

Коль скоро линейная составляющая правой части этого равенства доминирует, изменение F будет хорошо оцениваться величиной \hjgj(x)\. Последняя же при Ai п g,(х) из примера 8.9 близка к ед, т. е. «не выходит за уровень шума».

При определенных условиях рассматриваемую неотмасштаби-рованность производных удается устранить диагональным преобразованием переменных

x=Dy. (8.56)

В результате такого преобразования из F получается функция ¥ {у), разложение которой вдоль бу в окрестности точки i/ = D-x будет выглядеть так:

(У+УА)- {У)=уАу (y) + -ylejr(y)e,. + 0(yj) =

= yjdjgj (X) + i тЧЧу W + 0{fi)- (8.57)

Когда нелинейными по Yj слагаемыми можно пренебречь, отсюда следует, что модуль приращения W в результате сдвига yj на yj примерно равен \yjdjgj\.

При выборе dj исходят из желания добиться, чтобы при шаге, равном значению «оптимального» конечно-разностного интервала К (8.54), изменялась «половина» значащих разрядов F. Это приводит к уравнению

2]d,.g,\\ + \F(x)\

С решением

l+f Ml

(8.58)

2g/(x)

Масштабирование на основе вторых производных. Рассмотрим случай, когда в правой части (8.57) можно пренебречь линейным по dj слагаемым. В частности, при нулевой производной gy (х) изменение St при шаге yjCj будет равно

(J-H-TA)- Ш=у1ЧСА()+0(у1). (8.59)