Оптимальное управление двухуровневыми итерационными процессами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ЛОДШШ Ш СССР ШШРСШЗ ОТДЕЛЕНИЕ ИНСТИТУТ ШИШЖЙ

На правах руюостся

УДК 519.8

/

КАЛАШНИКОВА Наталья Ивановна

ОШМШНС® УПРАВЛЕНИЕ ДНШРОВНЕВШИ ШЕРАЦИОШШИ ПРОЦЕССАМИ

01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

дягссергаад* на еояснаЕие ученой степени кандидата {ашгеонвшт^шяячесгяй; наук1

1вм2стггяр1СЖ»ЕШ

Диссертация выполнена в Новосибирском ордена Трудового Красного Знамени государственном университете имена Ленинского комсомола

Научный руководитель - доктор физико-математических наук,

црофессор В.А.Булавский Официальные оппоненты: доктор физико-математических наук,

А.А.Каплан

кандидат фиэихо-датештнческшс наук, И«Я.ЗаЬотин

Ведущая организация - Ленинградский ордена Ленина и ордена

Трудового Красного Знамени государственный университет имени А.А.еданова

Зедита состоится цянваря 1989 года в .. часов на заседании Специализированного совета К 002.23.01 по присуждению учецой степени кандидата наук в Институте математики СО АН СССР т адресу: 630090, Новосибирск, 90, Университетский проспект, 4.

С диссертацией можно в библиотеке Института

математики СО АН СССР,

Автореферат разослан " " •_ 1988 г.

Ученый секретарь Специализированного совета кандидат физико-математических

наук у> .'• Ю.Д.Васильев

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

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

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

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

Научная новизна. Прелг. длояения о глобально линейной и локально сверхлинейной скорости сходимости основного и линейной

скорости сходимости внутреннего итерационных процессов позво-ши уточнить задачу минимизации трудоемкости двухуровневого итерационного процесса при заранее заданной конечной точности. Решение этой задачи получено с помощью перехода от целого числа шагов Я к вещественному.

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

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

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

Апробация работы.Результаты диссертационной работы

докладывались на:

I) 7-м Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования",г.Нарва-Шэсуу, 1982 г.

2} 1-й Всесоюзной научно-технической конференция "Синтез п проектирование многоуровневых систем управления",г.Барнаул, 1982 г»

3) 10-м Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования",г.Нарва-Мнзсуу, 1988 г.

4) УШ-й Всесоюзной кгчференцип "Проблемы теоретической кибернетики",г.Горькай,1988 г.

5) ХУЛ-11 и ХШ1-Й Дальневосточных математических школах-семинарах, г,Находка, 198? а 1988 гг.

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

Публикации.По теме диссертации имеются 4 публикации без соавторства и 3 публикации в соавторстве,которые в делом отра-&ают основные результаты работы.

Структура п объем диссертации.Диссертация состоит из введения и трех глав общим объемом 114 страниц,а также приложений I и 2,содер™а^юс результаты численных экспериментов.Список цитируемой литературы содержит 31 наименование.

Содержание диссертации <

Во введении дается краткий обзор предшествующих исследований и аннотируется содержание диссертации.

В главе I рассматривается итерационный процесс вида

• . и)

где Хен н ^ из ,в котором для практического постро-

ения Хе+х , в свою очередь,применяется итерационный процесс

называемый внутренним. Чаще всего задача нахоадешш Хгн по известному решается неточно,и процесс (I) заменяется на такой, в котором выполнены соотношения

' V % ' ••• . (3)

где У>0 - некоторый управляющий параметр,определяющий точность выполнения (£+!■) -го шага.Отсюда возникает важная задача оптимального (в некотором смысле) выбора -значения управляющего параметра \ на каждой шаге, '

В §1 главы I рассматривается достаточно типичный случай, когда основной процесс (I) глобально сходится линейно,а в некоторой окрестности V точки неподвижной точки отображения ста сходимость имеет порядок с (например,квадратичная при Ж-1 ),Другими словаш, найдутся числа 0<^><1 и 0 .зашсяще,вообще говоря,от начального приблшгения Ха .такие,что имеет место оценка

\\Х^-&(Хе)Ы /тп(р/ $)Их£-х/\Ц^^Л, Е- ох... (4)

