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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ рр^ ОД

1 9 ИЮН

На правах рукописи

ЧЕРКАСОВ Тимофей Михайлович

АЛГЕБРАИЧЕСКИЙ МЕТОД НАХОЖДЕНИЯ ЭКСТРЕМУМА ПОЛИНОМИАЛЬНОЙ ФУНКЦИИ

Специальность: 01.01.07 Вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

С анкт- П е тер бург 2000

Работа выполнена в Санкт-Петербургском государственном университете.

Научный руководитель: доктор физико-математических наук,

доцент А.Ю. Утешев

Официальные оппоненты: доктор физико-математических наук,

доцент С.Н. Андрианов доктор физико-математических наук, профессор В.Ф. Зайцев

Ведущая организация: Институт Систем Энергетики им.

Л.А.Мелентьева, СО РАН (Иркутск)

Защита диссертации состоится " 2-8 " Ьи-ОиЛ 2000 г. в ^ У часов на заседании диссертационного совета К-063.57.16 по защите диссертаций на соискание ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: Санкт-Петербург, Васильевский остров, 10 линия, дом 33, ауд.66.

С диссертацией можно ознакомиться в научной библиотеке им. A.M. Горького Санкт-Петербургского государственного университета.

Автореферат разослан слииО 2000 г.

Ученый секретарь диссертационного совета,

д.ф.-м.н. В.Ф. Горьковой

¿-/¿¿г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задача поиска экстремума полиномиальной функции при возможных ограничениях в виде полиномиальных неравенств известна своей важностью для приложений, будь то теория оптимального управления или задача распознавания образов. Её теоретическая сложность проявляется уже в частных случаях задач линейного или выпуклого программирования.

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

В последние десятилетия альтернативу числепвым составили методы символьные, позволяющие, например, свести с помощью элементарных операций решение системы алгебраических уравнений от нескольких неизвестных к решению одного уравнения от одного неизвестного. Широко используется для этой цели аппарат базисов Грёбнера, часто в комбинации с результатами классической теории исключения. Перспективность их применения обусловлена достаточным развитием вычислительной техники и систем аналитических вычислений таких как Maple, Mathematica, Reduce, находящих широкое применение в самых различных областях науки и техники.

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

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

2. построить аналитический алгоритм решения задачи многомерной полиномиальной оптимизации путём сведении ее к задаче локализации корней полинома в одномерном случае.

Научная новизна работы. Разработан символьный метод решения общей задачи полиномиального программирования. Основываясь на

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались на конференциях: СЭАМ'ЭЗ по компьютерным системам и прикладной математике (С.-Петербург, 1993), 1п1сг\-аГ94 по интервальным и компьютерно-алгебраическим методам (С.-Петербург, 1994) и Понтрягинской (Москва, 1998); на семинарах: исследовательского института по символьным вычислениям (ШБС, Линц, Австрия), РоЗБо-Об (г.Ираклио, Греция, 1995), по компьютерной алгебре ПО-МИ им.Стеклова РАН, а также на 11-ой международной Байкальской

школе-семинаре "Оптимизационные методы и их приложения"(Иркутск, 1998).

Работа была поддержана грантами Соросовского Аспиранта-Стипендиата за 1997 и 2000 гг.

Публикации. По материалам диссертации опубликовано 7 печатных работ.

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

СОДЕРЖАНИЕ РАБОТЫ

