автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Градиентные методы в задачах бесконечномерной оптимизации

I Российская академия наук СТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ

На правах рукописи УДК 517.97 : 618.511.4

КУТУЗОВ Алексей Александрович

ГРАДИЕНТНЫЕ МЕТОДЫ В ЗАДАЧАХ БЕСКОНЕЧНОМЕРНОЙ ОПТИМИЗАЦИИ

Специальность 05.13.01 "Управление в технических системах"

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1997

Работа выполнена в Институте проблем управления РАН

Научный руководитель:

доктор физико-математических наук, профессор Бобылев H.A.

Официальные оппоненты:

доктор технических наук, профессор Поляк Б.Т.

доктор физико-математических наук, профессор Антипин A.C.

Ведущая организация: Институт системного анализа РАН

Защита состоится " ^ ¿^^¿^ Ь ( 1997 г. в часов на заседании Диссертационного совета Д 002.08.03 Института проблем управления (117806, Москва, ул. Профсоюзная, д.65).

С диссертацией можно ознакомиться в библиотеке Института проблем управления. ^ ' %г><

Автореферат разослан ' " / ' 11997 г.

Ученый секретарь Дпссертацпонного совета

к.т.н. Власов С.А.

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

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

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

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

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

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

Цель работы. Целью работы является:

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

2. Исследование сходимости метода проекции градиента в задачах бесконечномерной оптимизации с ограничениями.

3. Исследование сходимости градиентных процедур в задачах классического вариационного исчисления.

4. Применение градиентного метода в конкретных задачах (задачи оптимального управления системами с сосредоточенными и распределёнными параметрами, задачи вариационного исчисления).

5. Анализ градиентных методов, применяемых в математич'еских моделях нейронных сетей.

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

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

X. Получены эффективные признаки сходимости градиентных процедур задачах безусловной минимизации невыпуклых функционалов, определённых на гильбертовых пространствах.

2. Исследован диапазон применимости метода проекции граднен-• та в задачах минимизации с ограничениями.

3. Доказана локальная сходимость градиентного метода в .задаче классического вариационного исчисления.

'4. Общие теоретические результаты применены к решению конкретных задач теории управления и инженерной практики (задачи сорбции и сушки. задачи Гурса-Дврбу. задачи Эйлера).

Апробация работы. Результаты диссертации докладывались на XXVI Воронежской зимней математической школе, на конференциях "Методы функционального анализа и их приложения" (Самара, 1994), "Математические задачи химической кинетики" (Тверь, 1995), "Устойчивость и колебания в нелинейных системах управления" (Москва, ИПУ РАН, 1996), "XXXIX научная конференция МФТИ" (Москва, 1996), а так же на семинарах Института проблем управления РАН, Института системного анализа РАН и Московского государственного университета.

Публикации. По теме диссертации автором опубликовано 8 научных работ.

Структура работы. Работа состоит из введения, четырёх параграфов, закелючення и списка литературы, содержащего 46 названий. Общий объём работы — 101 страница.

2. СОДЕРЖАНИЕ РАБОТЫ.

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

В первом параграфе исследуется сходимость градиентных процедур в задаче приближённого нахождения точек минимума функционалов, определённых на гильбертовых пространствах. Приводятся приложения к задачам классического вариационного исчисления. В нём выделяется класс функционалов, для которых удается доказать сходимость градиентных процедур. Этот класс составляют дифференцируемые' функционалы, градиенты которых удовлетворяют так называемому условию (Р, 5) Пале-Смейла. Класс таких функционалов достаточно широк. В частности, функционалы классического вариационного исчисления, регулярные многомерные интегральные функционалы, различные функционалы, возникающие в механике, статистической физике, теории управления сосредоточенными и распределёнными системами.

Пусть Н — вещественное гильбертово пространство со скалярным произведением (и, г). Рассмотрим на Н непрерывно дифференцируемый по Фреше функционал f-.II—* Ш.. ■

Будем говорить, что градиент V/ : Н —* Н функционала / удовлетворяет условию (Р, 5) Пале-Смейла, если для каждого ограниченного замкнутого множества М С Н из неравенства

V/(u)?¿ О (иеМ).

вытекает неравенство

М ||У/(и)|| > О.

