Методы приведенных направлений решения экстремальных задач с ограничениями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГ6 од

1 5 НОИ ¡^3

московский государственный университет

им.М.В.Ломоносова

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

ИЖУТКИН Виктор Сергеевич

УДК 519.853

НЕТОЛИ ПРИВЕДЕННЫХ НАПРАВЛЕНИИ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ С ОГРАНИЧЕНИЯМИ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора (физико-математических наук

Москва - 1993

Работа выполнена на кафедре прикладной математика физико-математического факультета .'¿арийского государственного университета, частично при цинансоьой поддержке программы "Университеты России" и Российского фонда фундаментальных исследований. Офкциалыше оппоненты: доктор физико-математических наук,

профессор Демьянов В.Ф., доктор физико-математических наук, с.н.с. Хадан В.Г., доктор технических наук профессор Пропой А.И. Ведущая организация: Институт Кибернетики АН Украины .

Защита состоится " ■{& - Ое^уд^/иг- 1993 года в ^ часов на заседают Специализированного Совета Д 053.05.38 пс защите диссертация на соискание ученой степени докторе нау) при Московском государственном университете по вдресу : 119399 Москва Ленинские горы , ИГУ , факультет ВМК, ауд. 686 . С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан " & " 19ЭЗ г.

7

Ученый секретарь Специализированного Совета Д 053.05.38 кандидат Физ.-мат.наук

профессор Н.П.Трифонов

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

Р А Б О Т Н

Актуальность томи.

Задачи нг» окстромум при наличии ограничений - большой класс задач с которыми приходится встречаться как в соЗствотю математических пробломях. так и в экономике, тохнико, практика планировании и организации проиаподстпа. СущоствошшЯ вклад в создание теории и мотодоп решении условна* экстромэлышх задач внесли Л.С.Анютин, С.А.Ашшюп, 8. íi. Булатов, Ф.П.Васильев, Р.гаоасои, А.И.Голиков, Б.Г.ГольатоЯн. А.М.Гуиал».О.М.Данидкн, В.Ф.Домьянов, Р,Г.Евтушенко» И.И.Еромин, П.М, Ермолов, В.Г.Жадан. Я,И.Заботил, С.К.Заприоп, В.И.Зорквдьцео, В.Г.Карманов,

A.А.Каплэн, Ф.М,Кириллова. Л.С.Крпсноцоков. В.Н.Мэлозомов,

B.С.Михалевич, а.С.Номировский. К.А.Нурминский, В.М.Панин, Б.Т,Поляк, а.И.Пропой, Б,К.Пшеничный, Н.И.Родковский, а.м.Рустюо, А.Г.Сухаров, а.К.Тихонов. А. А.Третьяков, Н.В.Третьяков, В.В.Федоров, Н.З.Шор, Д.Б.Юдин.

Хорошо известны работа зарубояшх учокых Р.БроЯдена, К.Ботсариса, . ф.вулфа, П.Гклла, К.Гроссмана, Д.Гольдгарба, Г.ЗоЙтондор.ка» В.Зангвилла,К.Кивиела,Г.Клей.чмихвля, К.Ломарошаля, Л.Майна, В.Мюрро*, Р. МиФЦдина, Д.Ди Пилло, Д.Паллашке, Е.Полака, Д.Розеиа, Ы.Райт, Э.Спедикато, Р.Флетчора, К.-Г.Эльстора.

Многие проблемы в коночном счато сводятся к задаче

rain (Г0Ш| ( О с Е"), п - и, л пг (1) О,* (X ( fjíX) < О, JfJ,)- /О,- (X € Ьп| fj(x)-0, 3£J2) , Bu долим три основных подхода к роиотш этой задачи.

Первий подход основан на решении той системы уравнений и Н$равенств, н которой сводятся необходимые условия оптимальности рассматриваемой задачи. Второй подход к решению задачи состоит в ТО«, чтобы сконструировать Функцию, безусловный минимум которой совпадает с решением исходной задачи или связан с ней опрошеют образом. Тогда к i, можно прийти, решив одну или несколько подзадач безусловной оптимизации. В основа третьего подхода легат идоя итеративного спуска, не выводящего за предав допустимого множества. При заборе направления $6wW> резвэгря вспомогательная экстремальная задача дщейногр й{вдр.§уячного

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

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

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

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

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

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

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

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

- 3 -

научная новизна работы состоит в слоду«$Ы:': Для мотодов рошения задачи нолшшЯноЯуслош'оЯ'бптюмзации' развит единый принцип построения направления-^ паршУтрическо'«-" вило, на его основе разработаш новйФ0 о-ЙгортЙМ ы&юя&г линеаризации и возможных направлоштй. В качестве направлений з итерационной точно используются модоЭицкровэгашо приведенный" градиент и ортогональная проекция градиента в поромонноЯ метрике.

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

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

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

Разработа.'ш метода спрооктирсзагаюго обобщенного градиента для задачи негладкой оптимизации с ограшиеииями. Прикладное значенио.

На основе единой схеки построения' катодов программно реализована на ПЭВМ IBM PC оптимизационна*?1 диалоговая система СДИС решения нолгатйных условных экстремальна з'Йдач г в рамках которой могут причиняться алгоритмы различных груйп5 дНя- решения-разнообразных экономических и технических- aaffl'iV flaw»

ногу? бить сюлптоноьоии гибрядвше алгоритмы, истзй>зуй£йо и® начальном и конэ-сюм этапах атерационного процесса- катода- первого» и второго порядков. На базе системы ОДиС разработай програмйпо-мэтодичяскнЯ комплекс изучения вшюухвзаншх методов оптимизаций Апробация работа. Результаты, вошедшие в диссертации,- 6' 1Э79-19Э2Г. докладывались автором на семинарах кафедры прикладной

математики МарГУ. кафодри экономической кибернетики КГУ (рух.-нроф. Заботин Я.И.), кафодри математической физики МГУ (проф. Васильев О.П.),кафодри исследования операций МГУ (академик РАН Краснощекое П.С.), кафодри теории управления СПГУ (проф. Демьянов В.О.). t'JJM УрО РАН (чл.-корр. РАН Еромиа И.И.), ВЦ РАН (чл.-корр. РАН Евтушенко Ю.Г.), Института Проблем Кибернетики РАН (проф. Карманов В.Г., Федоров В.В.), ЦЭМИ РАН (1:роф. Голылтейн Е.Г.), Института Кибернетики АНУ (академик Украшш Б.Н.Пшоиичный), Технического Университета Дроэдона (проф. DfiuiT И., Гроссман К.), Лойпцигского (проф. Фокке И.) и Берлинского (проФ.Гуддат Ю.) университетов, университета Карлсруэ (проф. Паллзшко Д.).

Результаты работы докладывались на следующих собраниях : конференции "Динамическое управление", Свердловск 1979, второй сколе-семинаре по оптимизации и ее нрилохониям в экономике, Ашхпбад 1904, пятой конференции "Управление в механических системах", Казаш 1985, конференции "Проблемы теоретической кибернетики", Иркутск 1985, Горький 1988, конференциях "Математическое программирование и приложения", 1985, 1987, 1989, 1991. 19ЭЗ, Байкальских сколах - семинарах "Методы оптимизации и приложения" 1978, 1980, 1986, IX-XII Симпозиумах-школах "Системы программного обеспечения решения задач оптимального планирования", Минск 1986, Нарва-Иыэссуу 1988, 1992, Кострома 1990, Межгосударственной конференции "Экстремальные задачи и их приложегая " Нижний Новгород 1992, Международной школе-семинаре по оптимизации и приложениям, Иркутск 1989.

Сделаны также доклады на Международных собраниях-.конференции "Математическое программирование" Зеллин 1983, XI конгрессе по применении математики в инженерных науках, Веймар 1964, конференциях по теории математического программирования н приложениям, Айзенах 1987, 1989, 1990. 33 научном коллоквиуме, Ильменау 1988, 8 конференции "Математические и компьютерные проблемы экономики", Кё'тен 1988, 17 симпозиуме по исследованию операций, Гамбург 1ЭЭ2 в Германии, конкретно', по математическому программированию, Галятето 1990 в Венгрии, XV ШИП конференщш по системному моделированию и оптимизации, Ц»рих 1991 в Пфойцарии.

Структура и обьем работа. Диссортация состоит из введения, трех глав, заключения, списка литературы и приложения. ОЛмЛ обьем диссертации - 2 20 страниц.

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

В $ 1 рассматривается задача а1п (Г0(Х)| X € П }„ 0»{х € Е"| !}(Х) * 0, ] ( .Ы17п»), (2) где Г^(х)0 3 € 7 - Л и (О) - достаточно гладкие функции.

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

Определим множество "активных" ограничений следующим образом Г:(х)Жх)-е). Р(х)= гсах (О.шахСГ^х) [ЗсЛ>,е>0.

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

Условно 1.1. Для ф1Ксированноя точки х0 е Е" суцостпуот таксе число N > 0о что множество =» (х ? Еп|Он(х)^м(х0)> ограничено. Здесь Фн(х) - Г0(х) + М?(х).

Условие 1.2. 3 каждой точко х,, являющейся решением (2), выполняется условна строгой дополняющей некесткости, т.е.

А? > 0, 3 €

Условие 1.3. Градто:гш ^(х), 3 € , линейно независим

для всех точек х е

Оплетет, что из условия 1.3 и непрерывности градиентов Гдх), 3 € Л штеказт существование такого числа е>0, что вектора 3 € .Их'.е) линейно независимы для всох х € О,,, 8 с СО.ёЗ.

Для построения в точко х направлопия в , дакцого убывшие точной птр&гиой функции ®н(х) , лшеарлзуем "активные"

■ - (А2А;' )т- "Г >,т1

I • н- 0 1

п-г

ограничения задачи (2), определяемые;функциями Г^(У), ,К.1(х:е). ¡..мучим систему линейных неравенств

<Г ^(х) (у-х><0, ¿«Лх.-е) . (3)

Означим за А=л (х:с > - матрицу, состоящую из столбцов

j€J(x:e) , г- количество элементов множества J(I;e) . Ь случао 0<г<п опродолим мотрицу Р = Р(х;е) размерности п-(п-г), р.шга п-г и матрицу К=П(х;е) размерности п-г, ранга г условиями АтР=0, Ата=1р. (4)

Здось I - единичная матрица порядка г. Укажем для случая 0<г<п накоторио способы построения,матриц Р,,Н, удовлетворяющих (4).

а. Разооьом матрицу-Ат на блоки, А*, и^ л| размориостоя гхг к гх(п-г) так, что АТ-(А^;А2>. Про.дпоА&эдя чноВырокдсккссть

(5!

р. Используем КЗ" - разложение матриц« ат

Ат-(Ь;0)0. (6;

здесь Ь-ловая треугольная, О-ортогональная матрицы разиврносте! г»г и пхп. Разобьем 0Т на блоки й* и размерностей п*г и п*(п-1 так, что ат=Ш?;ф. Положим

Р*0* , й=(1*1Г' «=А (АТА)~' . (7

Следующий способ является обобаонием способа р. 7. Пусть б - положительно определенная матрица разморяоет] тип. Существует такая левая треугольная матрица Н, что

с«ннт.

Определим матрицы Ь, 0 соотношением (6) с заменой Ат на аТН. Произведя аналогичное вышеприведенному разбиение матрицы положим

Р=Н0| , ¡ИК^Ь"1. (8)

Отметим, что при этом й - СА(АТСА)-1. Для матриц а, Р, определенных соотношениями (6), (8) выполняется Р(РТС Р)"'РТ«С-СА(АТСА)_1АТС. Нетрудно видеть, что при 0<г<п любой вектор а»у-удовлетворяпций системе неравенств (3), может быть записан в вал В - -Р2-К(7 + !),«( Е"-1", т ( ^ , (9)

где ^-неотрицательный ортант Е*", ^ (х)) 3 с «Т(х;е).

Если г«п, то из <3> находим

s - -R(V ♦ Г) , П-(ЛТГ' , v < Е? .• (10)

В случае г--0 выбор направления з но стШ1Ь>Р!о^&!гй4ФШ)ЛГ

и , для единообразия дальнейшего изложения • полбЖйм''

з 3 -Рз ■ р-1п , г ( Еп. П'Г)

Согласно (9)-<l t), построение удовлетворяющего• (3) вектора

з»у-х спой!ТС)1 к выбору матриц Р, R и' вЬкТбрЬв г ( E""r,v € Е^.-

Опродолим траектории двияония xu)= x+g1 ' ^(t). где

3(,>(t)»ts , t£0 » t-шагоьый порамотр. (124'

Изучим теперь возможности построения траектории движегаД' н^1

основе квадратичшх приближений ограничений задачи (2). Зам4няй>|

функции 3 € J<x;g) ограничений задачи (2) в точке'xх

их аппроксимациями второго порядка, получим систому

fj(t)»<fj(x), y-x>*0,5<y-Jt,f(у-х)><0, j€J(x;e), xtE".

Предполагая, что 0<r<n, используем следующее приближешюе решение

системы : у - x-Pz-R(v+f )-0.5Rq=x-3-0.5Rq, 2iEn*r,YiE^,

где q с Е1", qi»o,i^(x)3>, j<J(x;e), вектор о определен (9).

На основе (9) определим следующий способ построения

траектории движения, вытекающий из квадратичной аппроксимации

ограничений задачи (2): x(t)» x+o^(t),

3(2>(t)=U-Pz-R(v»i)-0.5tRqJ=ta-0.5t2Rq0 ОО.

Аналогично результатам В.К.Пзешгглого, В.¡i.Панина, икоем сцонку

изменения функции ®}((х) при движении из точки х вдоль

attbs*1'(t)0 1=1.2, для достаточно малого шага % г

Фн(х+з(П> < Фн(хтр1ух,г,7), 0<р<0.50

u..(x,z,v)= u(x,z,?)-NF(x),,

f<g(x),z>, r=Oy

u(x,z,v)« <g(X).Z>'KU(x),V+f(X)> 0<f<riv . (r3)

i<u(x),v*f(i)> tf=iiv

g(x)-PTf£(x>, u(x)~R*^(x). fM)

Имея я езду уменьшение штрафюй функции ®н(х) при1 двййэтзе* из тощи х ( здоль зСt> , будем выбирать бнреяотммеФ поправление а параметра г, т , Р , R из следующего »смуМя .

Условие 1.4» вункщез ?{x).fl(x),s{x),v(x) непрерывна tipа фиксированной в окрестности точка х ьаожестве J{x;e}, велэтинз прячем соотнозэвяа t^,(x,z,v)=0 влечет g(x)-0, Р(х)=0, <u(x),i(х)>«0, u(x)>0. 1*$>у

- 3 -

Покусано,что условия (15) эквивалентны необходимым условиям *.•': .-ромуке для задачи (2) в точке х.

<:■.•. гидно, условие 1.4 будет выполняться, если непрерывно •. ч.'/.ся^.'.е от х векторы z « E""r, V € выбирать из условий <0, причем <g(x),s>=0 <=> g(x)«0,(16) ;u(x).Y*i(x)>-NF(x) СО, причем (17)

•uu),v+rU)>-KF(x)'0 <=> (<и(х),Г(х)>»0, ?(х)«0, и(х)Х». (18) ">:гроделим вспомогательную функцию

<р(х,£)*£(х-?£Д), <P'(x,f)«g(x), где £(y,A.)«f_(y)«- Z Х^ГЛУ), X-(A.JI JiJ(x.e)),

j<J(X,G) 3

к - тскуц/П оокгор miожитолоЯ Лагранжа задачи (2). соотносил (16) означают, что вектор а задает направление усизшш функцда <р(х,£) s точке £«0, если она не является стационарной для ср(х,£). Для построения такого направле1шя будут ,:;;пользооаться различные методы безусловной минимизации нрименяемно к <р(х,£) с начальным приближением £»0, в частности :

Способ 1. Метод градиентного спуска порождает вектор .-.= -<р£(х,0) - Р^¿U) =-g(x) (19)

Способ 2. Метод Ньютонз определяет вектор -Up^Cx.OjrVpJtf.O)- -(PT£wP)"'P^-h(x). (20)

Для построения могут быть использованы различные катод минимизации ловой части (17) при veEf. При атом, чтобы взбежать рассмотрения случаев, ' когда минимум линейной функции из (17) lia Е+ но достигается, используется некоторая регуляризация. Укажем два способа построения вектора г:

Способ 1. <v)= АГ0Г.1П (<u,T^r>+0.5|R(r^i)|al tj > 0 ); (21)

Способ 2. iv)= Argmln {<u,Tj+i>+0.5|(T}+r)J2 | т] ? О ). В последнем случае имеем явное решение

v=r-u-n+, a*« ¡rax <а, 0). (22)

Показано, что приведенные способы выбора т удовлетворяют услозиаг (17), (18).

В §2 для решения задачи (2) предлагается основной

АЛГОРИТМ 2.1. I. Полагаем к=0, выбираем произвольную точку xQ с Е" н

параметры eQ € (0;il, |3 с (0;0.5), H > 0 . сиксируем способ построения векторов z , v.

ii. Следуя выбранному способу построения а, V, определяем величину - ин(хк,2к,74{).

Если о^^О, то хн является решенном задачи (2). Процесс

на этом заканчивается.

Пусть ы^сО. Определяем направление ок и

акш"ак1>(1)' гдо 1 < П'2К

Если

Л либо и^ > 3 с .1к, (23)

полаггом Ек+)=Ек, в противнем случпо принимаем ек>^га1л{ек,). Ш.Находим величину шага 1к

гя«тахи=2~1!«н<*и*ак{1)> < ©„(зс^ри^. (24)

IV.Получаем *1,цв*к+зк(1и). Процесс повторяется нз п. II. Показано, что побор иагч осуществляется на яаядой итерации за конечное число проб. Сходимость алгоритма уотанапливпет ТЕОРЕМА 2.1. Любая продельная точка гонерируокой алгоритмом 2.1 последовательности (х^У является решением задачи (2), При этом существует такое число е4>0 и номер К,, что ек=6«' ^ч• Скорость сходимости (хк> в случао использования для движения траектории о в^'ш устанавливает

ТЕОРЕМА 2.2. Пусть функции выпуклы, функция *0<х)

сильно выпукла при г < С1„ выполняется яоравонство 2 х£<К, вектор

11 ^

а(х) опредодйетсл согласно (19) так, что для некоторой константы |1>0 выполняется <Е<х),г(х )>$-р(№(х)1г*1г(х)}г), х«^ , 7(х) ЕНОирнчтся согласно (17), (13) так, что

и^(х)>|Г,(х)|, 3 « <Т(х;е) вдечот 7(х)»0. {25)

Тогда для скорости сходимости повлодоваталыюсти (хк), вырабатываемой о.-;гс ритмом при выборе траектории дошишя с при О > г «г п. справедлива оценка

Есла гв=пе то имеет ¡«сто оценка -3>п{хи+,

Для вариантов алторктмз, в которых двияокиэ происходит вдоль кршолкновноз траектория , справедлива

ТЕОРЕМА 2.3. Пусть ыатряш Г*(х), 3 £ Зя и СО), Р(Х) удовлетворяет условии Лшшца, матрица й(х)я опрэдиляотся способом 7 пра С=а^у(х,и), где и=-5гт^(х), матрица Я определяется

способом р. вектор г(х) определяется согласно (20) так, что при х->х,, |e(x)+h(x)| - о(|е(х)|)0 вектор ?(х) выбирается согласно (IT),(18),(25). Тогда дня последовательности (х^), вырабатываемой алгоритмом с использованием a(a*(t), найдется такой номер fc,, что tk-l для всех 19kg , и справедлива оценка

Отметим, что использование информации о вторых производных функций задачи, требуя значительных вычислительных затрат, не приводит к существенному ускорошш сходимости, поскольку квадратичные аппроксимации указанных функций хорошо приближают 8ти функции лишь в некоторой окрестности рассматриваемой точки и могут значительно отличаться от них вне атой окрестности. Сказанное озаачазт, что в начало йторацкс:п:сго процесса нецелесообразно тратить значительные усилия на построение спродолдэдих направление а и s(2*(t) векторов z и v. Вместе о том, иопользоватю криволинейных траекторий в окрестности решения приводит и ускорение сходимости итерационных процессов, О учетом втого, иа основе базового алгоритма 2.1 решения вадачк (2), построен гибридный

АЛГО'РИТИ 2.2

I. Полагаем к*0, выбираем произвольнув точку х0 € В" и

параметры в0 с (G}51, ß i (0;0-5), Н > 0 . Фиксируем способ построения векторов e.V.

IX. Согласно (13), (14), (7), (19), (22) определяем величину

«■WWW-

Бош ы^О, то хк является решением задачи (2). Процесс на атом заканчивается.

Пусть ц^О. Бели выполняется условие (23), переходим к u.U.2.

1, В случае < ~ или (23) не выполняются, согласно (7),(9),(13),(22),(12) определяем s=ak , о^1*(t)«tek

н переходим к III.

2. Опре^ляем вектор о. согласно (8), (20),(22),(9)

Далее используем 8*¿;(t).

III.Находим величину вага гк при движении вдоль а(г)-з(,,(») или э*а*(0 :

^-тахи-г"1 I ®н(Хц*0к(1,) < фм(1к>+РЧ|к' 1*Ю,1... >

IV. Получаем Если условна (23) не выполняется,

принимаем е^^гаШе^,!^))«, иначе полагаем Процесс повторяется нз п.II.

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

В $3 излагается модификация алгоритма для общей задачи нелинейного программирования, гдо присутствует ограничения -- равенства и неравенстве. Так во, как я о известном метода линеаризации, ограничешм - равенства звшияотся пв две неравенства. В случае, если в набор "е-активша" огртшчояий входят оба неравенства, определяющие ограниченно, при определении направления градиент входит в матрицу 4 одии раз, б соответствующая компонента вектора т полагается 'равной нули.

0 5 4 конкретизируется выбор параметров г, у. Показано, что ври выбор» матриц Р , П из (7) , г из (19), V из (21), получеоы направлено, опродолящео йзбостнно котодц лшоарззешш, розработакнкэ Б.Н.Паекичным , В.М.Пшшгем. .

В случае выбора матриц Р, Н из (5). а нз (19), V из (22), получим направление приведенного градиента Вул*а

■■(-¿а-. О4 I ° (гб>

. ц—ГА^1;«)^; гт« (ц+Г)+ - оценки множителей Лаграяха.

Выбирая Р и П из (8), а , 7 согласно (20), (22), имеем в=-<3{ 11П-А (ЛТСА)-1АТ0) Г^-А (АТСА)"'(Г+(-Ц-Х)+)>, (27)

и>-(Ат0АГ1АтС^;

Это направление - вариант проекции градиента в пероыеяноЯ ветряке. Показано, что это направление мохе? бить получепо о ремхах известного метода линеаризации о непояьзевбпгвм специальной нормализации. Рассмотрены два способа вычнеяепзл этого исправления, различные со трудоемкости.

Анализируя случая, когда вектор множителей Лаграижа строго положителен, т.е. «»(ц»Г)+>0, получаем, что вектор в

совпадает с направленном из метода Уилсона и мокет быть найдон

кз системы линейных уравнения £ д } ^ * ] * [ ~

На основе этого Факта конкретизируется гибридный алгоритм,

использующий при выборе направления ортогональное проектирование.

В 55 строятся методы приведенных направлений не основа

квадратичной штрафной функции Ф„(х) - я 2 (£*,(х))г.

И и к ^ *

Вначале, следуя Мюрров, считаем "активными" нарушенные огрштчония, а также то кто в предыдущей итерационной точке неотрицательные многсители Лаграпжа:

.иом направленно движения з в текущей точке х«хк в виде - Рг Р «I, асЕ", если г*о,

в* -Ра-К(7+Г),а«Еп"г,У€Ег, если о<г<п, .-Р<? + Г), П.{Ат)",,теЕг, если г-п,

причем А(х)-(г (х)], Р и П определены выло,

г определяется 09) . V—0,5ри(х)-Пх)*Г+(х). Подчеркнем, что здесь V но обязательно неотрицателен.

Шаг г выбираем из условия Фр(х+18}КФр(х)+1йри,г,т), где

йр(х,а,у)^<|)(х,г,У)-|<Г+(х),у+Г(х)>. и« <х,а,7) определено (13). Такой способ выбора параметров-определяет метод спроектированного лагранжиана, предлохешшй Ыюрреем.

Определим теперь множество в - нарушенных, ограничений ^(х)^(х;е)=(^|Г;(х)?-б},е>0 и матрицу А(х:е)«(Г}(хН

Стремясь болев точно аппроксимировать множество атш

ограничений касательным многообразием, будем подбирать параметр 1

неотрицательным (геБ^Ь Для решения задачи (2) предложен

АЛГОРИТМ 5.1 I. Полагаем к=0, выбираем произвольную точку х0 { Е" е

параштрц е0 г {0;б]„ р0, р € (0;0.5), N > 0 . Фиксируем

способ построения векторов г » т.

ii Вычислим и(хк, гк, Ук) из (13), определим р^^ 1 по формуле 2(1*(х. ))г

а-г-, осли и (хк.г .V ) > 0;

Рк„» и<^'2к'ук> Рк к к

рк , иначе.

ВЫЧИСЛЯОМ величину = и (Хк.2к,Ук) - § (Г>(хк))г.

Если и. > 0, то х„ является гюшониом задачи (2). Процесс на этом заканчивается.

Пусть и. < 0. Опродоляом направлогао з. из (9),(19),(22).

Если выполняется условие (23), полагаем ек+1 = ек, в против!юм случве принимаем е - п1п (е , |и |).

К+ 1 яр у^ ^

III.Находим величину шага 1к при дпихе1сии вдоль нагтравлония зк

1к=тах(1=2_1}ф (х+гз. ) $ Ф (**>+РЧ) ,1=0,1,..).

IV.Получаем Процесс повторяется из п.П.

Показано конечность процедуры дробления кага, доказана

сходимость алгоритма.

В 5 6 проводится обсуждение результатов , изложенных в первой главе. Методы решения задачи (2), основагаше на идее линеаризации или квадратичная аппроксимации целевой функции н ограничений строились и изучались во многих работах. Для указэшмх методов как правило устанавливается сходимость с линейной или сзерхлииейгой скоростью в зависимости от порядка используемых для построе:ия вспомогательной задачи производных. При этом сверхлинейная сходимость достигается за счет принудительного перехода в окрестности решения на движение с единичным шагом, гребущего на каждой итерации проверки достаточности убывания функции Бштгрива при таком паге. В методах приведется направлений, рассматриваемых в первой главе и основанных на результатах Б.Н.ГЪеничного и В.М.Панина, для получения свврхлинойной сходимости используется движение по криволинейной траектории и процедура регулировки параметра ек, определяющего множество активных ограничений, при этом переход из

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

В известных гибридных методах проверка критерия перехода метод высокого порядка осуществляется по следующей схем делается пробная итерация методом высокого порядка, после чего результатам этой пробной итерации выясняется, произошло ли результате ее существенное приближение к решению. В случ положительного ответа процесс продолжается с полученной точ; методом высокого порядка, в противном случав происходит возвр. к исходному методу. При этом информация , полученная в хо, реализации пробной итерации , в общем случае более никак I используется . В рамках схемы методов приведенных направлен] использование глобально сворхлинойно сходящихся методов I заключительном этапе решения задачи позволяет обойтись гибридном алгоритме без указанной вспомогательной итерацш Кроме того , отметим, что в известных гибридных метод! объединяемые метода основаны , как правило , на различш принципах и требуют решения существенно различи вспомогательных задач для реализации итерационного переход! В предлагаемом гибридном методе объединяемые методы принадлежа одной и той же группе методов приведенных направлений и I реализация отличается лишь способом выбора параметров г, \ определяющих направление движения а и построен! траектории движения х(М. что позволяет, в честности, упрости! их программную реализацию .

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

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

В 5 ? предлагается модифицированный способ линэаризаци

"е-активных" ограничений Г^(х), ,1с.1(х:е)={3{.1|-е О). еуО,

Гл(х)+<Г^(х)-в^(х),э><0, 0^0, J « Лх;е), который позволяет В точке X € О , При-условии <Гд(1),3><0. получать направлонио з, но выводящее из допустимой области.

Здось используом матрицу Х»А(х;е)=»(''(х)-е^(х)| ^.1(х;е)).

Будом считать, что вектор в удовлетворяет условию

(1+<0,и>)~'н7>0. (23)

Показано, что при выполнении отого условия столбцы матрицы А

линойно независимы (для линейно независимых X* (х),^ € <1(х;е)).

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

9Л-(Н| 2 V Л € J(x;e), (29)

яЯх.о)

2 )"' -тШИ , !и|у), 3 € <Нх;е), V* (0,0.5). (30)

По аналогии с (9)-(11) будем иметь

' Рг,_Р-1п, г < Е", если г=0,

о«. -£г-Н(7+Г),г < ЕП~Г, V < Е^, осли 0<г<п, ,-В(у+Г),Я=(АТ)"1, т € если г=п.'

Матрацы Р , П ш^еют то га размера я ранга, что и матрицы Р, И и связаны следующими соотношениями

Р=>Р+7П9 (Г0 )ТР=Р-7Й08Т, й=ПпПО(Г^ )тН=П-7ИСит.

три вып0л19шш условий АтР-0, А*Й=1Г.

1оказзно, что векторы а и в из (9)-(11) снязывзет соотношение э=зн&9, (31)

7де

Аналогично выиеприведешюму определены

э(1)с?)»го. г (32)

з(г,{гЫэ-0.5Г^, q={<з.f^\^>)| 3 € <>(х;8)), (33)

5(3>(г)=гз-0.5ггР.ч. я=(<з,Г^(х)э>+И1аНЗеЛх.е)). ае(2.3), (34)

Отеепш, что для и<0 и м-рашпенных значений 4 при движении ю указанным траекториям итерационные точки будут допустимыми I целевая функция убывает.

Показано, что для выбора а и 7 могут использоваться способы

(20), (22). Кроме них предложены другие варианты выбора :

в(х) и(х)

г -----• г-------• i-i-m

2=f lb<x)l V. f «Ь<*>» b(X)-i " ]. (35)

l о . b=o: l о . ь-о: l e J

S- -g|b|"1. v» (-и)+|Ь|-'-Г. (36)

В § 8 для задачи (2) предлагается

АЛГОРИТМ 8.1

I. Полагаем к=0, выбираем начальное приближение xQ € О и

параметры eQ € (0;ё1, р z (0;0.5), Н > 0 . Фиксируем . способ построения вокторов z.V.

II. Следуя виОракному способу получения uv, согласно (13), определяем величину иу^х^г^^).

Если то хк явдяотся решением задачи (2). Процесс

на этом заканчивается.

Пусть 0. Согласно (32) - (34) определяем в точке ;хк äk(t)=5k(1)(t), 1 € (1,2,3).

При этом, в случае использования s^1'(t), вектор ek » ö(xk)

—^определяем соотношением (29), 'для a£2)(t) строим вк согласно

(30), для s<3>(t) вектор 8к=0.

Если выполняется условие (23), полагаем ekf1«ek, в противном случае принимаем ek+1»mln{ek,luj).

III.Находим величину шага tk t^maxf t=2_11Г0 (хк+5к( t) )<f0(xk)+ßt7ku)k:

где 7к=7(хк) определяется (28).

IV.Полагаем xJe+1=xlc+aleXtk). процесс повторяется из шага II. Показано . что процедура дроблегая tk при выборе шага

