Оптимизация численных алгоритмов тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Михеев, Сергей Евгеньевич

• Михеев, Сергей Евгеньевич
• доктор физико-математических наук
• 2006

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

ВВЕДЕНИЕ

Глава 1.

ОБЩИЕ ВОПРОСЫ

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Глава 2.

РЕЛАКСАЦИОННОЕ УСКОРЕНИЕ ИТЕРАТИВНЫХ ПРОЦЕССОВ

§2.1. ОПИСАНИЕ ПРИНЦИПА МИНИМАЛЬНОСТИ.

§2.2. ТОЧНЫЕ РЕЛАКСАЦИИ

ДЛЯ МЕТОДА ПРОСТЫХ ИТЕРАЦИЙ

§2.3. ТОЧНЫЕ РЕЛАКСАЦИИ

В СКАЛЯРНОМ ПРОСТРАНСТВЕ

§2.4. МНОГОМЕРНЫЙ СЛУЧАЙ (р= 1).

§2.5. ОБОБЩАЮЩАЯ СХЕМА.

§2.6. СТАТИСТИЧЕСКИЕ СВОЙСТВА ТОЧНОЙ

РЕЛАКСАЦИИ МЕТОДА ПРОСТОЙ ИТЕРАЦИИ (р=1)

§2.7. АСИМПТОТИКА ТОЧНОЙ РЕЛАКСАЦИИ.

§2.8. НЕЛИНЕЙНАЯ СХОДИМОСТЬ (р > 1)

§2.9. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ.

Глава 3.

ДИФФЕРЕНЦИРОВАНИЕ ПО ИТЕРАЦИИ

§3.1. ПОЛУПРОИЗВОДНАЯ И ЕЕ СВОЙСТВА.

§3.2. АНАЛИЗ СХОДИМОСТИ

С ПОМОЩЬЮ ДИФФЕРЕНЦИРОВАНИЯ ПО ИТЕРАЦИИ

Глава 4.

НЕЛИНЕЙНЫЕ УРАВНЕНИЯ

§4.1. СУЩЕСТВОВАНИЕ И ОЦЕНКА РЕШЕНИЯ

НЕЛИНЕЙНОГО УРАВНЕНИЯ.

§4.2. СРАВНЕНИЕ С ИЗВЕСТНЫМИ РЕЗУЛЬТАТАМИ.

§4.3. СХОДИМОСТЬ МЕТОДА НЬЮТОНА.

§4.4. РАСХОДИМОСТЬ МЕТОДА НЬЮТОНА.

Глава 5.

МЕТОД КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ

§5.1. ОПИСАНИЕ МЕТОДА.

§5.2. ЛОКАЛЬНАЯ СХОДИМОСТЬ.

§5.3. ПОЛУГЛОБАЛЬНАЯ СХОДИМОСТЬ.

§5.4. ВЫБОР НАЧАЛЬНОЙ ТОЧКИ.

§5.5. МОДИФИКАЦИИ МЕТОДА

КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ.

Глава 6.

КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ

§6.1. РАЗЛИЧНЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ

КВАДРАТИЧНЫХ ПРОГРАММ-АППРОКСИМАЦИЙ

§6.2. ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ И АППРОКСИМАЦИЯ

§6.3. КВАДРАТИЧНЫЕ АГРЕГАТЫ.

§6.4. ВЫБОР УЗЛОВ ИНТЕРПОЛЯЦИИ.

§6.5. ВЫПУКЛОСТЬ ЛИНЕЙНО-КВАДРАТИЧНОГО АГРЕГАТА

§6.6. АЛГОРИТМ ТРЕХКООРДИНАТНОГО СПУСКА.

§6.7. АЛГОРИТМ ЧАСТИЧНОГО ПРОЕКТИРОВАНИЯ.

§6.8. АЛЬТЕРНАТИВНЫЙ ПОДХОД.

§6.9. МОДИФИКАЦИЯ МЕТОДА БИЛА.

Глава 7.

ДИСКРЕТНЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

И ПОИСКА ЭКСТРЕМУМА

§7.1. ДИСКРЕТНЫЙ МЕТОД ЧЕБЫШЕВА.

§7.2. МЕТОД МЮЛЛЕРА.

§7.3. ПОИСК ОДНОМЕРНОГО МИНИМУМА

НА ОСНОВЕ n-ТОЧЕЧНОЙ ИНТЕРПОЛЯЦИИ.

§7.4. УЧЕТ ПОГРЕШНОСТЕЙ ИЗМЕРЕНИЙ ПРИ МИНИМИЗАЦИИ

МЕТОДОМ ТРЕХТОЧЕЧНОЙ ИНТЕРПОЛЯЦИИ.

Глава 8.

МИНИМИЗАЦИЯ

НА КОМБИНАТОРНЫХ ПРОСТРАНСТВАХ

§8.1. АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЯ

ДЛЯ ОДНОГО СЕМЕЙСТВА ЗАДАЧ ОБСЛУЖИВАНИЯ

§8.2. КОМБИНАЦИОННОЕ ДОЗИРОВАНИЕ.

Глава 9.

МИНИМИЗАЦИЯ СЕПАРАБЕЛЬНЫХ ЦЕЛЕВЫХ ФУНКЦИЙ

Введение диссертации (часть автореферата) на тему «Оптимизация численных алгоритмов»

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

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

Вводной для глав 5-7 является гл. 1. Основной ее объект — нелинейная программа общего вида: z)—> mm, (0.1) где / — скалярная функция, именуемая целевой, D — именуемое допустимым некоторое множество; во многих важных приложениях оно задается формулой

D := {х\д(х) < 0}; (0.2) здесь х — n-мерный вектор; д — m-мерная вектор-функция. Программа (0.1) является ключевым элементом большинства задач на оптимизацию.

Исходной задачей в гл. 1, 5-7 является нелинейная программа (0.1) с допустимым множеством (0.2), именуемая здесь для краткости задачей А. В основе многих исследований методов нелинейного программирования лежит функция Лагранжа. Для задачи А она задается формулой

