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

ДОАДШ1Я НАУК СССР СИБНРСКШ ОТДЕЛЕНИЕ ИНСТИТУТ шзшши

На оравах рукописи УДК 519.8

КАЛАШНИКОВА Наталья Ивановна ОПТШШЙОВ УПРАВЛЕНИЕ ДВУХУРОВНЕВЫ® ИТЕРАЦИОННЫМИ

процессами

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

/

АВТОРЕФЕРАТ

дигсертаияа га сожставже ученой степени кандидата $®шкьштеявтшчесмй: наук5

йеяваоийзфск,!»

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

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

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

А.А.Каяла»

кандидат физико-математических наук, _ И. Я. Заботив

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

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

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

С диссертацией можно ознакомиться в библиотеке Института математики СО АН СССР,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5) ХУП-й и ХУШ-8 Дальневосточных математических школах-сегяшарлх,г.Находка, 1987 п 1988 хт.

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

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

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

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

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

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

х^&Щ . , (I)

где Хм и ЗС£ из Ят ,в котором для практического построения Хе^ , в свою очередь,применяется итерационный процесс

[ ^в'-^с »

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

, и... , сз)

где - некоторый управляющий параметр,определяющий точ-

ность выполнения (£+1) -го шага.Отсюда возникает важная задача оптимального (в некотором смысле) выбора -значения управляющего параметра ^ на каждом шаге,

В §1 главы I рассматривается достаточно типичный случай, когда основной процесс (I) глобально сходится линейно,а в некоторой окрестности V точка г!^- неподвижной точки отображения Ф эта сходимость имеет порядок 1+Л- с 1 (например,квадратичная при ).Другими словами,найдутся

числа 0<А< I и .зависящие,вообще говоря,от началь-

ного приближения Х0 ,такие,что имеет место оценка

^-Ф(хе)Н пип{р,$}-1х-х/}-//, (4)

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

\\2%- Ф(Хе)К М-, ...

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

на в Аорме

/я

■1М.+ А)- Щ , (5)

£ = 0 х й ; ГеГ

где - оценка начальной погрешности внешнего процесса

(I), В 1>\ - константа,а Г - множество последова-

тельностей { \ ]г та 131 х, чт о, во-первых, О при 00 ,и во-вторых,последовательность »определяемая соотноше-

ниями

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

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

, (в)

У

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

' <7>

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

Г&у- , (8)

Если ке имеет ¡.-.есто соотношение ^

%$(рт)* , (9)

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

где Т0> 0 - единственна положительный корень уравнения

Здесь функция Pft) определяется формулой

Я I** iW-TJi,liM)H r). (12)

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

дачкпц погрешности ^ перед началом (£+0 -го шага итерационного процесса (3) и не зависит от того,какую точность 6 мы •лсгтл достичь/Это обстоятельство делает удобным использование предложенного метода управления точностью двухуровневого итерационного процесса в вычислительной практике.

В глава XI диссертационной работы описана реализация разработанного в главе I способа управления точностью применительно к методу Ньютона решения нелинейной задачи дополнительности ОВД): найти вектор Х<К такой,что

Ж>0 , ¿(Х)>0 хУ(х)*0, (13)

где Rm-+ Яп принцдленат iwxaccy CX(Rm) .Метод состоит в следувщэм.Имея X^&Rm ,определяем Х^1 -решение лшшйпой задачи дополнительности:

Х9 О , ttf- J(xk) + Йх{<)(х-Х*}> О , хт-г<г»0 . (14) В§1 главы II диссертадш уточнены некоторые известные результаты о "глобальной сходимости метода Ньютона. Именно,доказаны следующие теоремы.

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

h /Г- /Г

из класса

С 'Усильно монотонно (существует скаляр > О такой,что

{Нос}-Щ), %-у) ?//• ¡¡я-и а2

для любых X , уе /?т ^'покомпонентно выпукло,и в любой точке R+ матрица

m

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

бого начального приближения Х°€ Rm последовательность (Х }, построенная истодом Ньютона,сходится к Х^ - единственному решению задачи (13).Ъ'сли,кроме того, Iе С (Я™),то сходимость

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

к-, (15)

для некоторого @

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

Теорема ...2 »2. Пусть отображение /•ГЧГ' задано в гаде Их)"кх* НЧ~) ,гдо Д - вещественная положительно определенная М*}П -матрица с параметром £1>0 (то есть ¿4 АЫ>

для Ит) ,а отоброаше «/».'Ят-*Цт

является п-зпрзршзно диф$ерек'щруемш с ограниченной х/ролзгод-пойгМтН^-р для кох ¿Гб/Т4;здесь 0<^< {/3 . Тогда для любого начального Д^б/?"7 последовательность , построенная методом Иьшона,сходится к ^ - единственному расе ялш задачи (13). Ее ли, кроме того, (/'б о сходимость будет квадратичной,то есть выполнена оцзнка (15) с некоторой константой

В §2 главы 21 получены теоремы о глобальной сходшссти неточного метода Ньэтояа.З частности »доказана

л/?»

Теорема 2.3. Пусть /<,. - (вмшетвенное) решзпие ВЕЩ (13) с отображением //%)• Ах +Ч>/Х) »удовлетворявшим условиям теореш 2.2. Тогда

й) 'для лзбого начального приблиязпяя X & К последовательность .построенная по правилу

