Введение к работе
Актуальность темы. Задача поиска экстремума полиномиальной функции при возможных ограничениях в виде полиномиальных неравенств известна своей важностью для приложений, будь то теория оптимального управления или задача распознавания образов. Её теоретическая сложность проявляется уже в частных случаях задач линейного или выпуклого программирования.
Традиционно используемые для решения задач нелинейной оптимизации итерационные методы имеют тот недостаток, что гарантируют сходимость к стационарной точке лишь при выборе достаточно близкого к ней начального приближения. Кроме того, эти методы малоэффективны для анализа поведения экстремума при вариации параметров, содержащихся в целевой функции.
В последние десятилетия альтернативу числепвым составили методы символьные, позволяющие, например, свести с помощью элементарных операций решение системы алгебраических уравнений от нескольких неизвестных к решению одного уравнения от одного неизвестного. Широко используется для этой цели аппарат базисов Грёбнера, часто в комбинации с результатами классической теории исключения. Перспективность их применения обусловлена достаточным развитием вычислительной техники и систем аналитических вычислений таких как Maple, Mathematica, Reduce, находящих широкое применение в самых различных областях науки и техники.
Цель и задачи исследования. Диссертация посвящена разработке конструктивных символьных (аналитических) алгоритмов решения задачи полиномиальной оптимизации общего вида. Перед диссертантом были поставлены следующие задачи:
-
разработать многомерный аналог системы полиномов Штурма для локализации решений систем полиномиальных уравнений;
-
построить аналитический алгоритм решения задачи многомерной полиномиальной оптимизации путём сведении ее к задаче локализации корней полинома в одномерном случае.
Научная новизна работы. Разработан символьный метод решения общей задачи полиномиального программирования. Основываясь на
точных методах определения числа корней полинома в некоторой алгебраической области, удаётся свести исходную задачу к одномерному случаю. Это существенно упрощает численные расчёты и позволяет провести качественные параметрический анализ задачи.
Практическая значимость работы. Практическая ценность результатов диссертации характеризуется тем, что разработанные в ней методы, алгоритмы и рекомендации изначально ориентированы на решение проблем реализуемости математического аппарата на базе общедоступных вычислительных средств типа персональных компьютеров.
Предлагаемые соискателем аналитические алгоритмы решения задачи полиномиальной оптимизации достаточно универсальны, т.е. применимы как для функций общего положения, так и для некоторых исключительных по своей природе случаев.
Методика исследования и программы, разработанные соискателем, будучи использованными на этапе качественного исследования математической модели объекта, позволяют:
-
обеспечить достоверность информации, полученной применением различных вычислительных схем;
-
существенно повысить эффективность и качество выполняемых расчетов;
-
проанализировать поведение объекта в зависимости от параметров.
Кроме того, с их помощью можно генерировать достаточно сложные тестовые примеры для проверки сходимости разрабатываемых численных или численно-аналитических алгоритмов и отладки программ.
Апробация работы. Основные результаты диссертации докладывались на конференциях: CSAM'93 по компьютерным системам и прикладной математике (С.-Петербург, 1993), Interval'94 по интервальным и компьютерно-алгебраическим методам (С.-Петербург, 1994) и Понтрягинской (Москва, 1998); на семинарах: исследовательского института по символьным вычислениям (RJSC, Линц, Австрия), PoSSo-95 (г.Ираклио, Греция, 1995), по компьютерной алгебре ПО-МИ им.Стеклова РАН, а также на 11-ой международной Байкальской
школе-семинаре "Оптимизационные методы и их приложения"(Иркутск, 1998).
Работа была поддержана грантами Соросовского Аспиранта-Стипендиата за 1997 и 2000 гг.
Публикации. По материалам диссертации опубликовано 7 печатных работ.
Объем и структура работы. Диссертационная работа состоит из введения, двух глав, содержащих основные результаты, иллюстрируемые численными примерами, и заключения. Работа изложена на 114 страницах; список цитируемой литературы включает 53 наименования.
Похожие диссертации на Алгебраический метод нахождения экстремума полиномиальной функции