является конечной. Доказана теорема сходимости алгоритма .

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

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

Далее, аналогично алгоритму 2.2, строится гибридный алгоритм 8.2 с допустимыми точками, использующий в качестве базового алгоритм 8.1. Вновь на начальном этапе итерационного процесса будем определять вектор г соотношением (19) при построении матриц Р, Н согласно^(7), а для итерационного перехода по направлению а , следуя (32). При попадании точки в окрестность решения воспользуемся способом (20) построения г. При этом, определяющие направление а матрицы Р, И будем строить по способу (8). Итерационный переход в этом случае осуществляется вдоль §*2)(г), согласно (33), или следуя (34) и

породит сверхлинейно сходящийся итерационный процесс.

Предложена модификация алгоритма 8.1 для задачи нелинейного программирования (1), содержащей наряду с ограничениями типа неравенств также ограничения - равенства . В основе модификации ложит предложенный В.П.Булатовым способ сведения (1) к задаче с ограничениями-неравенствами.

В $ 9 расмотрены конкретные реализации вшвприведэшшх алгоритмов. Аналогично алгоритмам из главы 1, вектор а определяется выбором матриц Р, Н и параметров геЕ"-? теЕ^, а воктор з в алгоритмах 8.1 и 8.2 о учетом (28),(31)

