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

Санкт-Петербургскиа Государственный Университет

на правах рукописи УДК 519.853

МИХЕЕВ Сергей Евгеньевич МЕТОДЫ ОПТИМИЗАЦИИ НА ОСНОВЕ НЕЛИНЕЙНЫХ АППРОКСИМАЦИЙ

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

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

Санкт-Петербург, 100Б

Работа выполнена на кафедр- информационных систем факультета прикладной математики - процессов управления Санкт-Петербургского университета

Н^/чный консультант: член-корр. РАН, доктор физшсо-матемашческих наук, профессор В.И.Зубов

Официальные оппоненты: член-корр. Международной АН Высшее Школы, доктор физико-математических наук, профессор Э.А.Толкачен доктор физико-мате!.: лических наук, профессор В.В.Дикусар доктор физико-«а-п.г.штических паук, профессор В.Е.Чилига

Ведущая грх'анизация - Институт Информатики РАН

Защита состоотся 1Р95 г. в >% часов на

заседании дассертациопого сс-ета Д-063.77.33 по защите диссертация на соискание ученой стегани доктора наук в Сатсг-Пь ¿ербургском государств енном университете по адрес! Санкт-Петербург, в.О., 10 линия, д. 33, ауд. 88.

С диссертацией можно ознакомится в Научной библиотеке им. М.Горького СПОГУ, Университетская набережная, дом 7А

Диссертация разослана г-7 с^^с ___1995 г.

Ученый секретарь диссертационного сонета А.П.,..абш

0Б1НАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Аппроксимацию целевой функции квадратичной вида

ГСх,хк5 = ГС хЬ + УГСхкХх-хкЭ + Сх-хк5тН(.Схк1Сх-х'!Э/2

с определением следующей итеративной точки, как точки минимума функции ?сх.хкэ по х, под названием метод параболоидов (для поиска безусловного экстремума) можно встретить у Ди.Ортегч и В.Решз-бодцга еще до 1970 г. Метод парабол .вдов имеет свои трудности, в частности при наличии не положительных собственных чисел у матрицы Гесса нг он не применим. Исправление ситуации добавлением с^сх-х*}2. а" >о к квадратичной аппроксимации восходит к К.Ле-венс^р.у (1944), к С.Годьдфелъду. р.Куранту, т.троттеру (1966 г.).

Мето" линеаризатчм Б.Н.Пшеничного и Ю.Н.Данилина - итеративный метод решения нелинейных программ обшрго вида - обходог вопрос об области действия итеративной апроксимации введением иа, э и введением добавки сх-хкэ3/2 в гсхкз+<7гсхкэсх-хкэ - линейную аппроксимацию целевоь функции. Функции-ограничения в нем заменялись на линейны« аппроксимации

дСх.хЬ = дСхкЭ УдС хкЭ С х-хк5 .

В одаой из модафгасац"* метода линеаризации для ускор 1иг сходимости хфедяагалось использовать квадратичную добавку сх-хЪЧ^сх^1'-' к линейной ацпроксмащш целев^л функции, где - гессиан со'>

ветствувдей функции Лаграша. В случае линейности функций-ограничений х Hf. Метод линеаризации испакьзовался В.А.Даугавет i задачах чебышен ¡кого г\«5->икения без ограничений и с линейным ограничениями (1982, 1883 г.)

Минимизация на каждой итерации icx.x'b по х при ограниче ниях gCx.xb о (именуемая в работе методом квадратичной оптими защи) как часть метода г.осждовательнса оптимизации управлени летательным объектом применялась В.М.Пономаревым <с 1970-х). Tai целевая функция и Функции-ограничения формировались в виде мзтема ткческих ожиданий функционалов п пепйииях систем дифференциальны уравнений. Поэтов "цена" каждого значения функции была очень высо кой и даже существенное усложнение алгоритма миымизащш легко оку па..ось повкшегчем скорости сходимости. Конкретные реализации метод выявили высокую скорость сходимости метода во многих случаях, н теоретическое обоснование ^ходииоста было найдено только до узхог круга. Не исследованным тогда остались скорость сходимости, вабо начальной точки, правило остановки, разобранные в атой работе.

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

Составной я лемент МКО - тот та иной способ решения квадратам ной программы. Одвим из удобных для расширения на случай смешанна ограничений вида s а и вх = ъ и сочетания переменных ограяу ченых и неограниченных по знзхсу является метод Била. L нем пре ставляет интерес вопрос, эффективного построения (по заникаемс алгоритмом памятью) начальной таблиц

В одномерном случае итератизг.е решение скалярного урзвнеш gCxD=0 и минимизация скалярной фуг.кции f(x) прк ломощи экстрапс ляционных полиномов порядая большего едаяину вог.чодит к П.Л. Чебыш ву. Интерполяционные полиномы можно встретить в методе Мхшера интерполяционном методе высокого порядка поиска одномерного мшим: иа Н.Е.Кирша (1968 г.). Однако разнообразие мегодо» на оснм интерполяции перспективных д~я исследования этим далеко нг иечерго вается.

