Алгебраический метод нахождения экстремума полиномиальной функции тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Черкасов, Тимофей Михайлович

• Черкасов, Тимофей Михайлович
• кандидат физико-математических наук
• 2000

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

Список обозначений и сокращений

Введение.

Глава 1. Экстремум полинома одной переменной.

§1.1. Вычисление характеристик ганкелевой матрицы

§1.2. Результант и субрезультанты

§1.3. Отделение решений в случае одной переменной

§1.4. Чувствительность значений корней

§1.5. Формула Маркова

§1.6. Нахождение максимума полинома одной переменной

Глава 2. Экстремум полинома нескольких переменных

§2.1. Многомерный результант по Пуассону

§2.2. Отделение решений в случае двз?х переменных

§2.3. Вычисление симметрических функций решений

§2.4. Метод Эрмита для двух переменных

§2.5. Результант трех полиномов двух переменных

§2.6. Метод Эрмита для трех и более переменных

§2.7. Условия знакоопределенности формы

§2.8. Нахождение максимума полинома нескольких переменных

§2.9. Условный максимум

Введение диссертации (часть автореферата) на тему «Алгебраический метод нахождения экстремума полиномиальной функции»

Задача нахождения глобального экстремума полиномиальной функции Р{х) е ж[Х],Х = (х\,. ,х£) (Е шь является типичной задачей невыпуклого нелинейного программирования. Актуальность этой задачи известна: она возникает и в теории оптимального управления и в задаче распознавания образов [2], [3], [19]. Сложность нахождения её гарантированно точного решения общего вида существенно ограничивает круг применимого математического аппарата. Действительно, при такой общей постановке неизбежен анализ стационарных точек целевой функции, тоесть вещественных нулей системы уравнений:

РР0/&Е1 = 0,. .,дР(Х)/дхь = 0 (1)

Уже установление точного числа этих нулей представляет затруднения. Но даже если предположить, что возможна локализация конкретного нуля, то нахождение его приближения с наперёд заданной точностью не всегда гарантированно численными методами, например, аналогичными методу Ньютона. Последний очень чувствителен как к выбору начального приближения, так и к возмущениям в коэффициентах системы (в нашем случае, функции Г(Х)). Эти недостатки численных методов известны уже в одномерном случае [22], не говоря уже о многомерном.

От этих недостатков свободны так назывемые символьные или аналитические методы, принципиальные отличия которых от численных заключаются в следующем:

• в процессе вычислений допускается использование только рациональных чисел и целых рациональных функций с символьными коэффициентами;

• результат (качественный или количественный) должен достигаться за конечное число элементарных алгебраических операций.

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

Целью диссертационного исследования является именно создание конструктивного символьного алгоритма поиска глобального экстремума, реализуемого на базе современных пакетов компьютерной алгебры. При этом критерием нахождения экстремума будет являться его локализация с заданной точностью (допуском) е, тоесть указание такого интервала ]а, 6[, b — а < е при рациональных а и 6, которому искомый экстремум принадлежит.

Основная идея предлагаемого в диссертации подхода заключается в сведении многомерной задачи поиска решений системы уравнений (1) к одномерной задаче локализации критических значений целевой функции. Принципиальным является тот факт, что при целевой функции из q[X] её критические значения оказываются алгебраическими числами, тоесть являются корнями некоторого полинома с целыми коэффициентами. И первой нашей задачей будет являться поиск указанного полинома. Формальное определение этого полинома можно дать следующим образом. Обозначим

Ai,.,Ajv}, Лj е сь набор нулей системы уравнений (1), тоесть все нули этой системы с учетом их кратностей. Обозначим

T{z) := (z - FÍA,)) F(Л«)) (2)

