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

российская академия наук

ИНСТИТУТ ПРОБЛЕМ КИБЕРНЕТИКИ

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

ЗАВРИЕВ Сергей Константинович

УДК 519.8

ПОМЕХОУСТОЙЧИВОСТЬ МЕТОДОВ НЕЛИНЕЙНОЙ ОПТИМИЗАЦИИ

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

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

Диссертация на соискание ученой степени доктора физико-математических наук (в форме научного доклада)

МОСКВА - 1992

Работа выполнена на факультете вычислительной математики и кибернетики Московского государственного университета им.М.В.Ломоносова.

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

профессор Ф.П.Васильев

доктор физико-математических наук, профессор В.Г.Карыанов

доктор "физико-математических наук, профессор Р.Г.Стронгин

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

Защита состоится "_"_1993 года в _часов

на заседании Специализированного Совета Д 003.78.01 по защите диссертаций на соискание ученой степени доктора наук при Институте проблем кибернетики РАН (117312, Москва, ул.Вавилова, 37).

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

Диссертация разослана

•Зй. : илсурття^ 1993 г.

Ученый секретарь Специализированного Совета к.ф.-ы.н. ---^ М.Ю.Беляев

Введение

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

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

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

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

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

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

Научная новизна работы состоит в следующем:

1. Впервые с единых позиций — на основе развитого в работе аппарата прямого метода Ляпунова — исследованы свойства сходимости

широкого круга алгоритмов нелинейной оптимизации при наличии неубывающих помех.

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

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

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

1. Прямой метод Ляпунова для анализа свойств притяжения (сходимости) итерационных процессов

1.1. Необходимость анализа устойчивости, в частности, притяжения (сходимости) итерационных процессов возникает в различных областях прикладной математики, например, в теории автоматического регулирования и численном анализе. Так, математический аппарат прямого (так называемого второго) метода Ляпунова развивался рядом исследователей специально исходя из потребностей анализа численных методов нелинейной оптимизации (см.работы В.А.Волкопского, Ю.Г.Евтушенко, И.И.Еремина, Ю.М.Ермольева, В.Г.Карманова, Ю.ИЛюбича, Г.Д.Майстровского, Е.А.Нурминского, Б.Т.По-ляка, \У.гапцт11, Е.Ро1ак, Й.Я.Меуег, С.О.Ь-Меуег и др.). Однако разработанная техника анализа сходимости часто не может быть применена при исследовании свойств оптимизационных алгоритмов при наличии помех. В настоящей части работы предложено развитие аппарата прямого метода

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

Рассмотрим итерационный процесс

Л: хЛНбУ(|г,хл), 4=4,2,..., ас'бХ,

где — точечно-множественное ото-

бражение, Д/ — натуральный рад, X с /? ^ — компакт, ( X ) — множество всех подмножеств мерное координатное пространство.

Для произвольной ограниченной последовательности Х^^ обозначим через -Уй { ОСп'} совокупность ее предельных точек и будем говорить, что последовательность {Эс'1,} притягивается (сходится) к множеству А , если

&{хп}сА

Пусть

'X обозначает совокупность всевозможных траекторий процесса XI , множество ОС ,

ос = и -ёЬ{ха}

мы будем называть аттрактором итерационного процесса ГТ. . Нашей задачей является нахождение (или по-крайней мере оценивание) множества

ОС .

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

на траекториях процесса, т.е. к анализу свойств убывания образов этих траекторий. В

случае процессов с непрерывным временем, например,

х = (ос) , ± £ С0,оо) , х(0)еХ,

это предполагает рассмотрение множества А 0 ,

А0 = {*еХ|< ^Сх)>>о},

т.е. такого множества, что функция VIO убывает на траекториях -процесса при движении их вне множества А0- После чего, при некоторых дополнительных условиях, в том числе в предположении о монотонном невозрастании V (•) на траекториях процесса, показывается, что всякая траектория притягивается (сходится) с множеству А0 ■

В случае дискретного времени для анализа локальной V(')— монотонности процесса Л. в точке X 6 X естественно рассмотреть величину

seV(a.x')

которую мы назовем величиной гарантированного предельного

VW-

убывания процесса XX в точке ЭССХ. Аналогично случаю непрерывного времени, в классическом предположении о том, что

veo есть функция

невозрастания (descent function — сокращенно d.f.) процесса Л . Т.е.

V(xn+IK Vlxa}GÍX?f (1.1)

известно, что всякая траектория процесса f\ притягивается к

множеству А. (0) ,

А(о) = {хбХ!&Сх)<о].

Скалярный критерий V (•) , применяемый при подобном анализе, называется функцией Ляпунова.

Специфика предлагаемого развития прямого метода Ляпунова состоит в следующем:

Во-первых, мы не требуем, чтобы функция Ляпунова V( • ^ являлась d.f. итерационного процесса П , т.е. условие (1.1) может нарушаться. Причиной этого является то, что для многих возмущенных итерационных процессов нетривиальной" функции невозрастания просто не существует. Поэтому нам необходим математический аппарат, позволяющий, в частности, применять d.f. невозмущенных процессов (процессов без помех) для анализа устойчивости процессов при наличии помех. Таким образом, в соответствии с предлагаемым подходом любая ограниченная снизу

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

свойствами неубывания V0) на траекториях процесса.

Во-вторых, при анализе устойчивости _ итерационных процессов мы будем использовать для оценивания аттракторов не только стандартный показатель Gr (•) гарантированного V(0~ убывания, но рассмотрим различные способы его масштабирования, позволяющие существенного уточнить получаемые оценки аттракторов.

1.2. Пусть функция V (• , • ) на 1Ы *Х такова, что,

Uif V(n, X ) > -ОО,

далее, мы будем рассматривать

в качестве функции Ляпунова итерационного процесса Л . Для простоты предположим, что функция V (•) не зависит от И и является непрерывной на X •

Обобщая определение множества

А(о)

, положим

A(g) = {xeXi GCxHo},

Множества A(<j), ^^ 0 , будут использоваться в работе для оценивания аттрактора итерационного процесса

п

. Однако, в некоторых

случаях, получаемые таким образом оценки оказываются слишком грубыми. Поэтому мы введем множества , dí U > определяемые с

использованием более тонкого (по сравнению с определением А. (О)) анализа

vio-

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

Положим

£о={хеХ13£>оЗЛ/€/Л/: \/зс'еВ£(ос)лХ Vn>A/

где 11Х'-Х||< £} , Е>0 . Лепсо

увидеть, что согласно определению множества 0 при достаточно больших П. функция Ляпунова ) монотонно не убывает на всякой траектории процесса, пока та движется вне ■

Пусть

Т-^^^^^и^О.я--!,г,...Д^^оо},

можно счЕггать, что всякое ^Т задает соответствующую

дискретизацию времени -^"Ь ^ на [.О, оо) по правилу:

Для любого ТГ

бТ определим

полагая

( + со , если а > О ;

О ОО , £СЛМ а< о.

Величину — 1)г£ У(х) естественно назвать предельной верхней производной на процессе XI. по времени, задаваемом ^ ,

в точке Х^-Х .

Положим

^ ={осбХ I

Л = П ^ . -гет

Далее определим величину

назовем предельной верхней производной

ЧО) на

процессе п по перемещению в точке осеХ . Положим

Лемма1.1. Множества , — непусты

и компактны, компакты, причем

Ж0с jb п Jk^ с и с А (оу

Введем также следующее расширение отображения V(-)-' R^ — точечно-множественное отображение Е V (•") X" ЭТ7 ( R ^") ,

EV(x)=[V(x), V(x) + müx(o;-fr(x))] cRd.

Легко увидеть, что Е V(' ) — замкнутое выпуклозначное отображение, причем в случае, кода V( • ) является d.i. процесса XI справедливо равенство

Множество Ас X назовем

Е V0)-

связным, если — связное. Нетрудно показать, что всякий

XGÍK

компакт X' С X может быть единственным образом представлен

в виде объединения непересекающихся Е\/(')- связных компонент. Более того, каждая £]/(')- связная компонента есть компакт и является объединением нескольких связных (в обычном смысле) компонент множества

Центральную роль при анализе притяжения итерационных процессов играет

Утверждение 1.1. Для всякой траектории "{X итерационного процесса -П. справедливо хотя бы одно из следующих утверждений:

У1. Существует предел -¿tm. "X — Х0 , причем X £

Л

У2. Существует предел -Lim, V (X ) — 1/ , причем

V Р П V( Л ^ и { эса1 притягивается к множеству Je^.

0 тет ri/r,

УЗ. 1) Существует такая С\1{')- связная компонента «T^q множества

, что

VClHx^cEVWx^ П Л^);

I ^nl

2) всякая подпоследовательность -[X J , удовлетворяющая

условию

Ит. \/Схт,г)= VCx"'), (О)

11 "♦ОО П. —»QO

притягивается к ^ ; более того, если

Mm, И тс"-- oca+Mi=0 , (")

n->oo i

то всякая подпоследовательность X "'Зг , удовлетворяющая условию о

= V(XA), (1.4)

П.-9СО П-+00 '

притягивается к

3) всякая подпоследовательность {х , удовлетворяющая условию I

iW^ Wg* VCx ) + f