Значения реальных целевых фракций, как правило, «огут измэря'

¡я только с некоторой погрешностью. Ее влияние на сюдамость интер-шяциояных методов исследовалось ешэ А.Островским (1980), но к ^стоящему времени кабор методов, снабженных полньм анализом влия-ия ошибок изм&рений относительно невелик.

Ряд задач на оптимизацию сводится к минимизации сепарабельных ункций ввда .....ькэ = е лсь^ при Е ь = в. г. о. I =

7п . таковы, напрмер, многие модели в экономике. Оптимизация раз-иения памяти в базах данных при разделенном хешировании приводит к

ь.

инимизации математических ожиданий м = п р-^2 1 (при специфика-

ь.

ИИ одного поля в запросе), либо иа = е (когда

гьцифицируется несколько полей) с дополнительным требованием цело-

исленности ь^.....ь^. Задачи минимизации м4 и мг без требо-

ания целочисленноета можно рассматривать как непрерывные нелиней-

ые аппроксимации исходных , имеющие простые алгоритмы решения в

лучае выпуклости г.....г . Использование таких аппроксима-

ш дяя итеративной минимизации при спецификации одного поля пред-

агалось Дк.Ритчи и Т.Лозано, при спецификации нескольких - А.Ахо

Дд.Ульманом. Неясной осталась ситуация, когда налагается требова-

ь.

ю лишь ц: яочислеяности 2

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

Несколько снижаются вычислительные затраты на определение; зна-!ниа целевой функции, если в упомянутой последовательности от ком-шации к комбинации происходит минимальное изменение состава. Кода »я позвол-юг создавать алгоритмы минимального изменения, но даже простейших случаях вида гею - |е*. - в| мину;сг вопрос об отсе-(ниях . Ддя решения задач минимизации на пространствах с большим голом элем тгов за разумное время необходимо изыскивать новые ал-|ригмы, допускающие включение отсечений.

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

лиз сходимости метода квадратичной ошимизации. Произвести необг дикые для применения в МКО модификации алгоритма решения квадрата ной программы. Лать ана-шг сходимости методов на основе Интерпол; ции полиномами высоких степеней с возможным учетом погревшос измерении. Разработать алгоритмы регэаия "елинеаных программ ] дискретных и комбинаторных пространствах.

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

Наюная новизна состоит в следуь-ß'"

1. Установлены предельно широкие условия, когда пешение нелинейной про:фаммы гсхэ —► min есть часть решения системы

31 * > So

VfCxD + кЧдСЮ =0 & \ > -> & ХдСхЭ = О & дСхЭ 5 О.

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

k-fl 1с

дующую лтерацию х по итераци;: х как решение кза.цратичнс программы

WCx^Cx-xS + Cx-xkDTHCxk3Cх-уЪ'З -► min

к _ к к , g (К >+Vg<x )"ÎK-K>5o

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

4. Установлены оценки вида ixk+1-ii s а»хк*1-х|с» для МКО.

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

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

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

8. Определена степень повышения т^чноста измерена от шага к шагу 6

¡охраняющая порядок сходимости, для квадратичной скалярной сяггими->ации интерполяционным многочленом.

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

jETCu Ct)5dt -» min ,

о 1 1 u=£ u.

-де uk____un u - неубывающие функции, возможно разрывные.

.0. Для задач вида Е'г-сь.э -► min, где ь - множество неотри-

1 1 ЬеВ

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

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

