Сингулярные дифференциальные уравнения в задачах оптимизации тема автореферата и диссертации по математике, 01.01.02 ВАК РФ

Цыганков, Александр Александрович АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Москва МЕСТО ЗАЩИТЫ
1999 ГОД ЗАЩИТЫ
   
01.01.02 КОД ВАК РФ
Диссертация по математике на тему «Сингулярные дифференциальные уравнения в задачах оптимизации»
 
 
Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Цыганков, Александр Александрович, Москва

' . г

Н ? :

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. ЛОМОНОСОВА

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

Кафедра общей математики

На правах рукописи

ЦЫГАНКОВ Александр Александрович

СИНГУЛЯРНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ В ЗАДАЧАХ ОПТИМИЗАЦИИ

01.01.02 - дифференциальные уравнения

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

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

доктор физико-математических наук

профессор М.М. Хапаев

Москва 1999

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..............................................................................................................3

ГЛАВА I. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ ЭКСТРЕМУМА.....................................................................................................16

§1. Постановка задачи.........................................................................................16

§ 2. Задача без ограничений...............................................................................20

§ 3. Задача с ограничениями в форме равенств.................................................22

§ 4. Задача с ограничениями в форме равенств (особый случай).....................32

§ 5. Задача с ограничениями в форме неравенств.............................................36

§ 6. Задача с ограничениями в форме неравенств (особые случаи).................47

§ 7. Задача с ограничениями в форме равенств и неравенств..........................55

§ 8. Задача с ограничениями в форме равенств и неравенств (особые случаи)65 ГЛАВА II. СИСТЕМЫ СИНГУЛЯРНЫХ ДИФФЕРЕНЦИАЛЬНЫХ

УРАВНЕНИЙ........................................................................................................74

§ 1. Задача без ограничений и с ограничениями в форме равенств.................74

§ 2. Задача с ограничениями в форме равенств и неравенств..........................79

§ 3. Задача оптимального управления................................................................83

ЗАКЛЮЧЕНИЕ....................................................................................................85

СПИСОК ЛИТЕРАТУРЫ...................................................................................86

ВВЕДЕНИЕ

Задача исследования функции на условный экстремум в течение многих лет неизменно привлекала внимание математиков. За последние десятилетия в работах [22-29] была построена теория необходимых и достаточных условий экстремума в задачах с ограничениями в форме равенств и неравенств в конечномерном и бесконечномерном случаях. Были также развиты разнообразные численные методы решения экстремальных задач [6-14].

В конце 80-х - начале 90-х годов в работах М.М. Хапаева [1-4] было предложено использовать для решения задач оптимизации системы сингулярных дифференциальных уравнений, правая часть которых обращается в бесконечность на некоторых поверхностях, называемых особыми (сингулярными) многообразиями.

Рассмотрим систему дифференциальных уравнений вида

х = Г(х,у), х(0) = Хо, ■ хеЯ", (1)

где у - параметры.

Определение 1. Особое многообразие g(x,y) = 0 называется притягивающим (устойчивым) в области X, если при любом Хо е X существует число Т такое, что

Нтв(х(х0,уД),у) = 0.

I—>Т •

Другими словами, интегральная кривая достигает особого многообразия за конечное время.

Определение 2. Особое многообразие §(х,у) = 0 называется полупритягивающим (полуустойчивым) в области X, если оно делит область X на две части Х+ и X", и если существует число Т такое, что

