автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Методы высоких порядков в задачах нелинейной оптимизации

- а л» «я

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

МИХЕЕВ Сергей Евгеньевич

МЕТОДЫ ВЫСОКИХ ПОРЯДКОВ В ЗАДАЧАХ НЕЛИНЕЙНОЙ ОПТИМИЗАЦИИ

05.13.16- Применение вычислительной техники, математического моделирования, математических методов п научных исследованиях

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

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

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

Официальные оппоненты:

доктор физико-математических наук, профессор

Чернецкий В.И. доктор физико-математических наук, профессор Смоктий О.И. доктор технических наук, профессор Терентьев И.В.

Ведущая организация - Вычислительный центр РАН.

Защита состоится 2 У- 11_ 199"?т. в часов

на заседании диссертационного совета Д.003.62.01 при Санкт-Петербургском институте информатики и автоматизации РАН по адресу: 199178, Санкт-Петербург, 14 линия д. 39.

С диссертацией можно ознакомится в библиотеке Санкт-Петербургского института информатики и автоматизации РАН.

Автореферат разослан ^ ^дд^ г

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

А.В. Копыльцов

Общая характеристика работы

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

Близкая к квадратичной целевая функция / аппроксимируется квадратичной

f(x, хк) = f{xk) + Vf(xk)(x - хк) + (х - хк)тН}{хк){х - *2)/2,

и следующая итеративная точка определяется, как точка минимума функции f(x,xk) по г. Под названием метод параболоидов (для поиска безусловного экстремума) это можно встретить у Лж. Ортеги и В. Рейнболдта еще до 1970 г. Метод параболоидов имеет свои трудности, в частности при наличии не положительных собственных чисел у матрицы Гесса II он не применим. Исправление ситуации добавлением at(x — хк)2, а* > 0 к квадратичной аппроксимации восходит к К. Левенбергу (1944), к С. Гольдфельду, Р. Куранту, Т. Троттеру (1966 г.).

Метод линеаризации Б.Н. Пшеничного и Ю.Н.Данилина -итеративный метод решения нелинейных программ общего вида - обходит вопрос об области действия итеративной аппроксимации введением шага и введением добавки (х — хк)2/2 в f(xk) + Vf(xk)(x — хк) - линейную аппроксимацию целевой функции. Функции-ограничения в нем заменялись на линейные аппроксимации

д(х,хк) = g(xk) + Vg(xk)(x - хк).

В одной из модификаций метода линеаризации для ускорения сходимости предлагалось использовать квадратичную добавку [х — хк)т Ьхх(х — хк) к линейной аппроксимации целевой функции, где - гессиан соответствующей функции Лагранжа. В случае линейности функций -ограничений Ьхг — • Метод линеаризации использовался В.А. Даугавет в задачах чебышевского приближения без ограничений и с линейными ограничениями (1982, 1983 г.)

Минимизация на каждой итерации /(х,хк) по х при ограничениях д(х,хк) < О, именуемая в работе методом квадратичной оптимизации (МКО), как часть метода последовательной оптимизации управления летательным объектом применялась В.М. Пономаревым (с 1970-х). Там целевая функция и функции-ограничения формировались в виде математических ожиданий функционалов на решениях систем дифференциальных уравнений. Поэтому "цена" каждого значения функции была очень высокой и даже существенное усложнение алгоритма минимизации легко окупалось повышением скорости сходимости. Конкретные реализации метода выявили высокую скорость сходимости метода во многих случаях, но теоретическое обоснование сходимости было найдено только для узкого круга. Не исследованным тогда остались скорость сходимости, выбор начальной точки, правило остановки, разобранные в этой работе.

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

Составной элемент МКО - тот или иной способ решения квадратичной программы. Одним из удобных для расширения на случай смешанных ограничений вида Ах < а и Вх = Ь и сочетания переменных ограниченных и неограниченных по знаку является метод Вила. В нем представляет интерес вопрос эффективного построения (по занимаемой алгоритмом памятью) начальной таблицы и проблема предотвращения зацикливания.

В одномерном случае итеративное решение скалярного уравнения д{х) = 0 и минимизация скалярной функции /(х) при помощи экстраполяционных полиномов порядка большего единицы восходит к П.Л. Чебышеву. Интерполяционные поли-

номы можно встретить в методе Мюллера и интерполяционном методе высокого порядка поиска одномерного минимума Н.Е.Кирина (1968 г.). Однако разнообразие методов на основе интерполяции, перспективных для исследования, этим далеко не исчерпывается.

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

Ряд задач на оптимизацию сводится к минимизации сепа-рабельных функций /(Ьх,..., Ьк) — когда = В,

6,- >0, г — 1, п. Таковы, например, многие модели в экономике. Оптимизация разбиения памяти в базах данных при раз-делышом хешировании приводит к минимизации математических ожиданий Л/х = (при спецификации одного поля в запросе), либо М2 = + 91-/2ь*), (когда специфицируется несколько полей) с дополнительным требованием целочи-сленности &!,...,&„. Задачи минимизации М\ и Мг без требования целочисленности можно рассматривать как непрерывные нелинейные аппроксимации исходных, имеющие простые алгоритмы решения в случае выпуклости /].,--.,/п- Использование таких аппроксимаций для итеративной минимизации при спецификации одного поля предлагалось Лж. Ритчи и Т. Лозано, при спецификации нескольких - А. Ахо и Дж. Ульманом. Неясной оставалась ситуация, когда налагается требование лишь целочисленности 2Ъ\

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

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

вать алгоритмы минимального изменения, но даже в простейших случаях целевой функции вида f(x) = l^z, — В\ минуют вопрос об отсечениях. Для решения задач минимизации на пространствах с большим числом элементов за разумное время необходимо изыскивать новые алгоритмы, допускающие включение отсечений.

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