[рактичаская значиность ßafiüIU. ОСНОВНЫе результаты СВЯЗЭНЫ С ЧИС-

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

.пробаиия материалов исследования проходила на сеишнаре кафедры нфс;мационных систем, на семинаре по теории управления под руко-юдством В.И.Зубова в Санкт-Петербургском университете, на семинаре и дифференциальным уравнениям под руководством Н.М.Матвеева в [едагогическом университет им. А.Герцэна, на семинаре ь ВЦ РАН, на

еминаре В umist (University of Manchester Institute of Science and

echnoiogyi, на международных конференциях: csam-эз (С.-Ш.). ntervai 94 (С.-Пб.), cde:'iv (Руссе, Болгария. 19fc7), sicde (Болга-\т, 1991). По теме диссертации опубликовано 16 работ общим обьемом 60 стр., иь них одно учебное пособие (6 печатных листов).

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

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

ГСхЭ -► го1п, (1

к«0

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

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

В 4 <х|дСхЭ 5 О, (2

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

Функция Лагранжа для задачи А радуется формулой

ГСх.ХЭ = Г С ¡С + ХдОО,

где х - т-мерная строка. Поиск у фу. хции Лагрггока седловой точю сх.хэ, определяемой неравенствами

рсх.хэ г: рсх.хэ £ рсх.хэ у х г о. у x «г я",

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

•усх.хэ = о & ^РСх.ХЭ 3 О & X ? О & Х7ХГСх.ХЭ =» о. (3)

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

*

рнкций гид.

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

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

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

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

Определения 1 и 2 подразумевают связность множества минималь-ых значений.

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

.Установлено, что Функция г сласо унимодальна, если любо-о числа с множество ис = с х | гсхэ з с > выпукло.

еорека 1.5. Ость г5 функции г и я слабо ун: .«оДальны; 5 1" - непрерывна; зэ у задачи С существует решены са.\э; > дг ас! гсоо * о. Тогда а есть решение ЗА.

Интересно, что условие непр рывности г з.^сь необходимо в ом смысле, при его нарушении можно построить гример, когда решение адачи С не есть решение задачи А. Оно может быть заменено на одго

з следуюодс:

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

.2) лоЗэл опорная в с. гиперплоскость к допустимому множеству х | с к хп < о инее! не Оолее одной то«ни касаниг с ним;

.3) касаголн.ая гиперплоскос'1 , проведенная в и к множеству

у

<x i rc>o < гс«о>, имеет только одну ибщую точку с его границей.

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

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

R теореме 5 вместо непрерывности г можно потребовать строго! унимодальное ЛИ ДЯЯ f ¿JÍO ДЯЯ д.

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

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

Творена i .6. Пусть п у ".эдачи А сущг твует решение х;

аз существует Тичка х" такая, что

Уд^хЗ-Сх*- ¡О < С. ( « I 4 '<! | д.СэЬ = 0>;

зз существует vrcio.

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

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

Теоромв 1.7. ПУСТЬ

13 у задачи А существует решение х;

23 V ¿ « I i <í|g.CíO=0> 3 Vg^ib / О;

-о функция д слабо унимодальна и непрерывна; 43 существует х* такая, что дсх'э < о (условие Слейтера); 53 существует vrcio.

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

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

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

' Гсх.хЬ = ?ГСхк)Сх-хкЗ + сх-хк3тнсхкЭсх-хкЭ-►

9< »,х >5о

дСх.хкЭ ^ ХхкЭСх-хкЭ + дСхкЭ

тносигельно х. здесь н - гессиан функции г, т.е. матрица из торых производных - матрица из * = ГТт. т.е.

В № исследуется локальная сходимость МКО.

еореиа 3.2.1- (О сходимости метода квадратичной оптимизации).

Пусть для всех х. х + д из области задания V с я" выполнятся У СЛОВИ.-.:

э исх + го - кхэи $ иди, где компонент вектор-функции д;

э существует положительное число г

г г 5рс«згз~* для всех а - баз

3 « ИСх + дз - НСхЭ i * лд»;

з существует положительное число р

3 «7ГСхЗНг 3 р ; > Цр-/ г>г Л /?;

) существует с» в V - решение задачи А ;

) сущэствутг решени системы л.хзсу - хз + дехэ < о относительно у.

ЗГДЭ:

) существует полоните льное число а такое, что любув точк;; шара

з - матрица из градиентов такое, что

такое, что «ад нехз >

н

S^ с v можно взять начально® для метода квадратичной оптимизации;

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

СС<5Э * -/rTV^CCi + L Sp toЭ<5С1 + /ñr l.p/(T> + tr/~TрЭ < 1;

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

Их**1 - al _. CC«xk - al D-«xk - а« . ■

а г г

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

Ее^лма распространенными являются такие нелинейные программы в которых часть ограничений или все имеюгг вид равенства. К эти не„.;Лейным прс раммам возможно применении МКп с использованием соответствующих квадратичных ^грограмм.

теорема з.г.2. Пусть некот(ме ограничения имеют вид равенств и выполнены условия теоргмы 3.2.1 с измененрыми условиями 2 и 8

2'. Существует ч:-ело г>о такое, то ¿ерно г > spcggtí~1 для все; таких g - баз j, в которых включены все градиенты левых чаете! ограничений-равенств.

8'. Существует у - решение системы

VgXxXy - хЭ + д.СхЭ О, ¿ = 1.2,...,m.

где знак s, есть = для ограничений-равенств и % для ограничений-неравенств. '

Тогда справедливы все утвервдения теоремы 3.2.1. ■

Teopoua 3.2.3. Пусть все ограничения "меют вид равенств и вьшолнеш условия теоремы 3.2.1 кроме условия 8, а условие 2 заменено на

2"э существует число г>о чакое, г > spccjT.n *>.

Тогда справедливо утверздек'% теоремы 3.2.1. •>■

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

Пусть я ■ ie. - обозначение м^ричноя нормы, равной сукме абсолютных зна^ний веет элементов матриц.

/х

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

екна з.4.1. Пусть д»ля каждой, точки интервала 10.приращение |ушщии у можно оцэжпъ следующим образом:

|уСв + /О - уСвЭ I 5 гСяЭ |Л| +■

дэ гее} - конечна, неотрицательна и суммируема по Лебегу;

»

Св.ЛЭ^Д -► О При А->0. Тогда |уСв>-уС05| £ /гССЭсИ..

о

[екна з.4.г. Пусть ч - отображение о^ск" в ^ с й", обладающее в V - некоторой окрестности уо. внутренней точи множества 1у. следующим свойством: с точностью до малых второго порядка по прошению к 1уг - у4*

ЧСУ2Э - ЧСу^Э «СХурсух - У43 +■ 0Су2 . .

•дэ о - непрерывная в ус невырожденная матрица и, кроме того, о"1» з с. вектор-функция о удовлетворяет неравенству

"ОСУ.-У^! 5 и «у2 - Л.

[ ис < 1. Обозначим ко = ЧСуо5.

Тогда в некоторой окрестности определено единственное

гепрерывное обратное отображение у = рсвэ такое, что

Э цСрСвЭЭ = в- 2Э рС«оЭ » уо;

О Ву - у I £ - а I.

о 1 —си о

ворвна з.4.1. Пусть внутри некоторой Области V е для всех х. : + л выполнены условия-.

з г > гр сс«зЪ_1э для всех <з - баз строк матрица -<;

О 1и'сх + /О - -ГГСх5( £ 1ЛЛ«; 35 |кИХхЭ1 5 р;

-э минимизируемая функция г БЬ^-укла, причем ограничены снизу ветчиной р > о собственные числа ее гессиана н;

о сущестауе^ у0 в Декартовом произведении V ц а | 1x1 < Гр> ■акой, что выполняете.-: ис < 1. где

= т г + С1 ♦ гр н -/п - = гСрУп * ТОу х.

Теорема а.з.1. Цусть вектор-функция g линейно унимодальна, У дуст:, для всех х, & выполнены условия:

ttCGCx^G^cx^^"41^ s г, для всех Gcxi - баз строк матрицы Ххэ;

23 HJCx + ДЭ - ЛСхЗ» £ ШЛИ ;

зэ р'± > sup г~*схз > о, где /Г'схз - наименьшее собственное число гесгиана нсхз iyr-ции f.

43 У ¡h. сх >- дэ - h. ,с»о| s г ид«, где h. . - элементы н;

L Ч v j 1 i ^ ч '

j

53 -/rVcxk3 й р.

Тогда для оценки удаленности решения ЗА от точки хк могут с 1ушп следующие вше формулы (4) или <5)

«о» - х1« £ Их**1 - xkl + fl~*СНСх^ЗСх11*1 - z3 « + HHCxk3Cr - хЗ « *■

* !оСх - xfe3,e3| + / т^ГСх^Э Уг L 1х - хЬК +

+ DHCxfc3S Их''*1 - х1, Vr L 1х - •. kl < Уг HgCxk3I + с

+ гГ^ИНСхЪ« Яхк*1 - хкй + ЙНСхк38 Уг KgCxk3КгУ2 т

* Г 2 fir »gCxk3ia + г L lgCxk3C Ср + 1НСхкЗ«(р Их' ''-хк1333 , <4, i

Id - хкИ £ «>-к*4 - хк1 <Уг IGCxkD» + П1НСхк}| + + р г I. iecxk3l + IC^xSn lxk+1 - хк J С Vr L ЙНСхкЭ1 (GCxk3l/-2 +

+ J ii»eCxk3*T'-2 + L ИНСхкЭ (^гЗ 3 /р>. a (5

При вычислениях методом квадратичной оптимизации вектор gcxk известен на к -м шаге, после наховд^ния становятся известны

ми существенные ограничения, по это*-/ ковко нати :gCxk5ii и ис пользовать формулу <4) для оценки удаленности от решения GA. Есл для всех баз строк матрицы j известна оценка типа nGCxk3! canst, то удобнее воспользоваться формулой (Б).

Условие 3 возможно заменить на условие г'1 г ^рсн"'с>оз.

В |4 по контактам задачи и значениям параметров задачи А точке определяется корректность выбора зтой точки в качестве нг

■ - функция Лагранжа задачи А.

» для того ко вектора уа область п принадлежит V. 5 = <х | «х - х°1 < у>, у = «ЧСуоЗ» £-5-^7 ■

Здесь год ч понимается сур.д. .....д1 эт, где .....I - иа-

1 1 в»

хексы ограничений, вошедох в о.

Пусть, кроме того, существует точка * такая, что дсхэ по-сомпонентно не положительно и левые части ограничений д^, I = Пи танейко унимодальны.

Тогда у ЗА существует решение а, и « «= п.

Гвороиа з.4.2. Если выполнены условия теоремы 3.3.1, а также

I) ИНСх + ДЭ - НСхЭВ < £|Д|;

&) С а с < 1. ГДЭ V = Ц Уп г/а.

исх + ¿О - ЛСхЭ» < Ь8Д»; I = V -/гп Р *■ Уп 3) сх | Их - хо» < гу> с V;

