Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [ 66 ] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

ции по системе MINOS (Муртаф и Сондерс (1977)) и в книге Муртафа j (1981).

Сервисные процедуры для проверки правильности программ вычисления производных имеются во всех больших оптимизационных библиотеках. По этому поводу см. работы Мюррея (1972b), Вулфа (1976) и Море (1979а).

8.2. СВОЙСТВА ЧИСЛЕННОГО РЕШЕНИЯ 8.2.1. ЧТО ТАКОЕ ПРАВИЛЬНЫЙ ОТВЕТ?

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

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

В разд. 2.1 уже отмечалось, что машины не способны находить абсолютно точные решения даже для очень простых задач. Поэтому требовать от них такие решения бессмысленно, и надо довольствоваться «хорошими» приближениями. Таким образом, встает проблема оценивания качества последних.

Принципиальная трудность состоит в том, что, ориентируясь на известные свойства аналитического решения, не всегда можно вынести правильное суждение о пригодности численного решения. Формальным выражением этих свойств обычно служит равенство Д(х*)=0,

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

;A(x);<6,

где 6-«малое» число. Конкретную величину 6 следует выбирать очень аккуратно с учетом особенностей задачи (иногда «малым» можно считать и 6=10).

К сожалению, норма вектора Д не обязательно (а точнее, редко) непосредственно характеризует расстояние до искомой точки: свя:»1

