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

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

Нелинейные ограничения. Для хорошо отмасштабированных и хорошо обусловленных задач с нелинейными ограничениями оценки достижимой точности те же, что и для задач, ограничения которых линейны (только вместо Д надо брать Д(х*), а вместо С (jc*) - матрицу Гессе функции Лагранжа W (х, К)). В отношении плохо обусловленных .задач этого сказать нельзя; здесь нелинейность ограничений осложняет дело.

8.2.3. КРИТЕРИИ ОСТАНОВА

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

Оптимизашюиный процесс желательно прервать, (i) если достигнута требуемая точность решения; (ii) если хорошее приближение еще не найдено, но скорость продвижения к опти>1уму так упала, Ч10 нет смысла считать дальше; (ii) если метод начал расходиться (из-за отсутствия у задачи приемлемого решения) или зациклился. Таким обра.зом, хорошие критерии останова до.пжны обеспечивать выход из програм.\1ы. когда получена подходящая точка, гарантировать минимум риска преждевременного прерывания и не допускать бессмысленных затрат маш1Шиого времени.

Возможность принять Xh в качесве численного решения определяется на основе условий оптимальности и признаков приближения последовательности [х] к пределу. К сожалению, для многих задач удается использовать лишь некоторые из условий, причем даже их точного соблюдения требовать нельзя (см. разд. 8.2.1). Поэгому н приходится существенно опираться на тесты второго типа. Сами по себе оии юже ненадежны: признаки близости преде-

, I

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

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

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

8.2.3.2. Критерии останова для безусловной оптимизации. Представленные в данном разделе условия окончания счета ориентированы на задачи без ограничений и включают лишь один свободный параметр Он н.меет смысл желаемой точности решения. Существуют две естественные формы запроса точности: первая - когда указывается желаемая близость к оптимуму по точке, вторая - по значению целевой функции. В определенных случаях между соотвегствующими уклонениями есть хорошая связь (см. разд. 8. 2.2.1), и тогда не важно, какую форму принять. Однако, если задача плохо обусловлена, постоянное эначение F peaiuayemCR для точек xi,, которые очень по-разно,ку уда.1ены от х*, и .здесь ожидать хорошей близости Xf, к х* нельзя; рассчитывать можно только близость Ft к F(x*). Поэтому мы предлагаем регулировать ........ паг,ол.ртппл1 т.. - числом правильных разрядов Fk, кот

точ-которое

ность параметром тр -числом правильных разрядов г/,, китирис хотелось бы получить. Подразумевается, что для fj. не превосходящих по мод}лю единицы, старшие разряды после десятичной точки дачжны учитываться, даже если в них стоят нули. Например, выбор Тр= 10"означает, что при \F(x*)ll желательно, чтобы у Ft и f (л:*) совпали шесть первых значащих цифр, а при \F(x*)\<\, чтобы Ft и Fix*) различались не бапее чем на Ю"".

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

UI- -i-f.<e.;

U2- lft-.->:*<ltf(l+ll*»ll): из. Ы1<уТг(1-ЫМ).

где бь - мера абсолютной погрешности, вычисляемая по формуле et=r,,(l + \Ft\) (8.13)