го метод квадратичной оптимизации дает сходимость к « - решению ЗА, 1хо - а» 5 г и скорость сходимости будет оцениваться неравенством

«х**1 - а» < СКхк - «I. р

Частным случаем задачи А является поиск решения с-ист&мы пели-

-ли дСхЭ = О (ПРО).

Тл. при о = сх | дсю = о> и произвольной целевой функции задача А совпадает с задачей ПРС. Нетрудно заметить, что кавдая итерация ио нко тогда есть ягер&дия по методу ш отона доя задачи ПРС.

Несмотря на большое количество результатов по сходимости метода Ньютона, применением идей доказательства сходимости мко е n5 получена новая теорема о сходимости метода Ныотсио дчя одного широкого класса функций. Там же дан контрпример, демонстрируй*:«! в некотором с мы;, лг необходимость условий этой теоремы. (В одномерном пространстве указана :эвыпуклая функция и начальная гичка на преде-лз условии теоремы, порождающие цикл з методе Ньютона).

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

1 ГШ i дсх+дэ - лсхэ 11 /■ «аи < и*). т.е. матрица Якоби

Д=о

икэет -лос. -лЬыум константу Лчтшыча в х;

8. I Л' СхЭ I = гСэО £ а> ; 3. ЬСхЭгСхЭ < в > О.