Градиент V/ функционала / называется локально липшицевым, если для каждого шара

В(г, и) = {и € Н : ||и - < г} существует константа Ь — Ь{г, и), для которой

||У/(и1) - У/(и2)|| < ЫН -«а|| (ui.ua 6 В(г,и)).

Точка и, € Н называется критической точкой функционала /, если V/(u») = О. Как известно, точки минимума дифференцируемых функционалов являются их критическими точками.

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

Чп+1 =«„-7,Л7/(ип) (п = 0,1,...). (1)

.Пусть / : Н —» М — дифференцируемый по Фреше функционал, градиент V/ : Н —* Н которого удовлетворяет условию (Р,Б) Пале-Смейла и является локально липшицевым. Пусть, далее, и, — единственная в шаре В (г, и,) критическая точка функционала /, реализующая его локальный минимум. Рассмотрим процедуру градиентного спуска (1) приближённого нахождения точки и,.

Теорема 1. Пусть управляющие параметры уп метода (1) удовлетворяют неравенствам

О < ß < 7п < Ь < 2Ь"\ (2)

где L — константа Липшица градиента V/ функционала f на шаре В(г,ит). Пусть начальное приближение и0 метода (1) достаточно близко к и„. Тогда последовательные приближения ип метода градиентного спуска (1) сходятся к и + :

lim ||un—u.|| = 0.

п—*оо

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

lim f(u) = оо, (3)

||u||—.ОО

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

Рассмотрим произвольное начальное приближение и0 и определим множество

Ото = {u е Я : /(и) < /К)}.

В силу условия (3) это множество ограничено и, следовательно, содержится в некотором шаре В0. Обозначим через L0 константу Липшица градиента V/ функционала / на шаре Во-

Теорема 2. Пусть и, — единственная критическая точка растущего функционала /, градиент V/ которого удовлетворяет условию (Р, S) Пале-Смейла. Пусть управляющие параметры -уп градиентного метода (1) удовлетворяют неравенствам

О < ßo < 7п < Ь0 < 2L~x.

(

Тогда

lim ||u„-u,|| = 0.

n—»oo

Рассмотрим задачу минимизации одномерного функционала вариационного исчисления

I

и) = J F(t,u,u)dt, u(0) = u(T) = О

(4)

с дважды непрерывно дифференцируемым лагранжианом F(t,u,p).

Экстремали функционала / — это решения двухточечной краевой задачи для уравнения Эйлера

d OF OF dt dp du ~ '

u(0) = u(T) = 0. (5)

Предположим, что лагранжиан F(t, u,p) функционала / удовлетворяет оценкам

\F(t,u,p)\ +

dF(t,u,p) &F(t,u,p)

du du2

0F(t,u,p) a2F(i,«,p)

dp QuQp

0 < с < -1 „ < C3(t,u)

^C^^uXl+p2), (6) <Ca(t,»)(l+ И), (7)

(8)

др2

(о < г < 1, и,р € В).

Тогда функционал / определен и дифференцируем по Фреше на про-

о >

странстве И'2[0, Т] абсолютно непрерывных функций и(<), удовлетворяющих условию (5), производные которых суммируемы с квадра-

о »

том. Пространство И'2[0, Т] гильбертово; скалярное произведение и норма в нем определяются равенствами

1

(u, v) = J u'(t)v'{t)dt,

о

IMI = ( J\At)f) '

Непосредственный подсчет показывает, что градиент функционала / имеет вид:

„ ч /й^, Г Г дГ , * /■ 8Р г } Г

= / — ^ - —¿Т(1Я - - —¿в + - —¿таз. ]др 3 ] ди Т J др Т 3 3 ди

о оо о оо

Из оценок (6) - (8) следует, что Градиент V/ функционала / являет-

о »

ся локально липшицевым на пространстве И<'2[0, Г] и удовлетворяет условию (Р, 5) Пале-Смейла. Поэтому из теорем 1 и 2 вытекают следующие утверждения.

Теорема 3. Пусть и» = и»(4) — изолированная в пространстве

о 1

И'2[0, Т] экстремаль функционала (4), реализующая его локальный минимум. Пусть Ь = Ь(г) — константа Липшица градиента V/

о 1

этого функционала на шаре В(г,и.) С И'2[0,Т]. Пусть