1ш^(х(х0,у,0,у) = 0,

при условии, что Хо принадлежит одной из частей Х+ или X".

На основе сингулярных многообразий были построены повторяющиеся движения в системе, содержащей быстрые и медленные переменные, аналогич-

ные релаксационным колебаниям [5]. Система описывала процессы, сопровождающие распространение магнитозвуковых волн в плазме.

Пример. Рассмотрим систему двух уравнений

—1

Х1 = (а11Х1 + а12Х2 ) х2 = (а21Х! + а22х2)

На фазовой плоскости (хьх2) вне прямых aiixi+ai2x2 = 0 и a2iXi+a22Xi = 0 фазовые траектории определяются линейной системой

Х1 = ^21Х1 ^22Х2 Х2 = <4lXl ^12Х2

Особыми многообразиями будут указанные прямые. Фазовой траекторией является кривая второго порядка до пересечения с этими прямыми. В точке пересечения имеет место разрыв производной фазовой траектории.

Рассмотрим теперь задачу исследования функции на условный экстремум f(x) -> inf, х е X = {х € Rn:gi(x) = 0, i - 1, ..., m; &(х) < 0, i = m+1, ..., /}, где функции f(x), gi(x), ..., g/(x) определены и непрерывно дифференцируемы на Rn.

Известно [11], что для нахождения min f(x) при наличии условий типа равенств и неравенств используется регулярная система дифференциальных уравнений

х = -ьх(хД)>

где Ьх(х,Я) - градиент функции Лагранжа.

В работе [3] было предложено вместо функции Лагранжа использовать функцию

K(x^) = f(x) + t^(x)g:p4x), i=l

называемую управляющей. Функции jj,;(x) регулярны в рассматриваемой области, а числа р, выбираются равными 1 или 2, хотя может быть удобнее другое положительное число. Функция K(x,jj.) на многообразиях g;(x) = 0 имеет особенности, в отличие от функции Лагранжа, которая регулярна. Наряду с функцией К указанного выше вида может быть удобно использовать функцию К вида

К(х, ц) = ? (х) + X ШЕГ* О) + .

Запишем теперь систему дифференциальных уравнений, правая часть которой представляет собой антиградиент функции К(х,ц):

х=-Кж(х,ц(х». (2)

Полученная К-система имеет сингулярные многообразия, определяемые условиями &(х) = О, I = 1, ..., /.

Функции ^¡(х) выбираются так, чтобы многообразия, определяемые условиями в форме равенств, были устойчивыми, а многообразия, определяемые условиями в форме неравенств - полуустойчивыми. Через функции ^(х) определяется область влияния многообразия &(х) = 0, обладающая тем свойством, что траектория, начинающаяся в этой области, приближается к этому многообразию, от функции ¡1;(х) зависит и скорость такого приближения.

В соответствии с описанным выше способом выбора множителей ц,(х) движение к допустимому множеству X совершается последовательно от одного устойчивого многообразия к другому. Достигнув устойчивого многообразия, траектория остается на нем, пока оно обладает устойчивостью. Достигнув следующего устойчивого многообразия, она движется по их пересечению и т.д. Такое движение напоминает скользящий режим в системах управления [18, 19].

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

Пример. [9, с. 367]. Пусть требуется решить задачу

Я(х) = х2+ху+у2 М, х е X = {(х,у) е Я2.^(х) = х+у-2 = 0}. Рассмотрим управляющую функцию вида

К(х,ц) = 1п % = х2+ху+у2+|_11п(х+у-2). Тогда К-система будет иметь вид

~ М-

х = -2х - у--

х + у-2

У (3)

Му = -х-2у--г

х + у-2

Откуда ~ (х + У) = _3(х + у)--, ^ = _3(ё + 2)-^. Тогда

<11 х + у-2 ей g

й 6.1

Г

з

= —3(g2 ч- 2g) — = —3(g +1)2 + 3 — . Если мы выберем — > т0

V 4 У

многообразие § = 0 будет притягивающим. С другой стороны

4(Х-У) = -(Х-У)>

ш

и траектория системы (3) будет притягиваться к прямой х = у на пересечении которой с прямой х+у = 2 в точке (1,1) имеет место условный минимум функции £

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

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

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

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

В 3-м и 4-м параграфах исследуется задача с ограничениями в форме равенств:

£(х)->ш£ хеХ={хбКп:Йх) = 0,1 = 1,..,ш}. (4)

где функции £ ..., ^ здесь и далее непрерывно дифференцируемы необходи-

п 1 гп

мое число раз на Я , а векторы , ..., - линейно независимы.

Как известно, существование ненулевых множителей Лагранжа для этой задачи эквивалентно тому, что в стационарной точке М0 е X обращается в нуль определитель Грама

<ут) (угсв1) ... г=<Уь1чг> (У%1У%1) ... (У§'Уёт)

(У§тУО (УётУё1) ... (УётУ§т) векторов У£ У§*, ..., Vgm. Таким образом, координаты стационарных точек могут быть найдены путем решения системы уравнений g1 = 0, { = 1, ..., т; Л^ = 0, ] = 1,...,/, где А] - миноры порядка т+1 матрицы

А =

x) x