Ленин з.ь.1. Пусть матр.ща асхэ невырождена и имеет локальнук констану Липшица ^.хэ в -бласти о. Тогда обратная матрица а"' тоне в области и имеет локальную ..онстанту Липшица

1-~СхЭ <, I А'ЧхЭ Iя ихЭ.

я

Теорема 3.5.1. ПУСТЬ ФУНКЦИЯ д ПршаДЯечшТ (Г.о-классу И

1. 1 - го<г- -/~д2Сх°У * с > О, „де го = гСх"Э; г. в': СО. где - .

X

Тогда срдестзует решение а , у. зленное от начальной точки х° не более, чем на а .

о-

Теорема 3.5.2 (Локальная сходимость погода Ньвтс;а!. ПУСТЬ ФУНКЦИЯ

д принадлежит с-,п>-классу и нексоргя ог^нка 2 удаленности решения от начальной точки удовлетворяет

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

ССсЭ = Сес - 1 - сЭ^с = 1;

( расчеты показывают, что с е а. 25. 1.205 р* ' л •

?.) Б 0 с о, где р = 1 + ссв^э,

X

Тогда:

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

X

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

«х1" -<*»•< ССс1хк - <*Ю Их* -'а»;

р<)

)> решение я системы дСх> = о единственно в шаре э 0 •

X

Если а < 1, то ссгию < сспоа. Поэтому когда верны нера-(енства Их1 - ая ссгьз <1 и Их" - < 1, справедлива следую-дая оценка скорости сходимости - «л < сои яхк - ая*.

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

D гоо- УдСх) • . где С - корень уравнения ССс:>=1;

pd

os " с D, где Р = 1 +CC<rd Э, d = -ln С1 -г <г/~я'Сх"ЗЪ/<г.

о о о о

X

'огда: а) существует решение « системы дсхэ = о, единственное в d

lape s " ;

X

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

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

Их1"* - скй < CCcllxk - а«Э«хк - al.

Георема 3.5.4 Условия теоремы 2 являются также и необходимыми в гом смысле, что г^и их нарушении возможно найти функцию и начальную гочку, для которых сходимость отсутствует. ■

В На исследуются возможности модификации МКО (ММКО). оказыва-зтся vrcx'D, jcxk3. дсхкз . должны вычисляться с возраставшей гочяостью, и?эче сходимость не гарантирована. Гессиан может быть зачислен лишь в начальной точке и это будет стоить сужения множест-за на котором гарантирована сходимость. В конкретных приложениях тагрешвости в вычислениях гессиана практически не сказывались на жорости сходимости, и, поскольку вычислительные затраты на итерада существенно снижалась в сравнении с ^модифицированным МКО, эбщне вычислительные расхода на достижение желаемой точности были заметно ниже. ■

Гоореиа 3.6.1. (О сходнмосги ИМКО). ПУСТЬ ВЫПОЛНеНЫ УСЛОВИЯ 1-8 георемы 3,2.1, тогда .

э> существует число' 5 > о такое, что любая точка шара S^ с v

может служить начальной для ММКО;

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

CC<S3 = уп /3[<5LVF Sp Н С1 + рт/пС/г pL + бйЭ + уг Lр * Ш < 1;

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

Ix**1 - а» < CCIxfc - al)Ixk - ai. в

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

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

В N5.1 рассмотрен дискретный аналог метода Чебышева рсшени/ скалярного уравнения гсхз = о. здесь для получения каждой следующее итерации предлагается использовать обратную интерполявдонЕув

задачу. с п последними узлами. Вычисляются в узлах ^.....хг

величины у. = fCx.j, i = ГГгГ. Находится свободный член а полинома р такого, что х. = гсх.э, t = Г7п. Один из yaiot xi,...,xn замещается на а в соответствии с правилом исключения.

<п)

Пусть м = sup|f со | sup|fc>o , где f - обратная К f

т

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

t ¿~

t, - t, - t., -. ..- L, = Irs И, к > n,

к к-! к - 2 k-n *

связанного с итерациями по ЩЧ соотноношедием t. 2 ln l>\ I*