; \(ХЫ)Н\Шп(х\ЯхкМ

где О ~ иекоторий скаляр,а

сходится к X* .если <

Л-ол,... ,

для некоторого ¿V6 (О, ¿АЗ. ^ ;

6}если,к тому ке, V £ С*(К.'") ц Т^""* 0 ври

то сходимость будет^ сверхлинаШюн.то есть справедливо соотно-, *. л/

в)если,вдобавок,начиная с некоторого К0 ^ N выполнено неравенство ,ЭО О ,то схо-

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

Под 1(хЬ) и пип(х, Нхк)* х*))

в формулировке теоремы понимаются векторы,полученные взятием покомпонентного минимума.

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

%'ШЬ^Р , АЧ ,й-1п(2-е).Теперь

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

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

^С

главы I,вычислим величивд-

ж срав-

%)■&!

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

заданная конечная точность.Если 6 до процесс окончен, - приближенное решение;если же . б ,то сравнил ^ с величиной ^р и найдем границу для погрешности шага по следующей формуле,объединяющей (6) - (12):

'гАе %>0 ~ корень уравнения (8),если р;

Е&есь PCf)*n f/^'T) V ■ (16)

1*0 t

Затем находим точку iE такую,что выполнено неравенство и определяем новое значение !/ .С найдениши X , V

■С 1о

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

. Б §3 главы II рассмотрены такге два способа нахоздешя £

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

£ а п/у?

цессе,начинающемся с точки Л&яешю.если ,2 £ Kf - теку-

щая итерация,то строится по цравилу

2м-№-¿№+6)1 , (17)

где A~f'(zk) , , ß>0 - некото-

рый скалщ>.Если i(CC^) ~ положительно определенная матрица с параметром^ж 0 <ß< 2f</üAf доказывается

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

ür ib

то есть к точке Н такой,что I h^ftj"*')!}" О .Вторым способом поиска точки является безусловная мигашизапря функции .имеющей вид Cj(X)"Д f i^)!+

*(Zj)U(Ax+$)ßi] .Здесь,как обычно, })„-min{0, Pj , Шх{0,р]

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

дача

zeRn (18)

Допустим,что задача (18) имеет решение Х^ и известно число

//Z*)-¿4 .Тогда решение задачи Ш) методой нагруженного функционала состоит в построении последовательности чисел /¿^ | и последовательности точек fXg} по рекуррентным формулам

Yix^d^h шпп , к-12,... , (к)

d d/^ЩьЙЙ Jx,2,... (20)

Через Y(X,d) в и (20) обозначена функция

ViШПтах(0, Hx)-d}f+ &[tnax{og

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

Теорема 3,3. Пусть i , % , i*i,2,...,m , - вылук^ыз двавдн непрерывно дифференцируемые функщш.мноаесгво допустимых точек задачи (18) ограничено и непусто,а векгорц , /б ^"(i .образуют линейно независимую систе-ыу.Кроме того,предположим,что

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

б) матрица

tfl*

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

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

Ix. ~ 0CJ4,® !z- ZA*

KH * к *

После того как доказана квадратичная скорость сходимости метода нагруженного функционала,в §3 главы III излагается схема приближенного решения задачи (18),которая опирается на результаты,полученные в первой главе диссертации.Сначала уточняется формула пересчета оценки dt , на случай,когда *X-t не

K^i к

является точным решением задачи (19).Именно,если целевая функция / сильно выпуклая с параметром р> 0 ,то есть выполнены неравенства

Щ) >Hz) * f'{z)[ij- х) +ßjij-xl2

для любых X , //С- Яп ,аßi>0 , La 1,2,..., , - аналогичные параметры для выпуклых функций , 1 = 1,2,..., frl ,то можно определить функцию (X: RH~* R по формуле

m^lftehdh+jZAlymi

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

М / l%th,(k)\Z .(22)

^ H'-h)~¿4 ib

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

Далее в §3 главы III описывается схема приближен? то счета методом нагруженного функционала.Пусть Cf1<f{%J- начальная оценка, %0 - начальное приближение.Проводим внутренний шаг, заключающийся в безусловной минимизации функции VfrT^Jкаким-либо методом (например,методом скорейшего спу та или сопряженных градиентов).Как-только в процессе минимизации получена точка Х0 ,для которой верно неравенство f(jC0)>d1 »находим

/V

величину f * Y(X0>di)/[f(%()~dii и сравниваем ее с зара-

!нев заданной точностью ¿>0 .Если ,то процоос окончен,

Хд - приблтсонное решение задачи (18). Б протишш случае возможны два исхода. Если .находа ^>0 - корень

уравнения у- Ц+Т) ¡п V+ В У

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

•Г , . х.

%)>£? - константа из оценки (21), О" Щ 1+}'/ .Затем по** /V >

латаем « Е°ли ко »находим корень

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

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

выполнены условия:

цг

11 у ПШ1\

где . Поело этиго, если ,пе-

7 р ^

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

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

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

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

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

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

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

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

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

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

1.06 окгагазащи управления точностью в двухуровневом процессе // 0птишза1ЩЯ,-1982.-Бып.29(46).-С» 5 - 21»

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

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

г.Нарпа-Йыэсуу,апрель 1982 г.-М.,1632. C.I3S - 140.

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

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

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

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

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

Подписано к печати 23.11.8« г. Ш 08608 Формат бумаги 60x84 1/16. Объем I п.л. 0,8 уч.-изд.л. Заказ Й 312 Тираж 100 экз.

Отпечатано на ротапринте Института математики СО All СССР 630090, Новосибирск, 90