5 = а + тш1Ш = а + (1+<0,и>)-1шНе (37)

и зависит от выбора вектора 9 € Используя (29), исключим из (37) вектор 6. Имеем

яЛх.е) з&(х,е)

- (1+1Г и*)"1- (1+2(2 ил)+Г\ дои.е).

«3(х,е) :(7(х.е) ¿€0(х,е)

Таким образом

з = э + и>[ 1 +2( V (ил)+Г1Нё . ё»(1,...,1)т. (38)

6)

Для вектора в, определяемого (30), имеем соответственно

ä » a+oHmlnCt .|u|v))l1 + !7 u^l)+ EuJJ_,Re. (39)

jej(x,e) jfJ(x.e)

Выбирая матрицы Р. П из (7), вектор z из (19), v согласно

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

Выбирая матрицы Р, R из (5), вектор г из (19), v согласно

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

Выбирая матрица р, R согласно (7), воктор г из (19). v из (22), будем иметь, с учетом (27), (38), направление, онредолящее метод возможных направлений с использованием ортогонального проектирования.

При построении методов криволинейного спуска с аспользов8ш:ем ортогонального проектирования, обладающих высокой скоростью сходимости , используем матрицы Р и П, вычисляете согласно (8), векторы z из (20), т из (22). Тогда с учетом (27), (33), (39) имеем :