Пусь.- наибольший корень уравнения vcv? = v" - vn_1 -...- 1 - о - характеристического для (8) - обозначен через .

Теореид 5.1.2. СПравеДЖИВО 2 > > /иСгО = 2nSCrt+l}. а

^посредственное вычисление, корней характеристического уравнения дает следующие оценки \*сго снизу дая Л^сгО:

N1 3 3 4 5 е 7

1 В1803 1 83928 1. 92755 1. 96504 г 98358 1. 9910в ,

1 33333 1 50000 1 60000 1. 66666 1 714S8 1. 75000

Все цифры в таблиде для \*Спэ верны в том смысле, что

х*сп> + o.ooool > л спэ > а.*(п).

Творена 5.1.а. СпрЭВеДОИВО A^Cn+lJ > Л^Сп?. п = 2.3... .

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

П - 1 у-• ^^

приближения удовлетворяют условиям 1 > У м |yk| , к = ГГп. Скорость схоцимост! по значениям функции моино оцэнить неравенством

In |yj S с^ + С1 п Н)УCl-rO, где к бОЛЫПЭ Г1 И с определяется по формуле с = шах сг~к inc -/tT |ук1э.

V= 1 , п

ИЛИ, более точно, с = шах СА.~к 1пС тПГ ly^P?.

к = 1 , п

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

, к

г* - 1 .-' К

!>,. I / М О , к > п. D = •

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

„-1,-..-, \v

К

П-1,----,

- X | S L / М D 1. к > п.

в

Теорема 5.2.1. ПуСТЬ

In (х - хк| S сД.*СЗЭ - In Vfi. (10)

где с < о, к = 1,2,3, тогда (10) справедливо с той же констэе той с и для к = 4,в..... Или в другом виде: пусть

с = таX ein |х-хк| Vfi ЭЛГк < О,, к = 1,2.8

тогда

|х-хк | S D / УЙ, D = e к=4,5,6,...

Те не идеи лежат в исследовании поиска одномерного минимума в основе п-точечной интерполяции ($5.3). Рассматривается задача поиск

безусловного локального минимума скалярной функции f е с"а bj н

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

этих узлах значения функции и построим интерполяционный полином степени n-i.-

рСхО = fCx^i, i * ktk+n-l.

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

наименьшим индексом, то есть хк . исключим.

После выбора начальных узлов хк , * = ГГп, этот алгорип определяет все последующие , к « n+i, п+г.....

Введем обозначение м = sup |fln>ci)D }/сгсп-1зо. Ключевым для

Г}е<а,Ь>

этого метода является разностное уравнение Ч ■ - t, = 1г> н.

к к-2 1с-п

с характеристическим уравнением

vcv) = V - V

- V - X = О.

Лго набольший корень ^сю участвует в оценке скорости сходимо-гги ввда теоремы Б. 1.4 вместо

1е»ма 5.3.1. Многочлен V имеет единственный положительный корень в нтервале ^сю = п + /5пг-4 э/сгп+гэ. £ = с 1+У9э/г^ и все его юрни - простые.

Непосредственные вычисления корней характеристического уравне-мя даот следующие оценки \*Сго снизу для \сп):

3 4 9 8 7 8

1.17339 1.32471 1. 27177 1.46S57 4/3 1.S3419 1.37617 1. S701 4 1 . 40770 i.seooo 1.43202 1. 60134

Все цифры в таблице для Х*сп) верные в том смысле, что ^cro е (х"сго.\*спэ 0.00001). Конечное число цифр иррациональных íCnD получено посредством простого усечения. С точностью до ю~* : округлением в большую сторону величина м есть i.eieo4.

Георема 5.3.3. Справедливо Л^Сп+13 > Л^Сп), п=3,4..... ■

Таким образе-;, для п = з7в можно использовать табличные оцэн-и Л*Сго с погрешностью не превосходящей 0.00001, для п = в.07 эденку > х'свз с погрешностью не более 0.017. Дяя теорети-

геских исследования можно использовать оценку мСЮ при всех п с югреиностью не 6ow

¿ - ¿/СЮ = О. SCI * УЭ -Cn + -/Sna-4 D/Cn+153.

йлеет место /ховз > \'свэ и мею У р.

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

> f * сГа>Ь5 ;

!) сужен интервал Са, Ы> так, ЧТО х е Са.Ь) и

п- 1

Г Í г «j.jp |Г"СиЭ| - У sup |f '''СЮ |¿C í-i?Cb-»>> О; u «< , ь > '—« и е ( л, ъ»

X 1

V П-Z/-.

3) выполнено С Са.ьэ. где р • D ✓ > м .

либо х. е С а. Ь>, к = Г7п, sf! ССа.ЬЗ. ГДЗ к к

» n en+i

4) выполнено с = юах Clri |х-хк I < о,

4 , Г»

либо с â rnax Cln У M fCxD/sSiX"* < О,

__к А

то скорость сходимости оценивается формулой

|х - S D^1 ' Ун*. D = »". к >1.