F(x,X) := f(x) + Xg(x), где А — m-мерная строка. Поиск у функции Лагранжа седловой точки (х, Д), определяемой неравенствами

F(x,\)>F(X,\)>F(X,\) VA>0, Ухе BP, двойственная задача) здесь — задача В. Связь между решением задачи А и х-составляющей решения задачи В описана в теоремах Куна-Таккера [84]. В случае дифференцируемости функций / и д, как известно, седловая точка необходимо удовлетворяет системе

VxF(x, А) = 0 A V\F(x, А) < 0 A А>0 A №\F(x,\) = 0, (0.3) часто называемой системой Куна-Таккера. Поиск решения системы (0.3) можно рассматривать как самостоятельную задачу, которую далее будем именовать задачей С. Выпуклость функций / и g гарантирует совпадение множества решений задач В и С [79]. Связь между решением задачи А и х-составляющей решения задачи С традиционно устанавливается при помощи посредника — задачи

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

Здесь будет исследована прямая взаимосвязь задач А и С.

В гл. 2 для улучшения сходимости итеративных методов, как одноточечных, так и многоточечных, предложен принцип минимальности (ПМ), суть которого не вызывает возражений. В упрощенном виде она такова.

Пусть существует итеративный процесс вида хк+1 = Л(хк), к = 0,1,., начатый из я0. Может оказаться, что базовый алгоритм Л использует не всю доступную на /г-шаге информацию. Ею может быть, например, оценка текущей погрешности dk, оценка невязки, или часто используемая оценка погрешности последующей итерации через оценку погрешности текущей

4(:rfc) - а|| < с\\хк - а||р, р > 1, Дс = 0,1,2,. (0.4)

Здесь {х1}о° — элементы некоторого банахового пространства, порождаемые базовым алгоритмом Л, а — искомая неподвижная точка этого алгоритма: а = Л{а).

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

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

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

Проведены численные эксперименты с точной релаксацией модифицированного метода Ньютона для скалярного уравнения (§2.9).

При обосновании численных методов (да и, вообще, при формулировании теорем) естественно желание предельно ослабить условия и, тем самым, усилить результат. Так, ограниченность производной, по возможности, заменяется на ее липшицевость. Например, в теореме Канторовича (ТК) о сходимости метода Ньютона ([18], гл.ХУШ, § 1, т. 6) решения уравнения д(х) = 0 присутствует условие вида ||<7"(я)|| < L V х 6 S. Ав теореме Канторовича, приведенной в книге [23] это условие заменяется на липшицевость д' в S.

Одним из ослаблений подобного рода (или иначе расширением класса рассматриваемых функций) является понятие полупроизводной, введенной в §3.1. Оно активно используется в методе дифференцирования по итерации (§3.2). Суть его состоит в параметризации отрезка, соединяющего решение а с текущей итерацией: xk(t) := а + t(xk — а), и исследовании задачи Коши для y{t) :=xk+l{t)-a = A{xk(t))-cr. y = F(y,xk,xk-a), 2/(0) = 0 с переходом к дифференциальному неравенству относительно ||у||. Так как y(l) = xk+1, оценка для ||j/(l)|| позволяет оценить погрешность последующего приближения.

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

6 гл. 4 понятие полупроизводной использовано в выяснении существования и оценивании удаленности решения нелинейного уравнения в банаховом пространстве д{х) = 0. (0.5)