Тогда полином J~{z) и является искомым. Для конструктивного его вычисления требуется, однако, определить его коэффициенты, тоесть, фактически вычислить некоторые функции нулей системы уравнений (1). Принципиальным является тот факт, что коэффициенты полинома T{z\ как, впрочем, и сам полином, являются симметрическими полиномами от нулей системы. Основополагающим результатом классической высшей алгебры, установленным в трудах крупнейших математиков XIX века — Гаусса, Пуассона, Якоби и Шлэфли — является тот, что значение любого симметрического полинома на нулях системы уравнений 0 (3) является целой рациональной функцией коэффициентов системы. В частности, для задачи полиномиальной оптимизации это означает, что при Р(Х) £ будет выполнено и включение Т{г) е

Методы вычисления симметрических функций нулей системы (3) были также разработаны в XIX веке — кроме упомянутых математиков ещё и Лиувиллем и фон Эшерихом (в статье [51] приведён краткий исторический обзор результатов, полученных в XIX веке). Область классической алгебры, которая включала в качестве составной части теорию симметрических функций нулей системы полиномиальных уравнений, называлась теорией исключения. Это название указывает на сущность теории: её целью ставилась разработка методов исключения переменных, тоесть преобразования системы (3) к эквивалентной (имеющей тот же набор решений) системе вида

XI - Фх(жь) = 0, — ,хЬ-Х - Фь-1(хь) = О, Фь{хь) = 0 (4) при рациональных Ф^ и выяснения условий осуществимости такого преобразования. Основным рабочим инструментом теории является многомерный результант, формально определяемый для полиномов Fl(X) ,. и С(Х), с^ (7 = т равенством

К°х{х) №(Х),. := Д^ЛО . С{Ам) . (5)

Здесь {Л1,., Адг} — набор нулей системы (3), а Л0 — некоторая величина, полиномиально зависящая от коэффициентов старших форм в разложениях полиномов ^(Х),., ^(Х) по убывающим степеням переменных. В смысле этого определения, функция введенная формулой (2), является (с точностью до целочисленного множителя) именно результантом:

Т(г) = П^ПХ) (дЕ(Х)/дхи ., дР{Х)/дхь) .

Являясь симметрическим полиномом нулей системы уравнений, результант должен рационально выражаться через коэффициенты полиномов этой системы. Практические способы вычисления результанта были также разработаны в XIX и начале XX века в трудах Кэли, Сильвестра, Диксона, Маколея и других ученых [33]. Все они были связаны с представлением результанта в детерминантном виде, тоесть в виде определителей элементами которых являлись либо непосредственно коэффициенты полиномов ., (7, либо некоторые рациональные функции этих коэффициентов.

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

На сегодняшний день исследователи вооружены целым арсеналом вычислительных систем, работающих на любых типах компьютеров. Обзоры и примеры работы с некоторыми из них можно найти в книгах [5] и [12]. Математический фундамент построения подобных систем освещён в [14] а вопросы практического применения — в [37].

При разработке указанных систем была произведена ревизия классических, а также разработка новых алгоритмов преобразования систем полиномиальных уравнений. Из таких новых алгоритмов в первую очередь следует назвать конструктивный метод построения базисов Грёб-нера идеала, порождаемого полиномами . Основы этого метода были заложены в работах Бухбергера и его последователей [5], [31] . Для полиномов общего положения при лексикографическом упорядочении мономов х\ у Х2 У . У хь базис будет иметь вид: хг - Ф1(хь),., хь-1 - Фь-\(х£), Фь(хь)} при полиномиальных Ф^, что и позволяет привести систему уравнений (3) к эквивалентной системе (4). Однако, несмотря на теоретическую обоснованность метода, его применение к практическим задачам не всегда приводило к успеху. Основной трудностью оказалась его вычислительная непредсказуемость: когда время счета конкретной системы могло оказаться невероятно большим, хотя отличие её от системы решаемой тем же методом за считанные минуты заключалось буквально в одном мономе. В этом смысле классические методы исключения переменых в полиномиальной системе являются более предсказуемыми — особенно с точки зрения оценки влияния параметров, входящих в коэффициенты системы. Поэтому в последнее десятилетие производятся попытки симбиоза детерминантных подходов к исключению с методом базисов Грёбнера, при этом на долю последнего выпадает менее трудоемкая задача определения структуры определителя.

Возвращаясь к разделу полиномиальной оптимизации, упомянем обзор [30], по применению символьных подходов для решения задач этой области по состоянию на 1992 год. Приведём некоторые ключевые ссылки из этого обзора. Задача поиска конечного глобального максимума полиномиальной функции может рассматриватся как задача элиминации (исключения) кванторов теории вещественных чисел первого порядка:

3^0 (уХ е шь(Г(Х) - г0 < 0) Л ЗХ0 € = Р(Х0))) .

Тарский [9] доказал алгебраическую разрешимость задач такого вида, однако приведённое им доказательство неконструктивно, тоесть на его основе нельзя построить вычислительный алгоритм. В работах H.H. Воробьёва, Д.Ю.Григорьева и др. [7],[10] была проведена оценка сложности вычислений в алгебре Тарского, но разработанные этими авторами алгоритмы также оказались малопригодными для расчетов реальных задач. С вычислительной точки зрения более конструктивным оказался предложенный Коллинзом и разработанный его коллегами и учениками метод цилиндрического алгебраического разложения [38]. Последний, фактически, заключался в сведении оптимизационной задачи к задаче определения совместности системы неравенств от переменной zq, путём последовательного исключения переменных с помощью одномерного результанта.