Далее,предполагается,что внутренний процесс (2) сходится ли-не%о то есть,для всех & справедливо неравенство

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

на в форме ^

Ы , (5)

1-е ^ и/ Гбгр

где О - оценка начальной погрешности внешнего процесса (I), В>М*р) - константа,а I - множество последовательностей {Уг}г такях, что .во-первых, ^ 0 при 00 ,н во-вторых,последовательность »определяемая соотноше-

ниям

является убывающей,Здесь ¿>0 - заранее заданная точность, при достижения которой процесс заканчивается.

В §2 главы I решается задача (5) минимизация суммарной трудоемкости,к ка основе ее решения предлагаются правила выбора оптимального значения ^ на шаге процесса (3). Именно,если текучая погрешность удовлетворяет неравенству

, (6)

то в качестве \ следует взять число

%-Р-?о% . (?)

где \ >0 - едпнственшй полоеттельнй! корень уравнения

Т&у- £п б? . (в)

Если Ев имеет место соотношение

%*(?№)* , (9)

то в качестве а£ рекомендуется выбрать величину

. (Ю)

где О ~ единственнкй положительный корень уравнения

. «I,

'"7 4

Здесь функцзд определяется формулой 1*0

Вашшм свойством этой методики является тот факт,что величина управляющего параметра , £*0,{,... »зависит лишь от величины погрзаности ^ перед началом -го шага итерационного процзсса (3) и не зависит ст того,какую точность 6 ми хотлм достичь. Это обстоятельство делает удобны,! использование пг/сдлояспцого метода управления точностью двухуровневого итерационного процесса в вычислительной практике.

В главе II диссертационной работы описана реализация разработанного в главе I способа управления точностью применительно к методу Ньютона ревдшш нелинейной задачи дополнительности ОЩ); найти вектор такой,что

х>о , ¿(х)>о хУСх)-о, (и)

где

/• Г- гг

прикадлеаит классу .Метод со-

стоит в сдедащш.Имоя Г£ а • .определяем X - решение линейной задачи дополнительности: £г>0 * Хк) * о , хг-г<Г-0 . ц4)

Б§1 главы И диссертации уточнены некоторые известные результаты о'глобальной сходимости метода Ньютона,Именно,доказаны следующее теоремы.

Теорема 2.1.Пусть отображение

Ь /Г- ят

кз класса

С (Я'П)склъпо монотонно (существует скалф ^ > О такой,что

Ш'х)-Щ), х-у) *//• //V-улг

для любых Я ) .покомпонентно выпукло,и в любой точ-

ке %<Е матрица

№

является -матрицей.Тогда для лю-

бого начального приближения последовательность },

построенная -ютодом Ньютона,сходится к - единственному решешш задачи (15). Ее ли, кроме того, Iе С (Я"1), то сходимость

будет квадратичной,то ость выполнено неравенство

!х*н~хрНЯ-11х*-хлИ\ к'0,1,... , (15)

для некоторого О ,

Напомним, что вещественная квадратная матрица Л1 называется 2 -матрицей,если ее впедпагоналышо элементы неположительны.

Теорша.2,2. Пусть отображение ¿¡й задано з ви-

да ¿(х)"А%+ ,гдо Д - вещественная: положительно

определенная Н1*}П -глтряца с параметром (ю есть иг/\Ц>

>/7ИШг для любых иеР™),& (яобршяж является непрерывно дифферзтегруемш с ограниченной производной: ¡Ч>'{Х)Н цр для псох ¿ге^"*; здесь 0<Ц< Ф . Тогда для любого начального Х^Я"' последовательность {'£''}, построенная методом Ньютона,сходится к - единственному ре-кениа задачи (13).Вся?,кроме того, сходимость

будет квадратичной,то есть выполнена оцзшеа (16) с некоторой константой сд>0

В §2 главы II получены теоремы о глобальной сходимости неточного метода Ньютона.3 частностидоказана

Теорема.2.3, Пусть Х^е Й™ - (единственное) решение ЩД (13) с отображением Нх)т Ах* У(X) ,удовлотлсрятакм условиям теорема 2.2.Тогда

а) 'для любого начальном приближения Х°& ^'"последовательность (Х^] .построенная по правилу

; Нк(хы)Ы \ Шп(хкЛхк)П

где Т^ @ - некоторый скаляр, а сходится к .если

