образуют функции, не имеющие непрерывных вторых производных, а также функции типа f (х)=х;+д4, характерные тем, что их матрицы Гессе, вычисленные в точках минимумов, состоят из одних нулей. При нулевой С (х*) особенности локального поведения F вблизи X* можно выяснить только по производным порядка Bbmie второго; например, отличие xi + xt от х{ + lOxl в окрестности начала координат определяется четвертой производной по X.j.

8.3.3.2. Оценивание числа обусловленности матрицы Гессе. Что

бы получить полное представление о свойствах матрицы Гессе, надо определить ее собственную систему, а это довольно трудоемкая вычислительная задача. Однако необходимость в столь исчерпывающих сведениях возникает редко. В то же время для построения хороших оценок значений Я, Я„ и отвечаюишх им собственных векторов достаточно иметь разложение С или аппроксимирующей ее матрицы по XoieccKOMy (см. разд. 2.2.5.2).

Обозначим через s и г номера соответственно наибольшего и наименьшего среди диагональных элементов фактора D из LDL-разложеиия С, т. е. d,.<d., и dd,. при любом i = 1, 2,..., п. Их отношение K = djd, будет связано с числом обусловленности cond (С) неравенством Kcond(G), причем, как правило, отличие к от cond (С) невелико. Точнее сказать, и и cond (С) чаще всего оказываются величинами одного порядка.

Пример 8.2. Возьмем матрицу

/22.3034 18.4384 7.6082 13.7463 \

18.4384 15.2666 6.2848 11.3694 >

7.6082 6.2848 2.5964 4.6881

\ 13.7463 11.3694 4.6881 8.4735 /

(8,15)

Ее число обусловленности равно 1,130599x10, а факторами Холесского будут

/ 0.8267 1 \

= 0.3411 -0.2105 1 I

\ 0.6163 0.2217 -0.1305 1 /

и D = diag (2.230x10, 2.344x10-», 7.785x10-, 5.613x10-») (элементы того и другого выписаны с точностью до четырех значащих цифр). При этом и = 3.9788х 10».

Ценой несложных дополнительных вычиспеиий можно получить лучшую оценку cond (G). Введем векторы

Нетрудно показать, что X„<dr/II Юг (5 и (iOs{dj</-(. Значит,

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

ИЛ"-

Если d,/II Юг (г»-,, и КФ\,-ъ для этого вектора справедливо приближенное равенство wtau,,. Если же ?i„ , и V. различаются не сильно и К-л€К-г< вектор и), будет «почти линейной комбинацией» и„ и u„ i. В обоих случаях w, является направлением отрицательной кривизны.

Аналогично и„ оценивается и Uj: в предположении близости [kjJA к и неравенства >.,>.j можно утверждать, что щса

«I0j/l0,s.

Для матрицы (8.15) максимальное и минимальное собственные числа равны = 4,8622797X 10> и Я, = 4.3006198х 10", а и, и и, выглядят следующим образом;

/ -0.437963 \ / -0.170007

/ 0.677217 \ / 0.560151 \ "1 = 1 0.230952 )• \ 0.417455 I

0.114370 0.875332 /

Векторы и K)j здесь получаются такими:

(-0.500240 \ / -0.437898 \

-0.194261 \ / -0,170052 \ 0.130467 • ". 0.114208 ]• 1.000000/ \ 0.875,377/

Заметьте, что й, и очень близки. Столь же хорошо срабатывает и формула оценивания и.

Наконец,

1.000000 4 0.826707 \ 0,341121 ]•

0.616332/

/ 0.677336 \ 0.559959 \ 0.231054 ) \ 0.417464/

-5У11Ык= 1.303443 X 10»,

и это-гораздо более точное, чем к, приближение числа обусловленности матрицы (8.15).

8.3.3.3. Чувствительность к возмущениям ограничений. В гладкой задаче на условный минимум вариащтн F вблизи решения можно связать с невязками активных ограничений. Эта связь задается множителями Лагранжа.

Обозначим через с вектор-функцию активных в х* ограничений, через Л матрицу (полного ранга) градиентов ее скалярных составляющих, а через q направление, для которого

й[9=1, сГ? = 0, (8.16)

Тогда, заменив в уравнении (8.12) нз разд. 8.2.2.2 произведение Ypy на hq, для x=x + hy получим

F{x) = F (x*) + h}.] +0(hq I). (8.17)

Пусть теперь x-некая близкая к х точка, про которую известно только то, что Су(х) = 6у, Ci{x) = 0, 1ф1При этом в первом приближении должно соблюдаться равенство л = .t + Sjq, где q - удовлетворяющий (8.16) вектор. Значит, на основании (8.17) можно утверждать, что с точностью до величин порядка бу разница между значениями F в х* и х есть 6у?*у.

Итак, на множитель Лагранжа активного ограничения можно смотреть как на меру чувствительности F к его возмущениям, и если, скажем, ?ч=1000, а ?ьа=10-% то позволительно сделать вывод, что первое активное ограничение «намного важнее» второго. Правда, подобное сопоставление предполагает примерно одинаковую нормировку ограничений: нормы градиентов нх функций не должны быть очень различными (см. разд. 8.7.3).

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

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

Как оценивать результаты решения линейных задач о наименьших квадратах, детально описано у Лоусона и Хансона (1974). Подробности и ссылки по поводу статистической интерпретации решений нелинейных задач этого тнпа можно найтн, например, в кшЕге Барда (1976). Различные аспекты анализа результатов безусловной минимизации функции общего вида обсуждались Мюрреем (1972b).

Оценки обусловленности, которые точнее представленных в разд.

8.3.3.2, НО требуют более сложных вычислений, даны в работах Кляйиа и др. (1979), ОЛнрн (1980b).

Способы определения характеристик чувствительности оптимума в задачах с нелинейными ограничения и ори [тированные на методы штрафных и модифицированных ф,нкщй Лагранжа, приведены у Фиакко и Мак-Кормика (1968), Фиакко (1976), Байса и Гонн-на (1977).

8.4. ЧТО МОЖЕТ НЕ ПОЛУЧАТЬСЯ (И КАК ТОГДА ПОСТУПАТЬ)

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

8.4.1. ПЕРЕПаПНЕНИЕ ПРИ ПОДСЧЕТЕ ФУНКЦИЙ ЗАДАЧИ

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

Переполнение во время процесса оптимизации может возникнуть нз-за того, что имеется неограниченное решение - в результате сходимости к таковому либо абсолю в нна минимизируемой функщти, либо норма очередного пр..ближення неизбежно станет слишком большой. Подобные случаи распознаются по устойчивому прогрессу прн отсутствии признаков близости предела. Если говорить о задачах на безусловный минимум, то, как правило, причиной неограниченности целевой функции снизу оказывается невнимательность пользователя. Правда, бывает, что о ней знают заранее и тем не менее не устраняют ее, надеясь найтн некий ограниченный локальный минимум (а алгоритм выходит из области его притяжения). Следует также отметить, что неограниченность довольно типична для подзадач, используемых в методах минимизации прн нелинейных ограничениях (см. разд. 6.2, 6.4 и 6.5)

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

должна быть неограниченной и при этом требовалось отыскать определенный локальный минимум, то успеха, возможно, удастся достичь, уменьшив максимальное разрешенное значение величины шага за одну итераштю (см. разд. 8.1.3.4) нли введя простые ограничения на переменные. Наконец, с неограниченностью в подзадачах методов условной оптимизащти, использующих штрафы, можно бороться увеличением штрафного параметра (см., например, рис. 6h). Однако не исключено, что и тут придегся принимать меры, рекомендованные выше для стимулирования локальной сходимости,- ведь целевая функция подзадачи может быть неограниченной снизу при любом значении штрафного параметра.

Иногда переполнение возникает при минимизации заведомо ограниченных снизу функций. В частности, это бывает на начальных итерациях квазиньютоновских методов. Компоненты выбираемых здесь направлений поиска нередко оказываются очень большими, и тогда пробные шаги одномерного спуска могут приводить в точки с бессмысленно большими координатами. Когда в функции есть быстрорастущие составляющие, скажем экспоненты или высокие степени х, попытка вычислить ее там почти наверняка приведет к переполнению. (Возьмите, к примеру, ехр(10л:,) и посмотрите, чго )юлучится, еслн поменять значение Xi с нуля на 10.) В таких случаях трудности устраняются правильным выбором максимальной длины шага (см. разд. 8.1.3.4).

8.4.2. НЕДОСТАТОЧНОЕ УМЕНЬШЕНИЕ ФУНКЦИИ ВЫИГРЫША

Во многих оптимизационных алгоритмах ставится требование, чтобы применяемая функщтя выигрыша Ф„ «существенно уменьшалась» на каждой итерации. Обеспечить это должна процедура выбора шага (см. разд, 4.3.2.1). Если она не способна дать нужный выигрыш, это считается признаком отказа. Чаще всего именно так происходит отказ алгоритмов данного класса.

Поскольку условия, определяющие достаточность полученного выигрыша, бывают весьма разнообразными, разобрать все причины аварийных остановов мы не в силах. Кстати говоря, некоторые стандартные программы сообщают об отка,зе блока одномерного поиска, когда производная функции выигрыша по выбранному направлению слишком близка к нулю. На самом деле это - признак неспособности алгоритма построить хорошие направления спуска; он будет обсуждаться в разд. 8.4.6. Здесь же речь пойдет о причинах, по которым могут стать нереализуемьшн неравенства вида

(м(Хк + «Л) < Фд1 Ы-III,; 11««Р*11<Д<..

(8.18) (8.19) (8.20)

В них (H/i>0) есть порог «существенного убывания» Ф; 6, (6, >0)-минимальный «ощутимый» шаг вдоль р; Aj(uj>D) - максимальное разрешенное расстояние между последовательными точками (см. разд. 8.1.3.4). Основное соображение при выборе 6 состоит в том, что вариации вектора переменных, при которых изменение функции Ф, меньше точности ее подсчета в Xj, бессмысленны. Одна из возможных формул вычисления 6 такова:

Эти и другие условия на обсуждаются также в разд. 4.3.2.1 и 8.1.3.4.

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

F(x-o,p)

Рис. fii. Возможные последствии ошибок в программах подсчета функции и градиента; точками отмечены вычисленные значения F{x-\-ap) при разных а, Черточки указывают направления касат[?льных, построенных в соответствии с вычисленными значениями производных.

ПОИСК осуществляется на основе простой полиномиальной аппроксимации вдоль выбранного направления; точка минимума очередного полинома берется в качестве очередного пробного шага. Если Фм или ее град11еит считаются неверно, аппроксимация будет вестись по бессмысленным данным, и тогда вероятность выполнить какие-либо разумные условия становится ничтожной. Например, в ситуации, изображенной на рис. 8i, алгоритм будет брать все меньшие и меньшие ац, но так и не сможет добиться убывания Ф,.

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