Для отображений д, обладающих липшицевой производной (класс С1'1) был получен результат - теорема 4.1, пересекающийся с известными теоремами Канторовича (ТК), Мысовских [58] (т. 1), Гавурина [7] (т. 1) в тех их частях (соответственно, ЧТК, ЧТМ, ЧТГ), где они касаются существования решения и оценки его удаленности от начального приближения.

Теорема 4.1 является расширением ЧТК на случай, когда известна оценка гм > ||(<7'(я))1||, является усилением ЧТМ в виде ослабления условий и усиления заключения, является усилением ЧТГ в виде ослабления условия.

Для отображения, обладающего полупроизводной (класс П) вначале в теореме 4.2 была получена оценка удаленности, затем найдены достаточные условия сходимости метода Ньютона и оценка скорости сходимости. Эти результаты не вложимы в упомянутые теоремы Канторовича, Мысовских, Гавурина, нет и обратного вложения. Конкретное отображение д, рассматриваемое как элемент из С1'1, может получить согласно этим теоремам гарантии по сходимости метода Ньютона и не получить как элемент из П согласно теоремам, приведенным в гл. 4. Возможно и наоборот. А также возможно получить гарантии при обеих трактовках и не получить ни в одной трактовке.

Большая часть итеративных методов поиска экстремума и решения систем нелинейных уравнений базируется на построении некоторой упрощенной здачи в окрестности итеративной точки. Последующее приближение есть решение этой упрощенной задачи. Наиболее распространенный способ упрощения — линейная экстраполяция (интерполяция) функций исходной задачи. Аппроксимирующая задача имеет тогда вид соответственно линейной программы или линейной системы, решение которых, как правило, несложно в вычислительном аспекте. Однако на шаге итеративного метода требуется рассчитать еще параметры аппроксимации, такие, например, как значения функций и их производных из исходной задачи. И может случиться, что вычислительная стоимость решения аппроксимирующей задачи многократно меньше, чем рассчет параметров. Тогда даже существенное усложнение аппроксимации будет оправдано: лишь бы оно увеличило скорость сходимости, поскольку последнее приводит к уменьшению общего числа шагов, потребных для получения решения заданной точности. Предпосылкой такого усовершенствования служит обладание некоторой информацией о нелинейностях параметров (см. гл. 5,7,9).

Следующей по сложности за линейной, по-видимому, надо признать квадратичную аппроксимацию. Именно она, т.е. квадратичная программа, составляет центральную часть метода квадратичной оптимизации (МКО) для решения задач нелинейного программирования общего вида. На практике этод метод хорошо зарекомендовал себя как составная часть метода последовательной оптимизации движения летательных объектов В.М.Пономарева [64]. Последнее служило, в частности, яркой иллюстрацией того что есть трудоемкость собственно метода на шаге и что есть затраты на вычисление параметров. Решение квадратичной программы образовывало первое, параметры же представляли собой математические ожидания функционалов от решений систем дифференциальных уравнений, описывающих движение летательного аппарата. Отношение первого к второму было ничтожно.

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

Методу квадратичной оптимизации посвящена глава 5. Его назначение — итеративное решение задачи (0.1) + (0.2), т.е. задачи А.

Пусть х есть текущее приближение. Тогда в соответствии с МКО следующее приближение к решению задачи А получается как решение квадратичной программы относительно параметров х: f(x,xk) := Vf(xk)(x - хк) + (х- хкуН(хк){х - хк)/2, д(х,хк) := J(xk){x - хк) + д(хк). f(x,xk)—у min (0.6) д(х,хк)< 0

Здесь Н — гессиан функции /, т.е. матрица из вторых производных J матрица из строк-градиентов Vgi: г = 1, га, т.е. - Ш"

Частные случаи метода квадратичной оптимизации предлагались и исследовались с 60-х годов. Так, для задачи А без ограничений, т.е. при D = i?n были предложены программы, реализующие фактически метод квадратичной оптимизации в чистом виде [96] и его модификацию, когда в качестве функции f(x,xk) берется квадратичный интерполяционный полином, совпадающий в некоторых 1 + n + п(п + 1)/2 точках с исходной целевой функцией / [94]. Дж. Ортега и В. Рейнболд этот частный случай называют методом параболоидов. Как составная часть метода последовательной оптимизации В.М. Пономарева, метод квадратичной оптимизации активно использовался при решении большого числа задач управления летательными объектами и другими системами [65], [66]. В [64] был доказан частный случай сходимости, когда система Куна-Таккера (0.3) эквивалентна своей подсистеме

Vf(x) + \J(x)=0 А Л^(гс) = 0. (0.7)

Тогда метод кваратичной оптимизации для задачи А можно сопоставить решению методом Ньютона некоторой системы нелинейных уравнений, являющихся подмножеством системы (0.3), и воспользоваться известными результатами для метода Ньютона. Однако большое количество конкретных задач (0.1) + (0.2) не обладает эквивалентностью систем (0.7) и (0.3), что делает актуальным теоретическое обоснование сходимости метода квадратичной оптимизации в применении к ним (§5.2), а также исследование критериев остановки итератиного процесса (§5.3) и исследование по выбору начальной точки (§5.4).

В §5.5 исследуются возможности модификации МКО по аналогии с модифицированным методом Ньютона. То есть, как сказываются на сходимости погрешности в вычислениях параметров для квадратичной программы на шаге. А именно, параметров Vf(xk), J(xk), д(хк), Н(хк). Нельзя ли какие-нибудь из них вычислить только в начальной точке и использовать затем вместо текущих значений, например, Н(х°) вместо Н(хк)1 Это дало бы существенное снижение общих вычислительных затрат.

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

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

В гл. 5 использование информации о нелинейном поведении целевой функции ограничилось аппроксимацией ее полиномом второго порядка. Тому было два основания: во-первых, построение многомерной аппроксимации более высокого порядка представляется весьма трудоемкой задачей, и, во-вторых, решать нелинейную программу с целевой функцией в виде полинома, порядка большего двух, значительно труднее в многомерном пространстве, чем квадратичную программу. В одномерном пространстве эти два затруднения существенно слабее, и в гл. 7 исследован ряд способов решения нелинейного уравнения и поиска одномерного экстремума. В §7.1 рассмотрен дискретный аналог метода Чебы-шева [3], [34] решения скалярного уравнения

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

М — величина, связанная с оценками сверху на \f'{x)\ и производную порядка п обратной к / функции), в общем виде достаточно подробно изученное еще = о.

0.8) tk - tk-i ~ - - tk-n - In M

0.9)

A.M. Островским [61] . Здесь не рассматривается общий случай, это позволило привести иные доказательства сходных утверждений, вполне достаточные для обслуживания дискретного метода Чебышева. Исследуется условие на начальные данные, гарантирующие сходимость и высокую скорость сходимости.

На базе §7.1 получены аналогичные результаты для решения (0.8) методом Мюллера (§7.2).

Те же идеи заложены в исследовании поиска одномерного минимума на основе n-точечной интерполяции (§7.3). Близкий метод был предложен Н.Е. Кири-ным и С.И. Веденяпиной [4], однако иной способ замещения узлов интерполяции имел последствием иные оценки скорости сходимости.

После получения обоснований итеративного метода, устойчивость его к ошибкам в исходных данных и к ошибкам округления — главное беспокойство для пользователя. В §7.4 исследуется сходимость метода трехточечной интерполяции (частный случай метода §7.3) при наличии погрешности в измерениях целевой функции [87]. Выясняется, нельзя ли повышением точности вычислений от шага к шагу сохранить тип сходимости.

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

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

В §8.1 исследуются алгоритмы поиска оптимального решения задач на обслуживание сеансов связи следующего вида:

Имеется га заявок на обслуживание. В каждой г-й заявке указывается отрезок времени Т; = [if,if], г = 1,ш, когда она может быть выполнена. Заявки выполняются на фиксированных непересекающихся участках обслуживания hi = \h\, hf\ во время сеанса связи [В, Е] D U"=i hj. На каждом участке hj может быть выполнена только одна заявка из числа тех, для которых hj содержится в некотором Ti . Требуется составить расписание, по которому обслуживается наибольшее число заявок.

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

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

Поскольку процесс идет в реальном времени, быстродействие алгоритма выбора имеет существенное значение. Предложен (см. §8.2) названный здесь пачечным алгоритм порождения комбинаторного пространства, обладающий порядком минимального изменения, как и двоично-отраженный я-разрядный код Грея [70], но, в отличие от последнего, позволяющий вводить отсечения.

Один из известных подходов к задаче наилучшего распределения капиталовложений в развитие городского коммунального хозяйства или экономики района, области, страны [16], [88] с помощью математического моделирования примерно таков.

На первом принципиальном шаге выбирается целевой функционал вида где t — время; Т — длительность срока планирования; Х{ — количественное состояние г-й отрасли; /; — функции вредности, убывающие с ростом ж»; Aj — веса. Фактически xi зависят не от времени, а от объема финансирования щ i-й отрасли: Xi = Х{(щ). Таким образом, задача приобретает вид где щ — возрастающие функции, ^Uj(i) = u(t) V £ € [0, Г], u(t) — заданная функция общего финансирования.

Сама такая постановка задачи является проблемой: каким должны быть fi и Aj, чтобы минимайзер для (0.11) воспринимался как оптимальное финансирование? То есть по сути: как добиться адекватности математической модели реалиям жизни? Даже при самом тщательном выборе /i,.,/n, но при Aj = . = А„ = 1 может случиться, что минимайзер для (0.11) вызовет недоумение заказчика. Здесь на помощь приходят веса. Закзчику предлагается количественно их оценить пропорционально важности отраслей. После чего находится новый минимайзер для новых весов. Эту процедуру можно повторять до получения приемлемого результата. Проблема адекватности кажется исчезнувшей, на самом деле всего лишь переместившись в адекватность выражения важности в виде некоторого числа.

В гл. 9 предлагается иной взгляд на проблему. Пусть есть приемлемый некоторым коллективом план й. И пусть существует функционал Фз(А,п), зависящий от плана и вектора параметров А. При каком значении вектора параметров А минимайзер функционала Ф2 будет совпадать с таким приемлемым планом? Ответ на этот вопрос дает возможность лучше понять сущность весов и назначать их более обосновано.

Эта обратная экономическая задача исследована для частного случая. Как приемлемый был взят опорный план — равномерное сокращение дефицита по отраслям, а в качестве целевой функции — функционал вида (0.10) с Д,., /п, равными квадратам текущих относительных дефицитов, и линейной зависимостью Xi(y) = Xio + СгЩ. Оказалось (т. 9.3), что вектор параметров А, обеспечивающий совпадение опорного плана и минимайзера для (0.10) существует и единствен.

Наряду с обратной экономической задачей исследуется и прямая. Т.е. веса Ai,.,An фиксируются и, соответственно, вводятся в (сливаются с) Д,.,/п

0.10)

0.11)

Поступление капиталовложений может быть непрерывным по времени и дискретным (т.е. и — разрывна). В предположении выпуклости функций Д,., /„ и кусочной непрерывности вторых производных /",., (т.е. целевой функционал — произвольная выпуклая кусочно гладкая сепарабельная целевая функция) предложен алгоритм построения плана. Доказано, что он — минимайзер.

Об обозначениях. Буква Т в верхнем индексе будет означать операцию транспонирования. Знак V — операция нахождения градиента, сам градиент будет пониматься как строка. Слева от знака ":=" находится обозначение того, что стоит справа от него. Справа от знака "=:" находится обозначение того, что стоит слева от него. В конце некоторых логических частей стоит знак ■ . Индекс итерации для векторных величин — верхний.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Михеев, Сергей Евгеньевич

ЗАКЛЮЧЕНИЕ

Взаимосвязь между решениями трех задач: нелинейной программой (А), поиском седловой точки функции Лагранжа (В), решением системы Куна-Таккера (С) традиционно формулируется в виде четырех теорем Куна-Таккера А—>В, В-*А, А-+С, С-*А. Кроме безусловной теоремы из В в А, (^-составляющая решения задачи В всегда есть решение задачи А) каждая из трех остальных имеет необходимый характер условий в том смысле, что для любого изъятия или ослабления какого либо условия можно привести контрпример, для которого утверждение соответствующей теоремы неверно, т.е. теоремы не могут быть усилены. Посредством суперпозиций двух пар этих теорем можно установить связи А—>С и С->А, причем каждая будет содержать требование выпуклости целевой функции f(x) и функций-ограничений д(х).

В гл. 1 получено более сильное утверждение: ^-составляющая решения системы Куна-Таккера является решением задачи А всего лишь при требовании слабой унимодальности fag, непрерывности / и отличия от нуля градиента / в х-составляющей решения задачи С. Показана невозможность ослабления этих требований (теорема 1.5 и контрпримеры к ней). Введенное здесь понятие слабой унимодальности трактуется как не убывание функции при удалении от ее множества минимальных значений вдоль любого луча. Получены альтернативные формулировки без требования непрерывности (теоремы 1.5' и 1.5").

Для обратной связи от решения задачи А к решению задачи С получены результаты также без требования выпуклости. В теореме 1.7 требуется всего лишь слабая унимодальность и непрерывность д вместо выпуклости fug. Теорема 1.6 вместо условия Слейтера и выпуклости / и д имеет лишь требование существования х* такого, что Vgi(x)(x* — х) < 0 для всех г, соответствующих существенным ограничениям: gi(x) = 0.

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

ПМ был применен к итеративным одноточечным методам, в которых последующие приближения порождаются алгоритмом Л: хк+1 = Л(хк), а в качестве дополнительной информации имелась оценка погрешности последующего приближения вида

4(z*+1)-a|| <ф*-а||р, р > 1, fc = 0,1,2,., где {я*}о° — элементы некоторого вещественного евклидова или гильбертова пространства, х° — начальное приближение, а — неподвижная точка исходного алгоритма: а = Л(а), с — положительная константа (если р = 1, то с € (0,1).

На основе ПМ получена модификация алгоритма а, названная точной релаксацией. В ней вместо итеративной последовательности {я*}о° предлагается строить последовательность элементов и последовательность чисел — оценок погрешностей — таких, что у0 = х°, do — каким то образом полученная оценка погрешности начального приближения, а остальные приближения и оценки погрешностей порождаются расчетными формулами вида ук + р (dk, Л(у*), с) - у"), dk+1 = A(dk, у\ с), где коэффициент релаксации р(-, •, •) определен из ПМ т.е так, чтобы погрешность <4+i для итерации ук+1 была минимальной при знании только значений 4-х его аргументов. Вычислительная стоимость расчетных формул коэффициента точной релаксации и оценки погрешности невелика: скалярное произведение элементов исходного пространства, два сложения в нем и от 3 до 8 арифметических операций. Выгода модификации проявляется в повышении скорости сходимости к нулю оценок погрешности {dk} в сравнении со скоростью убывания оценок погрешности {dk} итераций базового алгоритма. (При р = 1 справедливо dk = c^cfo, где d0 - априори известная оценка начального приближения.) Для модификации всегда dk+i < cdk. На некоторых шагах, вообще говоря, возможно dk+1 = cdk, но вероятность этого, в предположении равномерного распределения решения в шаре радиуса dk, соответствует приблизительно отношению меры машинного представления сферы радиуса d^V 1 — с2 к мере машинного представления шара радиуса dk, что даже для двумерного пространства и используемых в настоящее время ЭВМ есть ничтожная величина. В большинстве остальных случаев модификация обеспечивает меньшую оценку погрешности последующей итерации. В одномерном случае всегда справедлива с более сильная оценка dk+i < --dk.

1 + с

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

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

С помощью понятия полупроизводной получена теорема 4.1, которая в части оценки удаленности решения от заданной точки является расширением теоремы Канторовича ([18], гл.XVIII, § 1, т. 6) о сходимости метода Ньютона для уравнения д(х) = 0 на случай, когда известна оценка гм> ||(р'(ж))-1||. В сравнении с теоремой Мысовских ([58], т. 1) условия теоремы 4.1 слабее, а оценка удаленности всегда меньше. Используемая в теореме 4.1 оценка r0 > ИО/'Ос))-1!! допускает огрубление до гм, и тогда условия теоремы 4.1 содержатся в условиях теоремы Гавурина ([7], т. 1), а оценки удаленности совпадают. Т.е. теорема 4.1 является усилением теоремы Гавурина в части оценки удаленности корня, ибо в ней требуется лишь локальная липшицевость д' вместо более сильного условия локальной ограниченности производной Гато от д' в теореме Гавурина. Когда го < ги, Т. 4.1 является расширением теоремы Гавурина и дает лучшую оценку удаленности.

При существенно иных предположениях, чем в теоремах Канторовича, Мы-совских, Гавурина и 4.1, об отображении д получена теорема 4.2 об оценке удаленности решения от заданной точки. Для одних значений характерных параметров лучшую оценку предоставит теорема 4.2, для других — 4.1 (оценка из последней не хуже, чем в теоремах Канторовича, Мысовских, Гавурина). Суждения теорем 4.1 и 4.2 относятся к разным классам отображений: П и С1,1 (см. опред. 4.1, 4.2). В классе П с помощью дифференцирования по итерации получены результаты о сходимости метода Ньютона, не содержимые в полученных для класса С1'1 теоремах Канторовича, Мысовских, Гавурина и не объемлющие их.

Дифференцирование по итерации также было основным инструментом обоснования метода квадратичной оптимизации (МКО). МКО, т.е. итеративное решение нелинейной программы f{x) —> min при ограничениях д(х) < О посредством решения аппроксимирующих квадратичных программ на итерациях, описан довольно давно. Однако в общем случае, несмотря на великолепные практические результаты для некоторых классов задач, теоретического обоснования метода не было. В гл. 5 выяснено при каких условиях можно гарантировать сходимость, оценена скорость сходимости, погрешность по двум последовательным итерациям и удаленность решения от начальной точки.

Усиление результата автора в [28] было достигнуто в §5.2 в виде утверждения о сходимости метода к а — решению задачи А — из любой точки в окрестности а. Размеры окрестности являются некоторой функцией "естественных" ограничений: на скорость изменения производных функций-ограничений и элементов гессиана, а также на "сплющенность" системы градиентов функций-ограничений.

В §5.3 приведен критерий остановки итеративного процесса. Он позволяет оценить удаленность решения от текущей итерации по известному расстоянию до предыдущей итерации и тем же "естественным" [30] ограничениям. В §5.4 по константам задачи и значениям параметров задачи А в точке определяется корректность выбора этой точки в качестве начальной для МКО.

В §5.5 показано, что сходимость МКО можно сохранить и при приближенных вычислениях итерационных параметров. При этом функции V/(xk), J(xk), д(хк) должны вычисляться с возрастающей точностью, иначе сходимость не гарантирована. Гессиан же целевой функции может быть вычислен лишь в начальной точке, но это будет стоить сужения множества, на котором гарантирована сходимость. В конкретных приложениях [67], [30]. погрешности в вычислениях гессиана практически не сказывались на скорости сходимости, и, поскольку вычислительные затраты на итерацию существенно снижались в сравнении с немодифицированным МКО, общие вычислительные расходы на достижение желаемой точности были заметно ниже.

Очень тесно к МКО примыкают способы построения аппроксимаций нелинейных программ на итерации. Этот вопрос рассмотрен в гл. б. В §6.1 исследована проблема выбора узлов для построения линейной по параметрам аппроксимации. Как выяснилось (т. 6.5), для успешного построения этой аппроксимации достаточно включить в состав узлов такой набор, что задача линейной интерполяции на нем всегда имеет единственное решение. Бели аппроксимирующий агрегат линеен по аргументам, то таким набором, как известно, является набор узлов в общем положении. Если аппроксимирующий агрегат квадратичен по аргументам, то как для вещественного случая, так и для комплексного найдены алгоритмы порождения узлов, обеспечивающие существование и единственность решения задачи аппроксимации, и попутного отыскания параметров аппроксимирующего агрегата.

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

Важное место в МКО занимает процедура решения квадратичной программы. Исследована модификация метода Била (§6.9), позволяющая за конечное число шагов найти решение. Собственно метод Била преобразован в матричную форму, удобную для программирования на ЭВМ. Поиск допустимой начальной точки реализован в виде алгоритма с большим количеством общих с методом Била операторов, что позволяет создавать компактные программы. Модификация позволяет решать квадратичные программы с вырожденной матрицей квадратичной формы, а также воспринимать часть переменных ограниченными по знаку, а часть - нет. Создан простой алгоритм предотвращения зацикливания, при его использовании доказана конечность числа итераций, необходимых для достижения конечного или бесконечного решения или установления факта отсутствия решения.

Идее повышения эффективности вычислительного итеративного процесса служат и другие методы высоких порядков. К ним можно отности, как метод Чебышева решения скалярного уравнения f(x) = 0, так и его дискретный аналог, использующий обратную интерполяцию. В гл. 7 получена оценка скорости сходимости дискретного метода Чебышева неравенством вида хк-х\ < tie"cA*<n> , (*) где положительные и, с - константы, зависящие от начальных данных, a Ai (п) - наибольший корень характеристического полинома tn — tn~l -. — 1 = 0. Доказано

2 > Ai(n) > 2п/(п + 1)

Аналогичные оценки получены для метода Мюллера решения уравнения f(x) = 0 (прямая интерполяция по трем узлам на каждой итерации).

Поиск одномерного безусловного минимума при помощи п-точечной прямой интерполяции на каждой итерации имеет, как оказалось (гл. 7), аналогичную (*) оценку скорости сходимости, только вместо Ai(n) там следует поставить i/i (п) - наибольший положительный корень полинома tn — tn~2 — . — 1 = 0. Доказано п + V5n2 - 4)/(2п + 2) < i/i (n) < (1 + л/5)/2.

Поскольку 0 < 2 - Ai(n) < 0.01 при п > 7 и при п > 8 справедливо 0 < (1 + л/5)/2 — i/i (п) < 0.017, использование большого количества узлов в дискретном методе Чебышева и методе минимизации при помощи п-точечной интерполяции нецелесообразно.

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

Значительно усложняется поиск экстремума в комбинаторном пространстве. Отсутствие каких либо "направлений" предъявляет высокие требования к алгоритмам порождения таких пространств. Удачный алгоритм позволяет производить крупные отсечения заведомо худших комбинаций.

Для пространства сочетаний предложен названный здесь пачечным алгоритм, обладающий "порядком минимального изменения" также как и двоично-отраженный зеркальный код Грея. Бели каждый элемент исходной выборки из п элементов снабжен некоторым весом и требуется найти комбинацию с суммой весов наиболее близкой к заданной, то отсечения на основе пачечного алгоритма позволили сократить число рассматриваемых комбинаций примерно на два порядка, когда п = 14, что оказалось весьма существенным для общего алгоритма дозирования.

Для задач составления расписания сеансов связи был предложен алгоритм, жадный по концу заявок. Он показал высокую эффективность решения этих задач при численной реализации. Причем для задачи 1 из §8.1, он был не хуже по быстродействию алгоритма решения транспортной задачи, к которой она может быть приведена [73], а для задачи 2 поиск конкурентов алгоритму, жадному по концу заявок, пока остался безуспешен.

Оптимизацию распределения капиталовложений часто сводят к минимизации функционала вида = jf Е ШФ))*г с ограничениями вида Yl£i(t) = u(t), щ > 0, неизвестными здесь являются функции Xi(-), .,£„(•); Ах,., Ап — веса; функция и возрастает.

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

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