(доводы в пользу этого определения приводятся ниже). Первые два неравенства суть признаки близости последователыгастей {Fk] и {XfcJ к своим пределам. Третье представляет собой огрубление известного условия оптимальности lg(x*)ll=0.

Отметим, что, хотя речь шла только о поиске хорошего значения fft, а об уклонении от х* ничего не говорилось, в список включено условие U2, относящееся непосредственно к х. Для правильно отмасштабированиых задач его можно не вводить - оно будет следсгвием U1. Однако для прочих задач условие U2 полезно н заставит алгоритм отыскивать более подходящие точки. Нарушение условия U2 при выполненном U1 можег означать следующее; либо направление, выбранное в х „ было почти ортогонально градиенту, либо F имеет пологий минимум. В том н другом случае имсег смысл продолжить поиск

Суть приведенных условий прозрачна, но их конкретная формулировка требуег некоторых пояснений. Прежде всего, казалось бы, естественнее взять 6 равным тр\Рк\. Однако тогда при малых

if 1,1 условие U1 бы.по бы слишком жестким. Как прави.по, такие получаются сложением существенно отличных от нуля величин протпюположных знаков и. следовательно, вычнсляиэтся с низкой относительной точностью (см. разд, Ь.5.1.3). Поэтому для оценки близости к f/( и при нулевом и при F порядка единицы

разумно использовать один эталон. Именно это соображение определило выбор формулы вычисления Ой.

Исходя из результатов ра.чд. 8.2.2.1, соблазнителыю заменить правую часть ус/ювня U2 иа квадратный корень из вй/1С(х/,). Однако, так как величина С(л:й) обычно недоступна, полученное условие было бы непрактичным. В то же время для хороших задач оно не гак уже сильно отличалось бы от U2. Присутствие llxjil справа в условии U2 оправдано естественным желанием ослабить зависимость оценки близости х 1 к Xf, от масштаба переменных, а еднтшчная добавка к х,, полезна по тем же соображениям, что и в (8.13).

Некое недоумение может вызвать использование в условии U3 величины l/tf - ведь в соответствии с оценками разд. 8.2.2.1 надо было бы взять квадратичный корень. Тем не менее это не описка: практика показывает, что удовлетворять условию Ш с lTp слишком трудно и в присутствии U1, U2 его вполне можно смягчить. Аналоптчного остаблеиия условия U2 не требуется - если подставить в U2, U3 одинаковые степени тр, то условие U2 почта всегда будет следствт1ем U3 (но не наоборот).

Условия U1-из срабатывают, когда, попав в «хорошую» точку х,, „ алгоритм делает еще один шаг. На случай, еслн X;j j окажется настолько близкой к х*, что выйти нз нее с уменьшением F не удастся, предусматривают альтернативный останов по признаку

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

ана.11итических значений первых производных в услювия U3 н Ш можно подставлять их численные оценки.

Какую норму лучше всего взять для Ш-U4, завист ог числа переменных п. Если оно невелико, подойдет евклидова норма. При больших п разумнее использовать норму /, (максимум модуля по компонентам), так как при евклидовой норме удовлетворит]! условиям из, Ш становится слишком тяжело. Иногда применяют также «псевдонормы», масштабируемые в соответствии с величиной п.

Негладкие задачи. Критерии останова для алгоритмов негладкой минимизации (типа метода многогранника из ра:1д. 4.2.2) обычно сводятся к одному-единственному условию - требуется, чтобы некое изменение функции было меньше заданного гюрога. К примеру, на каждой тттерации метода многогранника определено n + l точек X,, х„ . . ., х,„ х„+, и соответствующих значений F, причем точки угюрядочиваются так, что Fif е. . -/„+i; здесь в качестве упомянутого условия берут неравенство

f„..-fi<V(l + fil)- (8.14)

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

8.2.3.3. Критерии останова для минимизации при линейных ограничениях. Ниже приводится перечень требований, выполнение которых может служить признаком успешного завершения поиска минимума при линейных ограничениях. Они ориентированы на методы активного набора, ттстюльзующие ортогональный базис нуль-пространства матрицы Л (см. разд. 5.1 и 5.2). Между ними и условиями, рассмотренными ранее, есть два принципиальных отличия. Во-первых, если хотя бы одно из ограничений обращается в х» в равенство, то место полного градиента займет спроектированный gz (Х/,). Во-вгторых, вводится допалнительное требование к оценкам множителей Лагранжа активных неравенств; тем самым контролируется правильность финалыюго активного набора.

Пусть /ц-полное число ограничений в рабочем списке ft-й итерации; ЛJ-вектор оценок нх множителей Лагранжа (размерности <j); а„-,„-минимальная среди оценок множителей активных неравенств; Я„„-оценка множителя (равенства или неравенства), имеющая максимальную норму; 8, - параметр, вычисляемый по формуле (8.13). Точку х, где есть активные ограничения (иначе надо было бы обратиться к условиям нз предыдущего раздела), предлагается считать численным решением, если

LC1. f, ,-f,<e,.

LC2. 1х, ,-х,<1Атр(1-1-х).

LC3. UzKv-AeA-

LC4. (Это условие надо проверять, только когда в рабочем списке есть хоть адно ограничение-неравенство.) Если <t > 1, то о„,„ S3 V-ie\I; если = 1, то o„i„ >lv(l +

Аналогичным U4 альтернативным признаком целесообразности останова теперь станет выполнение условий LC4 и I-C5. \gz\<v-A-

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

8.2.3.4. Критерии останова для минимизации при нелинейных ограничениях. Гладкие задачи. Поскольку методы решеш1Я задач с нелинейными ограничениями могут использовать принципиально разные стратегии поиска, в критериях их останова тоже возможны значительные вариации. Обширный класс составляют методы с адаптивными подзадачами (см. разд. 6.1.2.1). В них соотношения, по которым выносится суждение о качестве текущей точки, проверяются только в моменты завершения «основных» итераций (т. е. когда решена очередная подзадача). Обычно здесь рассматриваются изменения некоторых вепичии (оценок множителей Лагранжа. значений функции выигрыша и т. д.) в результате последней основной итера-Щ1И. В методах с детерминированными подзадачами (разд. 6.1.2.1) применяются другие критерии, причем и они варьируются в зависимости от характерных свойств последовате.тьностей генерируемых приближений {xj). Например, методы типа приведенных градиентов, сохраняющие допустимость, дают последовательности {Xft}, для которых векторы шагов из Xi, i в тяготеют к нуль-пространству матрицы активных ограничений Л(х*). Если задача хорошо отмасштабирована, нз этого следует, что вблизи решения будет

f»-.-f. = 0(x,-x,.,r)

(для методов, подходящих к решению «нетангенциально», такой связи нет).

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

NC1. :cKt<:.

NC2. игКУЛеЛ-

NC3. (Это условие надо проверять, только когда в рабочем списке есть хоть одно ограничение-неравенство.) Если

I <*> Ь то a„i„ > Vip] I; если < = I, то o„i„ Vtp(l +

Здесь Bj, tt, о„„ и величины, определенные в преды-

дущем разделе, есть вектор-фуикция активных в ограничений, а т - допуск на норму их невязок. Заметим, что в правой части аналогичного LC3 условия NC2 стоит не кубический корень из тр, а квадратный, т. е. оно жестче чем LC3. Это усиление целесообразно в связи с тем, что от теста типа U1 (или LC1) приходится отказаться (он годится лишь для упомянутых выше методов типа приведенных градиентов).

В программах методов с детерминированной подзадачей естественно использовать также следующее условие останова:

NC4. х,.,-х,<Г(1+х,).

При .этом нужно Предусмотреть и альтернативный набор «одноточечных» условий. Туда можно включить, например, неравенства NC2, NC3 и

NC5. с,<Е.,-

Негладкие задачи. Для решения негладких задач с нелинейными ограничениями обычно применяют методы, подобные описанному в разд. 6.2.2.2. В частности, для него разумным признаком успешного завершения поиска будет выполнение неравенства (8.14) и

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

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

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

14 2964