Как бы не совершенствовалась вычислительная техника, улучшение алгоритмов, закладываемых в нее остается вечно желанным. Всегда будут существовать задачи вычислительного типа, которые окажутся не доступны объединенным усилиям «металла» и математического обеспечения из-за нехватки быстродействия, памяти, несходимости итеративного процесса или просто отсутствия алгоритма решения.
В этой работе рассматриваются численные методы решения нелинейных уравнений и задач нелинейного программирования. Улучшение сходимости численных методов предлагается проводить с помощью принципа минимальности. Для исследования вопросов сходимости развивается аппарат дифференцирования по итерации на основе полупроизводной. Предлагаются новые алгоритмы.
Вводной для глав 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 VF (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 =. = А&bdquo- = 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*, (*) где положительные и, с — константы, зависящие от начальных данных, 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). Затем — оптимальность планов, когда и — произвольная возрастающая функция с разрывами.