В гл. 9 предложен алгоритм генерации минимайзера функционала весьма общего вида: с ограничениями вида £ «»(£)= u(t) и щ Неизвестными здесь являются отраслевые планы ui(-),.,un(-). Функции {/,•} предполагаются имеющими кусочно непрерывную вторую производную.

Вначале доказана оптимальность результата, выдаваемого этим алгоритмом, для случая u(t) = t (т. 9.6). Затем — оптимальность планов, когда и — произвольная возрастающая функция с разрывами.

Список литературы диссертационного исследования доктор физико-математических наук Михеев, Сергей Евгеньевич, 2006 год

1. Айзеке Р. Дифференциальные игры. М., 1967. 479 с.

2. Базара, Шетти. Нелинейное программирование. Теория и алгоритмы. -М., 1982. 583 с.

3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. Н. Численные методы. М., 1987. 598 с.

4. Веденялина С. И., Кирин Н.Е. Интерполяционный метод высокого порядка одномерного поиска минимума // Динамика систем и управление. Саранск, 1986. С. 69-75.

5. Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. М., 1998. 176 с.

6. Воеводин В. В. Вычислительные основы линейной алгебры. М., 1977. 552 с.

7. Гавурин М. К. Нелинейные функциональные уравнения и непрерывные аналоги итерационных методов // Изв. ВУЗов, 1956. № 5 (6). С. 18-31.

