Сингулярные дифференциальные уравнения в задачах оптимизации тема автореферата и диссертации по математике, 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, ..., т, траектория которой достигает точки возможного экстремума функции { за конечное время. При достижении траекто