Проблема овражности поверхности функционала ошибки

192 Часть II. Алгоритмические методы скалярной оптимизации

Из выражения (9.7) видно, что ввиду наличия быстро затухающей и мед­ ленно затухающей экспонент отчетливо выделяются два участка с суще­ ственно различным поведением решения. Первый, сравнительно непро­ должительный, характеризуется большими значениями производных dXi{i)ldx и означает спуск на дно оврага. На дне выполняются условия типа (9.2) и норма вектора градиента, а с ней и производные dXi(z)ldx становятся относительно малыми. Поэтому для второго участка харак­ терно относительно плавное изменение переменных х,. Таким образом, прослеживается полная аналогия с поведением решений так называемых жестких систем обыкновенных дифференциальных уравнений. В связи с этим в [32] было предложено следующее общее определение.

Определение 9.1

Функционал J(x) называется овраэюным, если отвечающая ему система дифференциальных уравнений (9.6) — жесткая.

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

3)lxeQ:L[X^{x)nQ<a-‘L[X^{x)l

где CD) — множество дважды непрерывно дифференцируемых на D функционалов;

Х,{А) — собственные числа матрицы вторых производных А = J’Xx), упо­ рядоченные по убыванию: Х(А) >Х2(А) > … >ХХАу, L(S) — минимальная константа Липшица в соотношении

\jx)- Jx)\<L(S)\х —х\;/xxeSczR

Основным в определении 9.2 является первое условие, констатирующее резко несимметричное расположение спектра матрицы J’Xx) относитель­ но начала координат: G [-m, Л/], М » w > 0. Второе и третье условия необходимы для описания свойства устойчивости множества Q: можно показать, что все ТСН, начинающиеся в любой точке х G Qg, быстро по­ падают в достаточно малую окрестность Q^ (е « 6) множества Q и ос­ таются там до выхода из множества б§.

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

Пусть в D czR» задана г-мерная поверхность (конфигурационное про­ странство)

Q = [xGDg,(x) = 0, / = 1,А7-г)}, g,eCD).

Определение 9.3

Функционал J(x)e CD)y DczR» называется овражным (жестким) в мно­

Число r называется размерностью (дна) оврага Q. Пример 9.1. Рассмотрим квадратичный функционал

Пусть собственные числа Л, матрицы А =/»(х) удовлетворяют неравенст­ вам (9.9), а Ui означают соответствующие собственные векторы. Предпо­ ложим, что det ^ ^ О и обозначим через х* решение уравнения Ах = Ь.

IVrfll

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

Таким образом, для квадратичных функционалов при сдвинутом в точку X* начале координат дно оврага Q совпадает с линейной оболочкой (9.11) собственных векторов, отвечающих малым собственным числам. Это согласуется с интуитивными представлениями, развитыми в

разд. 9.1.

На этом примере можно проиллюстрировать значение отдельных усло­ вий в определениях 9.2 и 9.3. Действительно, для квадратичного функ­ ционала (9.10) первое и второе условия могут выполняться для всего пространства Q = R» и любого 5 > 0. Необходимая линейная оболочка собственных векторов может быть выделена только при дополнительном требовании, эквивалентном третьему условию. В то же время требования 1, 3 также оказываются недостаточными. В этом случае сдвиг линейной оболочки Q, являющейся дном оврага, вдоль любого из не вошедших в оболочку собственных векторов не приведет к нарушению условий 1 и 3, а условие 2 при этом нарушится.

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

Определение 9.4

Пусть Vx G Q, det J»(x) Ф 0. Наименьшее из чисел а, удовлетворяющих оп­ ределению 9.2, называется степенью овралсносты J(x) в Q и обозначается г|(0. Отношение

r|(jc) = Aj (х) / min X. (х), xeQ

называется локальной степенью овражности J{x) в точке х. Для вырож­ денных матриц J»{x) величина г)(х) принимается равной бесконечности.

Если J»(x) > О, то

г|(;с) = cond[y»(x)] = maxX.(x)/min А.,(х).

В общем случае справедливо неравенство 1 < л < cond{J’). При наличии больших по модулю отрицательных собственных чисел к{х) (т. е. при отсутствии овражной ситуации) возможно неравенство ц(х) « cond[/»(x)]. Из высокой степени овражности Дх) в точке х следу­ ет плохая обусловленность матрицы J’Xx) обратное неверно. Дейст­

г(х) = 1, а cond[/»(^)] = М/т» 1. Данный функционал не будет отно­ ситься к классу овражных, что естественно, ибо трудностей при его ми­ нимизации, например методом наискорейшего спуска, не возникает. От­ личие между двумя характеристиками г](х) и cond[/»(x)] функционала J(x) часто игнорируется и овражными называют функционалы с боль­ шим числом cond(/»), что не оправдывается с позиций основных вы­ числительных трудностей, возникающих при решении задач оптимиза­ ции. Однако, учитывая указанную выше связь между г(х) и cond(y»)? овражные задачи, т. е. задачи минимизации овражных или жестких функционалов, далее будут называться плохо обусловленными задача­ ми оптимизации.

В каждом конкретном случае различные значения г|(х) следует считать большими. Здесь существует полная аналогия с понятием плохой обу­ словленности матрицы. В большинстве случаев все определяется точно­ стью вычислений и типом применяемого алгоритма оптимизации. Тра­ диционно принято классифицировать задачу как плохо обусловленную, если

где / — длина применяемой разрядной сетки компьютера. Однако и при меньших значениях г для многих алгоритмов могут возникать значи­ тельные вычислительные трудности, особенно если овражная структура сопровождается отсутствием выпуклости J(x).

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

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

сГк<пЪкх1

