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

[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]

рована рис. 8d. Видно, что достигнуто хорошее согласование модели с исходными данными, но при этом одна из разностей fi=yt-ф (х, tt) значительна. Чтобы устранить такой дефект, можно либо ввести в окрестность ti новые опорные точки, либо увеличить вес fi в целевой ф>нкции (т. е. умножить / на положительное число, большее единицы).


Рис. 8d. Большая невязка !i=yi-ф(л, ti) прн хороием соответстнин медщу функцией ф(;с, /) и данными наблюдений {yi).

8.3.1.2. Задачи с ограничениями. Тесты (i)-(ill) из разд. 8.3.1.1 легко обобщить на случа!! с ограничениями: если они линейны, надо заменить g. и 0 на ZTg и ZTQZ, а если нелинейны-на (xiJgh и Z(xt)T17 (л:, Я) Z (xJ, причем тогда следует обратить внимание и на достигнутую в конце поиска скорость сходимости оценок множителей Лаграижа (см, разд. 6.6).

Нулевые множители Лагранжа. Когда среди множителей Лагранжа, связанных с полученным численным решением, есть нулевые или почти нулевые, разобраться с ним нелегко. Дело в том, что знаки множителей активных неравенств определяют не только правильность финального рабочего списка, но и возможные способы улучшения имеющейся точки, если она неоптима.тьна (см разд. 5.8.3).

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

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

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


УрОв11ЯЕ(х)

--SM

C2(I>=0

С,{Х)=:0

Рис. 8е. Избыточное ограничение с нулевым множителем Лагранжа.

ного ограничения в точности равен нулю, т. е. в первом приближении слабые вариации этого ограничения на величину целевой функции ие влияют. (Чтобы убедиться оптималыюсти точки, где есть нулевые множители, надо исследовать вторые производные, которые не всегда доступны.) Это может означать, что оно избыточно, и решение не изменится, если его отбросить. Так будет, например, в случае, и:зображенном на рис. 8е: здесь избыточно ограничение Са (л:)>0. Однако возможна и иная ситуация, когда в результате отбрасывания ограничения с нулевым множителем решение меняется. Она проиллюстрирована рис. 81: равенство нулю мноЖ1ггеля Я,, объясняется тем, что начало координат - безусловно седловая точка, и, если убрать ограничение с, (х)0, у задачи просто не будет конечных решений.

Точка может оказаться неподходящей, даже когда все близкие к нулю множители положительны. Это вндно из примера, показанного на рис. 8g. С формальных позиций х=а есть корректное решение, удовлетворяющее ограничению ха как равенству, но, конечно, в подобных случаях естественно желать большего. При этом можно говорить о плохой обуслов.чеиностн, поскольку малая вариация способна привести к 3Ha4HTejrbHov[y смещению точки минимума.

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

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



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


направление . убытчця F(x)

Рис. 8f. Случай, когда ограничение с нулевым множителем .Пагранжа отбросить нельзя.

Коль скоро убедительного подтверждения правильности численного решения с почти нулевыми множителями получить не удается,

надо попробовать переформулировать задачу, например выявить и исключить «почти избыточные» ограничения.

Большие множители Лагранжа. Среди задач с нелинейными ограничениями есть такие, для которых множителей Лагранжа не существует (причина -дефект ранга матрицы Якоби функш1й активных ограничений А (х-); см. разд. 3.4.1). К счастью, сами они в приложениях практически не встречаются, но «близкие» к ним задачи с«почти линейно зависимыми» строками у А (а-) не редкость. Плохая обусловленность матрицы А (х») обычно приводит к тому, что модули всех множителей Лагранжа оказываются намного


Рис- 8g, Пример неподходящего решения с близким к нулю положительным множителем Лагранжа.

больше нормы lg{x*)l Однако большие множители могут объясняться и плохой нормировкой ограничений-ведь при делении функции ограничения на положительную величину ш модуль его множителя увеличится в w раз (см. разд. 8.7.3). Чтобы выявить истинную причину появления больших множителей, надо оценить число обусловленности отнормнрованиой матрицы Якоби-ре.зуль-тата преобразования А (х*), состоящего в делении каждой строки А{х) на ее евклидову норму. Оценку этого числа можно получить, например, с помощью /.-разложения (см. разд. 2.2.5.3). Таковой послужит отношение максимального по модулю диагонального элемента фактора L к минимальному. Если оно велико, то скорее всего дело в плохой обусловленности, а иначе-в плохой нормировке. В последнем счучае надо перенормировать ограничения каким-нибудь из способов, описанных в разд. 8.7.3: численное решение с большими оценкаьнт множителей ненадежно.

8.3.2. ДРУГИЕ СПОСОБЫ ПОДТВЕРЖДЕНИЯ ОПТИМАЛЬНОСТИ

Бывает, что даже после тщательного анализа выдачи программы пользователь все еще сомневается, правильно решена задача или нет. Тогда остается три способа обрести ясность:

(1) изменить параметры а.чгоритма;

(ii) воспачьзоваться другим алгоритлюм;

(iii) изменить задачу.

8.3.2.1. Варьирование параметров алгоритма. Самый понятный, а потому самый подходящий для варьирования параметр - характеристика точности одномерной минимизации г (см. (4.7) и (4.10) в разд. 4.3.2.1). В стандартных программах некоторых методов значение т] по умолчанию (см. разд. 8.1.2.1) берут довольно большим, допуская тем самым весьма приближенный одномерный поиск (например, для ньютоновских методов обычно рекомендуется ii=0.9). Следо-ватыьно, можно попытаться у.иучшить имеющуюся точку, потребовав, чтобы шаги подбирались аккуратнее (т. е. задав меньшее значение т]). Особенно полезно поэкспериментировать с т], если используется какой-нибудь из методов сопряженных градиентов, крайне чувствительных к точности одномерной минимизации (см. разд. 4.8.3).

Коль скоро существует возможность воспользоваться локальным поиском (см. разд. 8.1.3.6) и при первом обращении к программе этого не было сделано, для проверки полученного приближения надо вызвать ее еще раз, но уже с соответствующим запросом.

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



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

Иногда затруднения со сходимостью квазиньютоновского метода возникают из-за того, что с его помощью не удается построить достаточно хорошее приближение матрицы Гессе С (>:). Здесь дело можно поправить повторным запуском метода при использовании в качестве исходной оценки матрицы G{x) ее конечно-разностную аппроксимацию. В ряде случаев полезно провести расчеты с нового начального приближения. Надо только позаботиться о том, чтобы оно существенно отличалось от приближений первого цикла итераций. Хорошо взять точку, «противогюложную» полученной в результате этого цикла.

Если после какого-то из перечисленных изменений программа даст прежний ответ, у по.льзователя возрастет уверенность в том, что этот ответ правильный. Тем не менее надо помнить, что всегда (и особенно когда используется метод первого порядка) есть опасность повторной сходимости в неоптимальную точку.

8.3.2.2. Смена метода. Если варьированием параметров окончательная ясность не достигнута, надо попытаться применить другой метод. Как правило, лучше перейти к методу, который считается более надежным, но иногда полезно обратиться и к менее надежному - ведь бывает, например, что ньюгоновские направления получаются почти ортогональными градиенту и из-за этого оказываются хуже квазнньютоновских.

Допустим, первым был использован квазиньютоновский метод с аналитическими значениями первых производных. Тогда есть по меньшей мере три разумных способа контроля, а именно: запрограммировать вторые производные и применить метод ньютоновского типа; применить ньютоновский метод с конечно-разностной аппроксимацией матрицы Гессе; применить квазиньютоновскнй метод без вычисления производных. Можно также посмотреть, что получится, если в исходном методе аналитическое дифференцирование заменить численным по центральной конечно-разностной формуле. Взяв для проверки метод ньютоновского тнпа, в качестве начального приближения ему надо задать последнюю точку предыдущего просчета; это позволит выяснить свойства отвечающей ей матрицы Гессе. В противном случае счег следуег начать с какой-нибудь абсолютно не похожей на нее точки (тогда результат проверки будет бо.тее убедительным).

8.3.2.3. Изменения в задаче. Если описанные выше приемы оказываются безреаультатнвными. т. е. все еще нет окончательной уверенности в правн-пьности численного решения, то это скорее всего признак каких-то дефектов формулировки задачи, скажем плохого масштабирования (см. разд. 7.6 и 8.7) нли неудачного выбора переменных (см. разд. 7.6.1). Здесь остается то.чько один выход- сформулировать задачу более подходящим образом.

8.3.4. АН.1ЛИЗ ЧУВСТВИТЕЛЬНОСТИ Часто желательно иметь информацию о «чувствительности оптимума» по отношению к каким-то возмущениям. Например, могут понадобиться оценки последствий малых невязок в ограничениях; когда решается задача настройки модели на результаты наблюдений, важно бывает выяснить, как сказываются на х* погрешности исходных данных. Кроме того, иногда возникает потребность в определении вариаций х*, приводящих к минимальным или максимальным изменениям F.

8.3.3.1. Роль матрицы Гессе. Принципы анализа чувствительности функции к варьированию аргумента вблизи оптимального значения удобно пояснить на примере квадратичной формы

Ф{х)-

с-x+xGx

с положительно определенной матрицей С. Поведение Ф(дг) в окрестности минимума зависит от собственной системы последней (см. разд. 3.2.3). Обозначим собственные значения и векторы С через

{X./} и {U}. i=.....причем здесь и далее будем считать, что

?4>?bs>. . Тогда числом обусловленности С (см. разд. 2.2.4.3)

будет

cond(G) = g.

При cond(0)=l линии уровня Ф(л;) представляют собой концентрические окружности, а при прочих cond (С) - эллипсы Чем 6о.льше


Рис. 8h. Линии уровни квадратичных функций с cond{G)l и cond{G)IO

cond (О), тем сильнее онн сплющены. Как вндно из рнс. 8h, когда число cond (С) велико, приращения Ф (4 при одинаковых по норме, но разных по направлению вариациях х оказываются существенно разными. Направления, вдоль которых Ф{х) меняется сильнее всего, есть соответственно ы, и (г„.

Среди встречающихся на практике нелинейных функций большинство составляют такне, которые в окрестностях своих минимумов очень гюхожи иа квадратичные формы; исследование их чувствительности к изменениям v, как и в случае с Ф(х), сводится к анализу матрицы Гессе (см. разд. 8.2.2). Иной класс



[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