§(2,(tJ ■» ts-0.5t2Hq, q - «s.i^'e»!JtJ(x.e)),

s-8*<irt,s> f min (1,MV)(1 + | £ u1 |)1 CA(ATCA)"'e , ° 1 t j£j(x,e) J

8 - -GСIW~A(a'GА)~1A*G)Iq -CA(ATGA)"i(i>(-u-i)+), (40)

U - -(А7САГ*АтСГ^ , G - e||(x,ir), * = -(ATA)",Alrfo *

Другой вариант криволинейной траектории с допустимыми точками получим при 6*0 из (34), причем вэктор в определен (40).

Показано что при suборе натрки Р. R из (7) . о«кк>ров

z и у кз (35) или (36), явно получаемые направления в определяют алгоритмы P1 ü Р2 метода возможных направлений Зойтендойка со спэциалыюВ нормализацией .

В 5 Ю обсузазитсл результате второй главы. В методах возможных направлений {Г.зойтэнлейк. Э.Полак и др.), секгтапнах на линеаризации или квадратичной аппроксимации мраничений исходной задачи, дли определения направления спуска; но выводящего из допустимой области, решается вспомогательная задача линейного либо квадратичного программирования. Решение указанных задач трэбуот дополнительного итерационного' процесса. вообще говоря, бесконечного.

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

Для построения методов допустимых точек с ускоренной сходимостью в ряде работ привлекается идея организации итерационного процесса вдоль криволинейных траекторий вместо отрезков прямых. Теоретические основы построения методов криволинейного спуска для решения безусловных и условных экстремальных задач подробно исследовались А.А.Третьяковым. В работах В.С.Михалевича, Н.Н.Редковского и А.А.Перекатова но выводящая из допустимой области криволинейная траектория спуска строится на основе сведения (путем параметризации ограничений) исходной задачи к некоторой безусловной. Указанная параметризация определяется конструктивно лишь для областей простого вида .В отличие от таких методов, рассматриваемые в настоящей работе способы построения допустимых траекторий, развивающие подход С.Ботсариса, позволяют работать . с нелинейными ограничениями общего вида.Наконец, построенные гибридные алгоритмы единообразны на обеих фазах гибридного процесса и естественно переходят о первой фазы на вторую.

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

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

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

Рассмотрим задачу (2), предполагая, что f^ix), J с J -выпуклые, дифференцируемые функции. Как известно, поставленная задача является в общем случае некорректной. Как следствие, для методов ее решения в большинстве случаев устанавливается сходимость выраб&.ываемой последовательности ixk) лишь по функции, т.е в смысле соотношения

Ilm i(xj = Ein (Г(х) 1х(Ш, (41)

к-ко

в то время как сама последовательность (хк> может иметь несколько предельных точек. Подчеркнем, что и для методов, приведенных направлений (гл. 1,2) в условиях выпуклости f^d), J{J имеэт место сходимость (хк> лишь в смысле (41). Один из путей преодоления возникших трудностей заключается п специальной модификации рассматриваемых методов - их итеративной регуляризации . Регуляризованные метода вырабатывают последовательность-, (х^).. / сходящуюся по норме к некоторому решению задачи. Кроме того, они более устойчивы к ошибкам в исходных данных.

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

Будем считать, что целевая функция задачи известна с погрешностью, так что на k-той итерации вместо Г0(х) доступна функция f0lc(x) € С2 (Е") такая , что

тах |t0(x)-i0k<x)|> ^ ök. х « Е", бк > 0.

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

Tk(x)= f0k(x)+0.5akjxj2, V0. (42) •

В качестве базового алгоритма для регуляризации выбран один из простейших вариантов алгоритма 2.1, использукший движение по траектории sk(t)=ts. Регуляризация целевой функции слагаемым

О.бо^х!3 в (42) позволяет отказаться от процедуры итеративного изменения парамотра ек в п.П алгоритма. Вместе о теи потребуется некоторая модификация принятого ранее способа выбора шага из соотношения (24). Именно, образуем регуляризованнуп штрафную функцию

фм,а(х) • \W*mx) - f0k(x) ♦ NP(z) ♦ 0.5Ojt|x|a0 которая используется вместо итрафной Функции Фц(х). При этом в качество начального шага п процедуре дробления (24) вместо числа 1 выбираются элементы априорно заданной последовательности {ф„ где lim t' = 0 .

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

Рассмотрим тепорь регулярнзовашшй метод всэшйгшх направлений, получеюшй по описанной сизо схеме , на основе алгоритма 8.1. В отлгаэ от предыдущего, считаом, что по только целевая функция» но и часть ограничений задачи (2) могу? быть * задана о погрешностями, т.е., вместо функций f0(x), i€J0.

J0cJ, могут быть доступны лизь кх приблигешш 10к(х),1^(х},^0,

прочей ^(х)сСг(Е")Р J(JQ, IJk(t),JcJ0 - выпуклые функция. Учет

поточно задагашх ограничений будем осуществлять пра пойоги гладких функций втрзфа 11(х)-£ (f '(х))1*, П(х)=Я (f*(s))p, р > 2.

Предполагается, что

, i » i »

maxqro(x)-rok(x)|0 |П <х)-1уг)|> < 0 , lim ö - О

к-*о>

для всех X € 0о»{Х € гл(х)$0, J €

Вместо функции Тихонова (42) здесь используется функция Тихонова со штрафом

здесь р. (Ilm ßk«=0) играет роль штрафного ковфбаднвнта.

!с-ко

Для соответствующего алгоритма также установлона конзчнооть процедуры дробления при выборе иага, предложен вариап? выбора а согласования параметров о^, 0k, t'k, доказана сходимость предложенного алгоритма .

ОпясашшЯ способ регуляризации метода приведенных направления с допустимыми точками может быть также использован , для построения варианта этого метода, не предполагаемого выполнение основного условия линейной независимости градиентов . "активных" ограничений. Рассмотрим задачу (2), определенную | выпуклыми гладкими функциями ^(хк), 3<«1. Для простоты будем считать, что погрешности задания функции, вытокащио из постановки задачи, отсутствуют, т.о. в вышеприведенных обозначениях <Г0<Л, 0к=0. Если условие линейной независимости градиентов "активных" ограничится в рассматриваемой задаче не выполняется, то набор Градиентов "активных" ограничений (Г^СХд)), 3€<1к в точке хъ метит оказаться линейно зависимым, а соответствующая матрица Ак = ( Г^(ха) | 3 с ^ ) - плохо

обусловлешюй. Это делает невозможной или сильно затрудняет реализацию алгоритма 8.1. Во избежание этого будем считать! ограничения, порождающие линейную зависимость или плохую обусловленность набора (1^(хк)), 3<,1к задашшми с погрешностью, и , в соответствии с описанным выое способом регуляризации, учитывать их включением в штраф. Оставшиеся же ограничения учитываем с использованием модифицированной линеаризации. Тек самым производится некоторое расширение определенного ранее понятия некорректных экстремальных задач. К последним помимо задач, в которых не всякая мшшмрзируюцая последовательность сходится, предлагается относить задачи, на удовлетворяющие условию невырожденности .

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

В б 12 ' предлагаются варианты методов с использованием приведенного градиента , предназначенные для решения задачи (2) в предположений, что функции Зс<Т и <0} обладают свойствами

гладкости, ослзбл&нлыми по сравнению с условиями § 1.

Сначала строится метод приведенного субградиепта для задачи выпуклой лэдаффорвнцйруеыой оптимизации. Будем считать, что определявдиэ задачу (2) функции *0(х), 3 с <1 являются

выпуклыми на Е" и .вообще говоря, нвдафференцируеилм. В этой связи напомним, что для всякой такой функции f(x> d каждой точке *0< Е" определено множество

6t(x0)-{fi € Е": f(y)>f(x0}+<5 ,у-х0>, * у €

называемое субдиФ1юренциалом f(x) в точке xQ. Любой эломонт C(s0)€5f(х0) называется субградиентом функции f(x) в точке xQ.

Применим предложенный выше метод линеаризации о использованием проекционного градиента решения гладких задач нелинейного программировать . При этом в формулах , определяющих направление э „ заменил градиенты f¿(x), f}(x), JeJ(x:e) субградиентам! указанных Функций, то есть произвольными

векторами С0(х)€аг0(х), £^(х)€0Г^(х), JiJ(x;e), иаговыо параметры

t,. будем выбирать так, что £ t. «о, £ k k=0 K k=0 *

При соответствующих условиях доказана сходимость

последовательности (ik), вырабатываемой предлоконным алгоритмом

12.1 ( вариантом алгоритма 2.1} .

ПореЯдем теперь к рассмотрешш задачи мшг/мизащш функций,

удовлетворяющих условию Липшица. Класс Функция, удовлетворяющих

локальному условию Липшица, весьма пирок. Он содержит, например,

все непрерывно диффоронцируемые и кусочно-гладкие, а также

квязидиффоренцируемые функции (А.М.Гупал). В то ко время функции

рассматриваемого нами класса сохраняют некоторые полезные

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

свойств является возможность введения для локально лгашщевых

функция достаточно содержательного понятия обобщенного градиента,

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

градиента гладких функций. Обобщенным градиентом функция Г(х) в

точке х0 называют вектор ? (xQ), принадлежащий выпуклой оболочке

предельных точек всевозможных последовательностей (Г*(Ук)>. где

(ук) - произвольная, сходящаяся к х0 последовательность точек, d

каждой из которых существует градиент i'(yk).

В прилоюншлх нередко приходится сталкиваться с задачами, в

которых цэлевая функция Г0(х) не является зада:шой с самого

начала процесса, а последовательно уточняется в ходе рекештя

задачи. То есть, вместо fQ(x) имеется последовательность функций

f0k(x), приближащих в некоторон смысло fQ(x). Осуществить

операцию предельного перехода, найти ?0U) и после этого приступить к решению задачи по ряду причин часто бывает невозможно, либо нецелесообразно. В частности, во многих случаях функции f0kU) обладают лучшими но сравнению с fQ(x) свойствами гладкости, так что вместо продольной функции i0(x) целесообразно ммоть дело именно с f0k(x). Отсутствие возможности осуществить предельный переход во многих случаях приводит к тому, что адекватная оценка погрешности |fQ(x)-f0k(x)| оказывается недоступной. Таким образом возникает задача минимизации предельной локально липшицовой функции Г0(х) на множестве О с использованием на k-м ваге лишь информации о функции f0kU), боз привлечения оценок погрешности |Г0(х)-Г0к(х)|. Отсутствие последней оценхи существенно отличает поставленную задачу от некорректных задач выпуклого программирования, рассматривавшихся в $ 11, где эта оценка предполагалась известной. Подобного рода задачи называются предельными экстремальными задачами (О.М.Ермольев, а.М.Гупал). Для решения задачи (2) в предельной постановке построен алгоритм 12.2 ( вариант алгоритма 8.1 ). В случае, когда градиенты ¿¿kU) поддаются вычислению с приемлемыми затратами, то есть являются доступными, представляется возможная! использовэть вместо градиента ¿¿U) его аналог f£k(x). Полученное таким образом направлешю s можот ни быть направлением убывания исходной функции Г0(х). Поэтому вы^ор ваге осуществляется ( аналогично рогулярязовашшм методам §11) нз ■ расходящееся числового ряда.

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

Будем считать, что вмэсто известна некоторая случайная

оценка, Описанная ситуация является типичной, например, для задач стохастического программирования, в которых f0k(x) » jHiCkU;W)~ ДСк(х;»>)г>(аШ), тяа Л - акпк математического ожидания, W -случайный фактор. Тькьл ситуация возникает также при использовании длг. шпроксиывции заданной локально лнпшицовой функции i0;x) процедур сглаживания путем усреднения' поведения iQ(x) ш> «алой окрестности, содержащей точку х (А.М.Гупал).

При исаользовашш для вычисления возникавших каогомергаа

интегралов методов типа Монто-Карло, приходим к некоторой случайной оцонхе градиента Г^к(х) сглаженной функции iQ(x), Итак, при построении напрзвлештя в модификации алгоритма 8.1 для случая поточно заданных на К-м шаго в качество аналога градиента

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

Таким образом, для решения задачи (2) в предположении» что 10(х) локально липшицовая на Е" функция, Х.(х)0 JeJ -дифференцируемые функции с липшицевыми градиентами rj(x), JcJ примошм алгоритм 12.3 (вариант алгоритма (8.1) в комбинации о одним из известных способов построения оценок £к (А.М.Гупал)). При выполнении системы условий согласования последовательностей параметров „ опредолящих алгоритм 12.3, обесточивается сходимость вырабатываемой им последовательности (хк> к гягажэству решений (2) п.н.

В 5 13 строится метод возможных направлений для задачи выпуклого программирования в гильбертовом пространстве. С помощью предложенного Зуховицким С.И., Поляком P.A., Примаком U.E. параметрического представления направления бесконечномерная задача отыскания направления движения сводится к конечномерной задаче в пространстве параметров . Для ее рошония применяются способы „ изложенные в главо 2 .

В 5 14 проводится обсуждение результатов третьей главы.

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

Остановимся на сравнении построенных в } 12 модификаций методов приведенных направлений для задачи условной минимизации негладких функций о аналогичными известными методами. Во многих случаях такого рода методы получаются из тех или иных методов минимизации гладких функций заменой градиента функции подходящим его аналогом (субградиент, обобщенный градиент или их стохастические оценки ). В качество примера указом построенные u.m.Ермольевым, а.м.Гупзлом в^ригнты методов проекции градиента й условного градиента , предложенную А.М.Гулалом модификация метода возможных направлений для надави (2) с негладкой функцией

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