1. Установлены предельно широкие условия, когда решение нелинейной программы f(x) —► min есть часть решения системы

гМ<о

V/(ar) + Wg{x) = 0 & А > 0 к \д{х) = 0 к д{х) < 0 и обратно.

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

Vf(xk)(x-xk) + (x-xk)TH(xk)(x-xk)/2— min

3. Установлены критерии выбора начальной точки для МКО.

4. Установлены оценки вида — ж|| < а||;ск+1 — хк\\ для МКО.

5. Получена теорема о сходимости метода Ньютона решения системы нелинейных уравнений д(х) = 0 для одного класса функций.

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

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

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

9. Приведен и обоснован алгоритм решения задач вида

где «1, ..мп, и - неубывающие функции, возможно разрывные.

10. Для задач вида ~'' m'n' где D ~ множество неотри-

b£D

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

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

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

Апробация материалов исследования проходила на семинаре кафедры информационных систем, на семинаре по теории управления под руководством В.И.Зубова в Санкт-Петербургском университете, на семинаре по дифференциальным уравнениям под руководством Н.М.Матвеева в Педагогическом университете им. А. Герцена, на семинаре в ВИ РАН, на семинаре в UMIST (University of Manchester Institute of Science and Technology), на международных конференциях: CDE'IV (Руссе, Болгария, 1987), SICDE (Болгария, 1991), CSAM'93 (С.-Пб.), Interval 94 (С.-Пб.), ICI&C97 (С.-Пб.). По теме диссертации опубликовано 20 работ общим объемом 250 стр., из них одно учебное пособие (6 печатных листов).

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

Основной объект исследования здесь - нелинейные программы общего вида

/(х) — min, (1)

rgD

где / - скалярная функция, именуемая целевой, D - именуемое допустимым некоторое множество в области определения функции /.

По своему характеру первая глава является вводной для глав 3,4,6 и ее можно отнести к основам нелинейного программирования. Допустимое множество в этих главах задается формулой

£>-{x|ff(z)<0}, (2)

где х - n-мерный вектор, д - ш-мерная вектор-функция (х, д -столбцы). Исходной задачей в первых шести главах является нелинейная программа (1) с допустимым множеством (2), именуемая для краткости задачей А.

Поиск у функции Лагранжа, задаваемой формулой

F(x,X) = f(z)+\g(x),

где Л - m-мерная строка, седловой точки (г, А), определяемой неравенствами

F(x,X) > F(x,A) > F(x,X) VA > 0, Vx 6 Rn,

именуется задачей В. Связь между решением задачи А и х-составляющей решения задачи В описана в теоремах Куна-Таккера. В случае дифференцируемости функций / и д, как

известно, седловая точка необходимо удовлетворяет системе Куна-Таккера

YTF(x, А) = 0, к Л > 0, к VxF(x, А) < О, & X4\F(x, Л) = О,

(3)

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

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

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

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

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

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

Слабая унимодальность подразумевает связность множества минимальных значений.

Установлено, что функция / слабо унимодальна, если для любого числа с множество Мс = {x\f(x) < с} выпукло.

Теорема 1.5. Пусть у задачи С существует решение (а, А) и выполнены условия: 1) функции fug слабо унимодальны; 2) / - непрерывна; 3) V/(а) ф 0.

Тогда а есть решение ЗА.

Эту теорему нельзя усилить снятием или ослаблением какого либо условия. Однако,

Теорема 5-2. Условие непрерывности функции / можно заменить на одно из следующих

2.1) у задачи С не существует решения (а, А) и в векторе А менее, чем п ненулевых компонент, (га - размерность а);

2.2) любая опорная в а гиперплоскость к допустимому множеству {г|д(а;) < 0} имеет не более одной точки касания с ним;

2.3) касательная гиперплоскость в а к N имеет только одну общую точку с его границей. в

По аналогии со строго выпуклыми функциями можно ввести еще один класс функций.

Функцию / назовем строго унимодальной, если для любого действительного с множество {я|/(х) < с} строго выпукло.

Теорема 1.5-3. В теореме 1.5 вместо непрерывности / можно потребовать строгой унимодальности для f либо для д. ц

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

Напрямую (без использования ЗВ - задачи посредника) доказан более сильный результат.

Теорема 1.6. Пусть 1) у задачи А существует решение £•; 2) существует Ч/(х)\ 3) существует точка х* такая, что

• {х* - х) < 0, г € I = Ш{х) = 0}.

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

Условие 3) теоремы 1.6 неявно содержит следующее утверждение: "все существенные ограничения имеют в решении задачи А ненулевые градиенты". Если его сформулировать в явном виде, то оставшаяся часть может быть изменена таким образом.

Теорема 1.7. Пусть 1) у задачи А существует решение х\ 2) существует У/(£); 3) V» € I = {¿^.(¿О = 0} ЭУ^(ж) ф 0;

4) функция д слабо унимодальна и непрерывна;

5) существует х* такая, что д(х*) < 0 (условие Слейтера);

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

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

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

П(х) = VДхк)(х - хк) + (х - хк)тН(хк)(х - х*)/2 — пнп, \ g(x,xk)±g(xk) + J(xk)(x-xk)< О

относительно х. Здесь Я - гессиан функции /, 1 - матрица, строки которой есть У<7,, г — 1,тп.

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

Теорема 3.2.1. (О сходимости метода квадратичной оптимизации). Пусть для всех х,х + А из области задания V С Яп выполняются условия:

1) \\3(х + Д) — 7(х)||2 < ¿||Д||2, где 7 - матрица из градиентов компонент вектор-функции д;