8. Гантмахер Ф. Р. Теория матриц. М., 1988. 552 с.

9. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М., 1985.

10. Гельфанд И.М. Лекции по линейной алгебре. М., 1971. 272 с.

11. Гилл Ф., Мюррей У. Численные методы условной оптимизации. М., 1977. 290 с.

12. Далецкий Ю.Г., Крейн М.Г. Устойчивость решений дифференциальных уравнений в банаховом пространстве. М., 1970, 534 с.

13. Даугавет В.А. Метод дополнительного базиса в квадратичном программировании // Вестн. Ленингр. ун-та. 1992. Сер. 1, вып. 3. С. 31-38.

14. Дуткевич Ю.Г., Петросян JI. А. Игра с "линией жизни". Случай 1г захвата // Вестн. Ленингр. ун-та, 1969.№ 13. С. 31-38.

15. Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М., 1988. 440 с.

16. Зубов В. И., Петросян JI. А., Мейлахс А. М., Михеев С. Е. Отчет по теме: "Задача оптимального распределения капиталовложений". JL, 1971. 21 с.

17. Камачкин A.M., Михеев С.Б., Евстафьева В.В. Модели колебаний в нелинейных системах. СПб.: изд. СПбГУ, 2004. 194 с.

18. Канторович JI. В., Акилов Г. П. Функционльный анализ. М., 1977. 744 с.