притягивается кА($).

Мы: видим, что свойства сходимости траекторий итерационного

процесса XL существенно зависят от топологической структуры множества

Утверждение 1.1 дает нам ряд важных следствий.

Теорема 1.1. Всякая траектория}^]-итерационного процесса-П. обладает следующими свойствами:

1) найдется такая EV (• г— связная компонента

множества , что

■ft {VCx*1)}

2) всякая подпоследовательность X удовлетворяющая

условию (1.2) (и при выполнении (1.3) всякая подпоследовательность ^ » Удовлетворяющая (1.4)) притягивается к С/ щ. •

Теорема 1.2. Всякая траектория ^Х^^итерационного процесса П. обладает следующими свойствами:

1) {Ха} притягивается к АС^^, 9„= ¿^р У(х"1)-

IX-> сто

I р Т.

2) всякая подпоследовательность ^Х 1 , удовлетворяющая (1.2), притягивается к

Теорема 1.3. Пусть Сг(х) >0 ва X и Л/Х^&о^) нище не плотно в К. ^ .

Тоща всякая траектория ^Х^] итерационного процесса П- притягивается к некоторой \/(") ~ связной компоненте множества Д.

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

является ¿Л. процесса. п .

Тоща всякая траектория ^Х*"1} итерационного процесса Г\ притягивается к некоторой

VI.)-

связной компоненте множества

Получены обобщения утверждения 1.1 и теорем 1.1-1.4, позволяющие при анализе устойчивости итерационных процессов применять функции Ляпунова А/Х1,31) существенно зависящие от номера итерации И. , а также рассматривать вероятностные процессы.

1.3. Для итерационных процессов, траектории которых удовлетворяют условию (1.2), теорема 5.1 может быть существенно усилена.

Рассмотрим итерационный процесс

