Подробности
28.01.2010 12:08
Страница 14 из 19

 

 

Невыпуклые задачи глобальной оптимизации

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

Задачи глобальной оптимизации традиционно считаются весьма трудными. Интерес к упомянутому классу задач объясняется не только его практической значимостью, но также неожиданно открывшейся возможностью эффективного решения. Последнее во многом связано с успехами классической линейно-квадратичной теории оптимального управления. Эта теория, основы которой были заложены исследованиями Р.Калмана, Н.Н.Красовского и А.М.Летова (а в части, касающейся стохастических объектов, исследованиями А.Н.Колмогорова, М.Г.Крейна, Н.Винера, Р.С.Бьюси), включает разнообразные задачи оптимального управления, сводимые к минимизации выпуклого квадратичного функционала на аффинном пространстве. Значительный вклад в ее развитие внесли Я.К.Виллемс, В.И.Зубов, В.М.Кунцевич, А.Б.Куржанский, Ж.Л.Лионс, А.И.Лурье, В.И.Уткин, Е.Хопф и многие другие ученые. Методически эта область имеет важные связи с комплексным анализом, теорией устойчивости, стабилизации и оптимизации нелинейных динамических систем. В первую очередь это касается неопределенных систем (uncertain systems), т.е. систем, полная информация о которых отсутствует. Начиная с конца 60-х годов поток научных публикаций, относящихся к обсуждаемой области, принял лавинообразный характер; заметный интерес к ней сохранился до настоящего времени. Общеизвестно и практическое значение линейно-квадратичной теории оптимального управления.

Для большинства тех ситуаций, где возникают линейно-квадратичные задачи оптимального управления, значительный интерес представляют и аналогичные задачи с квадратичными ограничениями, вообще говоря, невыпуклыми. Такие ограничения часто дают возможность более точно учитывать возникающие на практике требования и тем самым лучше отражают существо проблемы. Вместе с тем теория соответствующих задач, сравнимая по эффективности предлагаемых ею методов решения с классической линейно-квадратичной теорией, долгое время отсутствовала. Это не случайно, так как внесение в постановку задачи квадратичных ограничений принципиально усложняет ситуацию. Усложнение объясняется, в частности, тем, что в результате возникает, вообще говоря, невыпуклая задача глобальной оптимизации. В общем случае такие задачи, как правило, с трудом поддаются решению. Соответствующим проблемам в последнее время уделяется много внимания. Отметим вместе с тем, что известные методы невыпуклой глобальной оптимизации в основной массе являются численными, часто основаны на эвристических идеях и не всегда сопровождаются гарантией сходимости. Более того, известно, что проблема построения универсального сходящегося метода невыпуклой глобальной оптимизации в определенном смысле неразрешима в принципе.

В [115, 116] было показано, что для некоторых невыпуклых линейно-квадратичных задач оптимального управления с квадратичными ограничениями соответствующие трудности эффективно преодолеваются. Более того, был предложен [115-117] общий метод, позволяющий строить эффективные алгоритмы решения упомянутых задач на базе классической линейно-квадратичной теории оптимального управления. Эти алгоритмы строго математически обоснованы, во многих случаях сводятся к вычислениям по явным формулам и гарантированно приводят к нахождению глобального оптимума. Новые случаи применимости этого метода были найдены в [118-122].

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

Общим критериям применимости метода и его приложениям посвящены исследования [115-128]. За цикл работ по абстрактной теории оптимального управления в 1997 году В.А.Якубовичу и А.С.Матвееву была присуждена премия Санкт-Петербургского Университета.

В 2000 году опубликована книга "Control Theory. Twenty -Five Seminal Papers (1932-1981)", в которой представлены 25 статей, оказавших по мнению специальной международной комиссии наибольшее влияние на развитие теории управления в 20-м столетии. В ней имеется одна из статей В.А. Якубовича.