^ра-^ьи-щшЧ , к-ол.....

для некоторого (О, ~~~ ^ ;

б)если,к тому но, при л . То сходимость буде^ оверхлииз&шй.то есть справедливо соо. шеше /т 2*!а о ;

, I I .

в)если,вдобавок,начиная с некоторого К0 & N выполнено

неравенство \4 ьфпм(хк>Н%к))1

дшость будет квадратичной,то есть верна оценка (15) с некоторой константой

Под »¡м(х*,ф1)) и Пйп(ОС,Я£к)Ч'(хЬ(Х'хЬ) в формулировке теореш понимаются векторы,волучешые взятием покомпонентного минимума.

В §3 главы II схема управления двухуровневым итерационным процессом,разработанная в главе I,применена к описанному выше неточному методу Ньютона.В частности,если 1Ш*АХ+Ч>(Х) удовлетворяет условиям теореш 2.2,положим <3," % ,

, /- I, , Л-1 , тгаеръ

процесс управления точностью (Ь 1) -го шага ыовно списать

2

так.Пусть X - текущая итерация.Тогда,как рекомендовано в §1

& А

главы I,вычислим величину

и сравним ее с величиной ,где £>0 - заранее

гН

заданная конечная точность.Если £ ,то процесс окон-

г

чен, ЗГ - приближенное решение;если ке , *{> 6 ,то срав-' ним ^ с величиной ^ и найдем границу для погрешности шага по следующей формуле,объединяющей (6) - (12):

'где корень уравнения (8),если

V• .где $>0 - корень уравнения (II).если V< О

»0 /о/"' 'в „ ж „ Й. 'О -Г

(то есть, ¿П %+ -0 ),

Здесь PCf)-H (ir2' J) U . (16)

1*0 ,

Затем находим точку ХкН такув.что выполнено неравенство

и определяем новое значение %! .0 найденными X н , V

h "о

процедура,описанная выше,повторяется.

Б §3 главы II рассмотрены таете два способа нахождения

£

точки X Первый способ состоит в следующем итеративном про-

>ч £ п^

цессе,начинающемся с точки .Е»леило,еслл ед+ - теку-

щая нтерадая.то строится ио правилу

Z*4*-ß<№+6)l . (iv)

где /f-y/^-j , . ß>0 - некото-

рый скаляр. Если f(tX^) - положительно определенная матрица с параметром^ и 0 <ß< 2ju/üA I ,то доказывается

линейная сходимость процесса (17} к точному решению задачи (14),

а в

то есть к точке ^ f такой,что О . Вторым спо-

собом поиска точки Я*** является безусловная минимизация фунадди R ,тещей вид Q{X)~- £ [ш* + ЦАх+5).]1+

/ 4 <> i

+(Zj)l.Здесь,как обычно, Osmütfä Р} , У?тах[О;р]

В главе III диссертационной работы предложенная в главе I методика управления точностью двухуровневого итерационного про^ цесса применена к методу нагруженного функционала для решения задачи выпуклого программирования,В §1 главы III дано описание этого метода,который состоит в следующем.Пусть заданы выпуклые функции / , % :Rn-*R , <?,—, М- ,и поставлена задача

xeRn de)

Ii

Допустим,что задача (16) имеет решение Х^ и известно число ¿^ < У/х#)"¿С .Тогда решение задачи Ш) методой нагруженного функционала состоит в построении последовательности чисел и последовательности точек ¡Хц.] по рекуррентным формулам

ШКп УЫк) , к'12,... , (19)

(20)

** "к

Через х(х,с1) в ^^ к (20) обозначена функция

У(хМПтах{0, НхН}}г* %(х)\]2-

[Hxydt*

В §2 главы III диссертации доказана квадратичная скорость сходимости зтого метода,Именно,справедлива

Теорема 3.3. Пусть / , if > i~l,2,...,№ , - выдук^ыз дважды непрерывно дифференцяруеше функцаи«множество допустимых точек задачи (18) ограничено и непусто,а векторы , Icl^-fi ■ %(Xt)m0] .образуют линейно независимую систему.Кроме того .предположи ,что

а) выполнено условие двойственной невырожденности,то есть найдутся положительные числа Л*' , ¿е1* .такие,что верно ра- . венство

б) матрица •

iSJjf

