К решению задачи об оптимальном параметре совместности для некоторого класса уравнений в нормированном пространстве тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Ровенская, Елена Александровна

• Ровенская, Елена Александровна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Ровенская, Елена Александровна

Введение

1 Постановка задачи и алгоритм решения

1.1 Исходная и расширенная задачи.

1.2 Дополнительные условия и алгоритм решения.

1.3 Конкретизация алгоритма.

1.4 Случай оператора, не зависящего от параметра.

Введение диссертации (часть автореферата) на тему «К решению задачи об оптимальном параметре совместности для некоторого класса уравнений в нормированном пространстве»

В диеертации рассматривается оптимизационные задачи вида: р —> min, FM = Ь(р), х е Х{р), Р > РоВ задаче (1), требуется найти наименьшее значение скалярного параметра р, при котором зависящее от этого параметра уравнение F(p,x) = b(p) имеет решение в пределах заданного множества Х{р)] нахождению подлежит также само это решение. Подобные постановки возникают в разного рода прикладных задачах (задачи оптимизации сетей страховых компаний, задачи оптимизации портфелей инновационных проектов - см., напр., [85,88]), а также при исследовании параметрических семейств операторных уравнений [88]).

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

Известно, что для решения невыпуклых задач оптимизации стандартные методы, например, градиентного типа (см. [12], [55], [32], [29]) могут быть не применимы. Известен также ряд общих подходов, применимых для решения широкого класса оптимизационных задач - методы штрафных и барьерных функций (см., напр., [12], [77]); гомотопические методы (см., напр., [97]); методы стохастической оптимизации [52]). Подходы этого класса, обладая значительной общностью, сопряжены, однако, с проблемой их конструктивной реализации при решении конкретных задач.