В ¿5.4 проведено исследование сходимости метода трехточечно] интерполяции (частный случай метода §5.3) при наличии погрешности i измерениях целевой функции. Оказалось, что при повышении обших вычислительных затрат на повышение точности измерений на каждом последующем шаге возможно сохранить тип сходимости. Пусть последовательность, порожденная итеративным процессом, используащим приближенные значения целевоафункции ук вместо точных yk = ,

к=4,г,... Погрешность измерений и оценку удаленности текущая итерации от решения зададим формулами

\ ж ** ~ h • i*k - *l - К • k --

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

|Сх • - хь ЗСх „ - х МД. - Ди - CyL - 5 3-■ k-4 k-a k-a k k k-l k 'k-»

•ССД. - Д 3Cx - x ) - Ci - ЛЭСх^. - x. 3J'Q3/-Q| < k k-i k-a k k-Ä k k k-1 1

S Ti/Cl + ¿3.

где

0 - СУк - У*-*™**-. - V ' ' VCx* " XV-«3'

А»

v к . z,

Т = » . с = min lln ^»¿j , Г = <1.2.3>,

-х*

Ийбо т = е , если I = <к-1 ,к-2,к-3>; 6 » const, < 1. Справедлива тага» оцешса скорости сходимости

V

|хк - х| 5 D D = вс, к > 1.

1= sup |f"'Ci)3 |/С2 sup | f "С г)> 13 > /«<а.Ы 7)е<в,Ь>

Z.

: = max х"Чп -g- должно быть отрицательно.

i»», г . а

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

п

ГСхЭ = Е ГСх.Э -► min. (11)

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

т

ФСхЗ = J Е ГЛхХиХиСтЭт dr. (12)

о

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

грзсдям ^.....un, подчиненные ограничению u = е u. , ucts -

»убывающая, непрерывная справа и в момент окончания- т непрерывная лева.

Обозначим dvjuo/dи через v сиз - интенсивность финансиро-ания i-й отрасли после вложения и средств; норматив с-й отрэс-

и - х. , то есть состояние, в которое желательно привести t-o

• '

отрасль; относительная нехватка - н. с vO = ex. - х.си.ээ/х. . Рпределениа опорного плана. Набор функций u.Cui, и 6 го.ш.

и

будем называть планом, если u.cui = J v.cu:><iu, а подинтегральные

1 о '

функции подчинены условиям v.cu> го. и п v. сю = 1 для всех и из to.ui. Если, кроме того, v.cu) прямо пропорциональна почти всюду величине сcu.iiн.си.э, где c.cu Vx - относительный

l t V It II i

коэффициент роста, то набор функций и.сиэ, ¿=Г7п, и <= to,из. будем называть опорным планом.

Теорема 6.1.1. Распределение средств, удовлетворяющее условию

« Си СЮ} X М.Си.СиЭЭ = Я.СОЭ ^ W.C03 ' ' 11 1 J

для всех t.j.u эквивалентно опорному плану.

Теорема 6.1.2. Пусть минимизируемый функционал имеет вид (12), где

(х. с u. СО

1 - — - -^-i- , с = const.,

х. х. i i

т > о, uco s х. - решение уравнения = о, i = ГГп.

Тогда минимизирущий набор utco.....unct;) будет опорным

планом в том и только том случае, ее та \.....хп приписать значе-

х. _

ЕИЯ i = к с н.\оУ ' где k > ' = 1,п" " t i

Теорема 6.1.3. Пусть rt.....rn - выпуклые функции и минимизируемый функционал имеет вид <12), неубывающие (возможно разрывные) u4....,«n подчинены ограничению и = £ и. , исо - неубывающая, непрерывна,.1 справа и в момент окончания г непрерывная слева.

Тогда, оптимальное распределение u°co.....можно построить

таким образом:

i ■ ■

ч°СО ■ Г и°СтЭс!т . u°CO = v.CuCOiuCO, i = Г~п. i J i t

о

где у.сиз определяются следующим способом

Положим vcio «= о, если существует j: > г'.с up.

Соотношение " £ « г » г^си.э» т1п г м: ит:> И определяет множество индексов Пусть J - подмножнество выделяемое соотношением г'^сиз = о £ е ] .

Если -> пусто, положим

у^иэ = ^ д1я £ « i.

Если J не пусто, положим у^иэ - о дяя г « / ч а для £ « 1 функции V. сю можно вьйрать произвольно ( но в соответствии с ограничения;--;! у.сиэ г о и Е = ■

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

к - £ Р1г 1 -► ш1п (13)

1ри ограничениях

ь. = в, ъ г о, £ = ГПГ. (14)

г

в N. (15)

де N - множество целых чисел. Задача целочисленного нелинейного рограммирования (13), (14), <15) решалась Ротни и Лозано. Окаэы-ается, предложенные ими алгоритм, пригоден также для применения к адачам более общего вида (12), (14), (15).

Введем к-асс функций

