Почти во всех оптимизационных алгоритмах естественно ставить условие «существенного убывания» применяемой функции выигрыша на каждой итерации. Невозможность удовлетворить этому условию служит надежным сигналом о какнх-то неполадках (см. разд. 8.4.2). Весьма распространенным и, по нашему мнению, неудачным критерием отказа является близость к нулю производной функции выигрыша по очередному направлению поиска. Более ) разумно определять в хц минимальное приемлемое расстояние 6» до следующей точки (величина 6й должна быть аккуратной оценкой той нормы \\Xf,+i-Xhll, при которой гарантирован правильный знак разности вычисляемых в x+i и х значений функций выигрыша) и считать, что алгоритм отказал, если он не может получить лучшего, чем xj, приближения, сделав шаг, превосходящий 6.

8.2.3.6. Выбор параметров в критериях останова. Ниже речь пойдет Б основном о выборе допуска для предетавленных в разд. 8.2.3.2 условий завершения поиска минимума без ограничений. Неудачный выбор tr может привести к серьезным потерям, так что к назначению тр следует подходить ответственно.

Казалось бы, чтобы не затягивать счет понапрасну, Tj, надо брать равным желаемой точности решения, а она определяется существом задачи; если, скажем, f описывает некую реальную зависимость с относнгельной ошибкой 3%, то и минимум точнее искать незачем. Однако, поскольку строгих гарантий близости к f(x*) условия останова не дают, получив точку, удовлетворяющую им «без запаса», трудно бывает поверить, что достигнута максимальная близость, на которую позволительно надеяться при соответствующем Тр. Иное дело, когда допустимая погрешность в оценке F(x*) составляет 3%, а условия выполнены для Тр=0.0001%; тут, наверное, каждый был бы уверен, что желаемая точность получена, и почти наверняка не ошибся бы.

Недостаточно жесткие требования к окончательному приближению опасны тем, что могут выполняться вдали от искомого решения. Возьмем, к примеру, функцию одной переменной, изображенную на рис. 8с. Если при поиске ее минимума в качестве критерия останова использовать неравенство lg(x)l<a(l-f F(x)) и положить 0=0.05, то на роль «численного решения» будут претендовать все точки, отвечающие обведенным участкам графика. Среди них есть и не имеющие к х* никакого отношения. Совсем иная картина возникает при а=10": точки, подчиняющиеся неравенству с таким параметром, удается найти лишь вблизи х*. Разумеегся, нетрудно построить аналогичную по виду, но хуже отмасштабиро-ванную функцию, для которой и условие g(x)<10"(l-l-F(x)J) реализуемо в далеких от х* точках, да только на практике подобные функции встречаются редко. Обычно же жестким критериям останова вне малой окрестности х* ие удовлетворить.

Наименьшее возможное значение тр определяется предельной

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