Тип невыпуклой задачи обычно создает специфические трудности па пути обоснования конструктивных алгоритмов решения. В связи с этим развиваются специализированные подходы, ориентированные на решение; конкретных типов задач певыпуклой оптимизации (см., напр. [9G|). Для некоторых классов задач, в определенном смысле близким к выпуклым, известны итерационные алгоритмы решения, использующие операции с функцией Лагранжа (см., напр., [79], [2]). В [G7-G9] предложен подход к итерационному решению оптимизационных задач, невыпуклость которых определяется присутствием в них разностей выпуклых функций. В [3] развиваются методы оптимизации, основанные на игровых моделях.

Широко исследуемый класс задач оптимизации составляют задачи оптимального управления. Центральным инструментом анализа таких задач является принцип максимума Понтрягипа [50]. Во многих случаях он позволяет получить окончательное решение задачи либо выявить его аналитическую структуру. Все же значительное число задач оптимального управления находятся за пределами сферы эффективного применения принципа максимума Понтрягипа. К числу таких задач относятся, прежде всего, задачи оптимального управления с фазовыми (а также смешанными) ограничениями: для них принцип максимума Понтрягипа имеет усложненную форму и трудно поддается аналитическому исследованию в конкретных ситуациях. Другой универсальный подход к решению задач оптимального управления, в том числе, с фазовыми ограничениями, объединяет метод динамического программирования [8], [11], [18], [21,22], [30,37], [05] и его обобщения (численная реализация этих методов сопряжена, вообще говоря, с большими размерностями вычислений). Большая серия работ посвящена изучению корректных дискретных аппроксимаций, позволяющих получать приближенные решения задач оптимального управления посредством решения конечномерных задач математического программирования (см. [70], [13], [48]). В [94], [57[ - [03] развиваются методы, ориентированные на решение различных типов задач оптимального управления.

Многие задачи оптимизации, как известно, некорректны: малые; возмущения их данных могут вести к большим отклонениям решений |12|. Построение методов регуляризации оптимизационных задач - нахождения их устойчивых приближенных решений на основании возмущенных данных - составляет обширный раздел теории некорректных задач [71], [20[, [45], |1,4|, |9|, [?, 12,15,10], [20|, [23], [24|, [28|, [31], [44|, [50], [51[, [01], [72,73[.

Материал настоящей диссертации примыкает к работам [38| - |43|, |82|

- [93], развивающим методы решения обратных задач динамики и задач оптимизации исходя из регуляризации известного в теории позиционного управления принципа экстремального сдвига H.H. Красовского [35]. Задача (1) ранее рассматривалась в [40,87,90], где, в предположении что функция F(p,x) линейна по аргументу х, построен основанный на принципе экстремального сдвига итерационный метод ее решения, указано его приложение к решению линейной задачи быстродействия с фазовыми ограничениями и приведен соответствующий регуляризирующий алгоритм.

В данной работе функция F(p,x) полагается, вообще говоря, нелинейной, но удовлетворяющей ряду ограничений, наиболее существенным из которых выступает условие выпуклости множеств F(p, Х(р)). Последнее условие позволяет путем подходящей рандомизации аргумента (см. [89|) сконструировать вспомогательную оптимизционную задачу с линейным ограничением-равенством, в определенном смысле эквивалентную задаче (1). Для вспомогательной задачи строится итерационный метод решения, обобщаяющий метод, ранее предложенный в [91], и устанавливается сходимость генерируемой им последовательности к решению исходной задачи (1). Предложенный метод конкретизируете применительно к некоторым частным случаям, включающим задачи оптимального управления со смешанными ограничениями. В конце работы конструируется связанный с этим методом регуляризирующий алгоритм.

В главе I рассматривается задача оптимизации вида (1) в нормированном пространстве X. В разделе 1.1 на нес накладываются такие основные требования, как требования непрерывности многозначного отображения р н-> Х(р) и функций р I—> b(p), {р,х) и-> F(p,x), а также требование того, что функция (р, х) н-> F(p,x) — Ь(р) является компактифнкатором (см. [89]) (условия (AI) - (A3)). При данных условиях устанавливается существование решения задачи (1) (следствие 1.1).

Далее накладывается упомянутое выше требование выпуклости множеств F(p,X(p)) (р > Pq) (условие (A4)) и строится расширенная задача оптимизации в пространстве вероятностных мер, являющихся выпуклыми комбинациями точечных мер Дирака: т т г=1 г=1

При этом носителем данных мер для каждого р > ро является множество Х(р). При сделанных предположениях полученная расширенная задача оказывается задачей выпуклого программирования.

В разделе 1.2 вводится ряд дополнительных предположений (условия (А5) - (А9)) и, с использованием эквивалентности исходной и расширенной задач, обосновывается основной алгоритм решения. Раздел 1.3 посвящен упрощению основного алгоритма.

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

В главе II рассматриваются приложения предложенного в главе I алгоритма к решению двух задач оптимального управления с фазовыми ограничениями.

В разделе 2.1 рассматривается задача быстродействия для п-мерной дифференциальной управляемой системы

1) = 1{*Ш) + 9Ш,1)и(Ь), (2) функционирующей на отрезке времени [0,Т] (Т > 0), из заданного начального состояния г° е Яп в заданное; конечное состояние г1 € Вп при смешанном геометрическом ограничении (¿(¿), ?/(£)) 6 (£ £ [0,Т]) па фазовую переменную и т - мерную управляющую переменную м(£).

В разделе 2.1.1 формулируются требования непрерывности функций /(•, •), /;(•, •) и замкнутозначности, выпуклозпачпости и ограниченности многозначного измеримого отображения $(•), гарантирующие существование решения поставленной задачи быстродействия (теорема 2.1).

Теоремы существования, учитывающие специфику конкретных классов задач оптимизации, приведены в |10|. |19|. [33], [34], [00]. [70]. [78|.

Далее исходная задача быстродействия сводится к задаче вида (1) в нормированном пространстве X = Ь2{[0, Т], В!1) х Ь\([О, Т], Ят), где Ь\([О, Т], Ят) - иространтство 1/2([0,Т], Я"1), снабженное слабой нормой (см., напр., [10]). На рассматриваемую управляемую систему накладывается дополнительное требование выпуклозначности образов С?) (р б [0,Т]), где - интегральный оператор системы (2), С - множество управляемых процессов (г(-), «(•)), удовлетворяющих смешанному ограничению (г(£),и(£)) б (*е[0 ,Т]).

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

Разделе 2.1.2 посвящен строгому обоснованию возможности применения общего метода к решению задачи быстродействия для системы (2) и его конкретизация.

В разделе 2.1.3 описан пример приложения указанного метода к решению задачи быстродействия для модели динамики одноногого прыгающего робота в фазе полета [95|. Приведены результаты численного эксперимента.

Раздел 2.2 посвящен приложению общего алгоритма, описанного в главе I, к задаче оптимизации смешанных ограничений для п-мериой дифференциальной управляемой системы (2). В этом разделе предполагается, что фазовая переменная и ш - мерная управляющая переменная м(£) удовлетворяют фазовому ограничению, зависящему от скалярного параметра р> Ро : 0 (1е[0,Т},р>р0).

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

В разделе 2.2.1 формулируются требования непрерывности функций /(■, •), /;(-,•) и многозначной функции (?(•,£) (£ б [0,Т]); измеримости многозначной функции С,}(р, •) (р>Ро)ш, требования замкнутозначности, выпуклозначности и ограниченности многозначного отображения (?(•,•): такжо требование монотонного возрастания многозначной функции р н-» С}(рЛ) для всех t G [0,Т]. При указанных предположениях доказывается существование решения рассматриваемой задачи оптимизации (теорема 2.5). Далее исходная задача вновь сводится к задаче вида (1) в нормированном пространстве X = Ь2([0,Т], Rn) х L2W([О,Т],Rm). На рассматриваемую управляемую систему накладывается дополнительное требование выпуклозначности образов F(p,X(p)) (р G [О, Г]), где F(-, •) - интегральный оператор системы (2), Х(р) - множество управляемых процессов (z(-), и(-)), удовлетворяющих смешанному ограничению (z(t),u(t)) G Q{p,t) (t G [0,T]).

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

Раздел 2.2.2 посвящен строгому обоснованию возможности применения общего метода к решению задачи оптимизации смешанного ограничения для системы (2) и его конкретизация.

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

В главе III задача (1) рассматривается при неточных входных данных F(-, •), b(-) и Х(-), отклоняющихся от неизвестных точных данных не больше, чем па заданные известные величины погрешностей.

Для падежного решения неустойчивых задач строится регуляризирую-щий оператор (регуляризирующий алгоритм) [71], [5]. Все методы решения неустойчивых задач так или иначе предполагают наличие какой-нибудь априорной информации о рассматриваемой задаче, о ее входных данных и их погрешностях и т.д. Различные аспекты проблемы использования априорной информации обсуждаются, например, в [17], [4G], [71,74]. Методы регуляризации для решения неустойчивых задач включают в себя метод стабилизации (метод стабилизирующих функционалов), разработанный А.Н. Тихоновым [71]; метод невязки [20|, |49|, [74]; метод квазирешений [2G], [71| и их многочисленные модификации.

Корректность задач оптимального управления при возмущениях пачального состояния рассматриваются в [98], [100]. Эти результаты получены как приложение абстрактной теории, развитой в [99].

В разделе 3.1 при некоторых предположениях, касающихся неизвестных точных входных данных (а именно, предположения непрерывности функций &(')> многозначного отображения Х(-), а также предположения о том, что F(•, •) — Ь(-) - компактпфикатор), предлагается регуляризирующий алгоритм решения задачи (1) с возмущенными входными данными Ь(-) и Х(-). Данный алгоритм включает в себя необходимость решать релаксиро-ванную задачу, сконструированную по исходной задаче (1).

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

Основные результаты диссертации:

1. Предложен итерационный метод поиска наименьшего значения скалярного параметра, при котором зависящее от этого параметра уравнение в нормированном пространстве имеет решение в заданном множестве, которое, вообще говоря, также зависит от параметра. Метод основан на идее метода экстремального сдвига Н. Н. Красовского. Доказана сходимость метода.

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

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

Основные результаты диссертации опубликованы в работах [101] - [105].

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

Список литературы диссертационного исследования кандидат физико-математических наук Ровенская, Елена Александровна, 2006 год

1. Антипин A.C. Метод регуляризации в задачах выпуклого программирования.// Экономика и математические методы. 1975. т. 11. К0- 2. С. 336342.

2. Антипин A.C. Методы нелинейного программирования, основанные на приямой и двойственной модификации функции Лагранжа. М.: Изд. ВНИИСИ. 1979.

3. Антипин A.C., Васильев Ф.П. Методы регуляризации для решения задач равновесного программирования с сдвоенными ограничениями. Журнал вычислительной математики и математической физики. 2005. т. 45. 1. С. 23-37.

4. Антипин A.C. Об едином подходе к методам решения некорректных экстремальных задач.// Вестник Московского Университета. Серия 1. Математика и механика. 1973. № 2. С. 60-67.

5. Бакупшнский A.B., Гончарский A.B. Некорректные задачи. Чмсленные методы и приложения. М.: Издательство МГУ. 1989.

6. Бахвалов Н.С. Численные методы. М.: Наука. 1973.

7. Беллман Р. Динамическое программирование. М.: ИЛ. 1960.

8. Гурман В.И. Принцип расширения в задачах управления. М.: Физмат-лит. 1997.

9. Денисов Д.В. Метод итеративной регуляризации в задачах условной минимизации.// Журнал Вычислительной Математики и Математической Физики. 1978. т. 18. Л* С. С. 1405-1415.

10. Дикусар В.В. Регуляризация вырожденной задачи оптимального управления.// Дифференциальные уравнения. 1998. т. 34. № 11. С. 1850-1865.

11. Жиглявский A.A. Математическая теория глобального случайного поиска. JL: Издательство ЛГУ. 1985.

12. Иванов В.К., Васин В.В., Танана В.П. Теория линейных некорректных задач и ее приложения. М.: Наука. 1978.

13. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М.: Наука. 1979.

14. Ишмухаметов А.З. Вопросы устойчивости и аппроксимации задач оптимального управления. М.: Издательство ВЦ РАН. 2000.

15. Ишмухаметов А.З. Методы решения задач оптимизации. М.: Издательство МЭИ. 1998.

16. Канторович JI.B., Акилов Г.П. Функциональный анализ. М.: Наука. 1984.

17. Калашников АЛ. Порядковая регуляризация некорректной задачи оптимального управления.// В сборнике: Дифференциальные и интегральные уравнения. Вып. 2. Горький: Изд. Горьковского Университета. 1978. С. 124-129.

18. Карманов В.Г. Математическое программирование. М.: Физматлит. 2000.

19. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука. 1976.34| Корнейчук Н.П. Экстремальные задачи теории приближения. М.: Наука. 1976.

20. Красовский H.H., Субботин А.И. Позиционные дифференциальные игры. М.: Наука. 1974.

21. Кротов В.Ф., Букрсев В.З., Гурман В.И. Новые методы вариационного исчисления в динамике полета. М.: Машиностроение. 1969.

22. Кротов В.Ф., Гурман В.И. Методы и задачи оптимального управления. М.: Наука. 1973.

23. Кряжимский A.B., Осипов Ю.С. Об одном алгоритмическом критерии разрешимости игровых задач для линейных управляемых систем. // Тр. Ин-та матем. механ. УрО РАН. 2000. т. 6. № 1. С. 2-10.

24. Кряжимский A.B., Осипов Ю.С. Экстремальные задачи с отделимыми графиками.// Кибсрн. сист. анал. 2002. No 2. С. 32-55.

25. Кряжимский A.B., Пащенко C.B. К решению линейной задачи быстродействия со смешанными ограничениями.// ВИНИТИ. Итоги пауки и техники. Сер. Современная математика и ее приложения. 2002. т. 90. С. 232-260.

26. Потапов М.М. Апрокснмация экстремальных задач в математической физике (гиперболические уравнения). М.: Издательство МГУ. 1985.

27. Потапов M.M. Метод прямых в задачах граничного управления и наблюдения для гиперболического уравнения с краевыми условиями второго и третьего рода. // Вестник МГУ. Серия 15, вычислительная математика и кибернетика. 1990. № 2. С. 35-41.

28. Потапов М.М. О сильной сходимости разностных аппроксимаций для задач граничного управления и наблюдения для волнового уравнения.// Журнал вычислительной математики и математической физики. 1998. т. 38. № 3. С. 387-397.

29. Потапов М.М. Об апроксимации но функционалу максиминных задач со связанными переменными, для систем Гурса-Дарбу при наличии фазовых ограничений.// Журнал вычислительной математики и математической физики. 1979. т. 19. № 3. С. 610-G21.

30. Потапов М.М., Раз гул и н А.В., Шамеева Т.Ю. Аппроксимация и регуляризация задачи оптимального управления для уравнения типа Шре-дингера.// Вестник МГУ. Серия 15, вычислительная математика и кибернетика. 1987. № 1. С. 8-13.

31. Пшеничный Б.Н. Необходимые условия экстремума. М.: Наука. 1982.

32. Роитенберг Я.Н. Автоматическое управление. М.: Наука. 1978.

33. Стрскаловский А.С. Элементы задач иевыпуклой оптимизации. Новосибирск: Наука. 2003.

34. Тихомиров В.М. Некоторые вопросы теории приближений. М.: Издательство МГУ. 1976.

35. Тихонов А.Н., Арсении В.Я. Методы решения некорректных задач. М.: Наука. 1986.

36. Тихонов А.Н., Васильев Ф.П. Методы решения некорректных экстремальных задач.// В книге: Banacli Center Publications. Vol. 3. Mathematical Models and Numerical Methods. Warshawa. 1978. pp. 297342.

37. Тихонов A.H., Васильев Ф.П., Потапов M.M., Юрий А.Д. О регуляризации задач минимизации на множествах, заданных приближенно.// Вестник МГУ. Серия 15, вычислительная математика и кибернетика. 1977. № 1. С. 4-19.

38. Тихонов А.Н., Леонов А.С., Я гол а А.Г. Нелинейные некорректные задачи. М.: Наука. 1995.|75. Треиогин В.А. Функциональный анализ. М.: Наука. 1980.

39. Федореико Р.П. Приближенное решение задач оптимального управления. М.: Наука. 1978.|77| Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной оптимизации. М.: Мир. 1972.

40. Филиппов А.Ф. О некоторых вопросах оптимального регулирования.// Вестник МГУ. Серия 1, математика и механика. 1959. № 2. С. 25-38.

41. Экланд И., Темам Р. Выпуклый анализ и вариационные проблемы. М.: Мир. 1979.

42. Kryazhimsky A., Watanabe Cli. Optimization of Technological growth. Gendaitosho. 2004.

43. Kryazhimsky A.V., Osipov Yu.S. Inverse Problems of Ordinary Differential Equations: Dynamical Solutions. Gordon and Beach. London. 1995.

44. Kryazhimsky A.V., Ermoliev Yu.M., Ruszczynski A. Constraint aggregation principle in convex optimization. // Mathematical Programming. Series B. 1997. Vol. 76. pp. 353-372.

45. Kryazhimsky A.V., Ruszczynski A. Constraint aggregation in infinite-dimensional spaces and applications.// International Institute for Applied Systems Analysis. Laxenburg. Austria. IR-97-051. 1997.

46. Kryazhimsky A.V., Digas B.V., Ermoliev Yu.M. Guaranteed optimization in insurance of catastrophic risks. // International Institute for Applied Systems Analysis. Laxenburg. Austria. IR--98-082. 1998.

47. Kryazhimsky A.V. Convex optimization via feedbacks. // SIAM Journal Control Optimization. 1999. Vol. 37. No 1. pp. 278-302.

48. Kryazhimsky A.V. Optimization problems with convex epigraphs. Application to optimal control. // Inteniatioanl Journal of Applied Mathematics and Computer Science. 2001. Vol. 11. No 4. pp. 101-129.

49. Kryazhimsky A.V., Ruszczynski A. Constraint aggregation in infinite-dimensional spaces and applications. // Math. Operat. Research. 2001. Vol. 2G. No 4. pp. 769-795.

50. Kryazhimskii A.V., Paschenko S.V. On the problem of optimal compatibility. J. Inv. Ill-Posed Problems. 2001. Vol. 9. No 3. pp. 283-300.

51. Matveev A.S. Yakubovich V.A. Nonconvex problems of global optimization.// St.Peterburg Mathematical Journal. 1993. Vol. 4. № 6. pp. 1217-1243.

52. Murray R.M., Li Z., Sastry S.S. A Mathematical Introduction to Robotic Manipulation. CRC Press. 1994.

53. Yakubovich V.A. Nonconvex optimization problems: The infinite-horizon linear-quadratic constraints.// Syst. and Contr. Lett. 1992. Vol. 16. pp. 1322.

54. Zangwill W.I., Garcia C.B. Pathways to Solutions, Fixed Points and Equilibria. Englewood Cliffs: Prentice Hall. 1981.

55. Zolezzi T. Well-posedness of optimal control problems.// Control and Cybernetics. 1994. Vol. 23. pp. 289-301.

56. Zolezzi T. Well-posedness critaria in optimization with application to the calculus of variation. // Nonlinear Analysis, Theory, Methodology and Application. 1995. Vol. 25. pp. 437-453.

57. Zolezzi T. Extended wellposedness of optimal control problems.// Discrete and Continuous Dynamic Systems. 1995. Vol. 1. pp. 547-553.

58. Ровепская E.A. К решению задачи об оптимальном параметре совместности для одного класса уравнений в банаховом пространстве. Журнал вычислительной математики и математической физики. 2004. т. 44. № 12. С. 2150-2166.

59. Ровепская Е.А. К решению задачи быстродействия с фазовыми ограничениями для простейшей модели прыгающего одноногого робота. Сборник "Нелинейная динамика и управление". М.: Изд. МГУ. 2005. К0- 5.

60. Ровепская Е.А. О задаче оптимизации фазового ограничения для линейной управляемой системы. Математические модели в экономике и экологии: Материалы научного семинара. М.: МАКС Пресс. 2004. С. 7578.