19. Карлин С., Стадден В. Чебышевские системы и их применение в анализе и статистике. М., 1976. 568 с.

20. Картан А. Дифференциальное исчисление, дифференциальные формы. -М., 1971. 392 с.

21. Кирин Н. Е., Сеисов Ю.Б. Оптимизация процессов в управляемых системах. Ашхабад, 1991. 264 с.

22. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М., 1972. 496 с.

23. Красносельский М.А. и др. Приближенное решение операторных уравнений. М., 1969. 455 с.

24. Красовский Н. Н. Игровые задачи о встрече. М., 1970. 420 с.

25. Кюнци Г., Крелле В. Нелинейное программирование. М., 1965. 304 с.

26. Липский В. Комбинаторика для программистов. М., 1988. 213 с.

27. Лорин Г. Сортировка и системы сортировки. М., 1983. 384 с.

28. Михеев С. Е. О сходимости метода последовательной оптимизации // Математическая физика. 1976. № 20. С. 52-58.

29. Михеев С. Е. Расширение теоремы Куна-Таккера на унимодальные функции // Математическая физика. 1977. № 21. С. 43-44.

30. Михеев С. Е. Вычислительные аспекты метода последовательной оптимизации // Вопросы механики и процессов управления. JL: изд. Ленингр.-унт., 1980. Вып. 4. С. 223-242.