где |X,| = max|Xj. Принимая 5 = Ем = 2″‘, где Ем— относительная машин­ ная точность (машинное эпсилон), а t — длина разрядной сетки мантис­ сы числа, получим оценку для абсолютных искажений собственных чисел из-за ошибок округления:

Параметр е„ известен для каждого компьютера. Из последнего неравен­ ства можно сделать следующее заключение. Если все вычисленные собст­ венные числа матрицы А = J»(x) достаточно велики, т. е. |Х,| > WEMIXII, ТО параметр г| может быть вычислен непосредственно. Если же некоторые из

вычисленных собственных чисел удовлетворяют неравенству |Л,| <«ем|Х1|, то все они должны быть отнесены к блоку малых собственных чисел, а для г имеем границу снизу:

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

9.3. Основные причины возникновения овражных целевых функционалов

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

Естественная причина появления овражной ситуации может быть связа­ на с наличием некоторых неучтенных устойчивых связей между управ­ ляемыми параметрами, определяемых внутренними законами функцио­ нирования моделируемой системы. Если уравнения связей известны, то часть управляемых параметров может быть исключена из рассмотрения. В этом случае наличие овражной ситуации целесообразно трактовать как

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

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

Фактор агрегированности аргументов минимизируемого функционала.

Выбор множества управляемых параметров (аргументов функционала) обычно производится по результатам анализа их влияния на основные характеристики оптимизируемой системы, а также исходя из реальных возможностей изменения этих параметров в нужных пределах. Результа­ том такого вполне естественного подхода является ситуация, когда век­ тор выходных характеристик у оптимизируемой системы в действитель­ ности зависит от S агрегатов:

где

Zi =фДл:); i = ls;s<n.

Подтверждением сказанному служит широко применяемый на практи­ ке метод декомпозиции, связанный с выделением этапов аппроксимации и реализации в процессе оптимального выбора параметров х, (см. разд. 8.4). Прямое решение задачи /(х)-^ min в пространстве парамет­ ров X в данном случае связано с наличием овражной ситуации. Действи­ тельно, значение J{x) мало меняется на множестве, определяемом равен­ ствами

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

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

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

Рассмотрим пример.

Пусть функционирование системы описывается вектор-функцией u{t) = [t/i(/), U2(t)], являющейся решением жесткой дифференциальной сис­ темы, где

Требуется получить оптимальные значения параметров Xi, Xi из условия наилучшего совпадения u{t) с заданной вектор-функцией u{t) для t €

Qxp(-Bt), то из соотношений (9.17) видно, что поведение решения u(t) для

^ ^ Uo, Т] будет определяться агрегатом z = Xi + Xi. Если продолжать счи­ тать Хх и Xi независимыми параметрами, то для оптимизационной задачи

У (Х) = [Wj (f1) — Й; (г, ) f + [^2 (^1) — «2 (^1 )]^ -«^ ^*^’

X

где /i = 1 G [^05 7]^ степень овражности равна г| = 1,8 х 10^ Мы здесь пред­ полагали, что заданная вектор-функция м(0 определяется соотноше­ ниями (9.17) при а = 1; Z? = 1,5; ^ = 20; 5 = 15. Степень овражности рас­ считывалась по формуле:

exp(-min(a, 6))

ехр(-тах(Л, 5))

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

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

Рассмотрим в качестве примера ограничения в виде равенств

5Д^) = 0, ;=1,р.

200 Часть II. Алгоритмические методы скалярной оптимизации

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

р

JQ (Л:, а) = / (х) + а ^ g] {х) -> min

7=1

С достаточно большим положительным коэффициентом а. При этом структура расширенного критерия 7о, содержащего большой параметр а, как правило, оказывается овражной, даже если исходный функционал J{x) этим свойством не обладает.

Пример 9.2. Пусть требуется найти х^ и ^2, минимизирующие квадратич­ ный функционал/(х) = х^^ + Xi при условии Xi = 2. Задача имеет очевид­ ное решение л:* =2, jc* = 0. Поступим формально и составим вспомога­ тельный функционал согласно общей рецептуре метода штрафных функций:

/о {х) = х,2 + Х2^ + а (х, — If = [(Х| — b^f /а,^]-^ [(х2 — Ьг? I aj^] + d,

где а, = ^1 + а; ^2 = U *i = 2 а / ( а + 1); ^2 = 0; Й? = 4а/(а + 1).

Уравнение линии уровня Jo(x) = const является уравнением эллипса с центром в точке (fei, 62) и длинами полуосей, относящихся как а2/а, =

= Vl + cj. При больших значениях а, обеспечивающих относительно точ­ ное выполнение ограничения Х] = 2, линии уровня оказываются сильно вытянутыми (рис. 9.3).

Чем точнее выполняются ограничения, тем ярче выражен эффект овражности. В данном случае степень овражности равна г| = 1 + а. Заметим, что линии уровня исходного функционала являются сферами и явление овражности отсутствует.

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

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

gj{x), могут потерять работоспособность все методы учета ограниче­ ний, основанные на обычной и модифицированной функциях Лагранжа, а также на линеаризации ограничений. Метод же штрафных функций в указанной ситуации применим. Он оказывается наименее чувствитель­ ным ко всем формам вырождения.

Рис. 9.3. Метод штрафных функций

Второй критической ситуацией, возникающей в практике оптимизации, является неоправданное завышение функциональных требований к объ­ екту оптимизации, которое приводит к пустому множеству D допусти­ мых значений управляемых параметров. В подобном случае наиболее целесообразно применять метод штрафных функций, позволяющий по­ лучить такое решение задачи ||gW|| -^min, для которого значение J(x)

минимально. Другие методы либо теряют смысл, либо заведомо не будут сходящимися.

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