где (ЙО — точечно-множественное отображение; числовая последовательность { СХ.^^ удовлетворяет условию 00

,п.=ч,1 . ,^ггь а =0, 2 а=оо

^ ' ' ' П.-»со ги Г1=4

помехи (г 1,2таковы, что

ряд О сходится

00

П = 1 п

(содержательно помехи такого типа имеют, как правило, вероятностную природу).

Введем некоторые обозначения. Для произвольной точки числа £ > О и множества А с К- ^ положим

II^-XIK &} , через ufit" А , d A H " - conv А будем обозначать соответственно внутренность, замыкание и выпуклую оболочку множества А

Нашей целью является анализ свойств протяжения траекторий { ОСа } итерационного процесса П , удовлетворяющих . условию

где

— некоторый компакт.

Относительно отображения ф (•, •) мы предположим следующее: найдется такое

отображение Ф0(- V- R ^ — 7П (Rj^

замкнутое и ограниченное в окрестности X , что для любых ЭСбХн О найдутся такие

A/etfV

и 5>0 , для которых

и и ■ф(л,|Ос ВДс^ Ф СхУ). уеВ^Сао ь

Ясно, что отображение С') на множестве ЗС является в некотором смысле верхним пределом семейства отображений ^ Ф ( П. , • ) у

Напомним, что локально-липшицева функция ) называется

регулярной в точке I £r R^ , если ) дифференцируема в ОС по любому направлению и ее производная ^^ -ß (эс/) по произвольному направлению Q удовлетворяет равенству

Кrruvoc < 9,€>,

где обозначает дифференциал Кларка функции ) в точке.

xeRk.

Фиксируем произвольную функцию V (.' ) . регулярную в окрестности X

Положим

= с£ {хеХ I ^лос mJun. < ^,

iuhcx) дефдо

Н(Х~)= ccmv {"ЭУСхО и К Сх")} ,

где КХ (х~) ^ обозначает конус нормалей к множеству X в точке Х(:Х. т.е. К^л (ос) есть сопряженный конус к контингентному конусу, определяемому как коническая оболочка множества

Справедлива следующая

Теорема 1.5. Всякая траектория {х*1^- итерационного процесса И , удовлетворяющая (1.5), такова, что выполнено следующее:

. 1) найдется такая связная компонента Л'» мно-

жества Л , для которой

2) всякая подпоследовательность { ЭС Г1"} С 1 ) ,

удовлетворяющая условию (1.2) ((1.4)) притягивается к

Следствие 1.1. Если множествоУ(«Л) нигде не плотно в , то всякая траектория ■{_ итерационного процесса П , удов-

летворяющая (1-5), притягивается к некоторой связной компоненте множества с4: .

Следствие 1.2. Если ^

У( ^ У(ха) + ... , ряд сходится,

а г

то траектория X Д , удовлетворяющая (1.5), притягивается к некоторой связной компоненте множества ¿¿к

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

2.1. Рассмотрим задачу математического программирования

9: ^ .

А = {хеХ | Сх) = 0,и4,...,тм,

где функции ^ С О > L~ 1 >-■•■» ^ • предполагаются не- •

прерывными и. непрерывно дифференцируемыми на

Положим

Р ХбА

■xflpt = {эс£а i 4opt }

(далее мы будем считать, что

> -оо и X0/)t Ф )•

На практике нередки ситуации, когда при решении оптимизационной задачи мы не располагаем точной информацией о значениях целевой функции и функций, задающих ограничения. Это может быть связано с особенностями изучаемой модели, погрешностями вычислений, ошибками округленна н т.д. Таким образом, применяемые численные алгоритмы оптимизации будут содержать помехи в используемых характеристиках задачи, т.е. на n-ой итерации алгоритма вместо, например, ^(СС ) и V-fCr/1) будут использоваться ¿(х'г)+Д0(п>х])п V#acft) Д.^ (л,Х*1), где До (П ,Х) G R^ , R^ — соответственно по-

мехи в значение целевой функции и ее градиенте в точке ЭС& R на п-ой итерации алгоритма. Влияние помех (возмущений) на свойства сходимости итерационных алгоритмов изучалось многими исследователями (см. работы Ф.П.Васильева, В.И.Норкнна, Б.Т.Поляка, J.E.Dennis, R.S.Dembo, R.Fontecilla, T.Steinhaug, TJ.Ypma, H.F.Walker и др.). Однако, как правило, в таких исследованиях рассматриваются помехи, удовлетворяющие условиям

itm. лир | &оО>эО\ = 0-

или, например, для задач безусловной оптимизации, ограничениям следующего типа!

«е1 II v|Cx)H, II ^(a.x^lU эе2 II v^Cx^ll,

h.= А,г,..., хб R^, , эд^const,1.

Часто допускаются только неточности в решении вспомогательных подзадач линейного (квадратичного) поиска (см., например, работы A.Tassopoulos и S.Storey (1984), J.L.Nazareth (1986), SJ.Wright (1987)). В некоторых случаях рассматриваемые классы возмущений определяются чрезвычайно сложно (см., например, работы P.E.Gill, W.Murray, M.A.Saunders и M.H.Wright (1982), R.De Leone, M.Gaudioso и L.Grippo (1984), L.Grippo, F.Lampariello и S.Lucidi (1988)), но общая черта подавляющего большинства этих исследований состоит в том, что в изучаемых ситуациях помехи стремятся к нулю,

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

Мы изучаем устойчивость оптимизационных алгоритмов по отношению к неопределенным неубывающим помехам, т.е. кода на n-ой итерации алгоритма погрешности, например, в значениях и V-^ С' ) удов-

летворяют лишь следующему ограничению:

где ¿0 , О , величины ¿в и Ь^ назовем уровнями соот-

ветствующих помех в алгоритме. Нашей задачей будет являться оценивание аттракторов возмущенных алгоритмов через уровни допускаемых помех (в частности через £с и ). В такой постановке помехоустойчивость алгоритмов нелинейной оптимизации изучена мало (отметим лишь отдельные работы P.T.Boggs и J.E.Dennis (1976), Ypma (1983), Б.Т.Поляка (1983), J.E.Dennis, H.F.Walker (1985), П.А.Дорофеева (1985)). Возможность проведения исследований в указанном направлении дает развитый нами

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

2.2. Градиентный метод. Рассмотрим задачу безусловной оптимизации:

90 £ (ОС,4) тхл,

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

обозначает класс вектор-функций, удовлетворяющих условию Липшица на множестве X с постоянной 1»>0 ).

Положим Xstat =

Далее, для упрощения формулировок, мы будем предполагать, что множества X(lO и Xsia{ (£) ограничены при всех Xf^Rj н£>0.

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

Предположение 2.1. Пусть (■ ) сильно выпукла на R^ с постоянной -б > О

Простейший алгоритм метода градиентного спуска имеет следующий

вид:

= г,

где OL/* О — шаговый множитель, AfL ; ЭС. £ — начальное

приближение.

Справедлива следующая

Теорема 2.1. Для всякой траектории {.Х*1^ алгоритма &М 4. выполнено следующее:

1) найдется такая КО- связная-компонента множества , что

( 1

2) всякая подпоследовательность ^ X ^ , удовлетворяющая

условию

Ипъ Кэс^^)^ ^¡п* ^х"-), (2.1)

а-»оо п.-»оо

притягивается к множеству С ^ч ^^^ ;

3) если, дополнительно, справедливо предположение 2.1, то { ХЛ притягивается к множеству X ( £ 4 / 2 £ ) .

Рассмотрим более сложный алгоритм градиентного метода, называемый методом скорейшего градиентного спуска:

&М2: хп+"= хл-ап кпу ЛуАх^+д^мЛ

где шаговые множители ^ СЬ ^ } определяются из условий:

Л- ^ О

> О — параметр, характеризующий точность линейного поиска, > 2£„

(мы полагаем Д.0 (.о,-)= ) ); начальное при-

ближение.

Теорема 2.2. Для всякой траектории {_ Х^" алгоритма б- М 2. выполнено следующее:

притягивается к множеству

2) всякая подпоследовательность { X удовлетворяющая условию (2.1), притягивается к множеству

3) если, дополнительно, справедливо предположение 2.1; то 1 притягивается г множеству

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

2.3. Метод покоординатного спуска." Изучим помехоустойчивость метода циклического покоординатного спуска.

Пусть в задаче

90

функция цели

и

• выпукла на •

Примем обозначения

^ = 1 ^ 5: —ортонормированный

базис .

согласно определению СО — "возмущенная" целевая функция задачи. Рассмотрим следующий алгоритм метода покоординатного спуска: Шаг 1. Положить К- == О

хЧХ1,

Шаг 2. Положить п = П. + А . Фиксировать ^ » • • • » ^ и" \ ^ §з И положить

- а

1

21-1 I ' с • и 1»•••>*■

Положить

ха = хЛ ; < = гГЛ •

о > Л п. )

Шаг 3. Положить = + 4 . Если } > 2 к , то перейти к шагу 5.

— п. — П.

Шаг 4. Вычислить ^ С П,, X + ).

~ _ п. 11

Если Ч-а^е^. )< -й^/2,то положить

х л ХИ + * е1 *

иначе положить

— а — п.

уг> » УГ*'\ 1г п.

Перейти к шагу 3.

Шаг 5. Положить Iг+1 — и,

х -^гК'

V - Vй •

п+н п >

_ Гвап. ,£СА* ^п-м =ггп,;

^ I <4,«*«

Перейти к шагу 2. Здесь

— параметр дробления шага, 0-о —

начальный параметр шага,

ае> г УбТТ^м

X С. — множество начальных приближений, X — компакт.

Ортонормированный базис на п-ой

итерации алгоритма может быть выбран простейшим образом:

п а

или, например, в может быть получен из X ? ^С и

£ с помощью процедуры Грамма-Шмидта.

Пусть

1)= ¿ишь | -К*^ ""ЮС. +

* х'бХ^

Справедлива следующая

Теорема 2.3. Всякая траектория {х"- 5 алгоритма С 1)1*1 притягивается к множеству

Если, дополнительно выполнено предположение 2.1, то {ОС1$ притягивается к множеству

Хор, (еДС^+т^+^/^ + гО-

Очевидно, что если в градиентном алгоритме

вычисляется по

формулам конечных разностей в условиях неточного задания 4-0 ) уровень помех в градиенте удовлетворяет условию £^>2 . Сравнивая

теперь результаты теорем 2.1, 2.2 н теоремы 2.3 (и учитывая неулучшаемость оценок теорем 2.1, 2.2) мы видим, что при О близких к единице метод покоординатного спуска оказывается более помехоустойчивым по сравнению с градиентным методом (алгоритм

съм

имеет меньших аттрактор по сравнению с алгоритмами &М1 и (гМ 2 ).

2.4. Метод Ньютона. Рассмотрим задачу в предположении 2.1.

• Пусть целевая функция £ (,' ) дважды непрерывно дифференцируема в окрестности В £>СХ0") решения задачи Х0 , V ^ С О £ ^Чр (. и

О < ьг ^ V2< М Ух^Б^С^.

Возмущенный метод Ньютона решения задачи

имеет следующий вид:

м-. эсгг+1 = ха-су^с^гЧкх"-)-^

где А( П. , ЭС.) — "суммарная" погрешность определения вектора сдвига на п-ой итерации алгоритма, образуемая

погрешностями определения гессиана, градиента, обращения гессиана, ошибками округления и. т.д.,

11 Ск-.х4) ¿^ Ухб Вр^Сх^ ,

Е у, > 0 — уровень погрешности;

X С - множество

начальных приближений.

Лемма 2.1. Найдутся такие 6 > 0 и окрестность ЪГ точки Хс , при которых для всякой траектории •{_ Х*1^ алгоритма /УМ с £ ^ £• выполнено следующее:

Оценку аттрактора возмущенного метода Ньютона с достаточно малым уровнем помех дает следующая

Теорема 2.4. Всякая траектория ^Х ^ алгоритма

А/М с Х=ии

^ £ притягивается к множеству

(с 4 - е^ Lг/г т)г - 2М е^ 1г/ тг}).

Показано, что в квадратичном случае полученная оценка гвляется точной.

2.5. Метод сопряженных градиентов. Рассмотрим задачу

90

в

предположении 2.1. Известный метод сопряженных градиентов в условиях помех имеет следующий вид:

СТ&М: а*" = ха+ ап

О п л П. , 0 ПН

Л + *л-р ,

Здесь числовая последовательность {^ ^ определяется по правилу

0, если

если 1= \ % , •

шаговые множители удовлетворяют условиям:

где — точность решения подзадач линейного поиска, . и

«-кгил { т.) = ос. = X }

/

(как н ранее формально полагаем ОС в — начальное приближение.

Справедлива

Теорема 2.5. Всякая траектория

{Л

алгоритма СТ&М

притягивается

к множеству Л^

2.6. Метод штрафных функций. Рассмотрим задачу математического программирования (ограничения-равенства отсутствуют) в пред-

положений, что X ^ — выпуклый компакт, А а X,

^(0,1= иг

или

Пусть ограничения задачи _) удовлетворяют следующему условию регулярности:

Я Сх4) = < I ^ гш. | д ¡_ ^ о у ф #

Легко вцдеть,' что (2.2) гарантируется, в частности, выполнением условия Слейтера.

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

Предположение 2.2. Пусть функции (• ") ), ,

выпуклы на X

Особое место среди задач математического программирования занимают так называемые "острые" задачи. Напомним (см.работы Б.Т.Поляка, А.Сготте, М-С-Ретя), что задача £Р называется $ - острой, ¿>0 , если

> У? Сх,Х0^ ) УхеА,

где ^Сх,Х)= Чг ЛI-

Далее вам потребуется рад обозначений. Пусть

АС*-)«

Положим

т, _

X Х^^Дх^ п В.(0)^0 I = ы

* П . _

X. estât — множество стационарных точек задачи условной оп- . химизации с ограничениями-неравенствами.

Сводя задачу ÇP с помощью метода штрафных (внешних штрафных) функций (см.работы Ф.П.Васильева, И.И.Еремина, В.Г.Кармапова, А.А.Каплана, Б.Т.Поляка, В.В.Федорова, A.V.Fiacco, G.P.McConnic, E.Polak, D.P.Bertsekas, O.L.Mangasarian и др.) к задаче

, пг о . .

* • хеХ

О 0 — штрафной параметр, и применяя градиентный метод при итеративном возрастании С , мы приходим к следующему алгоритму метода штрафных функций: П+<

+ С л % тх^ С о \ 9 ^ X» V 9 с о^Л ), п = 1, 2.,... , хЧХ.

где (•) — оператор проектирования на X , С^ / ц-оо , шаговые множители {<2п} удовлетворяют, например, следующему условию:

ч- а=|

хЧX

— начальное приближение.

Теорема 2.6. Для всякой траектории ^ алгоритма б-РМ

выполнено следующее:

1) найдется такая связная компонента С^) ^мно-

жества Хсиа(г С ^ ) . что

2) всякая подпоследовательность ; удовлетворяющая

условию

( ■е^ (^.«ч»)

притягивается к множеству С ^ ^ I

3) если, дополнительно, выполнено предположение 2.2, то

{хЧ

притягивается * множеству , 3)" А ;

4) если выполнено предположение 2.2 и задача ^Р является - острой, то при ^ траектория ^ХЛ][притягивается к .

В случае, когда иг£" А-^ 0 для решения задачи ^Р применим метод барьерных (внутренних штрафных) функций (см.работы Ф.П.Васильева, М.Ковач, Ю.Г.Евтушенко, А-У.Кассо, О.Р.МсСопшс, К.-Н.ЕЫег, РА.1лойта и др.), суть которого состоит ж сведении этой задачи к задачам

зсеи^А

т, .

и минимизации ^^ С' > ^ги) с помощью алгоритмов безусловной оптимизации. Так, градиентный алгоритм итеративного метода барьерных функций имеет следующий вид:

&ВМ: х*"« +

1-й .

хч £ и* А ,

где О.Л-Ч*,-- шаговые множители, — параметры барьера.

Показано, что. при неограничительных условиях на управляющие параметры и свойства устойчивости алгоритма бЬЛ вполне

аналогичны свойствам алгоритма G-PM (см.теорему 2.6).

Если в алгоритмах градиенты функций ограничений

V^ Сх) , , . ,'П. , вычисляются на n-ой итерации соответственно с помехами А^. ■>

И/^Ч^МК £j «Ъ Vx6-X,

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

Xesiat С . ^ , - , ) - { А 1 В V -. X т>0:

_ гл _

ЪаМ&Ъ + Z, \ Ь i эО,

Ч =0, L «■(,... , rwV

2.7. Квазиградиентный метод. Обратимся к задачам негладкой оптимизации (см.работы В.Ф.Демьянова, Б.Н.Пшеничного, В.В.Федорова, F.H.Clarke, O.L.Mangasarian, R.Mifflin, S.M.Robinson, R.T.Rockafellar н др.). Мы откажемся от предположений дифференцируемости функций 4С-) > PiO,1"'»-в ЗЗД24® ^ ст^-О и потребуем лишь их лишпицевости и регулярности в окрестности выпуклого компакта

Условия (2.2) регулярности ограничений задачи . ^ в негладком случае примут вид:

eonv {dgLLx.-),L€Rtx)]+K*(x)ßfo УхбХДху?.™

Для решения негладких задач разработан ряд итерационных квазиградиентных алгоритмов.(см. работы И.И.Еремина, Ю.М.Ермольева, А.С.Не-мировского, Ю.Е.Нестерова, В.И.Норкина, БТ.Поляка, Б.Н.Пшеничного, Е.А.Нурминского, С.В.Ржевского, Н.З.Шора, Д.Б.Юдина, C.Lemarechal, K.C.Kiviel и др.), мы рассмотрим метод, предложенный Б.Т.Поляком. Будем предполагать, что значения функций ( > ) , ¿= •{,..., IU,

задающих ограничения зада ну точно, а квазиградиенты

, I = ^ на п-ой итерации алгоритма вы-

числяются с погрешностями А,, (п., х), Д.^ - , ^ »

соответственно, причем

, II Л^ (.л, ху|| ^ , 1-1,..., т., УхеХ.

П.-1,2.,...

Таким образом, мы приходим к следующему итерационному алгоритму: л л 11 »1+<1 , ч и, ^

(З&М: х = р*.

/■ = 5 (У") + А, рс.л ) , если € А.;

РЛ € сопл, { (а^),'^^)},

ЕСЛИ Х^ А

где =

" кит.

шаговые множители -(0.а \ таковы, что

— начальное приближение. Введем , £4„)- стационарное множество задачи —

с О-{*€А1

— лг- __.

Справедлива

Теорема 2.7. Пусть уровни погрешностей , I ■= 4 ,. ■. > , в вычислении квазиградиентов функций, задающих ограничения, достаточно

малы, так что

сспу{-В£| (Э£.(х1),абЯ(*)}+ К* <24>

Тогда всякая траектория {х^ } алгоритма £}&.М обладает следующими свойствами:

1) найдется такая ^С* ) - связная компонента Х^^^С^}

множества Хс^а* (£1 ■> ^ >• ■• > ^ ^ . что

2) всякая подпоследовательность { X л} удовлетворяющая условию

^(х^^&т^ ¿(х"') С«)

1Х-*оО 1 4 ' П-+00 гч ' п-г-со I '

притягивается к множеству ^сяьа* » ) ' ^ ;

3) если, дополнительно, выполнено предположение 2.2 и 0 ¡,= \ ^ ' то|х 3 притягивается к множеству

Хо^ФО, Ь = вгсая1, Л;

4) если выполнено предположение 2.2, задача ^Р является % - острой и < у , = 0,"г. , то-{х11} притягивается

к рЪ • [

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

2.9. Построены новые конечно-разностные алгоритмы приближенной глобальной минимизации £ - выпуклых функций. Обоснование алгоритмов базируется на полученных оценках аттракторов возмущенных градиентного метода и метода циклического покоординатного спуска.

3. Устойчивость стохастических квазиградиентных алгоритмов решения минимаксных задач

3.1. В современной теории исследования операций существенно продвинута методология построения сложных, .учитывающих многообразную информацию, моделей. Разработаны принципы формирования критериев эффективности в случаях зависимости исхода операции от неконтролируемых и случайных факторов, наличия у оперирующей стороны не одной, а нескольких целей с имеющейся информацией о приоритетах этих целей, развита теория игр с непротивоположными интересами (см. работы Ю.Б.Гермейера, Н.Н.Моисеева, А-А.Васина, А.Ф.Каноненко, Н.В.Кукушкина, В.В.Морозова, В.В.Подиновского, В.В.Федорова и др.). Это в свою очередь привело к постановке широкого класса оптимизационных задач нестандартного, более сложного по сравнению с классическими гладкими и регулярными задачами математического программирования, вида и потребовало создания эффективных численных методов их решения.

Характерной чертой оптимизационных задач исследования операций является минимаксная структура целевых функционалов и функционалов, задающих ограничения, возникающая в следствии применения принципа гарантированного результата при учете в критериях эффективности модели неконтролируемых факторов. Фундаментальный подход к анализу минимаксных задач был разработан Ю.Б.Гермейером и В.В.Федоровым и состоит в сведении этих задач к задачам стохастического программирования:

хеА

А= € XI ^ 0 , 1=-1...., га. } , ¿«4,...,га,

где /4 _ вероятностная мера на

- компакт,

— б*- алгебра борелевских множеств на X . Стандартные итерационные алгоритмы оптимизации не могут быть непосредственно

применены для решения задачи SrP в связи со сложностями вычисления . с заданной точностью интегралов по V" на каждой итерации и, значит, возникает необходимость создания специальных методов стохастического программирования. Ю.М.Ермольевым был предложен способ построения методов решения задач , состоящий в том, что в стандартном

(детерминированном) оптимизационном алгоритме решения • задачи S51 на п-ой итерации значения

вычисляются по методу Монте-Карло или с использованием процедур стохастической аппроксимации типа Робннса-Монро. В дальнейшем этот подход разрабатывался в работах А.М.Гупала, Ю.М.Каниовского, В.Я.Кат-ковника, Н.М.Новиковой, В.И.Норюгаа, Е.А.Нурминского, Б.Т.Поляка и др.

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

В настоящей части представляемой работы усовершенствован математический аппарат построения стохастических аналогов детерминированных итерационных процессов, исследована устойчивость по отношению к неубывающим помехам метода проекции стохастических квазиградиентов, сконструированы и обоснованы стохастические квазиградиентные алгоритмы решения широкого крута оптимизационных задач исследования операций, в том числе минимаксных задач со связанными переменными, двухэтапных лексикографических минимаксных задач и задач оптимизации с бесконечным числом ограничений (так называемых semi-infinite programming problems — задач полубесконечного программирования).

3.2. Введем обозначения

_ _ оо _ оо _ оо

Y00=.®r,^00=.® £а , /<00-®^,

1 = 1

Мы видим, что стохастические алгоритмы решения задачи суть правила построения последовательностей случайных величин (с.в.)\ Х^ва вероятностном пространстве

Рассмотрена общая процедура стохастической аппроксимации типа Робинса-Монро и получены оценки ее скорости сходимости в среднем и ум оо — почти наверное (п.н.) Также" получены оценки случайных возмущений, возникающих при переходе от детерминированного процесса общего вида к его стохастическому аналогу посредством прямого вычисления характеристик по методу Монте-Карло. Эти результаты существенно использованы далее при построении стохастических аналогов сложных детерминированных алгоритмов оптимизации.

3.3. Пусть в задаче

¿9 функции ГЧО, о,лг- ,

непрерывны на и регулярны

на X для любого У , ¿= О, А,... , П , А С. йгЛ: X

Хс — выпуклый компакт и ограничения удовлетворяют условию регулярности (2.3).

Стохастический аналог квазиградиентного метода Б.Т.Поляка имеет следующий вид:

Г (х"\ у"-)+ ( и, Vй, и"-), Еслм аЛо;

=1

где & (х, ■ ) — произвольный стохастический квазиградиент случайной функции р в точке Х£ X . »У")^* Р1 "Сх»для

любого у £г У I 0, -f...т ( Г(х, ^обозначает обобщенный дифференциал Ф.Кларка функции F0 > ^ ) в точке X );

— реализация c.b.IJ , распределенной на ( Y^53)b соответствии с мерой , в п-ом независимом испытании, ^ = "(,2,..- ;

помехи Д.^ (rt, Ха, {,=0, измеримы, 11= 4 , 2 ,... и

подчинены оценке

II (а, < Ц J ^ (а, х, ^ , tt= 4,2,... , X £ X , </ € Y,

^ >0 , i = 0,, ЛЬ — уровни соответствующих помех;

ti J — числовые последовательности, удовлетворяющие следующим условиям:

в-п'^п,-*0,

( X ^ * , . • - > ^.^пг ) — начальное приближение.

Пусть уровни помех , fij £в алгоритме ¿QG-Mдо-

статочно малы, так что выполнено условие (2.4).

Теорема 3.1. Всякая траектория | Х1^ 1 алгоритма ¿Q&M. ^^ п.н. такова, что

1) найдется такая_ }— связная компонента Xcsfca£ ,

множества Xcstat Д™ которой

4СхМ = К IE { Xa} n Xtttat U<,

2) всякая подпоследовательность { X a J, удовлетворяющая условию (2.5), притягивается к множеству

Если выполнено предположение 2.2 и 8^ = 0 , l = f,..., ^ , то

{Л М

сю п-н- притягивается к множеству

Xopt СDfO,

I)= cLLam- Л.

Если выполнено предположение 2.2, задача является ^ — острой и £ < , =0 , , то притягивается х ХС(Л .

3.4. Рассмотрим задачу полубесконечного программирования

осе А

А = \хбХ1 о УуеУ},

где функции ") , ^ С* ) непрерывны на X х~¥ и выпуклы по X в окрестности выпуклого компакта для любого

у £ у У С £ ^ — компакт.

В применении к задаче ¿^{Р стохастический субградиентный аналог алгоритма

(2&М (см.2.7) имеет следующий вид:

а «

где , ГЬ

Ъ>х с**, УЧ**, ^)>ЕСЛИ

¡к*1*4.

шааос (.0 ; (р ;

^^— реализация с.в. , распределенной на СУ", соответствии с мерой , в п-ом независимом испытании, причем мера /Л тйхова, что пересечение любого открытого множества с

имеет положительную меру;

случайный вектор ^""(.Х^ ^ ^ } — "^п- измеРим и

числовые последовательности ■{ , \ ^"гь^ и ^пД Удов-

летворяют условиям:

» V-. >0, П.-1.1,... ; а,Лг -6^0, ^ о; ^^ С ¿-п,- а-н V ^п. ¿-П.-Ч < 1 ',

1Х->оо

начальное приближение.

Теорема 3.2. Всякая траектория XП } алгоритма 5 Ц&М1 ¡^^ п.н. притягивается к Х^.

Стохастический субградиентный аналог алгоритма

(см.2.6)

имеет следующий вид:

л«*,г,...,

где числовые последовательности ^ ^ и С ^ ^ удовлетворяют следующим ■ условиям:

°° 00 г 2,

2 а,„ = оо \ 2 С„ < оо •

остальные параметры те же, что и в предыдущем алгоритме.

Теорема 3.3. Всякая траектория ■^х'1'} алгоритма 5 & РМ. (М^ п.н. притягивается к .

3.5. Рассмотрим двухэтапную лексикографическую минимаксную задачу:

сМЛ&{: к (х)^ гш^ь ,

х^А

А = { хе X 1 1(х> Ч > ггшг ггш/х

где функции

> О , 4о 0 предполагаются выпуклыми по X в окрестности выпуклого компакта X С й Ь для любого £

т,

и непрерывными на множестве ЗС* V", (.X '^ € , 11 ) для любого .X &

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

мизационных задач.

Следующий алгоритм является развитием алгоритма & РМ:

S&PM: иЛ^^^-а^),

^ = о , в протиьшж случае j

где V = X*U =

f < СО 7 Г СОт

числовые последовательности > u^n, J® i'"' (г ^таковы, что

<Ln>cn\ > о, >U,..., aft,ca&Uo; to _ . ^ * ( „«К*

> 2 (Lft ) < OO'

начальное приближение^ остальные параметры те же, что и ранее.

Теорема 3.4. Всякая траектория (т^,и!1)]алгоритмаЬ5'РМ1 ^ п.н. притягивается к множеству Х^ V {4орЬ} , = Л 0*0 •

3.6. Рассмотрим задачу отыскания минимакса со связанными переменными: '

«ЛШФ2: «^-лос —^ ч

где функции '(■(•'), "^С'^ < предполагаются непрерывными

и непрерывно дифференцируемыми по X в окрестности множества

любого

Хс^ — выпуклый компакт, — компакт.

Введем обозначения

у* сх^ = \а <= ус^ I ■?^ = I*с*^>

1о и,ПУЖСхУ

Потребуем, чтобы точечно-множественное отображение УС») ; Х-*" 00 Удовлетворяло следующим условиям регулярности:

Cx.jp & У+ = Ус

для любого Положим

I з ць УСх^, Хро,

¿ = к-н , ^ А = 1, ц

^ >0, такме , что

X — множество точек, удовлетворяющих необходимые условиям

оптимальности В.В.Федорова в задаче на. связанный - минимакс.

Пусть

и) = С*, Х*1£ -V;

В применении к задаче стохастический аналог градиентного

алгоритма метода штрафных функций (см.2.6) примет следующий вид:

¿&РМ2: = иЛ- ^ сЛ, АД

-I , «о^ V,

где

гги

1=1 и

— реализация с.в. распределенной на $ВЗв соответствии с мерой ¿А ; -

числовые последовательности 7удовлетворяют ус-

ловиям:

со _

— начальное приближенна.

Ю- _ _

Для простоты предположим, что Ю 6 и , Л™'1,2Г.., оо- п.н. Теорема 3.5. Пусть множество

С X ^^^ \ — нигде не плотно.

Тоща всякая траектория ^ЦЗ^^Х , алгоритма ¿ОгРМ.2,

Мао~ п.н. притягивается к множеству V/ ^ , •

«»■сцт;

3.7. Сконструированы и обоснованы стохастические квазиградиентные алгоритмы решения более сложных по сравнению

классов

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

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

4.1. Рассмотрим задачу параметрического программирования

-?Сх/П-«- ггил, \ZteT ЬСП = {.хои ^ С*,0,

где функции »"О, ^ С* , 1 »'• •• •>пг , предполагаются выпуклыми на выпуклом компакте ^ С- Я ^ ,

Ы4,... ,т.,е ^с)для любого "I , Тс ву _

связный

компакт, °?(Х,.) , 6 Щ> (т,ь>)> 1=4,..., т.,.для лю-

бого X £ X. и ограничения задачи удовлетворяют условию Слейтера,

а = - таос. ггила. тдл а;СхД\>0..

Задачи параметрической оптимизации возникают при моделировании процессов управления (см.работы И.И.Еремина, В .Д.Мазурова, АА.Гай-воронского и др.), в многокритериальной оптимизации (см.работы В.А.Вязгина, В.В.Морозова, В.В.Нефедова, В.В.ПодиновскОго. В.В.Федорова и др.), глобальной оптимизации (смЛ.вис!сЫ, Н.ТЬЛоп£еп), стохастической оптимизации (Ю.М.Ермольев, 1.0ирасоуа, Р.КаИ и др.), методе вложения (см.работы Н.А.Бобылева, Б.ЮаПе, Н.Шаскег, Н.ТЬЛопкеп, 1.Си<1(к1 и др.). Численные алгоритмы решения параметрических оптимизационных задач изучались И.И.Ереминым, В.Д.Мазуровым, А.А.Гайворонским, Н А.Бобылевым, А.И.Пропоем, Д.М.ОПева, ДУ.С.ИешЬоИ, Л.СийсЫ, H.ThJongen и др.).

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

Положим

хемю г * Хср* (Д I *) = 1 *орЬ с-ь)+о1,

в частности, коща в задаче

функциональные ограничения отсутствуют ( т = О)

= {же XI *(*/«:)< |в|Л +

Через ) будем обозначать частную (непараметрическую)

задачу исходной задачи

99:

хе/ЧОО

Конечное множество

, назовем

, — приближенным решением ( [Ь) — решением) задачи ¿р^р^йЬ^О, ^>0 , если Т*— конечная (Ь-сеть на Т и

,х^)бХ0ргСоСЮ VI

Показана содержательность введенного понятия ^о'-. р} — решений для задач многокритериальной и глобальной оптимизации.

Для нахождения (с*. , р - решений задачи может быть

применен метод продолжения по параметру ^ решения какой-либо частной задачи

Напомним, что множество Т*= ,... ^С*Т* называется б* - цепью на Т*, если

8-ЬЛ- -Ь 11 с 1-1,..; >1

Суть алгоритмов метода продолжения для нахождения (.сА., -решений задачи (Р^Р состоит в следующем:

1) фиксируем 5 - цепь Т*= »•••» ^ на Т , являющуюся р — сетью.

2) Для начального значения параметра "Ь = ^ д находим

3) Если для некоторого И<А/, найденоX1<Г 11^)то очередное приближение

ха+< € х^Сот^)

