Введение к работе
Актуальность исследования. Как бы не совершенствовалась вычислительная техника, улучшение алгоритмов, закладываемых в нее, остается вечно востребованным Всегда будут существовать задачи вычислительного типа, которые окажутся не доступны объединенным усилиям "металла" и математического обеспечения из-за нехватки быстродействия, памяти, несходимости итеративного процесса или просто отсутствия алгоритма решения Постоянно будут вестись разработки новых, более эффективных численных алгоритмов В этом процессе представляются насущными три совсем различных направления
Во-первых, хорошо бы использовать уже имеющийся богатый арсенал итеративных методов в качестве некоторой базы для модификаций, которые улучшили бы качество сходимости
Во-вторых, само обоснование новых алгоритмов создает потребность в надлежащем инструменте, который бы дал возможность такого обоснования или существенно облегчил его.
В-третьих, использование в итеративных методах более сложных, но и более точных, аппроксимаций решаемой задачи, например, нелинейных вместо линейных, позволяет увеличить скорость сходимости методов и, тем самым, сократить общую вычислительную трудоемкость метода, несмотря на на большую пошаговую трудоемкость
В этой работе проводятся исследования в указаных направлениях. Для улучшения сходимости итеративных методов с приближениями в банаховых пространствах предложен принцип минимальности (ПМ) последующим приближением назначается минимайзер оценки его погрешности, а множество, в котором происходит поиск минимайзера, формируется на основе всей имеющейся на текущем шаге информации, включая результат работы исходного алгоритма на текущем шаге
Одной из часто имеющейся в распоряжении дополнительной информацией, которую можно использовать в ПМ, является оценка погрешности результата применения исходного алгоритма Л к текущему приближению х вида
\\Л(х)-а\\<с\\х-а\\Р, р>1, с> 0, (1)
(а — искомое решение). Она и исследовалась для самых распространенные значений параметра р: 1 — линейная сходимость и 2 — квадратичная сходимость
При обосновании численных методов, да и, вообще, при формулировании теорем, естественно желание предельно ослабить условия и,
тем самым, усилить результат Так, ограниченность производной, по возможности, заменяется на ее липшицевость Например, в теореме Канторовича о сходимости метода Ньютона для уравнения д(х) = О сам Л.В.Канторович использует условие вида ||g"(a;)|| < L V х Е S. А в теореме Канторовича в версии М.А Красносельского это условие заменяется на липшицевость д' в S.
Одним из ослаблений подобного рода, или иначе расширением класса рассматриваемых функций, является понятие полупроизводной отображения (6). Небольшой аппарат исчисления полупроизводных позволяет уточнять известные результаты и получать новые. Так, его применение к оценке удаленности решения нелинейного уравнения в банаховом пространстве от заданной точки позволило усилить известные теоремы Мысовских и Гавурина о методе Ньютона в тех их частях, где они касаются удаленности решения.
Получение оценки (1) часто является существенной частью обоснования одноточечного итеративного метода вида хк+1 := Л(хк), к = 0,1,... Удобным инструментом для этого оказался метод дифференцирования по итерации, куда органично вкладывается полупроизводная Его можно применить для обоснования сходимости метода Ньютона в классах функция, отличных от тех, которые рассматривали Л.В. Канторович, М.К. Гавурин, И.П. Мысовских в соответствующих теоремах о методе Ньютона.
Он же использовался и для обоснования метода квадратичной оптимизации (МКО), предназначенного для решения нелинейных программ вида f(x) —> min . Суть МКО — в последовательном состав-
д(х)<0 лении и решении квадратичных программ, которые являются аппроксимациями исходной нелинейной программы в текущей итеративной точке.
Под названием метод параболоидов это можно встретить у Дж Ортеги и В Рейнболдта для поиска безусловного экстремума. Модификации метода параболоидов рассматривались К. Левенбергом и С Гольдфельдом, Р. Курантом, Т. Троттером
Наиболее близка к МКО одна из модификаций метода линеаризации Б.Н Пшеничного и Ю.Н.Данилина. В ней для ускорения сходимости предлагалось ввести в линейную аппроксимацию целевой функции на шаге квадратичную добавку (х — xk)rLxx(x — хк)/2, где Lxx - гессиан соответствующей функции Лагранжа. В случае линейности функций-ограничений он совпадает с гессианом функции /, а сам метод линеаризации — с МКО.
МКО, как часть метода последовательной оптимизации управле-
ния летательным объектом применялась В М Пономаревым (с 1970-х) Там целевая функция и функции-ограничения формировались в виде математических ожиданий функционалов на решениях систем дифференциальных уравнений Поэтому "цена" каждого значения функции была очень высокой и даже существенное усложнение алгоритма минимизации легко окупалось повышением скорости сходимости Конкретные реализации метода выявили высокую скорость сходимости метода во многих случаях, но теоретическое обоснование сходимости было найдено только для узкого круга Не исследованным тогда остались скорость сходимости, выбор начальной точки, правило остановки, разобранные в этой работе.
В свою очередь, в построении квадратичной аппроксимации существуют некоторые проблемы. Если исходная целевая функция выпукла, то невыпуклость ее аппроксимации, видимо, является отрицательным качеством Если аппроксимация есть результат прямой интерполяции значений целевой функций, измеренных в некоторых узлах, то за счет погрешностей измерения она может оказаться не выпуклой К такому же осложнению может привести и применение метода наименьших квадратов при произвольном числе узлов. Поэтому должен быть найден метод построения квадратичных выпуклых аппроксимаций
В одномерном пространстве итеративное решение скалярного уравнения д(х) — 0 и минимизация скалярной функции f(x) при помощи экстраполяционных полиномов порядка большего единицы восходит к П Л. Чебышеву. Интерполяционные полиномы можно встретить в методе Мюллера и интерполяционном методе высокого порядка поиска одномерного минимума Н.Б. Кирина (1968 г.). Однако разнообразие методов на основе интерполяции, перспективных для исследования, этим далеко не исчерпывается.
Значения реальных целевых функций, как правило, могут измеряться только с некоторой погрешностью. Ее влияние на сходимость интерполяционных методов в одномерном пространстве исследовалось еще А Островским (1960), но к настоящему времени набор методов, снабженных полным анализом влияния ошибок измерений относительно невелик.
Аналогом аппроксимации функции, заданной в комбинаторном пространстве, является прогноз поведения функции по отношению к некоторой последовательности элементов комбинаторного пространства, исчерпывающей его. В зависимости от конкретной такой последовательности и от способа ее порождения возможно вводить те или иные отсечения, базируясь на прогнозе поведения.
Несколько снижаются вычислительные затраты на определение значений целевой функции, если в упомянутой последовательности от комбинации к комбинации происходит минимальное изменение состава элементов Коды Грея позволяют создавать алгоритмы минимального изменения, но даже в простейших случаях целевой функции вида /(ж) — \^Lix% — В\ минуют вопрос об отсечениях. Для решения задач минимизации на пространствах с большим числом элементов за разумное время необходимо изыскивать новые алгоритмы, допускающие включение отсечений
Цель исследования Применить ПМ для улучшения сходимости одноточечных итеративных методов в вещественном гильбертовом пространстве. Применить исчисление полупроизводных для оценки удаленности решения нелинейного уравнения в банаховом пространстве. Применить метод дифференцирования по итерации для обоснования метода Ньютона в специальных классах функций. Дать теоретическое обоснование применения нелинейных аппроксимаций в задачах оптимизации Произвести полный анализ сходимости метода квадратичной оптимизации. Произвести необходимые для применения в МКО модификации алгоритма решения квадратичной программы. Найти и обосновать алгоритмы построения выпуклых аппроксимаций. Дать анализ сходимости методов на основе интерполяции полиномами высоких степеней с возможным учетом погрешности измерений. Разработать алгоритмы решения нелинейных программ в некоторых комбинаторных пространствах.
Методы исследования. Используются основные факты и методы теории функций, теории меры, алгебры, выпуклого анализа, нелинейного программирования.
Научная новизна состоит в следующем.
1. Установлены предельно широкие условия, когда решение нелиней
ной программы /(ж) —> min есть часть решения системы
д(х)<0
V/(x) + №д(х) = О Л А > 0 Л Хд(х) = 0 Л д{х) < 0 и обратно
На основе оценки (1) и принципа минимальности получены формулы релаксации для произвольного одноточечного итеративного метода x'+1 = Л(х'), которые позволяют генерировать итерации с лучшей сходимостью, чем {ж*}.
Описано исчисление полупроизводных.
Обоснован метод дифференцирования по итерации, использующий полупроизводную и разностную производную.
5 Уточнены некоторые оценки удаленности решения нелинейного
уравнения в банаховом пространстве
6 Посредством метода дифференцирования по итерации обоснован ме
тод Ньютона решения нелинейного уравнения со специальной левой
частью
7. Установлены область сходимости и произведена оценка скорости сходимости метода квадратичной оптимизации (МКО), строящего последующую итерацию ж*+1 по итерации хк как решение квадратичной программы
V/(x*)(x - хк) + (х- xk)THf(xk)(x - хк)/2 -» mm
Установлены критерии выбора начальной точки для МКО. Установлены оценки вида ||a;fc+1 — х\\ < а||ж*+1 — a;fc|| для МКО.
Получены упрощенные необходимые и достаточные условия положительности квадратичной формы, менее трудоемкие, чем критерий Сильвестра
Разработаны способы построения выпуклых квадратичных аппроксимаций
10 Модифицирован метод Била решения квадратичных программ:
приведена табличная схема, позволяющая применять его для смешан
ного состава переменных (ограниченных и неограниченных по зна
ку), дан алгоритм поиска начальной допустимой таблицы, вкладыва
ющийся в основной алгоритм; указан алгоритм предотвращения за
цикливания
Получены оценки скорости сходимости дискретных методов высокого порядка в решении скалярных уравнений и поиске скалярного минимума, установлены условия на начальные узлы, гарантирующие сходимость.
Определена степень повышения точности измерений от шага к шагу, сохраняющая порядок сходимости, для квадратичной скалярной оптимизации интерполяционным многочленом.
Предложен алгоритм порождения комбинаторного пространства сочетаний минимального изменения, отличный от двоичного зеркально-отраженного кода Грея и позволяющий проводить эффективные отсечения в некоторых задачах на оптимизацию.
Приведен и обоснован алгоритм решения задач вида
гт
|/,(w,(i))
./о
где іц,. ип,и- неубывающие функции, возможно разрывные Практическая значимость работы. Основные результаты связаны с численными алгоритмами нелинейного программирования и имеют прикладной характер. Они могут применяться при решении конкретных оптимизационных задач. Предлагаемые математические аппараты позволяют улучшать сходимость известных итеративных методов и облегчать обоснование новых
Апробация материалов исследования проходила на семинаре кафедры информационных систем, на семинаре по теории управления под руководством В.И.Зубова в Санкт-Петербургском университете, на семинаре по дифференциальным уравнениям под руководством Н.М Матвеева в Педагогическом университете им. А Герцена, на семинаре в ВЦ РАН, на семинаре в UMIST (University of Manchester Institute of Science and Technology), на семинаре в институте математики и механики УрО РАН, на семинаре в Санкт-Петербургском Университете Экономики и Финансов; на международных конференциях: CDE'IV (Руссе, Болгария, 1987), SICDE (Болгария, 1991), CSAM'93 (С.-Пб.), Interval 94 (С.-Пб.), ICI&C97 (С -Пб ), MMSED-2004 (Москва), Устойчивость и процессы управления 2005 (С -Пб). По теме диссертации опубликована 31 работа общим объемом 780 стр., из них два учебных пособия (8 печатных листов) и две монографии (27.4 печ. листов).