2) существует положительное число г такое, что

г > 5р((ССт) ) для всех С - баз J\

3) ||Я(Я + Д)-Я(х)||2</||Д||2;

4) существует положительное число /? такое, что eigЯ(a;) > ¡3, где eig - операция нахождения наименьшего собственного числа;

5) \\Ъ/(х)\\2<р-

6) ЬРл/? < (37) существует внутри V точка а - решение задачи А;

8) существует решение системы 3{х){у — ж) + д(х) < 0 относительно у;

9) Бр Н(х) < Ярн-Тогда:

а) существует положительное число 6 такое, что любая точка шара С V может служить начальной для метода квадратичной оптимизации (МКО)

б) в качестве этого числа можно взять любое <5 > 0, удовлетворяющее одновременно С V и неравенство

С{6) = р~Ч(1+ ЬБрН^Щг + у/Ир/0) + Ьу/?р) < 1;

в) скорость сходимости МКО можно оценить неравенством

Если функции-ограничения выпуклы, то условие 8 в теореме 1 можно опустить.

Весьма распространенными являются такие нелинейные программы, в которых часть ограничений или все имеют вид равенства. К этим нелинейным программам возможно применение МКО с использованием соответствующих квадратичных программ. Теорема 1 с небольшим изменением применима и к этому случаю. Поскольку ограничение-равенство всегда существенно, условие 2 можно ослабить, потребовав обязательного включения в матрицу С всех линейно независимых градиентов левых частей ограничений-равенств (ЛЧОР). С другой стороны, в формулировке теоремы, как будет показано ниже, должно присутствовать требование линейной независимости градиентов ЛЧОР. Обе эти модификации обеспечиваются условием 2'. Существует г > О такое, что верно г > 8р((С£т)-1) для всех таких б - баз ], в которых включены все градиенты ЛЧОР.

И очевидно, должно быть изменено условие 8. 8'. Существует у - решение системы

^9г(х)(У ~ + 9>(х) <; 0, г = 1, т, где знак <{ есть = для ограничений-равенств и < для ограничений-неравенств. в

Если все ограничения имеют вид равенств, то справедлива теорема, отличная от теоремы 1 отсутствием условия 8 и заменой условия 2 на условие

2") существует число г > 0 такое, что г > Бр((,7т ,7)-1).

В §3.3 приводится критерий остановки итеративного процесса. Он позволяет оценить удаленность решения от текущей итерации по известному расстоянию до предыдущей итерации и тем же "естественным" ограничениям.

Справедлива следующая оценка расстояния от текущей итерации до допустимого множества.

Лемма 3.3.1. Пусть: 1) вектор-функция д : V С Я™ —> йт имеет производную I; 2) д(у) + 3{у){г — у) < 0;

3) \\:т(х + Д) - /т(г)||2 < £||Д||2 V*. г + Д е V.

Тогда ||з+(г)||2 < 1>(г — у)2/2, где операция "+" заменяет в столбце отрицательные компоненты на нули. В том же случае, если в 2) выполняется равенство, то справедлива оценка 11^)112 <1(,-у)2/2.

Для случая ограничений-равенств в ЗА справедлива Лемма 3.3.2. Пусть выполнены условия 1), 2) леммы 1 и также для всех г,х + ДеУ: 3) 8р((7(х),7(г)т))-1) < г;

4) ещ II > ¡3 > 0-, 5) Бр Я < Я;

6) |^/(*)||2 < р; 7) ||Л(* + Д) - Я(х)||2 < /||Д||2.

И пусть имеются три последовательные итерации а;0, х1, х2 метода квадратичной оптимизации. Тогда

Н^-а^Нг < у/г+(1 + Ву/?)*/3-2 ■

■ [Ьу/?{р + ¡(х1 - х°)2/2) + /Цх1 - х°||2/2] Их1 - :г0||2. Теорема 3.3.1. Пусть выполнены условия леммы 3.3.2 и Их1 - Х°||2 < ^(2р + 1(х1-х0)2),

^г+а + Бр [ЬМр+ - *°)2) + [{Xх - *°)2] <

< с < 1,

тогда метод квадратичной оптимизации, начатый в х°, сходится и имеет место оценка

Цх1 — а|[г < Цат1 — £°||2——-—.

1-е

Для случая ограничений-неравенств справедлива Лемма 3.3.3 Пусть функции fug нелинейной программы удовлетворяют условиям для всех х, х + Д £ V : 1) ||Н(х + Д) - Н(х)||3 < /||Д||2; 2) eig Н(х) > /3 > 0; 3) ||V/(z)||2 < р : 4) Sp Н{х) < В;

5)||7(г + Д)-7(х)||2<1||Д||2;

6) для всех G, баз J, верно Sp((G(x)GT(a;))_1) < г;

Обозначим через г1 итерацию, полученную методом квадратичной оптимизации из х1, положим v = х1 — х° и пусть

7)||S||2 = »<1; 8){у|||у-х1||2<^}сК; введем полином от v

СО) = у/Ць + (w + Ьф{р + /г2/2))(1 - 1/2 + и) + 1))];