Здесь мы вплотную сталкиваемся с ещё одной задачей, напрямую связанной с системой уравнений (3). В предположении вещественности всех коэффициентов полиномов Fj(X), было бы желательно локализовать (отделить) вещественные нули этой системы: тоесть, во-первых, указать, сколько из этих нулей будет вещественными, и, во-вторых, установить их точное число в произвольном параллелипипеде (боксе) Oj < Xj < bj (j = 1 ,.,L). Алгебраическая разрешимость этой задачи в одномерном случае (L = 1) известна из любого учебника по высшей алгебре [20] — это метод построения системы полиномов Штурма с помощью алгоритма Евклида. Оказывается, что и для многомерного случая можно построить аналог системы Штурма. Конструктивный метод был предложен в 1852-56 гг. Эрмитом [42] и, после долгого забвения, был возрождён в последнее десятилетие [26], [32], [48], [51], [52]. Метод основан на анализе индексов инерции матрицы квадратичной формы n n 2

EG(A3) Т.У1ЫА,)

6) рассматриваемой относительно переменных уь ., уы- Здесь {Ч?¿(Х)}^=1 — множество определённым образом подобранных мономов. При выборе = 1 сигнатура квадратичной формы (6) будет равна числу различных вещественных нулей системы уравнений (3); тогда при произвольной функции индексы инерции квадратичной формы (6) позволят нам установить число вещественных нулей в области > 0. Конструктивность метода Эрмита состоит в том, что элементы матрицы квадратичной формы (6) являются симметрическими полиномами нулей системы (3), и, следовательно, по уже упоминавшемуся выше результату Шлэфли, должны быть рационально выражаемыми через коэффициенты полиномов системы.

Метод Эрмита позволяет сформулировать задачу локализации абсолютного максимума целевой функции Р{Х) как задачу отделения вещественных корней полинома Именно, поставим целью установление числа стационарных точек полинома -Р(Х) (вещественных нулей системы (1)) в области к1", определяемой неравенством Р(Х) > г; здесь 2 считается вещественным параметром. Матрица квадратичной формы (6), соответствующей этой задаче, будет иметь элементами полиномиальные функции по г, а определитель — равным Т{х) с точностью до числового сомножителя из о. Главные же миноры этой матрицы и служат системой полиномов Штурма для Т{г)\ число вещественных нулей полинома Т{г) на интервале а < г < 6, как правило, равно разности между числами знакопостоянств в ряду этих главных миноров (поставленных по возрастанию их порядков, начиная с нулевого, равного 1) при подстановке в этот ряд границ рассматриваемого интервала. Подстановкой рациональных чисел, представляющих концы последовательности вложенных интервалов, мы можем построить сколь угодно точное рациональное приближение произвольного вещественного корня Как правило, максимальный из этих корней и даёт значение максимума целевой функции.

В предыдущем абзаце неявно предполалось, что искомый максимум .Р(Х) является конечным, тоесть достигается именно в стационарной точке. Очевидно, что это предположение будет выполнено не для всех Р(Х). Оно будет выполнено если старшая форма в разложении -Р(Х) по убывающим степеням переменных является отрицательно определенной. В случае когда с^ Г = 2 это условие легко проверяется с помощью критерия Сильвестра, но при с^ ^ > 2 до последнего времени был исследован лишь случай Ь — 2 переменных. Оказывается, что задача определения необходимых и достаточных условий знакоопределённости формы от Ь переменных в терминах коэффициентов этой формы является алгебраически разрешимой; а конструктивный метод проверки этих условий можно переформулировать как подходящую задачу полиномиальной оптимизации функции от Ь — 1 переменного. Таким образом, получается рекурсивный метод решения задачи полиномиальной оптимизации: когда условия конечности максимума функции от Ь переменных формулируются как условия отрицательности максимума другой функции от Ь — 1 переменной.

Последней задачей, которую требуется нам решить после локализации гтах = тах^(Х), является восстановление координат стационарной точки, соответствующей этому критическому значению. В случае, когда тах^(Х) достигается лишь в одной стационарной точке, такое восстановление может быть произведено с помощью формул аналогичных (4). Именно, значения соответствующих координат оказываются рациональными функциями от 2"гаах. Конструктивное построение указанных функций возможно с помощью миноров матрицы квадратичной формы (6), построенной для системы (1) при подходящем выборе функции в{Х).

