3.1. Явление овражности

Рассмотрим следующий пример критерия оптимальности, зависящего от двух управляемых параметров хь х2 [49]:

J(xvx2) = g02(xvx2) + og2x(xvx2) -» min,

(3.1)

где а — достаточно большое положительное число. Рассмотрим также уравнение

gi(xvx2) = 0,

(3.2)

определяющее в простейшем случае некоторую зависимость х2 =ср(х1). Тогда при стремлении параметра а к бесконечности значение функционала/ в каждой точке, гдеgi(xvx2)*0, будет неограниченно возрастать по абсолютной величи­не, оставаясь ограниченным и равным gl(xvx2) во всех точках на кривой х2=ф(х1). То же самое будет происходить с нормой вектора градиента

3.1. Явление овражности

73

Подпись: + 2ogi(xvx2)-f±дхх

л

дх2

2go(x{, Х2 )

Линии уровня J(х) = const для достаточно большого а представлены на рис. 3.1. Там же стрелками показано векторное поле антиградиентов, определяющее ло­кальные направления наискорейшего убывания J(x).

Х2 А


Ясно, что при достаточно больших а минимальные значения/ (х) следует искать вдоль зависимости х2 = (р(х{), определяющей так называемое дно оврага. Из (3.1) следует, что изменение J (х) вдоль дна задается выражением g I (х,, х2) и не зависит от величины параметра а. Таким образом, задача минимизации/ (х) сво­дится к минимизации функционала gl(xv (p(xt)) от одной переменной х{. В об­щем случае уравнение х2 = ц>(хх) обычно неизвестно.

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

Возможны различные усложнения и обобщения рассматриваемой ситуации. На­пример, уравнение (3.2) может, вообще говоря, определять не одно, а несколько решений х2 =ц>і(хі)у каждое из которых означает свой овраг. С точки зрения приложений более существенным обобщением является предположение о нали­чии многомерного дна оврага. Чтобы проиллюстрировать это явление, обратим­ся к следующему примеру:

т

В этом случае дно оврага задается системой уравнений

gi(x) = 0jG[i:ml (3.4)

что, в принципе, позволяет выразить тп параметров х{ через оставшиеся п - т пе­ременных. Предположим, не ограничивая общности, что уравнения (3.4) опреде­ляют следующие зависимости:

хх = ^>i(xm+lyхп),

Аналогично предыдущему случаю устанавливаем, что задача минимизации (3.3) при достаточно больших а эквивалентна минимизации функции go(<Pi> •••» Ф/л> xm+v •••»хп)от г=п-т переменныххп. Число г носит на­звание размерности дна оврага. Легко представить, что, например, для п = 3 по­верхности уровня одномерного оврага имеют характерный «сигарообразный» вид, а для двумерного оврага они будут близки к деформированным дискам.

В любом случае для овражной ситуации определяющим фактором является спе­циальная структура поверхностей уровня / (г), весьма сильно отличающаяся от сферической. Характерно наличие некоторой области притяжения (по сути — дна оврага) Q с Rn, содержащей оптимальную точку х* = arg min J(x). При этом норма вектора градиента J'(x) для х є Q, как правило, существенно меньше, чем в остальной части пространства.

Овражную структуру могут иметь не только функционалы вида (3.1), (3.3), явно содержащие большой параметр а. Можно привести следующий пример квадра­тичного функционала:

f(xi,x2) = 0,250025*2 +0,49995^ + 0,250025*2 -х{-х2. (3.5)

Линии уровня f(x) = const функционала (3.5) представляют семейство подоб­ных эллипсоидов с центром в точке (1:1). Длины полуосей эллипсоидов относят­ся при этом как 1:102. Указать большой параметр а в выражении (3.5) нельзя, хотя овражная ситуация налицо, и так же, как и в предыдущих случаях, явно вы­деляется дно оврага (прямая аЬ на рис. 3.2), имеющее уравнение х2 = 2 -хх. Под­ставляя выражение для х2 в (3.5), снова приходим к эквивалентной задаче мень­шей размерности:

/1(х1) = 10"4(х1 -I)2-l->min.

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

[40], с. 226: «с увеличением размерности задачи возрастает вероятность появ­ления оврагов»;

[50], с. 353: «большинство практических задач многопараметрической опти­мизации, особенно из области оптимального проектирования, страдает оби­лием такого рода ловушек (то есть оврагов)»;

[42], с. 272: «в экстремальных задачах проектирования необходимо использо­вать методы оптимизации, приспособленные для поиска экстремума, в ов­ражных ситуациях»;

[43], с. 161: «особенностью целевых функций при решении задач схемотехни­ческого проектирования является их гребневый (овражный при поиске мини­мума) характер, что приводит к большим вычислительным трудностям;

[17], с. 35: «Наибольшие трудности при поиске локального оптимума достав­ляют так называемые "овражные" ситуации».

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


Авторы: 239 А Б В Г Д Е З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я

Книги: 268 А Б В Г Д Е З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я