может быть получено с помощью какой-либо простой оптимизационной процедуры решения задачи

д ' • стартующей из точки X .

Мы рассмотрим ситуацию, когда за счет выбора достаточно малых.

£> 0 , точка Ха+1 6 П.+ 4 } может быть получена

„ а

из точки X всего лишь за один шаг итерационного метода решения задачи 9 и

п+1) • Таким образом, рассматриваемые алгоритмы метода продолжения в задачах суть параметризованные алгоритмы ло-

кального поиска.

4.2. Параметризованный градиентный метод. Рассмотрим задачу ГУб

ез

функциональных ограничений, т.е. задачу

990: "ип \ZteT,

хеХ

предполагая дополнительно, что функция f С' »"t) дифференцируема по x на X и vx i (• ,t) 6 Щ> С X, Ljf ) для любого téT .

Примем

Предположение 4.1. Пусть для некоторого dL0> 0 справедливо включение

Параметризованный метод скорейшего градиентного спуска имеет следующий вид:

PG-M: ха+<= ха-алр\

и- ,л/-1,

вде Т * = {t^ ,... } CT— 6- цепь наТ^ (5> О ; параметр <i-> О ;

A^CXjt.")^ R^— погрешность вычисления градиента V^-f-Cx^B точке CX,i)6 X хТ

I^Cx.fjK ц V(x,t)e X *Т,

Ь^ > 0 — уровень погрешности; ■

шаговые множители CL^ ^ удовлетворяют условию

a 1 CL>0

— точность (уровень погрешности) решения вспомогательной задачи линейного поиска.

Теорема 4.1. Пусть выполнено предположение 4.1 и параметры d , 8 , £,., и £gs алгоритма PG-M таковы, что

VeD2LL1 ; cL0 ;

2L<£,s « D2Li/2 ;

Тогда всякая траектория { ХЛ= X (t^), Л.= ,1,..., А/}■ алгоритма

pg-h

такова, что

Xae X^C-Llt^, п. — 1,..., Л/.

Таким образом, при произвольных с*-, ^ "> 0 для получения (Д, ji")-— решения задачиФ£?0 нам необходимо задаться в алгоритме Р&М подходящей S- цепью Т* * = ,... »'t^ ^являющейся £— сетью на Т , в, естественно, проводить вычисления с достаточно малыми уровнями погрешностей Ь ^ и £ £ s •