Рис. 8с. Точки, удовлетворяющие неравенству (g(x)I<0.05(H-l/(x)),

сходимости на последних итерациях поиска «очень точного» решения послужит дополнительным подтверждением близости найденной точки к X* (см. разд. 8.3.1). Если же алгоритм таков, что для тр есть порог, за которьш скорость увеличения времени поиска с уменьшением Тр резко возрастает, то использовать предельное значение Тр не стоит; слишком долго придется ждать ответа. В частности, сказанное относится к методу многогранника - даже когда речь идет о хорошей гладкой функции, задавать ему Тр, меньшие чем 10"=, не следует.

Промежуточное положение занимают алгоритмы сопряженных градиентов, эффективные скорости сходимостей которых чаще всего линейны. Если мантисса машинного представления числа содержит slO десятичных разрядов, для них обычно подходят tp порядка 10"*; при меньших s, как правило, можно взять Тр=10~*. Такие Тр позволяют надеяться, что у полученного в точке останова значения F(Xb) будет примерно min {VaS, 4} верных разрядов. Для большинства прикладных задач этого вполне достаточно, но вот только полной уверенности, что надежды оправдаются, нет.

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

Гд. 8. Практические еопросы

проксимации градиента не позволяют правильно ориентировать направления поиска вблизи искомой точки (где градиент равен нулю).

В хорошей библиотеке оптимизационного математического обеспечения для каждого метода будет определена своя рекомендуемая величина ту. Кроме того, может предусматриваться программный контршь пригодности значения Тр, заданного пользователем, и замена этого значения, коль скоро оно окажется неудовлетворительным. Тогда, например, если пользователь зафиксировал такой параметр Xf, что в(, получается меньше, чем оценка абсолютной ошибки вычисления F, программа сама увеличит т,. (Имея в виду возможность автоматической замены, не стоит прибегать к явно завышенным Ту как к способу обеспечить быстрый останов стандартной процедуры. Обычно для этого есть специальный параметр (см. разд. 8.1.3.5).)

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

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

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

Вопросы построения критериев останова для программ минимизации при нелинейных ограничениях близки вопросам оценки их функционирования; по этому поводу см. работу Гилла и Мюррея (1979с).

Об условиях завершения счета при решении систем нелинейных уравнений и нелинейных задач о наименьших квадратах можно прочесть у Денниса (1977), Денннса, Гэя и Уэлша (1977), Море (1979b). Особый класс составляют так называемые задачи с малыми невизкамн. Для ннх целевую функцию удается вычислять с необычно высокой точностью (см. разд. 8.5.1.3), и это находит отражение в соответствующих условиях.

Исчерпывающий анализ связи между приближенным решением системы линейных алгебраических уравнений и вектором их невязок дан в книге Уилкинсона (1965).

8.3. Анализ рвзудътптое счета

8.3. АНАЛИЗ РЕЗУЛЬТАТОВ СЧЕТА 8.3.1. ОЦЕНКА ПРИГОДНОСТИ ЧИСЛЕННОГО РЕШЕНИЯ

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

8.3.1.1. Безусловная минимизация. Получив по окончании поиска минимума без ограничений точку х, имеет смысл проверить

(i) вьшолнено ли неравенство l\g(xt)\\<\\g(xc)\\;

(ii) достигнута ли на завершающих итерациях высокая скорость сходимости;

(iii) можно ли оценить число обусловленности матрицы Гессе (илн ее приближения) небольшой величиной.

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

Из сказанного вытекает, например, что при 1(х„) порядка 10" вполне можно довольствоваться единичным значением g(Xfc). В подобной ситуации почти наверняка удовлетворится и критерий из из разд. 8.2.3.2. Однако неравенство Оз бывает также следствием плохой нормировки производных. Тогда при вьшолненном Ш проверка (i) даст отрицательный ответ. Именно в этом ее ценность. (Б условия останова требование существенного уменьшения нормы градиента не включают, так как при хорошем начальном приближении оно невыполнимо.)

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

Скорость сходимости можно оценивать по значениям норм градиентов или разностей Itft-i-f» на нескольких

(скажем, пяти) последних итерациях. Соотношения с г >

> 1 укажут на сверхлинейную сходимость, а быстрая линейная предполагает, что х IjM, где УИ > 2.

Идеальную картину проявления сверхлннеЙ1ЮЙ (а точнее, квадратичной) сходимости дают сведенные в табл. 8а характеристики

Таблица ва. Заключительные итерации поиска минимума функции Розенброка методом иьютоповского типа

Таблица ВЬ. Итерации поиска минимума функции Розенброка методом наискорейшего спуска

завершающих итераций поиска минимума функции Розенброка (см. пример 4.2 и рис. 4к)

F (X,. X,) = (л;-х,)= -Ь 100 (1 -А)

ньютоновским методом (см, разд. 4.4,1). Здесь все ясно и без последовательности ilk)- (Отметим, что функцию Розенброка в окрестности минимума удается вычислять с высокой точностью; см. разд. 8.5.1.3.)

Результаты применения к той же задаче метода наискорейшего спуска (см. разд. 4.3.2.2) содержатся в табл. 8Ь. Это - пример очень медленной линейной сходимости. Подобная картина, вообще говоря, подсказывает (в рассматриваелюм случае правильно), что до решения еще далеко.

На практике крайние ситуации типа представленных выше встречаются редко; обычно наблюдается нечто среднее между ними. В подтверждение этого тезиса приведена табл. 8с с данными решения одной прикладной задачи. Левая колонка этой таблицы похожа на правую в табл. 8Ь, но по разностям {1к} видно, что итерации сходятся достаточно быстро, хотя и с лннейтюй скоростью.

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

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

Таблица Вс. Заключительные итерации квазиньютоновского метода дли одной прикладной задачи

ГОДОВ ньютоновского типа: бывает, что из плохой точки x;(, i делается шаг в «очень хорошую» Хк, откуда выйти уже не удается - мешают ошибки округления. Тогда условия нормального останова могут не сработать (U1, U2, U3 из-за существенного различия между и х, а «одноточечное условие» U4 из-за недооценки погрешности вычисления F) и программа выдаст сообщение об отказе. Эта ситуация надежно распознается по неравенству llg),ll<g(, ill и хорошей обусловленности матрицы Гессе в ж».

Если при решении хорошо обусловленной задачи ньютоновский метод не обеспечивает сверхлинейной сходимости, стоит проверить, нет ли вблизи х* точек разрывов вторых производных. Последние должны быть достаточно большими (иначе они вряд ли сильно повлияли бы на сходимость), и поэтому их не трудно будет выявить. Кроме того, плохая сходимость ньютоновского мегода часто бывает результатом ошибок в программе построения матрицы Гессе, так что не следует пренебрегать возможностью ее оттестировать (см. разд. 8.1.4.2).

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

Приемлемое решение не обязательтю должно характеризоваться малостью F. Минимум суммы квадратов иногда оказывается большим просто потому, что в ней много слагаемых. В качестве другого примера можно назвать случай, когда в аадаче «подгонки» вектора X параметров функции (f(x, t) под результаты наблюдений {(/;}, имеющихся для точек {tj), какие-то квадраты (yi-tf {х, /i))" велики из-за больших производных tf(x, О по (. Эта ситуация проиллюстри-