где v/* =

Тогда ||х2 — ж1!^ < vC(v), где х2 - итерация по МКО от х1. Теорема 3.3.2. Пусть выполнены все условия леммы 3.3.3, а также C(v) i vy/*[2v + Lyjr{p + lv2 /2)] < с < 1. Тогда МКО, начатый в х° и имеющий следующую итерацию х1, сходится к некоторой точке а, причем

где С1 («>) = ОД, Ск+1{v) = C(vCk(v)) VJb > 1. в

В §3.4 по константам задачи и значениям параметров задачи А в точке определяется корректность выбора этой точки в качестве на- чальной для МКО. В качестве вспомогательного результата доказывается один вариант теоремы об обратном отображении.

Лемма 3.4.1. Пусть для каждой точки интервала [0,5] приращение функции у можно оценить следующим образом:

|¡/(s + Д) - y(s)| < ф)|Д| + о(в, Д), где z(s) - конечна, неотрицательна и суммируема по Лебегу: o(s, Д)/Д -»• 0 при Д 0. Тогда

\y{s) ~ l/(0)| < [' z(t)dt. Jo

Лемма 3.4.2. Пусть д - отображение 0у С Л" в П, С й", обладающее в V - некоторой окрестности уо, внутренней точки множества 0.у, следующим свойством: с точностью до малых второго порядка по отношению к ||г/2 — 2/1II

9(2/2) - 9(2/1) « <3(2/0(2/2 - 2/1) +0(2/2,2/1),

где С} - непрерывная в т/о невырожденная матрица, причем < с и (¿о = <5(2/о), вектор-функция О удовлетворяет

неравенству \\0{у2, гл)|| < и||у2 - 2/111,и ис < 1.

Обозначим во = д(г/о)-Тогда в некоторой окрестности точки во определено единственное непрерывное обратное отображение у — р(в) такое, что

1 )?(р(«)) = в; 2)р(50) = у0; 3) \\у-уа\\ < г _ ^ _ £\\s-so Ц.

где £ > 0 и может быть выбрана сколь угодно малой за счет выбора размеров окрестности точки «о.

Теорема 3.4.1. Пусть внутри некоторой области V Е Яп для всех + Д выполнены условия:

1) г > Эр((сСг)-1) для всех С1 - баз строк матрицы <7;

2) \УТ{Х + А) — /г(ат)||2 < 1/||Л||2;

3) ||Г/(а:)||2 < р; и также

4) минимизируемая функция / выпукла, причем ограничены снизу величиной ¡3 > 0 собственные числа ее гессиана Я;

5) ис < 1, где

с = ^г + (1 + Яр Н^г)2(32, и = Ьй, 2у/гр.

6) для некоторого вектора х° выполняется

П= {г|||х-а:0||2 < у} С V,

где 7 = «(2/о)г^Г. Я = ^Д*0) + д(х°) -

набор из первых т' наибольших по модулю компонент д(х°), т' - ранг матрицы ./(я0).

Пусть, кроме того, 7) д - слабо унимодальна и

8) значения всех компонент д в некоторой точке не положительно (выполнено условие Слейтера).

Тогда у ЗА существует решение а, и а'£й.

Теорема 3.4.2. Если выполнены условия теоремы 3.2.1, а также

для некоторой точки х° выполняется

{х|||х — х°||2 < 2-/} С V, 7 = дт-£—,

р(х°) - набор из первых т' наибольших по модулю компонент д(х°), т' - ранг матрицы J(x0). Тогда метод квадратичной оптимизации дает сходимость к а - решению ЗА, ||хо — а||2 < 7 и скорость сходимости будет оцениваться неравенством

|И+1-а||2<С||**-а||2. ■

Частным случаем задачи А является поиск решения системы нелинейных уравнений д(х) — О (ПРС).

Т.е. при Б = {х|у(х) = 0} и произвольной целевой функции задача А совпадает с задачей ПРС. Нетрудно заметить, что каждая итерация по МКО тогда есть итерация по методу Ньютона для задачи ПРС.

Несмотря на большое количество результатов по сходимости метода Ньютона, применением идей доказательства сходимости МКО в §3.5 получена новая теорема о сходимости метода Ньютона для одного широкого класса функций. Там же дан контрпример, демонстрирующий в некотором смысле необходимость условий этой теоремы. (В одномерном пространстве указана невыпуклая функция и начальная точка на пределе условий теоремы, порождающие цикл в методе Ньютона). Определение. Назовем сг,с1-классом множество функций д, удовлетворяющих следующим условиям: для всех х из Б С Я"

1. Нпг|| 1{х + А) — /(х)||/||Д|| < Ь{х), т.е. матрица Якоби имеет локальную константу Липшица в х;

2. = г(х) фоо; 3. Ь{х)г{х) < а > 0.

Лемма 3.5.1. Пусть матрица Л(х) невырождена и имеет локальную константу Липшица Ь{х) в области И. Тогда обратная матрица А-1 тоже в области Б имеет локальную константу Липшица

L-(x)<\\A-l(x)\\4(x). Теорема 3.5.1. Пусть функция д принадлежит и,с1-классу и

1. 1 - г0сгу/д2(х°) = е > О, где г0 = r(z°);

2. шар S^g принадлежит D, где do = —

Тогда существует решение а системы (1), удаленное от начальной точки х° не более, чем на do-

Теорема 3.5.2. (Локальная сходимость метода Ньютона). Пусть функция д принадлежит <т,Б-классу и некоторая оценка d удаленности решения от начальной точки удовлетворяет

1) crd = со < с, где с есть решение уравнения

С(с) = (ес - 1 - с)/с= 1; (расчеты показывают, что с £ (1.25,1-26));

2) шар о принадлежит D, где p=l + C(ad). Тогда:

а) метод Ньютона, начатый в зг°, корректно определен и сходится к конечному решению а, все итерации лежат в Spxt]

б) скорость сходимости оценивается неравенством

||;rfc+1 — а|| < С{о\\хк — alDUr^ — а||;

в) решение а системы д(х) = 0 единственно в шаре i. Следствие. Если d < 1, то из разложения С в ряд следует C(rLd) < C(rL)d. Поэтому если верны неравенства

\\хк — а||C(rL) < 1 и Цг* — а|| < 1, то справедлива следующая оценка скорости сходимости

||:ck+1 — а|| < C(rL)\\xk — а||2. н

Теорема 3.5.3. Пусть функция д принадлежит <т,В-классу и выполнены также условия

1) го<T\Jg2{xQ) < j^g, где с - корень уравнения С(с) = 1;

2) SPJ°CD, где р = 1 + C(ado), d0 = - ln(l - г0<Гу/РЩ)/<т. Тогда:

а) существует решение а системы д(х) = 0, единственное в шаре

б) метод Ньютона, начатый в х°, корректно определен и сходится к конечному решению а;

в) скорость сходимости оценивается неравенством

11х<:+1 — а11 < С(сг\\хк — аЮЦж* — а||.

Теорема 3.5.4. Условия теоремы 3.5.2 являются также и необходимыми в том смысле, что при их нарушении возможно найти функцию и начальную точку, для которых сходимость отсутствует. |

В §3.6 исследуются возможности модификации МКО (ММ-КО). Оказывается J(xk), д(хк) должны вычисляться

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

Теорема 3.6.1 (О сходимости ММКО). Пусть выполнены условия 1-8 теоремы 3.2.1 и Бр Н0 = Брц, тогда

а) существует число 5 > 0 такое, что любая точка х° шара из V может служить начальной для ММКО;

б) скорость сходимости ММКО можно оценить неравенством

н*^1 - а||2 < С(||х° - а||2, ||х* - а||2)||х* - а||2, где функция С определяется равенством

С(М) = БрнО-^^рЬ + Щ/Р + ^Ьр + 1{<1 + 6)}/¡3 < 1;

в) в качестве этого <5 можно взять любое решение неравенства

С(М)< 1. ■

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

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

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

В §5.1 рассмотрен дискретный аналог метода Чебышева решения скалярного уравнения f(x) = 0. Здесь для получения каждой следующей итерации предлагается использовать обратную интерполяционную задачу с п последними узлами. Вычисляются в узлах х\,...,х„ величины у; =/(аг,), г = 1,п. Находится свободный член а интерполяционного полинома Р такого, что Х{ — Р{х{), i = I,п. Один из узлов xi,...,xn замещается на а в соответствии с правилом исключения.

Пусть

М = sup |F(")(r)| • sup \f'(x)\/n\,

т

где F - обратная к / функция. Тогда ключевым для сходимости ДМЧ является поведение решения разностного уравнения

tk - tk-i - - tk-n = In Л/, k>n. (5)

связанного с итерациями по ДМЧ соотношением i,- > ln|j/,|. Пусть наибольший корень уравнения V(d) = vn— vn~1 —...— 1 =0 - характеристического для (4) - обозначен через Ai.

Теорема 5.1.2. Наибольший положительный корень характеристического уравнения удовлетворяет соотношению

2 > А! > ц(тг) = 2п/(п + 1). (6)

Непосредственное приближенное вычисление корней характеристического уравнения дает следующие оценки А*(п) снизу для А1(п):

А " 2 3 4 5 6 7

А* 1.61803 1.83928 1.92756 1.96594 1.98358 1.99196

1.33333 1.50000 1.60000 1.66666 1.71428 1.75000

Все цифры в таблице для А*(п) верны в том смысле, что А*(п) + 0.00001 > А^п).

Теорема 5.1.3. Справедливы неравенства Ах (га +1) > АЦ?«), при п = 2,3,...

Таким образом, для п = 2,7 можно использовать табличные оценки А*(п) с погрешностью не превосходящей 0.00001, для п = 8,200 - оценку А^г) > А(7) с погрешностью не большей 0.0001. Для теоретических исследований можно использовать оценку (б) при всех п с погрешностью не более 2/{п + 1).

Теорема 5.1.4. Сходимость ДМЧ можно гарантировать, когда начальные приближения удовлетворяют условиям

1> "~</М\ук\, к=Т~И. (7)

Скорость сходимости по значениям функции можно оценить неравенством

Ь \ук\ < сХ\{п) + (1п М)/( 1 - п), (8)

где к больше п и с определяется по формуле

с= тах (2~* 1п( "~у/м Ы)), (9)

или, более точно, с = тах*=1(...|П(А^*(п) 1п( п~\/~М ■

Потенцирование оценки логарифма (8) приводит к традиционному виду оценки

Ы< n~VM к>п,

где D = ес.

Для погрешности по аргументу имеет место оценка

\xk - х\< L -Vm Dx*, к > п,

где L = inf ~lf'(x) = sup F'(y). x у

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

Введем обозначения L = inf l/'C-OI- sup |/"(:с)|(& — а) и М= sup \f"'(x)\/(6L).

т£(а,Ь)

Теорема 5.2.1. Пусть

In |i — arfc| < сА?(3) — 1п\/л7, (10)

где с < 0, к = 1,2,3, Ai(3) - наибольший положительный корень характеристического уравнения tj3 — г?2 — f — 1 = 0. Тогда (10) справедливо с той же константой с и для к = 4,5,.... Или в другом виде: пусть

с - maxjt=li2,3(ln - хк\у/М)< 0,

тогда

\х-хк\< Dx"^/VM, Jt = 4,5,6, ...

где D = ec и Ai(3) € (1.83928,1.83929).

Те же идеи лежат в исследовании поиска одномерного минимума на основе n-точечной интерполяции (§5.3). Рассматривается задача поиска безусловного локального минимума скалярной функции f G С"а ь) на множестве (а, Ь). Предлагаемый итерационный метод решения этой задачи состоит в том, что на каждом шаге очередное приближение к точке минимума

находится как точка минимума интерполяционного многочлена, построенного по ранее найденным приближениям. Пусть имеются узлы xk,xk+i, ...,Xk+n~i достаточно близкие к решению ж. Вычислим в этих узлах значения функции и построим интерполяционный полином р степени п — 1:

P(s«) =/(*»)> г = к,к + п-\. Каким-либо способом определим точку локального минимума интерполяционного полинома, ближайшую к х в том же смысле, что и предыдущие узлы. Включим ее в состав узлов под обозначением Хк+п- Узел с наименьшим индексом, то есть х исключим.

После выбора начальных узлов Хк, к — 1 ,п, этот алгоритм определяет все последующие Хк, к — п + 1,п + 2,.... Положим М= sup |/(n)(77)|/(/(n — 1)!). Ключевым для этого

метода является разностное уравнение tk — tk-2~••■— tk-n — InM с характеристическим уравнением

= vn - vn~2 - ... - v - 1 = 0. Его наибольший корень v\(п) участвует в оценке скорости сходимости вида теоремы 5.1.4 вместо Ai(n).

Лемма 5.3.1. Многочлен V имеет единственный положительный корень корень в интервале

(p(n) = (n + V5п2 - 4)/(2п + 2), /2 = (l + V5/2), и все его корни - простые.

Непосредственные приближенные вычисления корней характеристического уравнения дают следующие оценки А*(п) снизу для Ai(n):

Ai П 3 4 5 6 7 8

А» 1.32471 1.46557 1.53415 1.57014 1.59000 1.60134

fi(n) 1.17539 1.27177 4/3 1.37617 1.40776 1.43202

Все цифры в таблице для А*(п) верные в том смысле, что А*(п) + 0.00001 > Ах(гг) > А*(п). Конечное число цифр у

иррациональных ц(п) получено посредством простого усечения. С точностью до Ю-5 с округлением в большую сторону Д = /î(oo) = 1.61804. В силу леммы 1 верно Ai(oo) = fi.

Теорема 5.3.3. Справедливо Ai(n+ 1) > Ai(n), п = 3,4,... .

Таким образом, для п = 3, 8 можно использовать табличные оценки А*(л) с погрешностью, не превосходяшей 0.00001, для п = 9,97 оценку Ai(n) > А*(8) с погрешностью не более Д — А*(8) < 0.017. Для теоретических исследований можно использовать вместо Ai(rc) его оценку /i(n) при всех п с погрешностью не более

Ц-ц(п) = 0.5(l + >/5 — (n + V5n2-4)/(n + l)).

Имеет место ^(98) > А*(8) и ц(п) У fi.

Теорема 5.3.4. Итеративный метод на основе n-точечной интерполяции корректно определен и сходится к решению исходной задачи, если

2) сужен интервал (а, 6) так, что х 6 (а, 6) и

1 = inf \r(u)\-J2 sup y-J^l(6-a)-2>0;

ue(a'6) (г - 2)!

3) выполнено Sj С (a,b), где p = DXl/ n~\ÎM, либо x,ь£(а,6), fc = l,n, С (a,b) совместное

^ = (Dxî + Da"+' )/ n'\/~M или с p= 2f'{xk)/ inf |/"(x)|.

V / (а.ь)

4) выполнено с = max (ln|z — a:,t| < 0, либо с = max (lnl n'VM f\x*)/ inf |/"(z)||) A~* < 0. Скорость сходимости тогда оценивается формулой

<DxÎ/"~¥m, D=ec, к>1.

В §5.4 проведено исследование сходимости метода трехточечной интерполяции (частный случай метода §5.3) при наличии погрешности в измерениях целевой функции. Оказалось,

что при повышении общих вычислительных затрат на повышение точности измерений на каждом последующем шаге возможно сохранить тип сходимости. Пусть {я*;}?3 последовательность, порожденная итеративным процессом, использующим приближенные значения целевой функции ук вместо точных ук = /(¿к), к — 1,2,.... Погрешность измерений и оценку удаленности текущей итерации от решения зададим формулами

А к-Ук-Ук, \хк-х\<гь, к- 1,2,...

Теорема 5.4.1. Лля обеспечения скорости сходимости порядка А = Л1 (3) описанного выше итеративного процесса достаточно получать значения функции с погрешностями, удовлетворяющими

\{хк-1 - хк-2){хк-2 - - Ajt-1 - (Ук - Ук-i)-

•((A* - Ak-i)(xk-2 - хк) - (Дк_2 - - xk-i))/Q]/Q\ <

<Т6/{1 + 6),

где Q = 2[(ук - Ук-\){хк-2 - Xfc) - (ук-2 - - £<fc-i)],

Г=е*, /={1,2,3},

где ¡¡, i £ I, - оценки удаленности первых трех узлов от решения, причем их нумерация должна обеспечить не возрастание оценок. Когда становятся известными оценки удаленности от решения произвольных трех подряд идущих узлов, можно воспользоваться формулой Т — есА4, I = {к — \,к— 2, к — 3}; в обоих случаях величина 6 есть некоторая константа из (0,1).

Справедлива также оценка скорости сходимости

\xk-x\<DxklM{\ + 6), D = ec, к> 1,

М= sup \f"\v)\/ inf \Г(Ч)\, пе(а,Ь) пе(а,Ь)

С = шах^А-11п(г,/(М(1 + ¿))) должно быть отрицательно.

Глава 6 возвращает к задаче поиска многомерного экстремума, для узкого, но важного в приложениях класса сепарабель-ных функций вида

п

/(*)=£/'(*•■)-ГПП1, (И)

1

Оптимизация капиталовложений в развитие городского коммунального хозяйства или экономики района, области, страны может быть смоделирована (в первом приближении) как задача минимизации некоторой сепарабельной целевой функции. Тогда в формуле (11): г - номер отрасли, х,- - количественное состояние ¡-й отрасли. Поступление капиталовложений может быть дискретным, непрерывным и смешанным по времени. В двух последних случаях минимизировать нужно целевой функционал вида

о

Обозначения: £,-(/) - количественное состояние ьй отрасли (переменной) в момент времени I, г = 1, п; х,-(и,-)-количественное состояние ¡-й отрасли после вложения в нее и,- средств, £,-(«;) - неубывающая с непрерывной производной с;(и{) > 0 функция; х,-е - норматив ¿-й отрасли, то есть состояние, в которое желательно привести ью отрасль; х,о = £»(0) - количественное состояние 1-й отрасли в начальный момент t = 0; общее финансирование и(<) - неубывающая, непрерывная справа и в момент окончания Т непрерывная слева функция времени; (I = и(Т); реальный план - это набор п неубывающих функций времени г/1(<),..., «„(*)> подчиненных условию и(<) = и«(0> эти функции из набора - реальные отраслевые планы. Они могут быть рассматриваемы также как функции от общего финансирования с областью задания (7. Последняя, при наличии скачков у функции и(<), не совпадает с отрезком [0, {/]. Тогда можно рассмотреть (виртуальный) план их(и), ...,ип(и), являющийся расширением реального. Потребуем также чтобы и,(и) были неубывающими функциями и выполнялось условие и = для всех и. Производные и,-(и) = с1щ(у.)/с1и - интенсивность финансирования ¡-й отрасли после вложения и средств; относительная нехватка Н{(и,-) = (х!е — х,(«,))/х,е.

Лемма 6.1.1. Отраслевые (виртуальные) планы удовлетворяют условию Липшица

О < щ(и + А) - щ(и) < Д УД > 0 \Л',и. Лемма 6.1.2. Отраслевые планы представимы в виде

где подынтегральные функции подчинены условиям и,(и) > О, и ^ = и Для всех и 6 [О, /У].

Если 1>;(и) = k{u)[xie/c^{ui)}Hi{ui), где к - нормирующий коэффициент такой, что ^ гЧ по прежнему равна 1 для всех и, то набор функций

будем называть опорным планом, а функции ^(и),..., 1'п(и) -управлениями.

Теорема 6.1.1. Определение опорного плана корректно в том смысле, что существует соответствующий набор непрерывных функций ыЦи),..., и„(ы).

Теорема 6.1.2. Для того, чтобы план, удовлетворял условию

необходимо и достаточно, чтобы он был опорный. Следствие 1. Опорный план - единственный. Следствие 2. Так как отношения относительных нехваток при опорном плане в силу теоремы 2 не зависят от суммарного финансирования и, расчет опорного плана можно вести по формулам

Г

и>(и) = I у> (й)<1й.

щ(и) = 1>;(ы)с/й, г = 1,п, и£[0,[/],

Щ(щ{и)) = Я,-(О)

К'И) ВД

Уг'.;', и

VI = к(и)Н^)х1е/а{щ) = к{и){х^ - хг0)/с,(и,), где к(и) - новый нормирующий коэффициент, определяемый из

Зависимость поступления средств от времени можно находить путем подстановки в и,(к) функции u(t), то есть

Mt)

щ(1) = ui(u(t)) = / Vi(u)du.

Jo

Теорема 6.1.3. Пусть минимизируемый функционал имеет вид

т

F= ( У>,■/<(","(0)Л.

J о

т>0, ЛМО) = (i + u(o) <£/<£>,

с,- = const, Zi - решение уравнения //(z,-) = 0, Аг- >0, г = 1,п. Тогда для того, чтобы минимизирующий набор wi(i),..., fn(0 был опорным планом необходимо и достаточно коэффициентам

Ai,..., А„ приписать значения А° = кх{е/с{Н{(0) = kxio/c{, i = 1,п, к - произвольное положительное число.

Следствие 1. Пусть требуется минимизировать функционал

m п Г = 1 1 = 1

где r+i > щг > 0 для всех г, г и

5>.т = ¿Л-, fi{x) = (1 - - Cix/xi)2.

i

Тогда минимизирующий набор иц,..., ипг будет опорным планом (т.е. Hi (и,- Г)/Я,(0) = Hj(ujr)/Hj(0) для всех i,j,r) в том и только в том случае, если Ai,..., А„ приписать значения

\ 0 xie

А,* = р— , где р-произволыюе положительное число. С,Я;(0)

Следствие 2. Теорема 3 верна и в том случае, если на u\(t),..., un(t) наложены дополнительные ограничения вида

щ(Т) = kHi(0)/ci: i=l, п.

совместные с условием Х^и^Т) = и{Т).

Теорема 6.1.4. Пусть функция общего финансирования и(2) не убывает и непрерывна справа в точках разрыва, функции отраслевого финансирования иг(2) = имеют обобщенные производные, удовлетворяющие соотношению ¿¡(<) = где и,- - реальные управления, подчиненные условиям 1>,(<) > О,

= 1 при всех <€[0,П и пусть минимизируемый функционал имеет вид

где fl,..., /„ - выпуклые функции с кусочечно-непрерывной второй производной, заданные на [0, {/]. Тогда оптимальный реальный план и^),..., и„(<) должен удовлетворять интегральным уравнениям

где реальные управления *>»(?) однозначно определяются через управления и; (и) описанным ниже способом.

Назначаем I'¡(0 = '•'¿(«(О) для всех моментов непрерывности функций ы(<) и

для моментов разрыва. Здесь П = [u(i — 0),u(i)], А - скачок u(t) в момент t.

Управления, в свою очередь, строятся так

Алгоритм AI. Положим Vj(u) = 0, если либо существуют производные /¿(«¿) > /¿(uj), либо не существует /,'(и,). И

пусть соотношение /¡(щ) = min//rl(um) определяет множество

индексов а 3 - его подмножнество, выделяемое соотношением //'(и,-) = 0. Если 3 пусто, положим

m

ц(и) = (/г(ч)]0иг(ч))-1)-1

-1

Если ] не пусто, положим ь,(и) = 0 для г £ I \ 7; а для г 6 / функции 1',-(и) можно выбрать произвольными измеримыми, но в соответствии с ограничениями Vi(u) > 0 и ^ г, = 1. ■

Дискретное программирование тесно связано с вопросами порождения пространств при реализации алгоритмов на ЭВМ. В §7.2 предложен названный здесь пачечным алгоритм порождения комбинаторного пространства (сочетаний), обладающий порядком минимального изменения так же, как и двоично-отраженный п-разрядный код Грея, но позволяющий вводить эффективные отсечения в некоторые задачи. В частности, в алгоритмы обслуживания комбинационного дозирования. Суть последнего в следующем.

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

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

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

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

Прямой (обратный) подалгоритм

1° Сдвигает, если возможно, пачку влево (вправо); если сдвинуть пачку нельзя - впереди (сзади) пачки стоит код-единица или же пачки подошла к концу (началу) кодового слова, то возвращается из стека кодовое слово и положение пачки, управление возвращается к тому алгоритму, который вызвал активный.

2° Засылает кодовое слово и положение пачки в стек.

3° Если размер пачки был больше 1, то сокращает его на 1, оставляя вне пачки первую (последнюю) код-единицу. Если размер пачки был равен 1, то вместо п. 4° выполняется п. 1°.

4° Передает управление обратному (прямому) алгоритму. ц

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

1) формирует начальное слово, содержащее единственную пачку, занимающею крайне правое (левое) положение;

2) передает управление прямому (обратному) алгоритму.

Ива варианта такой инициализации прямой и обратной, соответственно, приводят к порождению всего пространства, но в инвертированном порядке.

Численные эксперименты показали сокращение числа рассматриваемых комбинаций примерно на два порядка при п — 14.

Результаты выносимые на защиту. Теоремы о связи решений нелинейной программы и системы Куна-Таккера.

Обоснование метода квадратичной оптимизации - метода решения нелинейных программ. Модификация метода Била.

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

где «1, ...ип,и - неубывающие функции, возможно разрывные.

Алгоритмы поиска минимума сепарабельных целевых функций в дискретных пространствах.

Алгоритмы обслуживания процесса комбинационного дозирования.

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

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

■т

Выяснено, что 8-10 узлов - разумный предел, превышение которого реального увеличения скорости сходимости не дает.

Новый алгоритм порождения комбинаторных пространств позволил резко поднять быстродействие комбинационного дозирования.

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

По теме диссертации опубликованы следующие работы :

1. Алгоритм решения // Задача оптимального распределения капиталовложений, Ленингр. ун., Л. 1971.

2. Оптимальное расположение наблюдателей при каскадном наблюдении // Исследование операций и статистическое моделирование, Ленингр. ун., Л. 1972.

3. О сходимости метода последовательной оптимизации // Математическая физика, вып. 20, Наукова Лумка, Киев, 1976.

4. Расширение теоремы Куна-Таккера на унимодальные функции // Математическая физика, вып. 21, Наукова Лумка, Киев, 1977.

5. Моделирование экономико-производственных систем 1, ВИНИТИ н.80070823, 1980.

6. Моделирование экономико-производственных систем 2, ВИНИТИ н.7013087, 1982.

7. Вычислительные аспекты метода последовательной оптимизации // Методы математического анализа управляемых процессов, Ленингр. ун., 1980.

8. Одна задача распределения ресурсов и оптимизация сепара-бельных целевых функций // Методы математического анализа управляемых процессов, Ленингр. ун., Л., 1980.

9. Планирование распределения ресурсов с дискретным временем //Труды ЛКИ: Математические модели и САПР в судостроении, ЛКИ, 1982.

10. Задача распределения и смешанная целочисленная программа //Труды ЛКИ: Математические модели и САПР в судостроении, 1985.

11. О формировании пространственной волны в популяции ам-брозиевого листоеда // Математические.-методы моделирования и анализы управляемых процессов, Ленингр. ун., Л., 1989.

12. Модель уединенной волны в популяции амброзиевого листоеда. Conference on Differential Equations and Applications 4, Bulgaria, 1989.

13. Stability zones in Rhesus-systems // Second Intern. Colloquium on Differential Equations, Bulgaria, 1991.

14. Сходимость дискретного метода Чебышева и метода Мюллера // Вопросы механики и процессов управления, вып. 15, 1991.

15. Методы высоких порядков в задачах нелинейного программирования и решения уравнений. С.-Пб. ун., С.-Пб., 1992.

16. Алгоритмы решения одного семейства задач обслуживания // Дифференциальные уравнения с частными производными (Общая теория и приложения), СПб., 1992.

17. Properties of a subclass of recurrent functions // International Congress on Computer Systems and Applied Mathematics, St. Petersburg, 1993.

18. Measurment errors control in the 3-points interpolation method // CSAM'93, St.Petersburg, 1993.

19. Automatization of Interval Calculation // International Conference on Interval and Computer-Algebraic Methods in Science and Engineering, St.Petersburg, 1994.

20. Miheev S.E. A non Linear Differential Model of Sheduling. Proceedings of ICIfcC'97 (International conference on informatics and control). St.Petesburg, Russia, 1997, p. 835-840.

Подписано к печати 28.10.1997, заказ № 4"/3 Тираж 100?кз, объем 2 п.л. ПМЛ НИИХ СПбГУ. 198904, Санкт-Петербург, Университетстский пр. д. 2.