Р • <Г I Г = ^Г1СЬ15 * Г1 в у * С1>-1 ♦ г[ *

цэ г множество выпуклых, нигде возрастающих, ограниченных газу, не имеющих линейных участков и заданных на ю.ао функций, 5с д - свойство "сдвинутости", т.е. существование такого числа :о, что ь'со = д'С1-к5з и рассмотрим целочисленную программу

ГСЬ4.....Ьк3 -► и1 п (1в>

Ь. 20. Ь. еЫ, £=ГПГ, П. -В

I , ** ъ

где и - множество целых чисел, г « р.

Теорема 6.2.*. Решение ьн программы (16) уклоняется от ь* решения <16+) ( программа (16) без требования целочисленности менее чем на единицу: тлх |ь* - < 1.

I

Теорема 6.2.5. ьн - решение программы (16) - удовлетворяет

чь+ч < чь+\ -> ьы - 1ь+] < ь" - сь+]. I J I V J J

где ь*. ь* - компоненты решения программы (16+>, знак "V исподь зуется для операции взятия дробных частей. ■

Две последние теоремы обосновывают использование слэдуюшел алгоритма поиска целочисленного решения программы (1В).

А2. Получим решение ь* задачи (16+). Пусть I = <¿1 чь.ч > о> ]

= п. Упорядочим дробные части \ь.ч. с « I, в порядю

убывания (при наличии равных дробных частей это монет быть сделаю не единственным образом) и обозначим множество индексов шрвых I дробных частей через л. Положим

ь" = сь+1 У£ в х^а. ь" = сь+]+1 У( «л ьм = ь^" л « I.

11 I I

Этот алгоритм в силу теорем 4 и 5 породит при различных способах упорядочивания дробных частей все множество решений программ (12).

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

ь.

задачи (16) требованием целочисленности п1 = 2 ' вместо ь.. Если формула

' ТТ р. . < 6 i. (17)

где I = <1.....к>, дает только цзлые положительные значения г^,

пк. то они будут оптимальны, Если кет, то поиск оптимума являете? задачей дискретного программирования. Бе может существенно упростить применение алгоритма

3. Последовательно расчитываются наборы nm по формуле (17) на

аожествах i = i ( л2.....Каждое последующее множество

элучаеся из предыдущего путем исключения тех индексов ¿, для эторых п" - компонента решения гГ - менып? лиЗо равна единица, з последнем множестве i формула (17) выдает только болыпив циницы значения. Результатом алгоритма является множество э нем все компоненты оптимального решения равны единица, я

Следующее утверждение суживает пространство поиска.

эорека 6.2.7. Все решения п® дискретной программы

fCn.....п) -► min ___ . (18)

n.21, n.«N, i=l,k. 'V=neN

l L l

Зладают свойством

n, <1 -> n® = 1; i = mr,

i V *

45 n4.....nk. - расчитываются по формуле (17), ■

Дополнительное сужение пространства поиска обеспечивает

S)

»орсиа 6.2.8. п. < п. п. S п.,

r v j ' о

цэ п., г» (с,j « ir) рассчитывается по формуле (17) при i звном ir - множеству из алгоритма A3. ■

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

м = Е П Pl ГТ С1-Р.ЗП. -> min (19)

Sc<i . . . .k> ieS

ж ограничениях

П

i»i

п. = г,, п. > 1 , п.еМ, i = l,k, (20)

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

Дискретное программировать тесно связано о вопросами по-

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

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

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

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

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

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

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

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

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

Помимо прямого и обратного алгоритма пачечный алгоритм содержит глава!':;) процедуру, которая

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

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

Численные эксперименты показали сокращение числа рассматривае-IX комбинаций примерно на два порядка, когда п = 14. ■

Па Х£Я£ диссертации опубликованы следующие рашш*

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

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

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

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

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

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

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

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

Планирование распределения ресурсов с дискретным временем //Тру-ЛКИ: Математические модели и САПР в судостроении, ЛКИ, 1982. . Задача распределения и смешанная целочисленная программа //Тру-ЛМ: Математические модели и САПР в судостроении, 1985. . О формировании пространственной волны в популяции амброзиевого стоеда //Математические методы моделирования и анализы управляе-х процессов, ЛениЕгр. ун., Л., 1989.

. Модель уединенной ".мкы в популяции амброзиевого листоеда.

riferenc»? on Oirfer-fntiaL Equations and Applications 4, Bulgaria,

39.

Stability 2onos in Rhesus -syst ems /^Second Intern. Colloquium Differential Equations, Bulgaria. 1991.

. Сходимость дискретного метода Чебышева и метода Мюллера //Воп-

•Л J

росы механики и процессов удивления, вып. 15. 1991.

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

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

17. Properties of a subclass of recurr&nt functions //Internationa Congress on Computer Systems and Applied Mathematics, St. Petersburg, 1903.

18. Measurmeiit errors control in the 3-points interpolation metho УУСВАИ'вЭ, St. Petersburg, 1S93.

19. Automatization of Interval Calculation /'1 nternation.il Confe rence on Interval and Computer-Algebraic Methods in Science an Engineering, St. Petersburg, 1S94.