31. Михеев С. Е. Одна задача распределения ресурсов и минимизация сепа-рабельных целевых функций // Вопросы механики и процессов управления. Л.: изд. Ленингр.-унт., 1980. Вып. 4. С. 169-179.

32. Михеев С. Е., Каменев В. В. О формировании пространственной волны в популяции амброзиевого листоеда // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 1989. Вып. 12. С. 52-63.

33. Михеев С. Е. Сходимость дискретного метода Чебышева и метода Мюллера // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 1992. Вып. 15. С. 89-99.

34. Михеев С. Е. Методы высоких порядков в задачах нелинейного программирования и решения уравнений. СПб.: изд. СПбГУ, 1992. 95 с.

35. Михеев С. Е., Томина О. Н. Алгоритмы решения одного семейства задач обслуживания // Дифференциальные уравнения с частными производными (общая теория и приложения). СПб, 1992. С. 93-100.

36. Михеев С.Е., Силина Е.К. Одна модель колебательного движения // Вестник С.-Петербург, ун-та. 1994. Сер. 1, вып. 1 (№ 1). С. 72-76.

37. Михеев С. Е., Никольский А. М. Метод спуска в задачах аппроксимации // Процессы управления и устойчивость: Труды XXX научн. конф. -СПб., 1999. С. 119-125.

38. Михеев С. Е. Релаксационное ускорение. ВИНИТИ № 2089-В98,3.6.1998. 11 с.

39. Михеев С. Е. Зависимость конкурентоспособности труда от уровня акцизных налогов. ВИНИТИ №3012-В98,16.10.1998. 19 с.

40. Михеев С.Е. Выпуклая квадратичная интерполяция // Вестник С.Петербург. ун-та. 1999. Сер. 1, вып. 2 (№ 8). С. 42-48.

41. Михеев С. Е. Релаксационное ускорение на основе областей достижимости // Вестник С.-Петербург, ун-та. 1999. Сер. 1, вып. 3 (№ 15). С. 29-35.

42. Михеев С. Е. Управление конкурентоспособностью. СПб.: изд. СПбГУ, 2001. 36 с.

43. Михеев С.Е. Нелинейные методы в оптимизации. СПб.: изд. СПбГУ, 2001. 276 с.

44. Михеев С.Е. Эффективность релаксационного ускорения // Николай Ефимович Кирин (сборник статей). СПб., 2003. С. 183-197.

45. Михеев С.Е. Зоны безопасности в играх с линией жизни // Вестник С.-Петербург, ун-та. 2003. Сер. 1, вып. 3 (№ 17). С. 69-78.

46. Михеев С. Е. Комбиниационное дозирование // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 2003. № 19. С. 271-277.

47. Михеев С. Е. Метод трехкоординатного спуска // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 2004. № 21. С. 128-136.

48. Михеев С. Е. Выпуклая квадратичная аппроксимация // Вычислительные технологии. Новосибирск, 2004. Т.9, №4. С. 66-76.

49. Михеев С. Е. Спуск по базисным направлениям с ограничением // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 2004. № 22. С. 116-126.

50. Михеев С. Е. Конкурентоспособность и трудоемкость // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 2004. № 23. С. 118-141.

51. Михеев С. Е. Сходимость метода Ньютона на различных классах функций // Вычислительные технологии. Новосибирск, 2005. Т.10, №3. С. 72-86.

52. Михеев С. Е., Позняк JI.E. Улучшение оценок в одной теореме Мысовских о методе Ньютона // Труды международной конференции "Устойчивость и процессы управления". СПб, 2005. Т. 2. С. 876-885.

53. Михеев С. Е. Существование и опенка решения нелинейного уравнения в банаховом пространстве // Вестник С.-Петербург, ун-та. 2005. Сер. 10, вып. 3. С. 13-27.

54. Михеев В. С., Михеев С. Е. Точная релаксация модифицированного метода Ньютона // Процессы управления и устойчивость: Труды XXXVII международной научн. конф. СПб., 2006. С. 119-125.