9X1

поскольку Г представляет собой сумму их квадратов.

Главным результатом 3-го параграфа является следующая Теорема 1.3. Пусть в точке М0 е X обращается в нуль определитель Грама Г векторов У£ ..., Уёт. Тогда если в точке М0 квадратичная форма

(УГУ£) (УГУё*) (У^УГ) (Уё'Уё1)

(УГУВга)

(УётУО (У§тУё1) ••■ (У8тУ§т)

относительно миноров А] порядка т+1 матрицы А определена положительно (отрицательно), то в этой точке имеет место условный минимум (максимум) функции £

2

Задача об экстремуме функции Г на множестве X сводится к задаче об экстремуме на этом же множестве функции О. Рассматривать функцию в как квадратичную форму относительно А; удобно для доказательства существования в точке М0 ее безусловного экстремума. Уравнение 0 = 0 определяет сингулярное многообразие в построенной для доказательства теоремы системе дифференциальных уравнений. Отметим, что для решения задачи с ограничениями в форме равенств знание множителей Лагранжа не требуется.

В 4-м параграфе нами рассмотрен случай т = п - 1. В этом случае необходимым условием экстремума будет являться обращение в нуль в некоторой точке Мо еХ якобиана

А = I í,g '•••,§— \х1 ,х2, ...,хпу

функций ..., по переменным хь х2, ..., хп, поскольку тогда Г = А2. Достаточные условия экстремума устанавливает

Теорема 1.5. Пусть в точке М0 е X выполняется равенство А(М0) = 0. Тогда если в точке М0 определитель

v х} ,х2, ...,хп у

положителен (отрицателен), то в этой точке имеет место условный минимум (максимум) функции £

Если в точке М0 определитель А(1) обращается в нуль вместе с определи-

телями

Д(2) = I

V х1,х2,...,хп )

, А(3) = I

д(2)

,..., Л(21) = I

V х1,х2,...,хп у

V х1,х2,...,хп у

где / = 1, 2, ..., но определитель А(2/+1)(М0) ф 0, то при Л(2М)(М0) > 0 в точке М0 имеет место условный минимум функции £, а при Д(2/+1)(М0) < 0 - условный максимум.

Если в точке М0 определитель Д(1) обращается в нуль вместе с определителями а(2), а(3), ..., д(2М), но Л(2/)(М0) ф 0, то в этой точке условного экстремума

функции Гнет.

Уравнение Д(1) = 0 определяет сингулярное многообразие в построенной для доказательства теоремы системе дифференциальных уравнений.

В 5-м и 6-м параграфах рассматривается задача с ограничениями в форме неравенств:

£(х) М, х е X - {х е Яп:^(х) < 0,1 = 1, ..., /}.

Основными результатами 5-го параграфа являются следующие две теоремы.

Теорема 1.6. Для того, чтобы в некоторой точке М0 е Хт = {х е Ы.§!(х) = 0,1 = 1, ..., т; ¿(х) < 0,1 = т+1, ..., /} имел место условный минимум (максимум) функции £ необходимо, чтобы в этой точке обращался в нуль определитель Грама Г векторов Vg1, ..., а

функции 1= 1, ..., т, получающиеся из функции