В приложении приведено краткое описание оптимизационной диалоговой систош ОДИС, программно реализованной на основе единой схемы построения методов приведенных направлений и предназначенной для решения задачи нелинейного

программирования . Описан также разработанный с использованием ОДИС программно-методический комплекс для изучения этих методов.

ОСНОВШЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

4. Построена единая схома программной реализации предложенных методов приведошшх направлений, на ее основе разработана оптимизационная диалоговая система ОДИС решения задач нелинейной оптимизшши и изучения методов ее решения.

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

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

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

1. Ижуткин B.C., Кокурин M.D. Метод проектирования в переменной метрико для задачи выпуклого программирования

// йзвостия вузов. Математика. - 1983. - Я б - С. 78 - 80.

2. Ижуткин B.C., Кокурин M.D. О скорости сяодимостп проекционного метода с выбором шага дробленном для ресогш задачи выпуклого программирования // Известия вузов. Матемзтика. -1983. - А 6 - С. 53 - 55.

3. Ижуткин B.C. Обобщенный метод приведенного градиента для решения задачи выпуклого программирования // Тез. докл. II Всео. школы -семинара по оптимизации и ее приложениям к экономике,

16 - 22 мая 1984 г.Ашхабад : Изд-во ТГУ, 1984, - С 12S - 130»