Пусть справедливо более сильное

Предположение 4.2. Пусть функция •(■ (• , t} является сильно выпуклой на X с постоянной > О для любого "t £ Т .

В этом случае условия на параметры алгоритма pgm можно существенно ослабить.

Теорема 4.2. Пусть выполнено предположения 4.1, 4.2 и параметры dL,0 и tg. алгоритма

PG-M

таковы, что

ol+ ZL5 < dL0 ;

Zli^-^S+jj Ui + ^oL-

й + < «А..

Тогда всякая траектория х^ = Xl.'trO » >2.,..., Л/}, алгоритма

PGM

такова, что

*ае Xopt (d\ta^ , n = /V,

4.3. Параметризованный метод Ньютона. Рассмотрим задачу (PfPjZf в предположениях 4.1, 4.2 и дополнительно потребуем дважды непрерывную дифференцируемость $ С* Д) по X на X,v£x f 0,t)f lip ( X , L2) для любого teT •

Параметризованный метод Ньютона (cM-J.M.Ortega и W.C.Reinbolt (1970)) имеет следующий вид:

РА/М-. х"1 = зса- v*x taa,ta+i )-1vJ(x.n,tn„)+

где Т*= — &- цель на Т , £> 0 ;

параметр > 0 ;

А^ ( X,"t") в R ^ — "суммарная" погрешность определения вектора сдвига в точке Cx,t) £ X *"Г «