1Ч-х* ( < [х,-х* (» Д (xJ < А {X,). (8.5)

как правило, нет. При этом, чем хуже обусловлена задача, тем труднее хорошо оценить близость к х* по вычислимым критериям. Отсюда и возникают значительные отклонения «корректных численных решений» от аналитических. Сказанное проиллюстрировано в разд. 8.2.2.1 на примере с плохо обусловленной квадратичной формой.

Теперь несколько слов о причинах, по которым программа может выдать сообщение об отказе, хотя в действительности найден «правн-льный» ответ. Таковые бывают разными, но и здесь дело обычно в том, что неверно оценивается точность имеющегося приближения. Какие бы приемы для этого нн прив.лекались, всегда находятся ситуации, в которых они оказываются неудачными. Признак отказа, означающий, что установленных критериев близости к X* соблюсти не удается, часто является лишь следствием выхода на предел точности, обусловленный погрешностями машинной арифметики (см. разд. 8.2.2).

1 8.2.2. ПРЕДЕЛЬНАЯ ТОЧНОСТЬ РЕШЕНИЯ

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

Предельная точность чттсленного решения сильно .зависттт от погрешностей вычисления функций задачи. Ниже эти погрешности описываются верхней границей еа ЛЛи абсолютной ошибки подсчета F в X* (ед может автоматически оцениваться программой по указанному пользователем порогу ошибки подсчета F в начальной точке; см. разд. 8.5.3).

8.2.2.1. Задачи без ограничений. Для гладких задач безусловной минимизации в роли вычислимых показателей качества приближений обычно используют значения целевой функции F и ее градиента. Допустим, и.звестно, что результатом вычисления F в х* будет fl(F(x*)) = F(x)+o. (8.6)

где а-некое число, удовлетворяющее неравенству laKe,. Тогда все точки X, для которых

\F(x)-F{x)\e. (8.7)



приходится признать «неразличимыми»: каждая из них может оказаться численно неулучшаемой. Следовательно, (8.7) и есть основа для оценивания предельной точности. Любую лг, удовлетворяющую этому неравенству, будем называть прие.члемьин peiuenueM.

Общие соображения. Посмотрим, какие к выражение (8.7) допускает в случае, когда F дважды непрерывно дифференцируема, а д;*-точка сильного локального минимума, т.е. я(л:*)=0, и матрица С(х*) положительно определена. Для этого воспользуемся разложением F в окрестности х по Тейлору. Его можно записать так:

f (X) = f (X* + Лр) = F (у.*) +~ lipC (х*) р + 0 {Щ, (8.8)

где IIр 11= 1 и I /г = Jx-х*. Отсюда следует, что граничные х должны удовлетворять соотношению

IF (x)-F (х») \~h\ рС (X*) р I » 1

или, что эквивалентно.

Их-х»

(8.9)

рТО М р

Из (8.9) хорошо видно, как влияет на значения х-х* обусловленность матрицы G(x*): при плохо обусловленной С (х*) предельные уклонения х от х* для разных направлений р оказываются существенно различными. В частности, при р, представляющих собой линейные комбинации тех собственных векторов С (х*), которым отвечают наибольшие собственные значения, правая часть (8.9) будет относительно малой, в то время как вдоль собственных векторов G (х*), соответствующих наименьшим собст-венны.м значениям, допускаются намного более сильные уклоне-иия. Из сказанного ясно, что для плохо обусловленной задачи ошибка приемлемого решения по некоторым направлениям может оказаться весьма ощутимой.

В связи с тем что одним из наиболее употребительных критериев качества приближений является малость нормы градпента, полезно оценить и предельную точность совпадения g{x) с нулем. Разложим g(x) в окрестности х* по Тейлору:

g(x)=g (х« + hp) = hG (х«) р + 0 (h)

(напомним, что g(x*)=0). Чтобы получить искомую оценку, отбросим остаточный член, возведем полученное приближенное равенство в квадрат и подставим вместо h- правую часть (8.9). Это даст соотношение вида

(8.10)

Снова легко просматривается влияние обусловленности G (х). Если она плохая, то норма lg(x) будет бо.чьшой, когда р есть линейная комбинация собственных векторов G (х*), отвечающих наибольшим собственным значениям, и малой, когда соответствующие собственные значения относятся к группе наименьших.

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

F(x„ xj = u,-l)«+10-«(x,-1)+1. Ясно, что ее минимум достигается в х* = (1, 1). Пусть е = 10"" Тогда точк х = (1, 2Y будет граничным приемлемым решением: для нее F(x)= 1--10-. При этом [х-х*1 j= 1. Еще одно граничное приемлемое решение-точка х = (1-1-10-*, 1)Г; для нее тоже имеет место равенство F (х) = F (х*) + Ю-Если судить по удаленности от X*, то X намного лучше, чем х. Однако \g{x)l~2x /ч10-, а g(x) г = 2х 10-, т.е. по близости градиента к ну.пю - Стандартному критерию качества-«лучшей» ока.зывается х. Этот пример подтверждает высказанное в разд. 8.2.1. положение о том, что вычислимые критерии качества лишь косвенно отражают расстояние до искомой точки.

Хорошо отмасштабированные задачи. Чтобы представить себе характерные порядки предельных ошибок, надо посмотреть, какими они будут для «хорошо отмасштабированной» задачи (разд. 8.7). Имеется в виду тот случай, когда число обусловленности матрицы Гессе G(x*) не «очень велико» и F(x*), х* есть величины порядка единицы. В этих предположениях из (8.9) и (8.10) следуют оценки вида

Цх-х* = 0(К)

£г(Г)=0()/).

Среди прикладных программистов уже давно бытует мнение, что если F хорошо отмасштабирована, то в норме приемлемого решения будет примерно вдвое меньше правильных разрядов, чем в расчетных значениях F; первое из представленных соотношений вполне согласуется с ним. (По поводу относительной точности отдельных компонент X ничего сказать нельзя.) Более того, аналогичная оценка справедлива и для нормы градиента.

Обычно Ед>е.л,/; это значит, что число правильных разрядов в х, как правило, не превзойдет половины длины мантиссы. Однако, если F удается вычислять с повышенной точностью, реальны и меньшие ошибки (см. разд. 8.5.1.3).



Негладкие задачи. До сих пор речь шла о дважды неппевывнп дифференцируемых функциях. Если же F М разрь1вна Гвчаст ности, имеет разрыв в к\ неравенством (8.7) будут"скчГться даже некоторые из сколь угодно близких к х> то4к С™ст вуюш,ая ситуация изображена на рис. 8Ь. Хотя х. и х, отстоят от X на одинаковое расстояние, приемлемым решением можн назвать только х,. Чем «больше» окрестность х, в которой F (х) ЛЛЬ1 -«Рятность попасть в нее; сказать что-ни-

будь более конкретное в общем случае нельзя



Рис. 8Ь. Неравноценные приближения к функции.

аадаче минимизации разрывной

Если в x* терпят разрывы только производные, а сама F непрерывна, обеспечить соотношение F(x)xF{x) проще; однако и здесь конструктивные теоретические оценки возможны лишь при весьма жестких предположениях.

8.2.2.2. Точность в задачах с ограничениями. Предельную точность численного решения задачи с линейными равенствами и неравенствами можно оценить, анализируя отклонения от х* в двух взаимно ортогональных подпространствах - в нуль-просгранстве и ранг-пространстве матрицы А активных ограничений.

Точность в ранг-пространстве: линейные ограничения. Ниже показано, что предельная точность проекции численного решения на нуль-пространство А определяется не ошибкой подсчета f, а обусловленностью Л.

Искомая точка х* удов.летворяет равенству

Лх*=й.

причем, не умаляя общности, можно считать, что (Л и 6 суть величины порядка единицы. При этом, если х есть результат применения какого-нибудь из методов, рассмотренных в гл. 5, I получим

I Лх=Ъ-\-0{Е,). (8.П)

Обозначим через Y матрицу, чьи столбцы формируют базис полпространства, натянутого на столбцы А, н пусть 2--матрнца базиса его ортогонального дополнения. Тогда х можно представить так:

Подстановка правой части этого равенства в (8.11) дает АУру==ОШ.

Отсюда видно, что порядок величины ЦУруЦ связан с обусловленностью А. При хорошо обусловленной А эта величина того же порядка, что и ejj. Еслн же А обусловлена плохо, норма llVysjfl может оказаться большой, даже когда невязки активных ограничений в x почти нулевые.

Небезынтересно посмотреть, как возмущение Ypy отражается на значении F. Разлагая F в ряд Тейлора в окрестности л:*, получим

F (X* + Ypy) = F (х*)-4-g (x*YYpy+0 ( Ypyf) = = Fix) + X--AYpy + 0(lYpyf) (напомним, что (х*) = Л?."). В предположении хорошей обусловленности А из (8.12) следует, что

F (X* -I- Ypy)-F (x*) и X"AYpy = О (е„1 1). Прн плохо обусловленной А это неверно, так как тогда остаточный член в (8.12) отбрасывать нельзя.

Точность в нуль-пространстве; линейные ограничения. Оценивание предельной точности составляющей численного решения из нуль-пространства А проводится по схеме, аналогичной испо.ль-зованной в разд. 8.2.2.1 для случая без ограничений. Чтобы упростить изложение, допустим, что уклонений в ранг-пространстве нет, т.е. x = x*-f-Zp. Тогда, полностью повторяя рассуждения разд. 8.2.2.1, получим

,Zg(x.)r.2e.lIi№f.

(8.12)



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [ 66 ] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0008