55. Михеев С. Е., Позняк JI.T. Одна новая теорема существования решения нелинейного уравнения в банаховых пространствах // Вестник С.Петербург. ун-та. 2006. Сер. 10, вып. 3. С. 35-43.

56. Мухачева Э. А., Рубинштейн Г. Ш. Математическое программирование. Новосибирск, 1987. 274 с.

57. Мысовских И.П. К вопросу о сходимости метода Ньютона. // Труды Матем. ин-та им. Стеклова. 1949. №28. С. 145-147.

58. Мысовских И.П. О сходимости метода JI.B. Канторовича решения функциональных уравнений и его применениях // Докл. АН СССР 70. 1950. №4. С. 565-568.

59. Никольский С. М. Курс математического анализа. М., 1973. Т. 1. 432с.

60. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М., 1975. 558 с.

61. Островский А. М. Решение уравнений и систем уравнений. М., 1963. 220 с.

62. Панин В. М. Нормализованный метод конечных штрафов в задаче нелинейного программирования // Докл. АН СССР. Сер. мат. 1989. Т.304, №3. С. 549-552.

63. Петросян JI. А. Игры преследования с "линией жизни" // Вестн. Ленингр. ун-та. 1967. №13. С. 76-86.

64. Пономарев В.М., Горичев Ю.В., Городецкий В. И. Последовательная оптимизация нелинейного закона управления // Нелинейная оптимизация систем автоматического управления / Под ред. В. М. Пономарева. -М., 1970. С. 15-19.

65. Пономарев В. М., Литвинов Л. П. Основы автоматического регулирования и управления. М., 1974. 439 с.

66. Поцелуев А. В., Майборода JI. А., Пономарев В. М. и др. Статистический анализ и оптимизация следящих систем. М., 1977. 360 с.

67. Пшеничный Б. Н., Данилин Ю. М. Численные методы в экстремальных задачах. М., 1975. 319 с.

68. Пшеничный Б. Н. Метод линеаризации. М., 1983.

69. Пшеничный Б. Н., Панин В. М. Линейная сходимость методов линеаризации. // Докл. АН СССР. Сер. А. 1987. №4. С. 16-18.

70. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. М., 1971. 476 с.

71. Розенвассер Е. Н., Юсупов Р. М. Чувствительность систем автоматического управления. М., 1981. 464 с.

72. Рокафеллар Р. Т. Выпуклый анализ. М., 1973. 469 с.

73. Танаев В. С., Шкурба В. В. Введение в теорию расписаний. М., 1975. 256 с.

74. Титчмарш Е. Теория функций. М., 1982. 463 с.

75. Уилкинсон Дж. X. Алгебраическая проблема собственных значений. -М., 1970. 564 с.

76. Ульман Дж. Основы систем баз данных. М., 1983. 334 с.

77. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. М., 1960. 656 с.

78. Хартман Ф. Обыкновенные дифференциальные уравнения. М.: Мир, 1970, 720 с.

79. Хедли Дж. Нелинейное и динамическое программирование. М., 1967. 506 с.

80. Хейгеман JL, Янг Д. Прикладные итерационные методы. М., 1986. 446 с.

81. Химмельблау Д. Прикладное нелинейное программирование. М., 1975. 534 с.

82. Хлямков А. В. Замечание о сходимости метода парабол // Матем. заметки. 1998. Т. 63, вып. 2. С. 309.

83. Шилов Г.Е. Математический анализ: Специальный курс. М., 1961. 436 с.

84. Эрроу К.Дж., Гурвиц JL, Удзава X. Исследования по линейному и нелинейному программированию. М., 1962. 334 с.

85. Юдин Д. В., Голынтейн Е. Г. Линейное программирование. М., 1963. 424 с.

86. Miheev S. E. Stability zones in rhesus-systems // Abstracts of Invited Lectures к Short Comm. Delivered at the Second International Colloquium on Differential Equations, Bulgaria, 1991. P. 191.

87. Miheev S.E., Kokina V. G. Measurement errors control in the 3-points interpolation method // Intern. Congr. on Computer Systems and Applied Math. St.Petersburg, 1993. P. 272.

88. Miheev S.E. A non Linear Differential Model of Sheduling // Proc. ICI&C97 (Intern. Conf. Inform. Control). St .Petersburg, Russia, 1997. P. 835840.

89. Miheev S.E. Contraction of attainability domains in a game of pursuit // Game Theory and Applications / Eds. L. Petrosjan, V. Mazalov. Nova Science Pbl., N.Y. 1996. Vol. 2, P. 193-207.

90. Miheev S. E. Contraction of Attainability Domains in a Game of Pursuit. Nova J. Mathematics: Game Theory and Algebra. Nova Science Publ., N.Y. 1997. Vol.6, № 2/3. P. 147-161.

91. Miheev S.E. Relaxation Acceleration in Iterative Methods // Proceedings volume from the 11th IFAC Workshop "Control Applications of Optimization 2000". 2000. Vol. 1. P. 243-248.

92. Miheev S. E. Tax system & and interest to new industrial capacities // Труды Международной конференции "Математическое моделирование социальной и экономической динамики" (MMSED-2004). М., 2004. стр. 212216.

93. Rothnie J.B., Lozano Т. Attribute based life organization in a paged memory environment // Comm. ACM. 1974. Vol. 17:2. P. 63-69.

94. Schmidt J., Trinkaus H. Extremwetermittlung mit Funktionswerten von mehreren Veranderlichen // Computing. 1966. Bd. 1. S. 224-232.

95. Schwetlick H. Numerische Loesung nichtlinearer Gleichungen. Berlin, 1979, 346 S.

96. Spath H. The damped Taylor's series method for minimizing a sum of squares and for solving systems of nonlinear equations // Comm. ACM. 1967. Vol. 10. P. 726-728.