l&zU,t)U£s V(x,t)6X*T,

£ ^ > 0 — уровень этой погрешности.

Теорема 4.3. Пуль параметры алгоритма РЛ/М удовлетворяют условиям:

(си+zLS) ({ + {}*■)*■)+и е^. < ¿0

тогда всякая траектория

{ха }алгоритма РЫ1А

такова, что

В случае отсутствия помех проанализирована сравнительная эффективность алгоритмов

■р&м и рл/м

. Показано, что при малых «I) 0 алгоритм рым оказывается более эффективным при нахождении (оС,^- решений задачипо сравнению с Р&М .

4.4. Параметризованный метод проекции субградиентов. Обратимся к негладкому случаю.

Сначала мы рассмотрим задачу

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

Рб^М: я^'ерЬх С^-а-р"'),

1де Т*= V^i >•••» "t/^ } — S-сеть на Т* , S>0 ;

обозначает условный б- субдифференциал выпуклой функции -f-О точке X на множестве X., 6^0 •;

<1>0

— шаговый множитель. oL dl > 0 — параметры.

Справедлива следующая Теорема 4.4. Пусть в алгоритме Р S &М

Up"' II К, Л= 4,2.,.. .,N-1» K=corw*>0,

и параметры d , 8, и Q. удовлетворяют условиям: 0< CL ^ "Wu {.oLdS/2"D К% Ol'/fTK} > О ^ £. « (W (eLdi/4 2) , dL'K/2^2);