0</?<7 п<Ь< 2Ь~Х (9)

и начальное приближение и0 = ио(0 градиентного метода

и"+1 = и"-7ЧУ —^—У —л:—

О 0 0

IV «9р Г V У ди )

достаточно близко в норме W\[0,T\ к и,. Тогда■

Hm |К(0-«.(011^1о:п=0. (11)

Теорема 4. Пусть и, = u,(i) единственная экстремаль функционала (4) и

lim /(и) = оо.

IMIo, -ОО

w'io.r)

Пусть и0 = Uo(i) — начальное приближение метода (10) и множество

о 1

ОТТо = {и € VV2[0, Т] : /(и) < /(«„)}

о

о о

лежит в шаре В(г,и„). Пусть, наконец, выполнены неравенства (9), где Ь —константа Липшица градиента V/ на шаре В(г,и,) С

о 1

И^О, !Г]. Тогда имеет место сходимость (11).

Рассмотрим в Ш1*1 ограниченную область О с достаточно глад-

о т

кой границей. Пусть 1У2 (О) — пространство Соболева функций и(х) (х е О), имеющих обобщённые производные до порядка тп, суммируемые с квадратом, и нулевой след на границе дО области П

о

вместе с производными до порядка т — 1. Пространство XV2 (П) — гильбертово; скалярное произведение и норма в нем определяются равенствами

(«.«)• ,0, = 21 [тГиТГуЛх, и'учп) 3

|о|=:тп

1М1 = ( £ / 1Х>"«|аЛг) /2

Здесь

\dxtS \дхк/

а = (о!,... ,с*л')> а> — целые неотрицательные числа;

о т

|а| = с*1 + . • • + ал/. Рассмотрим на IV2 интегральный функционал

/(и) = Ур(х,и,£>и,...,/?ти)<гх, (12)

где

^(х) = {2>аи(х); |а| = )Ь} (Л = 1,... ,т). Экстремали функционала (12) — это обобщённые решения из

о т

(О) задачи Дирихле для уравнения Эйлера этого функционала £ ......^,0,

2?к«(х) 0 (|*|<п»-1). Справедливо следующее утверждение

Теорема 5. Пусть u,' = и,{х) — изолированная в пространстве

о

IV2 (О) экстремаль функционала (12), реализующая его локальный минимум. Пусть L — константа Липшица градиента V/ функци-

о m

онала / на шаре J3(r, ti.) С W2 (П). Пусть выполнены неравенства (9). Пусть, наконец, начальное приближение «о = ио(х) градиентного метода

«п+1 = "п — 7пД_т £

г I ^ |а|<т

о т

достаточно близко в норме VV2 (ii) к и,. Тогда имеет место сходимость у

lim ||ип(х) - о = О.

n—oo WJ*(n)

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

Метод проекции градиента является одним из основных методов минимизации задач с ограничениями.

Процедура этого метода в задаче

/ /(«) - тт.

Кием 4 '

сводится к построению последовательных приближений х0, определяемых равенством

/

ип+1= Рм{ип--1пЪ1(ип)) (п = 0,1,...). (14)

Здесь V — оператор градиента, а 7„ — некоторая последовательность положительных чисел (управляющих параметров метода), а Ри — оператор проектирования на множество М.

В этом параграфе выделен класс функционалов, определённых на гильбертовых пространствах (Н-правильные функционалы), для которых удалось доказать сходимость метода проекции градиента.

Класс /f-правильных функционалов довольно широк. К нему относятся регулярные интегральные функционалы, определённые на

о

пространствах Соболева W™(Cl), функционалы классического вариационного исчисления, функционалы, возникающие в задачах оптимизации систем, описываемых уравнениями Гурса-Дарбу, функционалы в задачах коррекции движения и т.д.

Пусть Н — вещественное гильбертово пространство со скалярным произведением (u,v). Дифференцируемый на Н функционал / называется .ff-правильным, если его градиент V/ : Н —* Н локально Липшицев и удовлетворяет условию (S):

если последовательность ип слабо сходится к точке и0 G Н и

lhT(V/(un),u„ -u0) < О, (15)

П—- ОС

ТО

lim ||u„ — u0|| = 0. (16)

п—'ОС

Пусть, далее, М С Н — замкнутое выпуклое множество, а Рм : Н —» М — оператор проектирования пространства Н на множество М. Как известно, оператор Рд/ всегда существует, удовлетворяет условию Липшица

< II«!-«all (17)

и для любого V&M

(и- Рм(и),Рм(и)~ v)>0 (18)

Точка к, 6 М называется критической точкой функционала / : М —* если для некоторого Л, < О

A.V/(u.) 6 Щи.), (19)

где ЛГ(и.) — нормальный конус к множеству М в точке п..

Рассмотрим процедуру (14) метода проекции градиента отыскания минимума функционала /.

Теорема в. Пусть и. — изолированном критическая точка Н-правильного функционала f : М —* М, реализующая его локальный минимум. Пусть управляющие параметры ~/п в методе (14) удовлетворяют неравенствам

о < Oí < 7n < »2 < 2/L, (20)

где L — константа Липшица градиента V/ : М —+ Н. Пусть начальное приближение и0 6 М достаточно близко к и,. Тогда приближения ип в методе (14) сходятся к точке и, по норме пространства Н:

lim ||un-w.||=0. (21)

n—»oo

Если множество М ограничено, а критическая точка и, единственна, то для сходимости метода (14) требование близости начального приближения Uq к и, излишне. Справедлива

Теорема 7. Пусть множество М ограничено, и, — единственная критическая точка функционала f : М М, а управляющие параметры -уп в (1-fJ удовлетворяют неравенствам (20). Тогда для любого начального приближения uq имеет место сходимость (21).

Простые примеры показывают, что для неограниченных множеств Л/ единственность критической точки и., в которой реализуется минимум функционала / на М недостаточна для сходимости метода (14) к и, при любом и0. Однако, если функционал / является растущим на множестве М, т.е.

lim /(и) = оо, (22)

1М|-°о и е м

то сходимость метода (14) к и, имеет место при любом начальном приближении ti0.

Теорема 8. Пусть и, — единственная критическая точка растущего Н -правильного функционала / : М —+ М. Пусть выполнены неравенства (20). Тогда и, реализует глобальный минимум функционала f на множестве М и для любого начального приближения uq € М имеет место сходимость (21).

При исследовании процессов сорбции, сушки и др. возникает следующая задача:

JJ y>°(«, t, x(a,t),u(s,t))dsdt —► min (23)

Q

д2х Ох дх

— =Cl{s,t)x + C2(s,t)—+C3(8,t)— + C0(8,t)u (24) х(0, t) = 'О (О < t < Т), х(я,0) = О (О < я < S) (25)

JJ u2(s,t)dsdt < р2. (20)

О

Здесь Q = {(в,í) е JR2 : (О < s < S, 0 < í < T)} — прямоугольник на плоскости JR2, х = (xi,...,x„), и = (ui,...,ur), функция iр° и матрицы С0,Си С2, непрерывно дифференцируемы по совокупности переменных, причем частные производные и удовлетворяют условию Липшица по х, и и существует а > О такое, что

(ç>l(s,t,x,Ui) - ï>°u(s,t,x,u2),ui - U2) > a IK - u2|f . (27)

При сделанных предположениях задача Гурса-Дарбу (24) - (25) при каждом фиксированном и = u(s,t) 6 имеет единственное решение х = D(u). Поэтому задача (23) - (26) эквивалентна задаче минимизации функционала

/(u) = JJ V>°(s,t,D(u),u)dsdt (28)

Q

на шаре В{р) С.

Верна следующая теорема.

Теорема 9. Пусть и, — единственная на шаре В(р) С L^(Q) критическая точка функционала (23), являющаяся точкой его глобального минимума на В(р). Пусть параметры fn удовлетворяют оценкам

0 < Û! < 7п < < 2/L,

где L — константа Липшица градиента функционала (23). Тогда для любого начального приближения u0(s,t) € В(р) метод (14) сходится е L^(Q) »« u,(s,t):

lim ||и„ -u.||t;(Q) = 0.

n—*оо э

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

1

/(г) =У"г(х'(0,Х(0,«)Л. (29)

о

о

рассматриваемого на пространстве С [О, 1] непрерывных функций, обращающихся в ноль в точках О и 1.

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

о

странствах И'™ при больших тп обладают хорошими дифференциальными свойствами, но не являются слабо полунепрерывными.

о

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

о

функционалов в пространствах с равномерными нормами типа СЧ, в которых гладкость таких функционалов определяется лишь гладкостью их интегрантов.

Пусть лагранжиан Р функционала (29) непрерывен по всем переменным, его производные и Рх/ непрерывны по < и удовлетворяют условию Липшица

*>(ра,9а.01 < ¿(|р, -Ра| + |*1 -<Ы). '

а вторая производная Рг>х> непрерывна по всем переменным и удовлетворяет неравенству

Рх'ж' > а > О. (31)

Найдем вид градиента V/ функционала /, рассматриваемого на

о о

пространстве Ci[0,1). Пусть h = h(t) 6 С [0,1]. Тогда 1 t <V/(x),ft) = У (Fm.(x'(t),x(t),t)- J Fx{x'{B),x(s),s)da- (32) о о

1 т

-J (fx,(x'(t),x(t),t) - f Fx(x'.(s),x(s),s)dsJdrJ h'(t)dt.

0

Отсюда следует, что г

^/(*) = Д^(х'(г),х(г),г)-У" Рх{х\„),х{в),8^^Т - (33) о о

1 т '

J(Fя.^x'^т),x^т),т)- у *'«(*'(').*(•).')<*«)<'»■.

о о

Из формулы (34) следует, чтд V/(x) € 1] С 1] и

(У/(д;),Л) совпадет со скалярным произведением в про-

о

странстве И^О, 1].

Для минимизации функционала / воспользуемся градиентной процедурой

хп+1 = хп - 7п^/(хп), (34)

о

где х0 — некоторый элемент пространства С [0,1], а -уп — последовательность положительных, чисел, называемых управляющими параметрами метода (34) и удовлетворяющих неравенствам

0 < < 7„ < а2 < 1/41,; (35)

здесь Ь — константа, входящая в неравенства (30).

Теорема 10. Пусть х, = х,(£) — изолированная в пространстве

о

С [0,1] экстремаль функционала (29), реализующая его локальный

о

минимум. Пусть начальное приближение х0 = х0(Ь) € С [0,1] гра-

о

диентного метода (34) достаточно близко по норме С [0,1] К1,.

Тогда

lim ||x„(i)-a:.(i)||. =0. (36)

n—оо C'lo.l]

О

В чехвёрхом параграфе рассматриваются нейронные сети, описываемые нелинейными динамическими системами. Приводится оценка количества асимптотически устойчивых положений равновесия для системы Хопфилда. Изучаются вопросы применения нейронных сетей в задачах оптимизации и ассоциативной памяти, моделирования нейронных сетей на цифровых ЭВМ.

Сеть Хопфилда состоит иэ п нейронов с одинаковой функцией выхода. Состояние 1-го нейрона, т.е. уровень его возбуждения, описывается скалярной функцией х,(£) (г = 1,...,тг). Динамика сети Хопфилда описывается следующей системой обыкновенных дифференциальных .авнений

с1х Л

= -Ох + Т/(х) + 1.

(37)

Здесь

I =

вектор, зависящий только от входных сигналов сети, которые предполагаются постоянными.

Т =

Г

-1

I ■ ■ ■ £пп 1

— матрица синаптических весов связей между нейронами; она часто предполагается симметричной.

О ... О

О О

— положительно определенная диагональная матрица,

/(*0 ]

</(*„) и

п

— вектор выходов нейронов. Функция выхода /(•) обычно предполагается монотонно возрастающей и ограниченной. Выходом сети Хопфнлда при заданном начальном состоянии х(0) является ее асимптотически устойчивое положение равновесия, к которому стремится j-(f) при t —> оо.

Специфика модели Хопфилда состоит в том, что существует функция энергии Е(х), убывающая вдоль траекторий системы (37), которая используется при изучении качественных свойств этой системы. В частности, это позволяет использовать нейронную сеть для решения разнообразных задач оптимизации.

Пусть данные представляют собой набор п - мерных векторов a¡,. .., íim. Требуется построить нейронную сеть, способную по искаженному входному сигналу ац восстановить неискаженный сигнал а*, 1 < к < га. Одним из наиболее широко распространенных подходов является модель Хопфилда. В этом случае входной сигнал определяет начальное состояние нейронов. Различные варианты этой схемы хорошо изучены экспериментально. Так, моделирование на цифровых ЭВМ показывает, что сеть работает удовлетворительно, если т < 0,14п. Основной трудностью этого подхода является наличие асимптотически устойчивых положений равновесия отличных от заданных, что снижает надёжность распознавания.

Для дифференциальной модели (37) постановка задачи выглядит следующим образом: найти матрицы D,T, вектор I и скалярную функцию f(x), чтобы система (37) имела асимптотически устойчивые положения равновесия в заданных точках ai,... ,ат. Желательно отсутствие других асимптотически устойчивых положений равновесия. Система (37) посредством замены переменной сводится к системе

Здесь матрица Н(х) является положительно определённой и симметричной при всех х.

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

(38)

(39)

>=1

о

гладкой функцией. Условия, которым должны удовлетворять Т и I имеют вид:

- Та{ + Да.) -1 = 0 1 < t < m

L tnl

iln|

tnn J

+

f'(x г) 0 ... 0 0 f'(x2) ... 0

0

0

.-(40) >0 (41)

при

(t = 1,..., m).

Условие (40) является системой тп линейных уравнений относительно коэффициентов Т и I. Если через Ати(Л) обозначить наибольшее собственное значение матрицы А', то условие (41) можно заменить эквивалентным ему условием (42)

Атах(Г)<с= min {/'(*.•)!_ }• 1<<<п l<j<m

(42)

Известно много оценок границ спектра матрицы через её коэффициенты. Применяя какую-либо из этих оценок можно свести задачу (40), (42) к стандартной задаче на условный экстремум, методы решения которой хорошо известны. Эксперименты показывают, что этот подход-является вполне приемлемым, особенно если для решения задачи на условный экстремум использовать нейронную сеть. Однако его практическое применение осложняется по ряду причин. Во-первых, в результате минимизации может быть найден локальный экстремум, в котором условие (42) не выполнено, в то время как для глобального минимума оно выполняется. Во-вторых, могут появиться посторонние асимптотически устойчивые положения равновесия. Эти проблемы в настоящее время не решены.

В четвёртом параграфе получена оценка количества асимптотически устойчивых положений равновесия для произвольной динамической системы, обладающей глобальной функцией энергии. В частности, этот результат применим к системе (37). Из (40) следует, что количество положений равновесия системы (38) имеет поря-п

док —. Ниже доказано, что по крайней мере половина из положений

равновесия системы (38) неустойчивы. Поэтому при конструирова-

п

нии нейронной сети нельзя брать т > —. Это означает, что эмпирическая оценка т < 0,14п не может быть существенно улучшена за счет выбора алгоритма синтеза.

Теорема 11. Если функция Е{х) е С2(JR"), имеет к невырожденных критических точек, и

lim Е(х) = +оо, (43)

то количество точек строго локального минимума Е(х) не пре-

Ш

восходит 1 — 1 + 1.

Теорема 11 применима к системе Хопфилда лишь при дополнительных предположениях, связанных с условием (43). Однако они не являются существенными. Будем предполагать, что /(х) € С(Ш) П Ь00(Ш),П = сИад(с11,..., ¿„) > О, Г 6 -И"*", I 6 Шп.

Теорема 12. Если функция Е(х) 6 С2(Шп) убывает вдоль траекторий системы (37) и имеет к невырожденных критических точек, то количество точек строго локального мингилума Е(х) не

, Г*1

превосходит 1 — 1 + 1.

Нейронные сети и, в частности, сеть Хопфилда широко применяются в задачах оптимизации, где нейронная сеть решает задачу нахождения точек локального минимума функции Е{х), убывающей вдоль траекторий системы (37). Общепринятым считается следующий подход: строится функция Е(х), локальные минимумы которой являются решениями задачи. Затем строится нейронная сеть (обычно в виде электронной схемы), которая описывается такой системой уравнений, что функция Е(х) убывает вдоль траекторий этой системы. Структура сети и веса связей определяются с помощью функции Е(х), поэтому нет необходимости в применении обучения.

Часто рассматривается задача нахождения минимума функции f(x) при ограничениях д;(х) > О 1 < г < р. Обозначим

дТ(х) = — гшп{0,<7;(х)}.

Функция энергии Е(х) выбрана в виде

р

Е(х)=пх)+с^2(д7(т))2. 1=1

Нейронная сеть описывается системой уравнений

<1хк 1 8Е(х)

= (44)

Здесь с, Ск — некоторые положительные постоянные. Вопрос об устойчивости положений равновесия системы (44) изучен достаточно полно. Однако асимптотически устойчивое положение равновесия может не удовлетворять ограничениям задачи.

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

В работе доказано существование положения равновесия в системе (37) при минимальных предположениях.

Теорема 13. Пусть

/(*) е с(Л) п ¿«.(л);

Г> = <Иад(дх.....<1п) > О, Т 6 Лйпхп, I € й". Тогда в системе (37)

существует положение равновесия.

Другим подходом экспериментального изучения нейронных сетей является моделирование на цифровых ЭВМ. Известно много стандартных методов численного решения задачи Коши для системы обыкновенных дифференциальных уравнений. Однако убывание функции Е(х) вдоль траекторий системы (37) не обеспечивает, вообще говоря, убывание Е(х) в процессе численного интегрирования.

Разностное уравнение метода Эйлера с переменным шагом для системы (37) имеет вид

Ук+1 =ук + Ьк(-Оук + Т/(ук) + 1). (45)

Из теоремы 14, приведенной ниже, следует убывание последовательности {Е(ук)} при достаточно малом шаге Л*. Отметим, что шаг может не быть постоянным: при приближении ук к положению равновесия системы (37) его следует уменьшать.

Теорема 14. Пусть функция Е(х) € С1 (.К") убывает вдоль траекторий системы

х =

14 при всех х справедлива оценка

(УЕ(х),Г(х)) <-* ||Г(*)||" (46)'

(где а и и — положительные числа, не зависящие от х). Пусть градиент ^7Е{х) удовлетворяет условию Липшица

- ЪЕ(х2)|| < £ ||х! - х2||, V хих2 6 Ж"

а последовательность {у*,} определена формулой

Ук+1 = Ук + ЬкР{ук);

?/о — произвольно. Тогда при

л*<уРЧЫ1Г2

последовательность {Е(уп)} убывает.

В заключении диссертации сформулированы основные выводы, полученные в работе.

Основные результаты работы состоят в следующем:

1. Исследован вопрос применимости градиентных методов в задачах минимизации невыпуклых функционалов без ограничений.

2. Изучена сходимость метода проекции градиента в задачах минимизации невыпуклых функционалов с ограничениями.

3. Доказана равномерная сходимость градиентных процедур в задачах классического вариационного исчисления.

4. Исследовано применение градиентных методов для реализации нейронных сетей.

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

Публикации по теме диссертации;

■1. Дементьев С.Н., Кутузов A.A. Градиентные методы в задачах управления распределёнными системами. XXVI Воронежская зимняя математическая школа. Воронеж, 1994.

2. Кутузов A.A. Градиентные методы в задачах математической физики. Методы функционального анализа и их приложения. Самара, 1994.

3. Бобылев H.A., Кутузов A.A. О методе проекции градиента в задачах бесконечномерной оптимизации. Автоматика и телемеханика, N 5, 1995.

4. Дементьев С.Н., Исмаилов И.Г., Кутузов A.A. Градиентные методы в задачах оптимального управления распределёнными системами. Математические задачи химической кинетики. Тверь, 1995.

5. Н.А.Бобылев, С.К.Коровин, Кутузов A.A. Градиентные методы в бесконечномерных задачах. // Дифференциальные уравнения. т. 31, No. 10, 1995.

6. Кутузов A.A. Итерационные методы решения вариационных задач. // XXXIX научная конференция МФТИ. Секция проблем управления. Москва, 1996.

7. Исмаилов И.Г., Кутузов A.A. Градиентные процедуры для интегральных функционалов. // Автоматика и телемеханика. No. 3, 1997.

8. Бобылев Н. А., Булатов А. В., Кутузов А. А., Коровин С. К. Некоторые свойства математических моделей нейронных сетей. // Автоматика и телемеханика. No. 4, 1997.

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

in.HTHf.1C0.UR4