4. ishutkln V.S., Schönefeld К.А. Globalization of ths. !TiIsen-type itethoäa for Konlinearly Conatralned Optimization Problems // Wissenschaftliche Zeitschrift der HAB (Procsedinga of the 10 IKM).-Weimar, 1984.- p. 69 - T2.

5. Ижуткин B.C. Метод приведенного градиента для решения одного класса задач оптимального управления // Материалы 5 Всесопз. конф. по управлению в мехшшческих системах.-Квзаш», 1965. - С. 41 - 42.

6. Ishutkln V.S., Klelnnlchel И. Verfahren der Zulässigen Richtungen unter Benutzung reduzierter Gradienten für nichtlineare Op t im 1 erungn probl егеэ // Kathenaticcha Operationsforschung und StatlBtiH .S. Optlaisatioil. -1935. -V. 16.- S. 373 - 390.

7. Ижуткин B.C. Об одной модификации метода линеаризации о ускоренной сходимостью // Известия вузов. Математика.-1986,- N 8. - С. 27 - 30.

8. Ижуткин B.C. , Кокурин М.Ю. О гибридном методе нелинойного программирования, исполозующом криволинейный спуск // Известия вузов. Математика. - 1986. - » 2 - С.61 - 64.

9. Izhutkln V.S., Schönefeld К. On the Globalization of ИПвоп-type Optimization Methods by Meana of Generalized Reduced Gradient Methods //Computing.- 1986. - V. 37 -P. 151-169.