О <5 < OLdlV^LB2-

Тогда всякая траектория ^ ОсЛ $ алгоритма

P6G-M

такова, что

ха€ B^ CX^tC^l-t^^nЛ, Л/. .

В наших предположениях задача ФФ эквивалентна следующей выпуклой задачи типа

W0CO: F С.х, с, t ■) min, VteT,

0С6Х

при любых С > С с = [Ло Х>/ ^ * . Для приближенного решения задачи

990 (с)

может быть применен алгоритм Р5&М.

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

Заключение

Основные результаты диссертации состоят в следующем:

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

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

3. Разработаны и обоснованы новые помехоустойчивые стохастические квазиградиентяые алгоритмы решения широкого класса минимаксных задач, в том числе минимаксных задач со связанными переменными, двухэтапных лексикографических минимаксных задач, задач с бесконечным числом ограничений.

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

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

Результаты диссертации докладывались на Международной конференции "Стохастическая оптимизация" (Киев, 1983), Международной конференции "Математическая оптимизация - теория и приложения" (Айзенах, Германия,

1989), II Международном семинаре "Глобальная оптимизация" (Шопрон, Венгрия, 1990), I Советско-Итальянской конференции по методам и приложениям математического программирования (Цетраро, Италия, 1992), научных семинарах Курантовского института математических наук Нью-Йоркского университета (США, 1991), Центра численной оптимизации Хэтфилдского политехнического института (Великобритания, 1991), на Всесоюзном научно-техническом семинаре "Численные методы нелинейного программирования" (Харьков, 1979), XVI Всесоюзной школе-коллоквиуме по теории вероятностей и математической статистике (Бакуриани, 1982) ,11 Всесоюзной школе-семинаре по оптимизации и ее приложениям в экономике (Ашхабад, 1984), ряде республиканский конференций и семинаров, на Ломоносовских чтениях в МГУ (1988), научных семинарах ИПК РАН, ВЦ РАН, ИК У АН.

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

1. Завриев С.К. Комбинированный метод штрафов и стохастического градиента для поиска максимина. Ж. вычисл.матем. и мат.физ., 1979, т.19, № 2, с.329-342.

2. Завриев С.К. Метод решения лексикографических задач предельной оптимизации. В сб.: Прикладная математика и математическое обеспечение ЭВМ, М.: 1980, с.37-38.

3. Завриев С.К. Об отыскании стационарных точек в задаче поиска максимина с ограничениями. Вестн. Моск. ун-та. Сер. 15, Вычисл.матем. и кибернетика, 1980, № 2, с.48-57.

4. Завриев С.К. О методе решения стохастической минимаксной задачи. В сб.: Математические методы исследования операций, М.: Изд-во МГУ, 1981, с.76-83.

5. Завриев С.К. Стохастический метод невязок для поиска максимина. Ж. вычисл.матем. и мат.физ., 1981, т. il, № 3, с.585-594.

6. Завриев С.К. О построении стохастических аналогов итерационных методов. В сб.: Всесоюзная школа-коллоквиум по теории вероятностей и математической статистике. Материалы, Тбилиси, Изд-во "Мацниереба", 1982, с.131-132.

7. Ereshko F.I., Fedorov V.V., Zavriev S.K. Mathematical Methods for the Analysis of Hierarhical Systems. I. IIASA, Laxenburg, Austria, CP-84-19, 1984, p. 1-18.

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

9. Завриев С.К. Об одном численном алгоритме аппроксимации множества эффективных по Парето решений. В сб.: Всесоюзная шко-ла-семинарпо оптимизации и ее приложениям в экономике. Тезисы докладов, Ашхабад, 1984, с.119-120.

10. Завриев С.К. Стохастические градиентные методы решения минимаксных задач. В сб.: Международная конференция "Стохастическая оптимизация". Тезисы докладов, Киев, 1984, с.91-93.

11. Завриев С.К. Стохастические градиентные методы решения минимаксных задач. Опыт общей теории сходимости итерационных алгоритмов оптимизации. М., Изд-во МГУ (ротапринт), 1984, 83 с.

12. Завриев С.К. Об одном аналоге усиленного закона больших чисел для сумм зависимых случайных величин. В сб.: Программное обеспечение и модели исследования операций. М., Изд-во МГУ, 1986, с.167-177.

13. Завриев С.К. Субградиентные методы решения задач двухэтапной лексикографической оптимизации с бесконечным числом ограничений. В сб.: Системное программирование и вопросы оптимизации. М., Изд-во МГУ, 1987, с.138-155.

14. Березнев В.А., Завриев С.К., Третьяков А.А. Взаимосвязь теоремы Лагранжа с геометрией допустимых множеств. Доклады АН СССР, 1988, т. 300, № 6, с.1289-1291.

г»

15. Завриев С.К., Макиева А.Ю. Об устойчивости градиентного алгоритма итеративного метода штрафов. В сб.: Математические методы в теории САПР, роботов и систем, Калинин, 1988, с.52-58.

16. Завриев С.К., Перевозчиков А.Г. Об одном алгоритме адаптивного управления роботом. В сб.: Математические методы в теории САПР, роботов и систем, Калинин, 1988, с.89-94.

17. Завриев С.К., Макиева А.Ю. Помехоустойчивость алгоритмов последовательной безусловной оптимизации I. Метод штрафных функций. МГУ, М., Деп. ВИНИТИ 8232-В88, 1988, с.1-29.

18. Завриев С.К., Макиева А.Ю. Помехоустойчивость алгоритмов последовательной безусловной оптимизации II. Метод барьерных функций МГУ, М„ Деп. ВИНИТИ 8233-В88, 1988, с. 1-24.

19. Добров Б.В., Завриев С.К. Методы условной оптимизации, основанные на пошаговом исключении переменных. МГУ, М., Деп. ВИНИТИ 7662-В88,

1988, с. 1-33.

20. Завриев С.К., Макиева А.Ю. О численной реализации градиентного алгоритма итеративного метода штрафов. В сб.: Математические методы описания, САПР и управления, Калинин, 1989, с.29-34.

21. Завриев С.К., Перевозчиков А.Г. О построении стохастических конечно-разностных методов синтеза оптимальной конструкции робота. В сб.: Математические методы описания, САПР и управления, Калинин,

1989, с. 117-124.

22. Завриев С.К. Конечный субградиентный алгоритм приближенного решения задачи параметрического программирования. В сб.: Вычислительные комплексы и моделирование сложных систем. М., Изд-во МГУ, 1989, с.111-117.

23. Завриев С.К, Макиева А.Ю. Ассимптотические свойства оштрафованных целевых функций в регулярных задачах математического программирования. В сб.: Вычислительные комплексы и моделирование сложных систем. М., Изд-во МГУ, 1989, с.117-124.

24. Завриев С.К., Завриева М.К. Стохастический градиентный алгоритм итерационного метода штрафов для отыскания связанного максимина. В сб.: Программное оборудование и вопросы принятия решений. М., Изд-во МГУ, 1989, с.105-117.

25. Завриев С.К., Перевозчиков А.Г. Прямой метод Ляпунова в исследовании притяжения траекторий конечно-разностных включений. Ж, вычисл.матем. и мат.физ., 1990, т. 30, № 1, с.22-32.

26. Завриев С.К., Перевозчиков А.Г. Метод стохастического обобщенного градиента для решения минимаксных задач со связанными ограничениями. Ж. вычисл.матем. и мат.физ., 1990, т. 30. № 4, с.491-500.

27. Завриев С.К. Об устойчивости метода градиентного спуска с помехами переменного уровня. Ж. вычисл.матем. и мат.физ., 1990, т. 30, № 7, с.997-1007.

28. Завриев С.К. Критерии окончания счета во вспомогательных задачах методов последовательной безусловной оптимизации. I Метод барьерных функций. Вестн. Моск. ун-та. Сер. 15, Вычисл.матем. н кибернетика, 1990, № 1, с.70-76.

29. Завриев С.К. Критерии окончания счета во вспомогательных задачах методов последовательной безусловной оптимизации. II Метод штрафных функций. Вестн. Моск. ун-та. Сер. 15, Вычисл.матем. и кибернетики, 1990, № 2, с.57-61.

30. Завриев С.К., Перевозчиков А.Г. Притяжение траекторий конечно-разностных включений и устойчивость численных методов стохастической негладкой оптимизации. Доклады АН СССР, 1990, т. 313, № 6, с.1373-1376.

31. Завриев С.К., Перевозчиков А.Г. Стохастический квазиградлентный метод оптимизации параметров динамических систем. Кибернетика, 1990, № 4, с.104-108.

32. Завриев С.К. Помехоустойчивость метода условного градиента. В сб.: Программное обеспечение и модели системного анализа. М., Изд-во МГУ, 1991, с.161-165.

33. Завриев С.К., Костюк Ф.В. Метод тяжелого шарика в невыпуклых задачах оптимизации. В сб.: Программное обеспечение и модели системного анализа. М., Изд-во МГУ, 1991, с.179-186.

34. Завриев С.К., Перевозчиков А.Г. Об устойчивости алгоритма Б.Т.Поляка в регулярных невыпуклых задачах. В сб.: Программное о бес-

печенке и модели системного анализа. М., Изд-во МГУ, 1991, с.165-173. ■

35. Завриев С.К., Перевозчиков А.Г. Об одной формуле исчисления стохастических обобщенных градиентов. В сб.: Программное обеспечение и модели системного анализа. М., Изд-во МГУ, с.173-179.

36. Зазрнез С.К, Перевозчиков А.Г. Комбинированный метод стохастических хвазиграднентсз и штрафных фунхций для решения минимаксных задач со связанными переменными. Кибернетика и системный анализ, 1991, № б, с.102-106.

37. Завриев С.К., Перевозчихов А.Г. Стохастический конечно-разностный алгоритм минимизации функция максимика. Ж. вычисл.матсм. и мат.физ., 1991, т. 31, № 4, с.629-633.

38. Sturua E.G., Zavriev S.K. A Trajectory Algorithm Based on the Gradient Method I. The Search on the Quasioptimal Trajectories Journal of Global Optimization, 1991, v. 1, № 3, p.375-388.

39. Завриев C.K., Перевозчиков А.Г. Стохйстистические методы обобщенного градиента в задачах синтеза динамических систем. Вести. Моск. ун-та, Сер. 15, Вычисл.матем. и кибернетика, 1992, № 4, с.47-52.

40. Завриев С.К. Конечные алгоритмы метода продолжения в задачах выпуклой параметрической оптимизации. В сб.: Обратные задачи математического программирования. М., ВЦ РАН, 1992, с.86-103.

41. Завриев С.К. Об устойчивости вычислительной схемы метода сопряженных градиентов. В сб.: Вопросы кибернетики. М., РАН, 1992, с.102-118.

42. Zavriev S.K. On the Global Optimization Properties of Finite-Difference Local Descent Algorithms. Journal of Global Optimization, 1993, v.3, p.67-78.

__Тир... -iP°_ За к__4Ai—

Предприятие «ПАТЕНТ». Москва, Г-59, Бережковская наб., 24