Традиционный подход к поиску экстремума полинома Р(А') £ X = . .,хь) заключается в исследовании стационарных точек, т.е. вещественных нулей системы уравнений:

¡дхг = 0,..., дР{Х)¡дхь = 0 . (1)

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

Основная идея предлагаемого в диссертации подхода заключается в сведении многомерной задачи поиска решений системы уравнений (1) к одномерной задаче локализации критических значений целевой функции. Принципиальным является тот факт, что при целевой функции из а[Х] её критические значения оказываются алгебраическими числами, т.е. являются корнями некоторого полинома с целыми коэффициентами. Первой задачей, решаемой в диссертации, является поиск этого полинома, формальное определение которого можно дать следующим образом. Обозначим {Л1,..., Лд-}, Лу 6 С1 набор нулей

системы уравнений (1), т.е. все нули этой системы с учетом их крат-ностей. Обозначим:

. (2)

Тогда полином и является искомым. Для конструктивного вычисления требуется, однако, определить его коэффициенты, т.е. фактически вычислить некоторые функции нулей системы уравнений (1). Принципиальным является тот факт, что коэффициенты полинома как, впрочем, и сам полином, являются симметрическими полиномами от нулей системы. Основополагающим результатом классической высшей алгебры, установленным в трудах крупнейших математиков XIX века — Гаусса, Пуассона, Якоби и Шлэфли — является тот, что значение любого симметрического полинома на нулях системы уравнений:

= 0 (3)

является целой рациональной функцией коэффициентов системы. Одним из таких полиномов является результант полиномов Р\(Х),..., Р[,(Х) и С(Х), т.е. функция вида

отвечающая за условие существования общих нулей системы (3) и уравнения О(Х) = 0. Очевидно, что:

ад = (аг(х)/дхи...,дг(х)/дх^ ,

и при Р(Х) 6 будет выполнено и включение € о[г].

В диссертации даётся конструктивное развитие одного из способов вычисления значений симметрических полиномов на нулях системы (3), восходящего к работам Якоби. Этот способ позволяет не только вычислить полином (2), но и применить для локализации его нулей (т.е. критических значений целевой функции) метод Эрмита. Изложение материала построено на основе рекурсии по размерности пространства области определения.

Первая глава содержит обзор классических результатов по установлению взаимного расположения корней полиномов /(ж) и д(х) от одной переменной: начиная с понятий результанта ?£(/,<?) , дискриминанта £>(/), субрезультантов и кончая способом локализации корней

полинома f{x), основанным на результатах Якоби, Эрмита, Сильвестра и Кронекера. Рассматриваются три ганкелевые матрицы:

S = Н = С = [снк}^1()1 (4)

элементы которых вычисляются по рекуррентным формулам, как коэффициенты рядов Лорана:

г. ■

1 j=о ^ i=o ' j=o

Они являются значениями определенных симметрических рациональных функций от корней Ах,...,Ап полинома f(x), (например, Sj известен как j-я сумма Ньютона: Sj = Aj Ч-----1- Ht)- Сигнатура матрицы S

оказывается равной числу различных вещественных корней полинома f(x), а по индексам инерции матриц С или Н вычисляется количество вещественных корней f(x), удовлетворяющих условию д(х) = 0 или д{х) > 0 (последнее обозначается nrr{/(x) = 0 j д(х) > 0}). Все упомянутые величины устанавливаются посредством нахождения чисел знакопостоянств Р и знакоперемен V в рядах главных миноров Sj,Hj,Cj соответствующих матриц.

Сформулируем теперь задачу локализации max F(x) для F(x) — А0хп -I-----H An, при /1о < 0 и n чётном, как задачу поиска числа:

nrr{F'(x) = 0 | х > z} .

Теорема 1 . Если матрицы (4) построить для выбора }{х) := F'{x), g{x) := F{X) ~ z, то

Hn-i{z) = Sn^{F(Aj) - z) ■ ■ ■ (F(Xn-i) - *) = Sn-{D(F(x) - z) ,

а при выполнении условий \ ф 0,0(Jr(z)) ф 0 справедливо:

nrr{F'(x) = 0} = nrr{J?(z) = 0} ,

пгг{^"(2) = 0 | a < z < 6} = nrr{F'(x) - 0 | a < F(x) <b} = = Р(1,Я1(а),...,Я„-1(а)) - Р(1,ВД,. - .,Нп^(Ь)) . (5)

Здесь Ai,..., An_i — корни F'[x).

Эта теорема утверждает, что последовательность Н\{г)}.Нп-\{г) фактически играет роль системы полиномов Штурма для задачи локализации корней Отделив с её помощью критические значения функции .Р(ж), в том числе и тахР(х), мы можем, при необходимости, восстановить и соответствующую стационарную точку по формуле:

(п - 1)Ах

пАо

Ь,\ Лг

Ьп-2 К-1

К-г К-ъ

Ь<1п-6

Нп-2

(6)

В диссертации производится анализ существенности условий теоремы 1. Например, условием 1Э{Т{г)) ф 0 пренебречь нельзя, т.к. при его нарушении число вещественных стационарных точек и вещественных критических значений могут оказаться различными. Так, для Р{х) — —х6 — 135а:2 — 324ж максимальный вещественный корень Т{£) равен 540, но он не даёт истинного значения тах.Р, т.к. соответствует паре мнимых корней Р'(х): А^г = (—3 + г\/15)/2. Тем не менее разность (5) оказывается достаточно "умной", чтобы локализовать истинное значение шах Р даже в случае одинаковых критических значений функции. Дополнительный анализ условия ^(А^) = -Р(Л^) привёл к следующему результату.

Теорема 2 . Имеем:

V{Г{z)) = Т[С(Р')]3Ф2(А0,..., .

Здесь Т — константа, зависящая от т, а Ф — форма степени 3(п - 2)(п - 3)/2. Установлено, что Ф = 1 дляп = 3, Ф = , Р")/Аа дляп = 4, и Ф = и(Б[Р"']2 - 6Р'ГЩ/А1'п для п = 5,6.

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

Р(Х) = ¿ЦХ) + ^(Х) + • • • + Р0

(7)

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

случае, сформулируем проблему локализации шах Р(Х) как задачу нахождения числа вещественных нулей (пгг) системы в заданной алгебраической области:

пи{(1) | Р(Х) - г > 0} .

Решать её будем с помощью обобщения метода Эрмита в и£. Для определения числа вещественных нулей системы (3) и количества тех из них, что удовлетворяют условию в(Х) = 0 или в(Х) > 0 (последнее обозначается пгя{(3) | С(х) > 0}), составим три блочно-ганкелевые матрицы 5, Н и С порядка N х N при N := щ • ••п£, щ Так,

например, для Ь — 3:

5 := [^ачх] к , := « '

а — обобщённые суммы Ньютона:

N

вллл := ]С а?Рр~(р > ЛР :г= (аг» ъ) ■ р-1

По аналогии составляются и матрицы Я и С из элементов:

р=1 р=1 *

соответственно. Здесь J{X) — якобиан полиномов Р3{Х).

Поскольку элементы матриц 8,Н и С являются рациональными симметрическими функциями нулей системы (3), они должны рационально выражаться через коэффициенты полиномов Р^(Х). Для их конструктивного вычисления в диссертации используется метод Яко-би. Тогда, по знакам главных миноров матриц 5 и Н, можем

установить искомое число нулей системы (3) в алгебраической области.

Теорема 3 Если Эм ^ 0 то все ■решения системы (3) ■различны и

Если, вдобавок, Нц ф 0, то

пга{(3)|С(ЛГ)>0} = Р(1,Я1,...,Я№)-^(1,51,...,5Л) . (8)

Кроме того,

SN=T* J] J{Ар), Ня — Sf[ Д G(Ap), CN = T* Д G(Ap) .

1 <p<N 1 <p<N 1 <p<N

Структура величины T* была также выяснена. Оказалось, что она зависит лишь от коэффициентов старших форм в разложениях полиномов Fj(X) по убывающим степеням переменных, а именно, она является рациональной функцией этих коэффициентов, причём в знаменателе стоит некоторая степень результанта этих форм после подстановки в них X —♦ (si,..., 1,1). Условие отличия знаменателя от нуля га-ратнирует нам существование в точности N нулей системы (3). Для системы (1) это условие эквивалентно существованию N — (п — 1)L стационарных точек. Знакоопределенность же старшей формы Fn{X) в разложении (7) будет гарантировать отличие от нуля числителя в Т*; а её проверка может быть рекурсивно, по числу L, сведена к задаче условной оптимизации полиномиальной функции от L — 1 переменных. Так, например, при L — 2 оно устанавливается посредством проверки равенства nrr{Fn(a:x, 1) = 0} = 0 по теореме Якоби. Это условие нельзя ослабить до знакопостоянства: sup(—xfx^ — xiz^ — xf) = 1/4 "достигается" на бесконечности.

Теорема 4 Если матрицы S и Н построить для системы уравнений (3) при выборе G(x) :— F(X) — z и при этом Т* 0,5jv ^ 0, то :

HN(z) = SNT{z) ,

где полином J~(z) определён формулой (2). Далее, при -ф- 0 бу-

дем иметь:

nrz {(3) | а < F{X) < = пгг {Л» = 0|а<г<Ь} =

= P(l,H1{a),...,HN(a))-P(l,H1{b),...,HN(b)) . (9)

Этим результатом мы свели задачу локализации абсолютного maxF(X) к задаче отделения максимального корня полинома F(z); для последнего система миноров Hi(z),... ,Hn(z) играет роль системы полиномов Штурма. При этом вовсе не обязательно находить аналитическое выражение для миноров матрицы Н как полиномов от z — для локализации корня достаточно будет подставить числовые (рациональные) значения для параметра z в саму матрицу Н и анализировать как меняются знаки числовых миноров при увеличении или

уменьшении параметра. Исключительным здесь будет случай одинаковых или очень близких критических значений, т.е. малость числа \Т>(^(г))\. Снова, как и в одномерном случае, нельзя утверждать, что при Т>{Т{г)) = 0 максимальный вещественный корень Т{£) совпадает с тах.Р(.ЛГ):

тах{-2х{~ - х^ + 7/&х\ + ххх2~Ъ1^х1) = 11/48,

а максимальный корень соответствующего полинома ^(г) равен 11/32. Оказывается, что этот корень достигается целевой функцией на паре мнимых стационарных точек: (¿¿^^р®, Однако, также как и при Ь — 1, разность (9) обладает свойством "игнорирования" вещественных корней Т{£), соответствующих парам комплексно-сопряженных стационарных точек; но при атом даст верную информацию о наличии (и количестве) вещественных стационарных точек, в которых F(X) принимает одинаковые критические значения. В случае единственности такой стационарной точки, её координаты могут быть найдены как рациональные функции величины г пах Р(Х) по формулам, аналогичным (6):

, ©1 ©2 , ©X Х\ = 51,0,...,0 + тр-, Х2 — 50,1,...,о т- -, ...,Х1 — «0,0.....1 + •

, — I ,г > • • • ' .........1 ' и

Иц-1

Здесь Эу — определённым образом составленные миноры матрицы Н.

Задача поиска тах Р(Х) в области, описываемой полиномиальным неравенством 0{Х) > 0, решается в той же идеологии. Она разбивается на две подзадачи: локализации максимума х> целевой функции внутри области:

пгг{(1) | Р{Х) > г,в{Х) > 0} (10)

и локализации условного максимума г^ на границе области:

пга

{ЪЩ-ЪЪ-.....(и)

Теорема 5 (Марков) Если

то:

nrz{/ = 0 \ gi > 0,... ,дк > 0} = (12)

+ £ nrz{/=0 | ад > 0} +

1<J,<A'

+ £ nrz{/ = 0 | ghgh > 0} + T-<ji<h<X

+ £ nrz{/ - 0 | gngn9h > 0} +

l<lx<h<h<K

+ ■ • • + nrz{/ = 0 I 31^2■■■дк > о}]

Применение теоремы 3 и формулы 12 позволяет построить полиномиальные по z системы для нахождения этих чисел.

Числа (10) и (11) не являются взаимно независимыми. Так, при L = 2 и, в предположении, что кривая G(xi,x2) = 0 состоит только из одного овала, они связаны между собой соотношением:

nrz{(l) | G > 0,H(F) > 0} -nrz{(l) | G > 0,7i(F) < 0} = = 1 + |(nrz{ G(xu x2) = 0, J{G, F) = 0 | J{J{G,F), F) > 0 }-— nrz{G(x\,x2) — 0, J(G,F) = 0 | J(J(G,F),F)< 0}),

вытекающим из теории индекса Кронекера-Пуанкаре. Здесь J — якобиан, "Н — гессиан, а первое слагаемое в левой части равенства дает число точек локального экстремума внутри области

G(xъх2) > 0.

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

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

Для случая L = 2 и L = 3 переменных теоретические результаты проиллюстрированы примерами, просчитанными с помощью вспомогательных процедур, написанных диссертантом для системы аналити-

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

ВЫВОДЫ

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

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

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

Основные публикации по теме диссертации

1. Uteshev A.Yu., Shulyak S.G., Cherkasov T.M. Hermite's Method for Separation of Solutions of Algebraic Equations Systems and Its Realization in REDUCE.// Abstracts of the International Congress on Computer Systems and Applied Mathematics — CSAM'93, 1993, St.Petersburg, P. 114

2. Uteshev A.Yu., Shulyak S.G., Cherkasov T.M. Systems of Algebraic Inequalities: Consistency and Structure of the Set of Solutions.// Abstracts of the International Conference on Interval and Computer- Algebraic Methods in Science and Engineering - Interval'94, 1994, St .Petersburg, P.237-238

3. Утешев А.Ю., Черкасов T.M. Локализация решений систем алгебраических уравнений и неравенств. Метод Эрмита.// ДАН России, 1996, Т.347, №4, С.451-453

4. Черкасов Т.М. Алгебраический метод решения задачи полиномиального программирования.// Ргос. of the 11th Baikal International School-Seminar - Optimization Methods and Their Applications, 1998, Irkutsk, P.216-219

5. Uteshev A.Yu., Cherkasov T.M. Symbolic Algorithms for Polynomial Optimization Problem.// Abstracts of Optimal Control and Appendices — Int. Conf. Dedicated to the 90th Anniversary of L.S.Pontryagin, 1998, Moscow, P. 197-198

6. Uteshev A.Yu., Cherkasov T.M. The Search for the Maximum of a Polynomial.// Journal of Symbolic Computations, 1998, V.25, P.587-618

7. Утешев А.Ю., Черкасов T.M. К задаче полиномиальной оптимизации.// ЛАН России, 1998, Т.361, №2, С.168-170

ЛР№ 040815 от 22.05.97.

Подписано к печати 25.05.2000 г. Формат бумаги 60X90 1/16. Бумага офсетная. Печать ризографпческая. Объем 1 пл. Тираж 100 экз. Заказ 1403. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198904, Санкт-Петербург, Старый Петергоф, Университетский пр. 2.

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

Введение.

Глава 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. При решении задачи поиска максимума в области, описываемой системой полиномиальных неравенств, не следует проводить предварительного исследования ни системы условий на совместность, ни самой целевой функции на наличие максимума на бесконечности. Предложенный алгоритм позволит проверить второе из этих условий автоматически — в ходе проверки условий применимости метода Эрмита. Непустота допустимого множества выяснится в ходе нахождения условного экстремума целевой функции на потенциальных граничных многообразиях этого множества. Проверка условия достижимости максимума в нескольких стационарных точках должна также производиться лишь тогда, когда за достаточное число подстановок не удается отделить критические значения.