tO. Ижуткин B.C. Эллипсоидная нормализация в методе линеаризации решения систем неравенств // Материалы 5 Всесоюз. конф. "Методы математического программирования и программное обеспечение".-Свердловскt 1987,- С. 51 - 52.

11. Izhutkln V.S. Hybride Verfaiiren der Reduzierten Gradienten // Материалы Мохдунор. конф. "Optimierungatheorle und Anwendungen*.-Elaenach, 1987.-S. 73 - 74.

12. Ижуткин B.C. Метод приведенного градиента для задачи стохастической оптимизации о нелинейными ограничениями

// Материалы 8-й конф. "Mathematische und rechentechnische

Probleme der StoXiwlrtachaft'i-Kö'then, 1988.- C. 8.

13. Ижуткин B.C., Кокурин Ы.О. Методы приведенных направлений для задачи нелинейного программирования // Журнал вычислительной математики и математической физики. -1988. -Т.28, N 12.- С. 1799 - 181-3.

14. Ижуткин B.C. Задача выбора направлен с эллипсоидной нормализацией в методах нелинейного программирования // Материалы 8 Всесоюз. конф. "Проблемы теоретической кибернетики".- Горький, 1988.- С. 134.

15. Иаугкин B.C. Об использовании эллипсоидной нормализации при решении задач выбора направления в методе линеаризации // Вестник МГУ. Сер.15.- 1988. -И 3.- С. 43 - 49.