(Уё1)2-^ (Уё'Уё2) - (У81У8т)

0== (Ув2^1) С?ё2)2~ё2 - Уё2^ёт)

заменой строки ((У^1), О7^2), ..., - ¿, (Уё%т)) на строку

((УГУ^1), (VfVg2),...,(VfVg1),...,(VfVgm)), были в этой точке отрицательными (положительными) или имели в ней условный максимум (минимум) равный нулю.

Таким образом исходная задача может породить последовательность "вложенных" аналогичных задач. Уравнение Э = 0 определяет сингулярное многообразие в построенной для доказательства теоремы системе дифференциальных уравнений.

Достаточные условия экстремума устанавливает

Теорема 1.7. Пусть в точке Мо <е Хт обращается в нуль определитель

—, . 1 т

Грама Г векторов Уё , ..., Уё . Тогда если в точке М0 квадратичная форма в относительно миноров А; матрицы А определена положительно (отрицательно), а квадратичные формы С;, 1 = 1, ..., т, получающиеся из О заменой строки

((Ув'УО, (У^1), ..., (Ув'УД ..., (У^У§т)) на строку ((У^, (УЯ^1), (У£Уё'), (У£У§т)) относительно тех же миноров определены отрицательно, то в этой точке имеет место условный минимум (максимум) функции £

В 6-м параграфе нами рассмотрены особые случаи т = п-1иш = п. При т = п - 1 справедлива Теорема 1.8. Пусть в точке

М0 е Хт = {х € 11п:ё;(х) = 0,1 = 1, ..., п - 1; ¿(х) < 0,1 = п, ..., /} обращается в нуль определитель

Д = I

Тогда если в точке М0 определитель

Vх! >Х2 »

V х1 ,х2,... ,хп у

положителен (отрицателен) или имеет в ней условный минимум (максимум) равный нулю, а определители Д(/}, 1 = 1, ..., п - 1 получающиеся из Д(1) заменой

строки на строку (1^ ,...,), отрицательны в точке М0 или имеют

в ней условный максимум равный нулю, то в точке М0 имеет место условный минимум (максимум) функции £

При ш = п необходимые условия экстремума, сформулированные в теореме 1.6, являются и достаточными.

В параграфах 7 и 8 рассматривается общий случай - задача с ограничениями в форме равенств и неравенств:

£(х) —» ш£, хеХ={хеКп:^(х) = 0,1=1, ..., ш; ¿(х) <0,1 = т+1, ...,/}. (5) Основными результатами 7-го параграфа являются следующие две теоремы, представляющие собой обобщение теорем 1.6 и 1.7. Теорема 1.10. Для того, чтобы в некоторой точке М0 е Хт+к ={хе ^(х) = 0,1=1, ..., т+к; ¿(х) < 0, {= т+к+1, ..., /} имел место условный минимум (максимум) функции £ необходимо, чтобы в этой точке обращался в нуль определитель Грама векторов У£, Уё1, ..., Уёт+к, а функ-

ции ё;, 1 = ш+1, ..., т+к, получающиеся из функции (Уё1Уё1) ••• (У81У8т+1)

Б =

(У81У8и+к)

(У§тУ8т+к) (У§га+1УНт+к) (Уит+к)2 -ят+к

(У§тУ§1) ... (У§гаУ§т) (У§тУ§т+1) (уёт+1у§!) ... (уёт+1уёт) (У§т+1)2-Ет+1 (Уёт+ку§1) ... (У§т+кУВт) (У§т+кУ§т+1)

заменой строки ((У^1), (У^Уё2), ..., (Уё;)2 - ¿, ..., на строку

((У£У8!), (У^2), ..., (УfVgi), ..., (У1Уят+к)), были в точке М0 отрицательными (положительными) или имели в ней условный максимум (минимум) равный нулю.

Теорема 1.11. Пусть в точке М0 е Хш+к обращается в нуль определитель Грама Г векторов У£ ..., Уяш+к. Тогда если в точке М0 квадратичная форма

(УГУ£) (УГУя1) ••• (УГУёт+к) а= (У^1) ... (У81У8т+к)

(Уёт+кУ£) (Уёт+кУ81) ■■■ (Уёт+кУёт+к) относительно миноров А, т+к+1-го порядка матрицы

А =

>Х1

т+к

2

эх,

гт+к 'Х2

гт+к 'х„

определена положительно (отрицательно), а квадратичные формы ^ 1 = т+1, ..., т+к, получающиеся из О заменой строки ((У^У!}, (У81Уё1), ..., (У^У^), ..., (Уё;Уёш+к)) на строку ((У^, (У^1), ..., (У£У§;), ..., (У&ёт+к)) относительно тех же миноров определены отрицательно, то в точке Мо имеет место условный минимум (максимум) функции £

Последний параграф первой главы посвящен рассмотрению особых случаев т+к = п - 1 и т+к = п.

При т+к = п - 1 справедлива Теорема 1.12. Пусть в точке

М0 е Х„_! = {х е БГ.^х) = 0,1 = 1, п-1; ¿(х) < 0,1 = п, ..., /}

обращается в нуль определитель

Д = ]

Тогда если в точке М0 определитель

Д(1) = I

чх1 ,х2, ...,хпу

\ х1 ,х2,.. .,хп /

положителен (отрицателен) или имеет в ней условный минимум (максимум) равный нулю, а определители Д(;!), 1 = т+1, ..., п - 1, получающиеся из Д(1) заменой строки (ё^ на строку (^,...,4) отрицательны в точке М0 или

имеют в ней условный максимум равный нулю, то в точке М0 имеет место условный минимум (максимум) функции £

При т+к = п необходимые условия экстремума, сформулированные в теореме 1.10, являются и достаточными.

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

Первый параграф посвящен задачам без ограничений и с ограничениями в форме равенств.

Для решения задачи (4) предлагается система сингулярных дифференциальных уравнений

УТ Уё>

(У^) (У^1) .

х - —

гп

+-

(У§тУ0 (У§тУв') ... (УётУёт)

0 Уё' ... Уёт

Х1 / в1 (УЕЧ1) ... (Уё'УёП

С^"^1) ... (У8тУёт)

+

(6)

где %[ > 0, 1 = 1, ..., т, Г0 - определитель Грама векторов ..., Уёт, в силу ко-

торой каждое из многообразий £ = 0 достигается за конечное время. Достижению траекторией системы (6) какого-либо многообразия ё'(х) = 0 соответствует изменение ее структуры: сингулярное многообразие заменяется соответствующим регулярным устойчивым многообразием. В построенной системе многообразия ё'(х) = 0, 1 = 1, ..., ш являются притягивающими (устойчивыми). Попав на многообразие = 0 траектория остается на нем до встречи со следующим сингулярным многообразием, а затем движется по их пересечению и т.д. Выбором множителей т; возможно управление порядком достижения многообразий. Таким образом за конечное время система сингулярных дифференциальных уравнений (6) перейдет в систему регулярных дифференциальных уравнений, для которой точка минимума является экспоненциально устойчивым положением равновесия, а дискретный вариант метода локально сходится к ней со скоростью геометрической прогрессии при достаточно малом постоянном шаге интегрирования по схеме Эйлера.

Наряду с системой (6) в § 1 рассматривается система

1

х = —

ОГ

VI у%1 ... у%т

<уе1чг) (Уё1Уё1) - (Уе1ъл) (УётУ{) (Уё^Уё1) - (УётУёт)

+

+-

о

т1 /Г

ь/ё1 хт/§т

(УГУГ) (УГУё]) (Уё^) (Уё'Уё1)

уё™ (УГУёт)

(Уё'Уё1") (УётУёт)

(7)

(УётУ^ (Уё^ё1)

где х0 > -1, х; > 0, 1= 1, ..., т, траектория которой достигает точки возможного экстремума функции { за конечное время. При достижении траекто