Обобщая вышеизложенное, сформулируем основные цели диссертационного исследования:

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

• определение условий знакоопределённости формы от Ь > 2 переменных;

• построение аналога системы полиномов Штурма для локализации абсолютного максимума полиномиальной функции;

• восстановление координат стационарной точки, соответствующей тахР(Х).

Изложение теоретических основ приведенного алгоритма будет построено на основе рекурсии по размерности пространства области определения. Мы ограничиваемся случаями Ь = 1,2 переменных1; они излагаются в главах с соответствующими номерами.

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

1. Получено конструктивное развитие метода Эрмита: разработан многомерный аналог системы полиномов Штурма для локализации решений систем полиномиальных уравнений.

2. Предложен новый метод исключения переменных в системе уравнений (3), основанный на построении подходящей блочно-ганкелевой матрицы.

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

Теоретические основы для Ь > 2 переменных усложняются несущественно, но резко возрастают проблемы, связанные с ресурсоёмкостью вычислительных средств

Для решения одномерной задачи и исследования особенностей работы алгоритма диссертантом разработан пакет программ в системе аналитических вычислений Reduce 3.3. Предоставлена возможность производить рассчёты с символьными параметрами в выражениях коэффициентов исследуемых функций.

Для случая L = 2 переменных теоретические результаты проиллюстрированы примерами, просчитанными с помощью вспомогательных процедур, написанных диссертантом для системы аналитических вычислений Maple V Release 5. С их помощью становится возможным решение задач, для которых стандартные функции системы не применимы — например, в случае области определения, заданной полиномиальным неравенством.

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

• случай достижимости max.F(X) в более чем одной стационарной точке;

• случай, когда maxF(X) не совпадает с максимальным вещественным корнем F{z)\

• случай, когда старшая форма в разложении F(X) неположительна, но, в то же время, не является отрицательно определённой.

Методика исследования и программы, разработанные соискателем, будучи примененными на этапе качественного исследования математической модели объекта, позволяют:

1. обеспечить достоверность информации, полученной применением различных вычислительных схем;

2. существенно повысить эффективность и качество выполняемых расчетов;

3. проанализировать поведение объекта в зависимости от параметров.

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

Диссертация в целом, а также ее отдельные разделы докладывались на конференциях: CSAM'93 по компьютерным системам и прикладной математике (С.-Петербург, 1993), Interval'94 по интервальным и компьютерно-алгебраическим методам (С.-Петербург, 1994) и Понтрягинс-кой (Москва, 1998); на семинарах исследовательского института по символьным вычислениям (RISC, Линц, Австрия), на открытом семинаре PoSSo-95 (г. Ираклио, Греция); на 11-ой международной Байкальской школе-семинаре "Оптимизационные методы и их приложения"(Иркутск, 1998); а также на семинарах кафедры математического моделирования энергетических систем Санкт-Петербургского государственного университета.

Диссертационная работа состоит из введения, двух глав, содержащих основные результаты, иллюстрируемые численными примерами, и заключения. Работа изложена на 114 страницах; список цитируемой литературы включает 53 наименования. Основное содержание диссертации отражено в семи опубликованных работах.

Заключение диссертации по теме «Вычислительная математика», Черкасов, Тимофей Михайлович

ЗАКЛЮЧЕНИЕ

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

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

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

3. Разработана техника построения аналитических критериев знакоопределенности полинома.

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

Из анализа проведенных теоретических исследований вытекают следующие практические рекомендации:

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

- 109 разбить параметрическое пространство "сеткой", получаемой вычислением определителя при частных значениях этих параметров, тем более, что этот процесс легко распараллелить.

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

3. При решении задачи поиска максимума в области, описываемой системой полиномиальных неравенств, не следует проводить предварительного исследования ни системы условий на совместность, ни самой целевой функции на наличие максимума на бесконечности. Предложенный алгоритм позволит проверить второе из этих условий автоматически — в ходе проверки условий применимости метода Эрмита. Непустота допустимого множества выяснится в ходе нахождения условного экстремума целевой функции на потенциальных граничных многообразиях этого множества. Проверка условия достижимости максимума в нескольких стационарных точках должна также производиться лишь тогда, когда за достаточное число подстановок не удается отделить критические значения.