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

• Тарасова, Виктория Валерьевна
• кандидат физико-математических наук
• 2005

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

Введение.

1. Задача минимаксного управления и условия разрешимости.

1.1. Оптимальная стабилизация линейных управляемых систем при полной информации о координатах состояния.

1.2. Оптимальная стабилизация линейных управляемых систем при неполной информации о координатах состояния.

1.3. Задача минимаксного управления.

1.4. Применение условий разрешимости при решении задачи минимаксного управления.

2. Метод Яхаджи.

3. Применение методов оптимизации к решению задачи минимаксного управления.

3.1. Субдифференциал выпуклой функции. Различные обобщения понятия субдифференциала.

3.2. Метод обобщенного градиентного спуска.

3.3. Квазидифференцируемые функции и их свойства.

3.4. Свойства функции Лп (6{М).

3.5. Решение задачи минимаксного управления методами наискорейшего спуска и квазиньютоновским методом.

3.6. Решение задачи минимаксного управления методами негладкого анализа.

3.6. Анализ практических расчетов.

4. Субдифференциал максимального собственного числа симметричной матрицы.

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

Задача аналитического конструирования регуляторов (АКР) при ограничении на состав измеряемых и используемых для целей управления координат состояния объекта имеет несомненное прикладпое значение. Общий подход к решению задачи АКР развит в работах В. И. Зубова [18, 19], Р. Калмана [66], Н. Н. Красовского [24], А. М. Летова [26] и др. В главе 1 рассматривается общая задача оптимальной стабилизации линейных управляемых систем при полной и неполной информации о координатах состояния. Рассматривается управляемая динамическая система X F(t) X Q{t) и, х(/о) лГд, для t>tQ, где x-x{t). системы; UER Здесь xeR" вектор координат состояния вектор управления; t время, t некоторый P{t), Q{t) матрицы фиксированный начальный момент времени; размеров (nxn) и (пхг) соответственно. Предполагается, что элементы матриц Р я Q являются непрерывными, ограниченными функциями, заданными при всех t>tg.B стационарном случае обычно полагают tQ=O, что не ограничивает общности изложения. В случае постановки задачи неполной информации измеряется не сам вектор X координат состояния объекта, а так называемый вектор выходов системы управления у eR, связанный с вектором х линейным соотношением у Нх. Здесь Н матрица размера (к х п) максимального ранга, причем к <п. Управление задают в виде где М (г X«)-матрица, а ее элементы являются вещественными, непрерывными, ограниченными функциями, заданными при всех t>tH такие, что нулевое решение замкнутой системы экспоненциально устойчиво. Стабилизирующие свойства управления, а также его качество, оценивают, используя интегральный квадратичный критерий качества где /ц- некоторый фиксированный начальный момент времени, A{t),C(t) симметричные матрицы размеров (пхп) и (гхг) соответственно с непрерывными, ограниченными элементами, причем C{t) положительно определенная матрица для всех Управление, ttt. наименьшее возможное значение доставляющее функционалу, называется оптимальным управлением. Задача оптимизации, описанная в главе 1, известна как проблема "аналитического конструирования регулятора (АКР) В главе 1 приводятся теоремы о существования решения в задаче АКР в случае полной и неполной информации о состоянии объекта, а также метод построения оптимального управления. Однако условия данных теорем в прикладных задачах накладывает порой слишком жесткие ограничения, что влечет за собой необходимость вносить изменения в формулировку изучаемой проблемы. Далее рассматривается минимаксный подход к решению задачи АКР в стационарном случае, а также условия разрешимости поставленной задачи. Задача АКР в ее минимаксной формулировке рассматривалась в работах К Мышкова [29, 31], Т. Яхаджи [64, 65] и др. При формулировке задачи минимаксного управления в стационарном случае допустимое управление задают в виде и My МНх, где ueR,у ELR\X&R" и М матрица (гхи) такая, что нулевое решение замкнутой системы экспоненциально функционалом устойчиво, качество стабилизации оценивается =1 где J{U,XQ)= {хАх и и 0 9{М) симметричная матрица, являющаяся решением уравнения Ляпунова При формулировке задачи оптимизация функционала J{u) минимаксного управления показано: означает минимизацию наибольшего собственного числа Я,, {в) матрицы в. Далее сформулированы необходимые и достаточные условия суп1:ествования решения задачи минимаксного управления и показано, что при применении их в обш,ем случае возникают значительные затруднения уже в слзае п 2. Но так как оптимизируемый функционал имеет специальный вид, то для решения минимаксной задачи стабилизации предлагается использовать численные методы решения минимаксных задач обш;его вида. В главе 2 рассматривается метод Яхаджи [64, 65] поиска минимаксного решения задачи АКР. Приводится как оригинальный, так и модифицированный метод Яхаджи. Приводятся теоремы, показываюп],ие сходимость метода Яхаджи. Также в главе 2 рассматриваются примеры практического применения данного метода для решения задачи минимаксного управления. В приложениях к главе 2 представлены результаты расчетов.При решении поставленной задачи также возникает вопрос о рассмотрении вопросов устойчивости замкнутой системы управления. Вопросы устойчивости широко изучены в работах Ляпунова [27]. Автором диссертации предлагается решать вопрос о допустимости матрицы М посредством критерия Рауса-Гурвица, так как рассматриваемая система стационарна. Однако численный метод Яхаджи является эффективным при решении задачи минимаксного управления только в случае некратности максимального собственного значения матрицы 9 на каждом шаге метода. Таким образом, остается открытым вопрос о решении поставленной задачи в случае, когда на каком-либо из шагов кратность максимального собственного числа Я,, (6*) не равна единице. В главе 3 предлагается использование классических методов минимизации для решения задачи минимаксного управления. Приводятся формулировки метода наискорейшего спуска и квазиньютоновского метода, теоремы о сходимости. Данные методы есть методы минимизации непрерывно дифференцируемых функций. При решении задачи минимаксного управления с использованием как метода наискорейшего спуска, так и квазиньютоновского метода, функция /1„(6(М)) рассматривается как функция /1ДМ). Функция /i,,(-) непрерывно дифференцируема на каждом шаге также только в случае, когда кратность /l(MJ) равна единице. При использовании метода наискорейшего спуска в качестве направления спуска на к-тош шаге выбирается антиградиент -/1,(М.), который предлагается рассчитывать, используя любые известные методы, например, аппарат конечных разностей. Схема квазиньютоновского метода совпадает со схемой метода наискорейшего спуска, но направление спуска выбирается следуюш;им образом: Вид матрицы Нк указан в главе 3. При применении описанных методов минимизации на каждом шаге встает вопрос решения задачи одномерной минимизации, так как где а, доставляет min/l,, (Af). Задачу одномерной минимизации можно решать любым известным методом. В приведенных в работе расчетах задача одномерной минимизации решается методом золотого сечения. Таким образом, применение данных методов возможно также только в случае некратных собственных чисел. В этой главе также рассмотрено практическое использование методов для решения поставленной задачи, в приложении приведены результаты расчетов. Отметим, что при решении численных задач минимаксного управления с одинаковыми условиями методом Яхаджи и методом наискорейшего спуска (или квазиньютоновского метода) наиболее эффективным оказался метод Яхаджи. При практическом применении всех методов, описанных выше, необходима проверка кратности Я„(6(М.)) на каждом шаге. Однако преимущество классических методов минимизации в том, что они тесно связаны в идейном плане с методами негладкого анализа, описанными далее в главе 3, которые позволяют решать задачу минимаксного управления в случае кратных собственных значений. Обп],ность классических методов и методов негладкого анализа позволяет упростить программные продукты для решения задачи минимаксного управления. Задачи минимизации или максимизации негладких функций изучены в работах Демьянова В.Ф. и Малоземова В.П [12, 13, 14, 15], Пшеничного Б.Н. [40, 41, 42, 43] и т.д. В главе 3 приведены элементы негладкого анализа, которые необходимы нам для понимания использования методов минимизации негладких функций. Отдельно выпуклость рассмотрены Я{0), свойства функции в(М) ЯДб(М)). Показана в области Гурвица, дифференцируемость непрерывность и субдифференцируемость Д,(М). Отмеченные свойства необходимы для дальнейшего развития методов решения задачи минимаксного управления и для обоснования сходимости данных методов к решению поставленной задачи. В работах Шора П.З. [55] и Баженова Л.Г. [5] исследуется метод минимизации почти-дифференцируемых функций. Параграф 3.5 главы 3 посвяш;ен применению метода минимизации почти-дифференцируемых функций к решению задачи минимаксного управления. Сформулированы определения почти-дифференцируемых функций, почти-градиента. В этом же параграфе формулируется метод минимизации почти- дифференцируемых функций и условия сходимости. Показано, что в случае, если кратность /1„(6(М.)) не равна единице на каком-либо шаге, функция /1„(М) является почти-дифференцируемой в точке М.. Таким образом, применение численного метода минимизации ПДФ-функций правомерно при решении задачи минимаксного управления Паправление спуска на А:- том шаге выбирается следующим образом: WSx и g (Mj.) некоторый почти-градиент функции Я„ (М) в точке М.. Применение метода минимизации ПДФ-функций не требует на каждом шаге решения задачи одномерной минимизации, так как сходимость данного метода доказана в случае, когда шаг выбирается из условия а, +0, 1.1, а, +С0.работах по негладкому анализу широко изучены субдифференциальные методы решения минимаксных задач. Известно, что в случае, когда функция субдифференцируема, почти-градиент совпадает с субградиентом функции. Так как функция Я,, {М,.) субдифференцируема, то в качестве направления спуска в методе минимизации почти- дифференцируемых функций можем использовать любой известный субградиент 1,(М) или использовать методы субдифференциального исчисления. Также в главе 3 предлагается использовать для решения поставленной задачи субградиентный метод с почти полной релаксацией, так как все методы, упомянутые выше, не являются релаксационными, а данная особенность метода дает суш;ественные преимущества при практическом применении. Отличительной особенностью субградиентных методов является их простота, вследствии того, что на каждом шаге требуется лишь найти какой-нибудь субградиент. Однако суш;ественным недостатком этих методов является их медленная сходимость. Преодоление этого недостатка также изучено в книге В. Ф. Демьянова и Л. В. Васильева. [13] и рассмотрено в текуш;ей главе. При применение субградиентного метода к решению задачи минимаксного управления шаговый множитель а может быть выбран несколькими способами. В зависимости от способа выбора последовательности а,. указанный субградиентный метод обладает теми или иными свойствами. Численные примеры применения данного метода к решению нашей задачи таюке рассмотрены в главе 3. Результаты расчетов приведены в приложении. Как было отмечено выше, использование субградиентного метода позволяет решать поставленную задачу и в слзае, когда кратность /1„(6(М.)) не равна единице на каком-либо шаге. В главе 4 рассмотрены результаты вычисления субдифференциала максимального собственного числа произвольной симметричной матрицы, полученные в работе А. Льюиса и Ж-Б. Ириа Урути. [59]. Авторами получено аналитическое выражение субдифференциала. Данное выражение имеет большое теоретическое значение, однако использование его при решении задачи минимаксного управления, для поиска субдифференциала \{в{М)) представляется затруднительным. В главе 4 также приведено выражение производной по направлению максимального собственного числа произвольной симметричной матрицы. Задача поиска субдифференциала или субградиента функции A,,(6(MJ) при численной реализации методов не рассматривается автором подробно. Однако следует отметить, что задача поиска субдифференциала или субградиента произвольной функции в точке широко изучена в работах В. Ф. Демьянова и продолжает развитие на кафедре математической теории моделирования систем управления, факультета прикладной математики процессов управления Санкт-Петербургского государственного университета. Итак, методы, предложенные для решения задачи минимаксного управления в случае кратных собственных чисел, есть методы негладкой оптимизации, которые являются обобш;ением методов первого порядка для гладких функций. Таким образом, использование и тех и других методов в комплексе позволяет разработать поставленной задачи в обш;ем случае. Основными результатами, которые получены в итоге исследований и выносятся на защиту, являются: 1) Исследованы свойства функции \{в{МУ), которые впоследствии численный аппарат для решения позволяют предложить метод решения ноставленной задачи в общем 2) Обосновано использование методов негладкого анализа для решения поставленной задачи. 3) Исследовано численное применение упомянутых выше методов, осуществлена программная реализация методов в среде MATEMATICA 3.0, представлены результаты расчетов.СПИСОК_ЛИТЕРАТУРЫ содержит перечень работ, использованных при написании диссертации, а также монографии и обзоры, в которых можно найти подробные списки работ, касающихся обсуждаемых вопросов. Диссертация в целом, а также ее отдельные положения и полученные результаты докладывались на XXXII научной конференции «Процессы управления и устойчивость» факультета прикладной математики процессов управления (г. Санкт-Петербург, апрель 2001 г.), XXXIII научной конференции «Процессы управления и устойчивость» факультета прикладной математики процессов управления (г. Санкт-Петербург, апрель 2002 г.), XXXIV научной конференции «Процессы управления и устойчивость» факультета прикладной математики процессов управления (г. Санкт-Петербург, апрель 2003 г.), XXXV «Процессы управления и устойчивость» научной конференции прикладной факультета математики- процессов управления (г. Санкт-Петербург, апрель 2004 г.), XIII международной конференции. «Проблемы теоретической кибернетики (г.Казань, 2002 г.), а также неоднократно докладывались на научном семинаре на кафедре математической теории моделирования систем управления факультета прикладной математики- процессов управления Санкт-Петербургского государственного университета.

Список литературы диссертационного исследования кандидат физико-математических наук Тарасова, Виктория Валерьевна, 2005 год

1. Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптимальное управление. М., Наука, 1979.432 с.

2. Амбросенок (Тарасова) В.В. К вопросу о минимаксном решении задачи аналитического конструирования регуляторов. // Труды XXXII конференции студентов и аспирантов. Процессы управления и устойчивость. ООП НИИ Химии СПбГУ. 2001. С.14-17.

3. Амбросенок (Тарасова) В.В. К вопросу об использовании квазидифференциального подхода к решению минимаксной задачи управления. // Труды XXXIII конференции студентов и аспирантов. «Процессы управления и устойчивость». ООП НИИ Химии СПбГУ. 2002. С.16-18.

4. Амбросенок (Тарасова) В.В. К вопросу о решении задачи минимаксного управления// .Труды XXXIV конференции студентов и аспирантов. «Процессы управления и устойчивость». Из-во СПбУ. 2003. С. 13-18.

5. Баженов А.Г. Об условиях сходимости метода минимизации почти-дифференцируемых функций // Кибернетика. 1972. № 4. С.71-72.

6. Барбашин Е.А. Введение в теорию устойчивости. М., Наука, 1967. 223 с.

7. Васильев Ф.П. Лекции по методам решения экстремальных задач. М., Изд-во Московского университета. 1974. 374 с.

8. Габасов Р.Н., Кириллова Ф.М. Методы оптимизации. Л., Изд-во ЛГУ, 1975. 279 с.

9. Гантмахер Ф.Р. Теория матриц. М., Наука, 1966. 576 с.

10. Гирсанов И.В. Лекции по математической теории экстремальных задач. М, Изд-во МГУ, 1970. 118 с.11 .Демидович Б.П. Лекции по математической теории устойчивости. М., Наука, 1967. 472 с.

11. Демьянов В.Ф. Условия экстремума и вариационные задачи. СПб., ООП НИИ Химии СпбГУ, 2000. 136 с.

12. Демьянов В.Ф., Васильев JI.B. Недифференцируемая оптимизация. М., Наука, 1981. 383 с.

13. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М., Наука, 1972. 368 с.

14. Демьянов В.Ф., Рубинов A.M. Основы негладкого анализа и квазидифференциальное исчисление. М., Наука, 1990. 431 с.

15. Демьянов В.Ф., Рубинов A.M. Приближенные методы решений экстремальных задач. JL, Изд-во ЛГУ, 1968. 180 с.

16. Ермольев Ю.М. Методы стохастического программирования. М., Наука, 1976. 192 с.

17. Зубов В.И. Лекции по теории управления. М., Наука, 1975. 496 с.

18. Зубов В.И. Теория оптимального управления. Л., Судостроение, 1966. 352 с.

19. Зубов В.И. Устойчивость движения. М., Высшая школа, 1984. 232 с.

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

21. Карманов В.Г. Математическое программирование. М., Наука, 1980. 256 с.

22. Кларк Ф. Оптимизация и негладкий анализ. М., Наука, 1988. 280 с.

23. Красовский Н.Н. Теория управления движением. Линейные системы. М, Наука, 1968.475 с.

24. Кусраев А.Г., Кутателадзе С. С. Субдифференциальное исчисление. Новосибирск, Наука, 1987. 383 с.

25. Летов A.M. Математическая теория процессов управления. М., Наука, 1981. 256 с.

26. Ляпунов A.M. Общая задача об устойчивости движения. М., Гостехиздат, 1950. 472 с.

27. Моисеев Н.Н. Элементы теории оптимальных систем. М., Наука, 1975. 528 с.

28. Мышков С.К. Линейные управляемые системы с неполной информацией о координатах состояния. // Негладкие задачи теории оптимизации и управления, под. ред. Демьянова В.Ф. Л., Изд-во ЛГУ. 1982. С 248-272.

29. Мышков С.К. Оптимальная в среднем стабилизация линейных управляемых систем // Вестник ЛГУ. 1971. №7 С. 90-97.

30. Мышков С.К. Условия разрешимости задачи оптимальной в среднем стабилизации линейных управляемых систем с неполной информацией // Вопросы механики и процессов управления, под ред. В.В. Новожилова. Л., Изд-во ЛГУ. 1978. № 2. С. 148-157.

31. Мышков С.К, Амбросенок (Тарасова) В.В. К вопросу о решении задачи минимаксного управления // Тезисы докладов XIII международной конф. «Проблемы теоретической кибернетики». Казань. 2002. С. 19-21.

32. ПолакБ.Т. Введение в оптимизацию. М., Наука, 1983. 384 с.

33. Полякова Л.Н. Метод точных штрафных функций. СПб., ООП НИИ Химии СПбГУ, 2001. 38 с.

34. Полякова Л.Н. Методические указания к курсу «Негладкий анализ». Тема: Квазидифференцируемые множества. СПб., ООП НИИ Химии СпбГУ, 2001.26 с.

35. Полякова Л.Н. Необходимые условия экстремума квазидифференцируемых функций // Вестник Ленингр. ун-та. 1980. № 13. С.57-62.

36. Полякова Л.Н. Об одной задаче негладкой оптимизации // Кибернетика. 1982. №2. С.119-122.

37. Полякова JI.H. Учебно-методическое пособие по решению задач выпуклого анализа. СПб., ООП НИИ Химии СпбГУ, 2004. 36 с.

38. Понтрягин А.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М., Наука, 1969. 384 с.

39. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М., Наука, 1990. 320 с.

40. Пшеничный Б.Н. Необходимые условия экстремума. М., Наука, 1969. 151 с.

41. Пшеничный Б.Н. О необходимых условиях экстремума для негладких функций // Кибернетика. 1977. № 6. С.92-96.АЪ.Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М., Наука, 1975. 320 с.

42. Рокафеллар Р. Выпуклый анализ. М., Наука, 1973. 472 с.

43. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М., Наука, 1986.325 с.

44. Тарасова В.В. К вопросу о решении задачи минимаксного управления// Депонирована в ВИНИТИ №647 от 20.04.2004.

45. Тарасова В.В. Некоторые методы решения задачи минимаксного управления// Труды XXXV конференции студентов и аспирантов. «Процессы управления и устойчивость». Из-во СПбУ. 2004. С.113-121.

46. Уилкинсон Д.Х. Алгебраическая проблема собственных' значений. М., Наука, 1970. 564 с.

47. Фадеев Д.К. Лекции по алгебре. М., Наука, 1984. 416 с.

48. Фадеев Д.К., Фадеева В.Н. Вычислительные методы линейной алгебры. М., Физматгиз, 1960. 656 с.

49. Федоров В.В. Численные методы максимина. М., Наука, 1979. 278 с.

50. Чатаев Н.Г. Устойчивость движения. М., Наука, 1990. 176 с.

51. Шор Н.З. Использование операции растяжения пространства в задачах минимизации выпуклых функций// Кибернетика. Киев. Наукова Думка, 1970, № 1. С.6-12.

52. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. К., Наукова думка, 1979. 199 с.

53. Шор Н.З. О классе почти-дифференцируемых функций и одном методе минимизации функций этого класса// Кибернетика. Киев.: Наукова Думка, 1972, № 4. С.65-70.

54. Элъсголъц JI.3. Дифференциальные уравнения и вариационное исчисление. М., Наука, 1969. 424 с.

55. Bhatia R. Perturbation bounds for the matrix eigenvalue. Research Notes in Mathematics 162. Pitman Publishers, 1987

56. Hiriart-Uruty J.-B. From convex optimization to nonconvex optimization // Nonsmooth Optimization and Related Topics, Clarke F.H., Demyanov V.F., Giannessi F. Eds., Plenum Press, 1989. P. 219-239.

57. Hiriart-Uruty J.-B, Lewis A.S. The Clarke and Michel-Penot subdifferentials of the eigenvalues of symmetric matrix // Computational Optimization and Applications. 1998. N 13. P. 13-23.

58. Hiriart-Uruty J.-B., Seeger A., Ye D. Sensitivity analysis for a class of convex functions defined over a space of symmetric matrices // Lecture Notes in economics and mathematical systems. 1992. P. 133-154.

59. Lewis A.S., Overton M.L. Eigenvalue optimization// Acta. Numerica. 1996. vol. 5, P. 149-190.

60. Overton M. On minimizing the maximum eigenvalue of a symmetric matrix. // SIAM J. Matrix. Anal. Appl. 1988. vol. 9, P. 256-268.

61. Seeger A. An external problem involving matricial quadratic forms. // Rev. Mat. Apl. 1990. vol. 11, P. 117-132.

62. Yahagi Т. Design of optimal output feedback control systems. // International Journal Control. 1973. vol. 18, N 4. P. 839-848.

63. Yahagi T. Minimax output feedback regulators. // Journal of Dynamic Systems, Measurement, and Control. 1976. vol. 98, N 3. P. 270-276.вв.Калман P., Фалб. П., Арбиб M., Очерки по математической теории систем. М., Мир, 1971. 400 с.