не имеет направлений вырождения 3 .удовлетворяющих равенствам

Тогда существуют константы >0 , >0 .такие,что при достаточно больших к выполнены оценки

- KUß 1z-ZJ*

fc+i * к *

После того как доказана квадратичная скорость сходимости метода нагруженного функционала,в §3 главы III излагается схема приближенного решения задачи (18),которая опирается на результаты, полученные в первой главе диссертации.Сначала уточняется формула пересчета оценки на случай,когда СС^ не является точным решением задачи (19).Именно,если целевая функция / сильно выпуклая с параметром Д> 0 ,то есть выполнены неравенства

Щ) >Нх) + f'fz)(<j- X) +ßjij-xi2

для любых X , //€ Яп ,üßi>0 s h 1,2,..., М .-аналогичные параметры для выпуклых функций '-q , i« {&..., ,то мояно определить функцию й: Rn-* R по формуле

т

Тогда если )> d^ ,но Х^ не является допустимой точкой в задаче (18),положил

ri .>/+ Ж4) i 4)f . (22)

k НЧУ dk

Очевидно,что уточненная формула (22) совпадает с исходной формулой (20), если - точное решение задачи (19): в этом случае О

Далее в §3 главы III описывается схема нриблияеш то счета методом нагруженного функционала.Пусть Cf1<JfzJ- начальная оценка, %0 - начальное приближение.Проводим внутренний шаг, заключающийся в безусловной минимизации функции V/^^j каким-либо методом (например,методом скорейаего спу та или сопряженных градиентов).Как только в процессе минимизации получена точка Х0 ,для которой верно неравенство Hxo)>di .находим

л» *

величину 11 сравниваем ее с зара-

'нее заданной точностью £ > О .Если '/<£ ,то процоос окончен,

•с

Х0 - ирибликошюа роптание задачи (18). В протишш случае возшаш два исхода. Если *{ »р!$) ,находим \>0 - корень уравнения Т^Т" +

Здесь в качества параметра 0<р< 1 выбирается величина

,

* УЪАмт-м 1 й (,1

%>0 - константа из оценки (21),О' Л*/»/ .Затем полагаем <СИ » Если та у < р/$ »находим корзнь 1>0 уравнения

Зд«еь Р(^) - фрвсцкя, заданная формулой (16). Затеи полагаем '

В обоих случаях продолжаем процесс минимизации функции У/^йу) до пор,пока не получки точку ,для которой

ВШ1СШЮШ условия:

/¿и >4 и < %.^у, | *)

где ^ = 4 Посло э*иго,осла »пе-

ресчитываем оценку по формуле (22) при к повторяем процедуру, описанную выше,начиная с 4 а ,

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

Перечислим в заключение основные результаты диссертации.

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

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

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

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

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

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

Основные результаты диссертации отражены в следующих • публикациях.

1.06 оотвкизадш управлений точностьв в двухуровневом процессе // Оптимизация.-1982,-Вып.23(46).-0. 5 - 21.

2.Управление точностью выполнения шага в методе нагруженного фувкщюнала//Штишзадая. -1982. -Вып. 30(47). -С. 115 - 127.

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

г.Нарва-Йыэсуу,апрель 1982 г.-М.,1982. С.139 - 140.

4.06 оптимальном управлении внутренней точностью в двухуровневых итерационных процессах//Сннтез и проектироваше многоуровневых систем управлення:Тез.докл./1-я Воесоюзн.научно-, технич.конф.,г.Барнаул,окт.1982 г.-Часть I.-Барнаул,изд.Алтайского гос.ун-та,1982. - С.129 - 131.

5.Глобальная сходимость неточного метода Ньютона для решения задачи дополнительности//Оптймиз8ция.-1988,-Вып.42(59).-С.66 - 85 (в соавторстве).

6.Управление точностью выполнения шага в методе Ньютона

для решения нелинейной задачи дополаательност^'/Оптимизация.-1988 Вып.43(60).-С.27 - 40 (в соавторстве).

7.Глобальная сходимость, неточного метода Ньютона для решения нелинейной задачи дополнительности//Системы программного обеспечения решения задач оптимального планирования:Тез.докл./ 10-й Всесоюзн.сими. ,Нарва-11ыэсуу,март 1988.-М. ,1988.-С.30 - 31 (в соавторстве).