16. Ижуткин B.C. Метод приведенного градиента для задачи стохастической оптимизации с нелинейными ограничениями // Восткик МГУ. Сер.15.-1989. -n 2.- С. 78-81.

17. Ижутккк B.C. Метод приведенного субградиента для задача выпуклой недзффореицируомой оптимизации // Материалы 10 Всесоюз.

симпозиума "Системы программного обеспечения решения задачи оптимального планирования".-Нарва, 1988.- 0 . 28 - 29.

18.: Ижуткин B.C., Кокурин M.D. Методы приведенных направлений для задачи нелинейного программирования // Материалы 33-го Мождунар. науч. коллоквиума.-ИЛьменау, 1988.-С. 49-51.

19. Ижуткин B.C. Об одном классе методов линеаризации для осйцей задачи нелинейного программирования // Ыатериалы 6 Всасош. конф. "Методы математического программирования и программное обеспечение".-Свердловск, 1989.-С. 102 - 103.

20. Ижуткин B.C. Об использовании приведенного градиента для одного класса задач оптимального управления // йатерналн Международной конференции "Optlmlerungatheorle und Anwendungen" .- Eisenach, 1989.-С. 105 - 1С».

21. Ижуткин B.C., Кокурин И.Ю. Об итеративной регуляризации метода приведенных направлений для задачи выпуклого программирования // Материалы Цездунеродной конференция "Optlralerungatheorle und Anwendungen".-Eisenach, 1969.-0.128-129.

22. Ижуткин B.C., Кокурин И.Ю. Об одном классе методов возможных траекторий для решения задачи нелинейного программирования // Тезисы докладов Международной ик.-соминара "Методы оптимизации и их приложения".-Иркутек, 1909.- О. 98 - 99.

23. Ижуткин B.C. Гибридные методы приведенных направлений для задачи нелинейного программирования // Материалы 11 Всесоюз. симпозиума "Системы программного обеспечения реиения задач оптимального планирования".-Кострома, 1990.- С. 23.

24. izhutkln v.s. Methods of Reduced Directions for Ceneral Nonlinear Programing Problem // Материалы X Меддунар. кенф. по мат. программированию.-Галятото (Венгрия), 1990.-

С. 19 - 22.

25. Ижуткин B.C., Кокурин H.D. Метода приведенных, направлений с допустимыми точками для задачи нелинейного программирования // Журнал вычислительной математики а математической физики.-1990.-T.3Q.-К 2,- С. 217 - 230.

26. Izhutkln V.s. Method of Reduced Subgradlent for Convex Uonsmooth Optimization // Материалы Международной конференции "Optiinlerungatheorle und Anwendungen".-Elsenach, 1990.-C. 59-63.

27. Ижуткин b.c., Петропавловский М.В. Метода приведенных направлений о различными функциями выигрыше для задачи нелинейного программирования в их программная реализация // Материал» 7 Всесоюз. конф. " Методы математического программирования и программное обеспечение Свердловск , 1991 .-С. 72.

28. Izhutkln V.S. Methods of Reduced Directions with Different Merit Function for Nonlinear Programing Problema

// Abstracts 15 IPIP Conference. -Zurich,, 1991.- P. 178 - 179.

29. Ижуткин B.C., Кокурин M.D., Петропавловский М.В. Оптимизационная диалоговая система ОДИС на основе методов приведенных направлений // Материалы XII Конференции-"Системы программного обеспечения решоиия економических задач". -Нарва-Иыассуу, 1992.- С. 10 - 11.

30. Izhutkln V.S.о Petropaviovskll M.V. Methods of Reduced Directions with Different Coat Function for Nonlinear Trograuralng Problem // Operations Research '92 . Heidelberg: Phyeica - Verlag, 1993.- P. 183 - 169.

31. Ижуткин B.C.о Петропавловский М.В. Метода приведенных направлений о допустимыми точками на основе различных фунюсий виигрцша // Материалы конференции "Математическое программирование и приложения ".-Екатеринбург, 1993.- С. £>3.

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

В работах с немецкими коллегами - профессором Г. Клейнмихелем и доктором К. Шеиэфольдом - автором предложен один алгоритм обобщенного метода приведенного градиента и единообразная реализация катодов первой и второй фазы гибридного алгоритма.

Подписано к печати 12.10.93 г. Заказ 1019. Тираж 100.