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

Нац'юнальна академ>я наук УкраТни 1нститут* кибернетики 1*мен1 В. М. Глушкова

РГ6 од

2 о 19*6 На правах рукопису

УДК 519.8 АЛЕКСАНДРОВА Валентина Михайлпвна

ЧИСЕЛЬН1 МЕТОДИ РОЗВ'ЯЗАННЯ СК1НЧЕННОВИМ1РНИХ ВАР1АЦШНИХ НЕР1ВНОСТЕЙ

Я. 7ё

математичне моделювання та обчислювальн! .методи в наукових дослщженнях

Автореферат дисертаци на здобуття наукового ступеня кандидата ф1зико-математичних наук

КиГв 1996

Дисертащею е рукопис

Робота виконана в 1нститут1 ибернетики iMeHi В. М. Глуш-кова HAH Украши.

HayKOBi KepiBHHKH: академш HAH Украши,

доктор (}изико-математичних наук ПШЕНИЧНИИ Борис Миколайович,

доктор ф1зико-математичних наук ПАН1Н BiKTop Михайлович.

Офкийш опонентн: доктор ({нзико-математичних наук ГУПАЛ А. М„

кандидат (¡лзико-математичних наук ЖУРБЕНКО М. Г.

Провщна оргашзащя: Кшвський ушверситет iMeHi Тараса Шевченка.

. Захнст в1дбудеться « ^ ■» -- 199 6 р 0 -

год. на заыданш спещал1зовано1 вчено! ради Д 01.39.02 при 1нститут1 1ибернетики iMeHi В. М. Глушкова HAH Украши за адресою:

252022 К.И1В 22, проспект Академжа Глушкова, 40.

3 дисертащею можна ознайомитися в науково-техшчному apxißi ¡нет и туту.

Автореферат роз^лашш « ^ > ---__—_ 199 ^ р.

Учений секретар спещал5зовано! вчено! ради

СИНЯВСЬКИП В. Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальшсть теми. Проблема розв'язання скшчешювим1рних вар1ащйних нер1вностей е важливою областю дослщження внаандок того, що вони е узагальненням задач оптим1зацн, розв'язання операторних р!внянь, зчаходження сщловнх точок. До них зводяться задач1 багатокрнтер1ально1 оптим!зацн, задали прийняття ршень, що виникають при дослщжеиш статичних моделей р1вноваги в економнп. Зокрема, у вигляд1 вар1ащйшгх нер1вностей можуть оути сформульоваш задача розподшу торпвл1, а також модель то описують вщношення мiж виробництвом та спожнванням, м1ж попитом 1 споживанням та цшами. Окр1м того, областю застосування вар1ацшних нер1вностей е модел1 знаходження точок р1вновагн по Нешу в теорц ¡гор. Тому методи розв'язання вар1ацшних нер1вностей мають важливе значения для виргаення проблем в р!зномаштних сферах д1яльности

Основою математичного апарату ще! теорй стала теор!я монотонних сператор1в, яка була розвинена в роботах М. Вайнберга, Ж. Л. Люнса, Г. Ж. Мнгп,I. Екланда, Р. Т. Рокафелара. Фундаментальна результатн були одержан! стосовно питань ¡снувапня, единосп та локально! единосп розв'язку вар1ащйних нер1вностей. На вщмшу ш'д теорн ¡агування та единосп, яка е майже завершеною областю досладження, теория побудови алгоритм1в дгся розв'язання вар1ащйшсх нер1вностей розвинена недостатньо. Гснукгн методи з теоретично високими оцшками швидкосп зб1жност1 е, як правило, локально зб1жними I потребують розв'язання складних допом!Жних задач на В1ШДШЙ нeлiнiйнiй множит обмежень. Для методт першого порядку, запропонованих, наприклад, Б.М.Пшеничним, навпаки при ефектившй реал1зацн кожно! ггерацн та нелокальшй зб!жносТ1 1терац1йно1 послвдовносп, оцшки швидкосп зб1жносп в окол1 розв'язку не встановлено. В алгоритмах, що базуються на розв'язанш системи необхщних умов першого порядку демпф1рованими методами Ньютона, також виникають проблеми внаслвдок особливостей ще? шстеми, а саме П недиференщйовносп далеко в:д розв'язку.

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

Мета роботи. Запропонувати глобально з6гжн1 алгоритмн, яю б дозволяли ефектнвно знаходити розв'язок вар1ац;йних нер1виостей з сильно монотонним оператором. 3 щею метою' вар1ацпшу нер!вшсть сформулювати у вигшцц еквшалентно! задач! оптим!зацп, для розв'язання якш застосувати розвинений апарат математичного програмування.

Ослабити вимогу сильно! монотонносп оператора i побудувати глобально зб1жний метод першого порядку для розв'язання BapianifuiHx нер1вностей з монотонним оператором.

Застосувати '¡дею сполучення двох метод!в, яка була запропонована Б.М.Пшеничним та Л.А.Соболенко в умовшй оптммЬацп, для побудовн прискореного алгоритму розв'язання Bapiaiiifiiiiix нершностей.

Метоли дослщжень. В основу дослщжень покладено матсматичний апарат ;eopii умовно! оптим1зацп, зокрема метод1в послщовного квадратичного нрограмування, дискретного мш1максу та недиференщйовних штрафних функшй.

üayKQsajiQ£U3iULpQ.6i2XU. Запропоновано оптим1защйний шдхщ до побудови глобально зб1жних алгор! lie розв'язання BapiauiftHHX нершностей з сильно монотонним опера юром та опуклою множимою обмежень, у тому числ! алгоритм1в ньютошвського тину, що мають надшшйну швидюсть зб1жносп в окол1 розв'язку. Одержана оцшка лЫйно! швндкосп зб1жност! модифжованого методу Б.М.Пшеничного для розв'язання вар1ац1йних нершностей э сильно монотонним оператором. Побудовано регуляризований алгоритм першого порядку для BapiaiiiitHitx liepioiiocTefi з монотонним оператором на обмеженому багатограннику.

На ociioei сполучення двох метод]в сформульовано глобально зб1жний метод для розв'язання BapiauiAnnx nepißiiocTefi з сильно монотонним оператором, який мае квадратичну швидмсть з61жносп в окол1 розв'язку.

Теоретична i практична uiHiiicrb роботи. Робота с частиною программ наукових дослщжень, ЯК1 проводяться у В1ДДШ1 обчислювальних мстод!в онтпм1заци Ыституту мбернетики ¡мен» В.М.Глушкова HAH Украши.

Наведеш в дисертацп результати чиселыюго експернмеиту показують, що запропоноваж алгоритми можуть бути використаш для розв'язання задач економ1КИ, теорн irop, як! зводяться до BapiauiftHKX uepiiuiocreii.

Аиробашя робот. Результати роботи доповщались на ccMinapax у вшил! обчислювальних метод1в оптим1зацн 1нституту ыбернетнки ¡Meni В.М.Глушкова HAH Украши, у Кшвському ушверситет1 im. Тараса Шевченка, на Il-ift Украшськш конференцн "Авт«матика-95", м. Льв1в, 26-30 вересня 1995 р.

Публ1каш1- За темою дисертащйно! роботи опублковано 7 робЬ, список яких наведено в кшщ автореферату.

Структура i_ß6car_pi>6oiii. Робота складаеться з югупу, трьох роздшв, ч"патку, висновку та списку лЬератури 3 75 найменувань. Загальни >6сяг роботи становнть 95 cropiHOK.

3MICT РОБОТИ У Bcryni обгрунтовуеться актуальшсть тематики доонджень, даеться короткий огляд ¡снуючих тдхсдав до розв'язання вар1ащйних Hepieiiocreft. 3mictobho викладено основы! результата, AKi одержан! в дисертацп.

Дисертащя присвячена методам розв'язаннл скшченновим^рних eapiauiftHnx нер1вностей. Вихщна задача полягае у знаходженш точки

п

х, € С1ж С R • дляяко!

(F(x.),x-x.) ¿0. V* € П,. (1)

Задача (1) вивчасться в залежносп в!д виконання наступннх

умов:

я п

а) оператор F(x): R -> R неперервно диференщйовний та сильно монотонний

AW * (F(x)p,p) Z ni\p\\2 Vx, p 6 r", (2)

де А/ £ т. > 0 - craai;

б) множима Q^ задаетьси у вигляд1

nt - {x € r" I A,(x) £ 0, / = 1...../}, (3)

де (x), / = 1, ..., I - onyicni неперервно диференщйовш функцн, та мае внутр1шню точку,

в) град!енти А( (дг), / е ¡(х) » {/el.....I | А, (х) =>

« h (х) а шах {0, А((х), .... А;(х)}} лиийно незалежш в розв'язку х. (умова регулярное« обмежень);

п п

д) оператор F(x): R -> R монотонний

(F (х)р,р) 2: 0 Vx,p € ft". (4)

t

Всюди вектори, наприклад, х ■ {х }, розглядаються як вектор-

стовбщ з компонентами х ;(•,■) - знак скалярного добугку; || • || - евклщова норма вектора; Г - знак транспонування. Позначимо шг= (хт; Хт), Lt(a)) = F(x)+ Н(х)Х, де Н(х) • матриця вим1ру

лх/, стовбц! яко| е Ау(х), / =* 1, ...,/; h(x) - вектор-функщя з

компонентами h (x), i = 1.....I. |/.| » I - мльмсть елемент1в в

множит I, = /(х,). Нижш сим воли х в та в в (<о)

введен! для зручносп позначень i не ознлчають похшних; в peiini

випадшв вони означають вщповщш похщш: (га) = dtp(a>)/dx, ~ ^„(юК^ i т.д.

У першому роздЫ розглянуто ^apiauiilni nepiBHOcri (1) з сильно монотонним оператором F(x). Запропоновано перехад до екв1валентних задач нелшШно! умовно1 оптим1зацн та розглянуто обчислювальш метода ix розв'язання. На оснош метод«в послщовного квадратичного програмування та використання недиференщйовно! штрафно! функцп побудовано глобально зб1жний метод розв'язання задач1 (1) - (3). Для запропонованого алгоритму встановлена оцшка лппйно1 швидкЬсп зб1жносп.

В §1.1 викладеио ¡снуюч1 щдходи до розв'язання вартцшннх KepiBHocrcK та деяк1 niflOMi факти' теорн ¡снування та единосп розв'язку.

Ведомо, що задача (1) при виконанш умов а), б) мае единий розв'язок х,.

т г т

Точку со, =(х, ;Я,,), х. eiJ назвемо парою Куна-Такера задач! (1) - (3), якщо для не! виконуються необхщш умови першого порядку:

Lx(со.) = 0, *.'./»,(*.) = О, х'. ^ 0, / = 1.....I. (5)

Якщо, OKpiM умов а), б), виконусться умова в), то X. також визначасться в (5) однозначно, таким чином со, - единий розв'язок системи

LJto) = 0, Xh.(x) = 0, А.(х) <; О, X 2: / = 1, L (6) Якщо оператор F(x) - монотонний, то задача (1), (3), (4) може мати неединий розв'язок х, е {х,} = X,. Однак, внаслщок пркпущення

б), необхщш умови першого порядку (5) для задачi (1) е також i достатшми.

Точки = (xf; Хт,), ям задовшьняють систем! (5), назвемо

шуканими як для задач! (1) - (3), так ¡для задач! (1), (3), (4).

В §1.2 для знаходження розв'язку ситеми (6) побудовано flei задач! иелшшпсл умовно! онтим1зацп з аргументом

т г т п+1

о) = (х ; X ) е R . Перехщ до екв1валентних оптимиацШиих

задач бшьшого шж шшдиа задача BUMipy обумовлений

- ,г

неиотеи олльшстю оператора F(x) (F (х) * F (х)). Одшею з таких еквшален тннх задач оптим1заци е задача

min ©(со),. е , . (7)

де 0(со) = |рх(со)||2 - (ММ), = х Л+, А+ =

X го, / = 1...../}. Вщмггимо, що функщя ©(со) була вперше

використана Б.М.Пшеничним для розв'язання вар!ацшних нер1вностей.

Цшьова функщя друго! екв!валентно'{ задач! оптим!заца вводиться як фтакщя квадрату вщхилу р!вностей системи (6)

( М®)

ф(со) = ^||1ш(со)||2 , 1а(со) н

I *,*/<*>

(8)

а вщповвдна еквталентна оптимвацшна задача мае иигляд:

щщ Ф(о), га б . (9)

со

Будемо називати стацюнарними точками задач (7), (9) точки со е , ям задовшьняють необх!дним умовам екстремуму першого поряду вщповщно! зада-п оптим!зацн.

Теорема 1. Будь-яка стацюнарна точка со задач (7), (9) е шуканою для задач 1 (1) - (3). В точщ х, множники Лагранжа для еквталентно! задач! (7), що вщповщають обмеженням множини ,

задовшьняють умовам: ц = - ЛДх,), / = 1...../, 8 б {А,,} = Л,,

а для задач! (9) в!дповщш множники дор1внюють нулю.

Результат теорсми 1 не можна поширити на задачу (1), (3), (4). При виконанн! умови д) можуть ¡снувати стацюнарн! точки ю' задач (7), (9), для яких сЛЭ(со)/е?со = 0," <Лр(со) / £&о = 0, але со) * О,

©(ю) > 0, ф(со) >0.

Наведемо шин власти восп функци ф(со).

Лема I. Якхцо в точщ яка з розв'язком задач! (1) при виконанш умов а) - в), Я, > 0 для вс1х / е /,, то матриця Ь (со , )

п+1

невироджена ! для будь-яких о 6 Я

2

(Ф««,*®.)01'31) ^ "^Н03!! • % > 0- (10)

Лема 2. Якщо в задач! (1) - (3) множина О. ^ окр!м нер!вностей

о

задаеться л!н!йними р!вностями = 0, у е / = {!,...,/•},

розв'язок х, задач! (1) ¡снуе, в точщ х, виконуеться (5), град!енти

о. /

(л:,), / е /, и I лшшно незалежш, Я., > 0 для Bcix i е I, та

2

(¿„(ffl.Kx) 2: m|MI . т > 0 (П)

о

для Bcix х е М = {* | (kt (х, ),х) = 0, / б I, U 1 }. то виконуеться (10).

• Вщомо, що справедлив1сть HepiBHOCTi (11) на множит М називаеться достатньою умовою другого порядку, яка гарантуе локальну едишсть розв'язку х, задачi (1).

Лема 3. Для будь-якого фжсованого С £ 0 множина

п +

Gc = {со € R х А | <р(ш) £ С] обмежена.

Задача (1) при виконанш умов а) - в) зводиться до задач1 мнпм^аци (9), яка мае единий розв'язок со,. Цшьова функщя ф(со)

Л + v '

задач! (9) мае обмежеш на R к А лшЦ р1вня, едину на йа стацюиарну точку to,, яка е точкою глобального мпнмуму функци

<р(ш) i в око/ii яко'1 ф((о) сильно опукла, якщо X, > 0, / 6 .

В § 1.3 для розв'язання екв1валентно'1 задач! оптим1заци (9) розглядаються методи посладовного квадратичного програмування з

використанням недиференщйовнр! штрафно'! функци Ф(о); N) — +

= ф(со) + Nh (х), N - коефщ!ент штрафу. Задача (9) з.ставляеться з задачею

min Ф(ю; N), со б R" х А+ . (12)

ш

Лемь 4. Розв'язок со, задач! (9) е стацюнарною точкою задач!

(12) для будь-якого N Z 0. Навпакн, яке б не було значения N £ 0, стацюнарна точка задач! (12), яка належить обласп , е розв'язком

задач! (9).

Теорема 2. Якщо OKpiM умов а) - в) вихщно! задач! (1), функци ht(x),i = 1, ..., / силиноопукш:

mjlxll2 * (И](г)х,х) й М¿Щ Ух, г е r", (i3)

де А Г > ■ >. > 0 - сталь то стащонарн! точки со ,N задач! (12) обмежеш pianoMipiio поЛг>у,деу> 0 - стала. Знайдеться, окр!м тою, порогове значения N > 0 таке, що со = со, для будь-якого Л' 2; Л'.

Для метсдав послщовного квадратичного програмування допом1Жна задача, яка е апроксимащею (9), мае вигляд:

(Фв(®*).® - fflA> + - ®*>'® ~ ®*>

mm

0)

(14)

h.(xk) + {ht(xk\x-xk) <, О, X £ 0, / = 1, ..:, /, де Ак - симетрична (п + I) х (п + Г) -матриця, яка для будь-яхих

п+/

А = 0, 1, ... та р е R задовшьняеумовк

а\\р\\2 й (Акр,р) Z А\\р\\ , А а > 0. (15)

I

В задач! (14) враховуються обмеження X > 0 для ecix 1

i = 1, ..., /, оскшьки Bci X входять до виразу'функцп <р(со). Щодо

обмежень h. (х к) + (h.(x к),х - х к) < 0, то'ix можна враховувати не

для ecix i = 1, ..., /, а лише для «' е = { /' | hf{xk) £ +

h (х к) - 8 / N}, де 5> 0 - стала.

Дал1 на основ1 розглянутого оптим!защйного шдходу вивчаються обчислювалын методи розв'язання варюцшних нер!вностей (1) - (3). Будемо називати методи виршення BapiauifniHX неровностей, як1 використовують обчйслення оператора F(x) та град!ент1в функцш h.(x), i = 1,...,/, методами першого порядку, а

методи, яы потребують визначення матриць h. (х), F (х) або ix

апроксимащй, методами другого порядку.

В §1.4 сформульовано глобально зб1жний метод розв'язання сильно опуклих BapiauiftHHX нер1вностей, який е методом послщовного квадратичного програмування для розв'язку ;кв1валентно'1 задач! оптим!зацн (9). 1теращя методу мае вигляд: шЬ| = со к + а, крк, де

рк — а - <й к, л о) - розв'язок задач! (14); а^ визначаеться з релаксацн функпн Ф(со; N) по правилу ApMifto. Встановлено, що ¡терацшна поапдовшсть цього методу глобально збпаеться до розв'язку задач! (1) - (3) з лМйною швидюстю зб!жносп в окол! розв'язку.

Теорема 3. Якщо виконуються умови а) - в) задач! (1), множина

fi^ обмежена, F (х), И. (х), 1 = 1...../ задовшьняють умов!

Л!пшиця, то со -> со0, -> 0, Qк 0 для к -> оо,

а^ > а > 0 i, починаючи з деяко! ¡терацн, величина N к = N е сталою. Якщо оператор F(:с) неперервно диференц!йовний та

монотонний, виконуються умови 6) та в), X, >0 для ecix i е I,, в точц! со. • виконуються достатш умови другого порядку, то для (о к —>• со, в OKOni розв'язку со, cni аведлив1 ощвки:

£ дФ(<»к-,Ю, ||шА - о).|| 5 Cqm, q е (0; 1). Хоча побудований метод е методом першого порядку ввдносно оптим1зацшно! задач! (9), однак, Bin е методом другого порядку вадносно виидно! задач! (1). Перевагою такого гйдходу пор1вняно з вадомими методами розв'язання Bapiaummtx нер!вностей, а саме, проекщйними,»е те, що матрицю А к можна варповати. Якщо,

наприклад, матрицю Ак вибирати так, щоб Ак -> ^ (со,; 0; 0), де .£(•) - функц!я Лагранжа оптим1зацшно1 задач! (9), то можна прийти до швидкозб!жного методу ньютошвського типу, використовуючи обчислення матриць h. (х), F (х). " ;

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

Друшй-ршшд присвячений алгоритмам першого порядку для розв'язання BapianifiHnx нер!вностей,

В . §2.1 розглянуто модифшацио методу, який було запропоновано Б.М.Пшеничним, для вар1ащйних нер1вностей з сильно монотонним оператором та опуклими обмеженнями-нер!вностями.

На кожшй ¡терацн вказаного алгоритму наближення обчислюються за формулою: =хк +акрк> к = С, 1, ... .

Дапом!жна задача, яка використовуеться для визначення напрямку рк, мае вигляд:

min i(F(x ),p) + ]:{Ар,р)},

р 2 (16)

h.(xk) + (/r(xk),p) £ 0, / = 1.....1.

Величина множн жа ак обчиа..оет1.ся з релаксацн функцн

v(x,X) е min L(x;p;X) = - -|!L ||2+(М(*))> де Их\ р\ X) ■ г 2 *

функция .¡ранжа задач! (16). Таким чином, ак - найбшьше серед

— S

чисел а = 2 , j = 0, 1, ям задовшьняють одночасно неровностям:

у(хк + арк-,1к) - МкИ (хк + арк) 2: v(xk; Хк) -

2 (17)

- Nки (х4)+ еа

2

И\хк +арк) <, р, р>Л+(дг0). . (18)

Позначимо Ук = Ч7^;^) = у(хк;Хк) - + (хк) =

= - АРк>Рк)+ &к>Кхк)) -МкИ+(хк).

Ведомо, що умови Ч^ = 0 або —► 0, необхщш, а якщо

£\кйМк, (19)

/=1

то 1 достатш для того, щоб вщповщно хк = х< або хк -> х,. Якщо

виконуеться умова(19),то 5 0.

У модифшованому алгорич.-.л для вибору а к закпсгь нер^вносп

(17) використовуеться нер1вшсть

+ 2 у(хк +арк;\к)~ N кИ (хк+арк)2.( 1 - еа )Ч'^,е>0.

Теорема 4. Якщо для зада-п (1) виконуються припущення а), б), матрищ Р (х), А. (х), / = 1, ..., / задовшьняюгь умов1 Лшшиця, множина О^ обмежена, то модифжований алгоритм зб1гаеться по прямих та двоктих змшних: д; к х,, X к {к,}, де {А.,} -множена векторов множшшв Лагранжа задач1 (1) в точщ л:, . При

цьому рк -> 0, Ч'к 0 для ¿->оо; ак £ а > 0 для век к = 0, 1, .,., величина Л^ = N стала для к £ к0- В окол1 розв'язку х, справедлив! оцшки:

|Ф4| 5 С<А ||р4|| 5 ||х4 - х.Ц £ С2ч\, (20)

1/2

де д е (0; 1), д., = д .

На баз1 оц1нок (20) для модифшованого алгоритму доведена липйна швидюсть зб1жносп методу Б.М.Пшеничного. Одержана оцшка лнпшкм швидкосп збшност1 разом з доказаною рашше властив!стю глобально! зб1жносп та простота реал1зацн ¡терацп методу дають основу для ствердження, що пш е найкращим серед ¡снуючих алгоритм1в першою порядку для розв'язання вар1ащйних нер1вностей з сильно м нотонним оператором.

Бшышсть метод1в для розв'язання вар1ацшних нер1вностей иотребують сильно! монотонности оператора Р(х). На вадмшу вед них в §2.2 побудовано регуляризований алгоритм першого порядку для розв'язання задач! (1), для яко! умова а) замшена на умову д), а множина С1х е обмеженим багатогранником. Допом1жною задачею регуляризованого методу е задача квадратичного програмування:

(21)

шах

р

HF(xk),p) - Ц~М\1

ht(xk) + (h^x^p) á 0, i = 1, ..., /. Для вибору множннка ак використовуеться функщя ©о^(<и), де ак > 0 - параметр регуляризацн. Функцш (со), як i розглянута

рашше функщя v(x; ÄJ, е цшьовою функщею, двойлчм до допом1жно1 задачЦ21):

вв(®) = max¿"(®;p) = -5-!|1х(сй)||2 - (МОО).

р ^^

Дал1 розглядаеться задача (1), (4), в якй множина Q^ е обмеженим багатогранником:

Пж « {* -е R" | h.(x) т (b.,x) + dt á 0, i = 1...../}• (22)

Формуяювання алгоритму. Виберемо довшьними xfl eß^, а0 > 0, е е (0; 1), q е (0; 1) та позначимо ©t(co) = ©в (ш),

= (Xk,h(xк)). Запишемо к-у ¡теращю в точщ хк * х%,

{рк * 0), к = 0, 1.....

L Розв'язуючи задачу (21) та двокту до Hei, знаходимо

Р . X , Т. . Якщо I4? | < а., то йдемо на III, якщо I к а , * * * * * к . к

то - на II.

И | ^ а ). Визначаемо а. як найбшьше серед чисел * к *

а = 2 min {1; а^Ч^О, s = 0, 1.....яю задовшьняють HepiBHoeri

©¿(х^ + арк;Хк) ¿ ®к(®к) + еа^, i знаходимо точку = х^ + а крк- Покладемо ам = ак;

кшець ¡тераци. '

Ш (|ЧРд | < ак). Покладемо xk+¡ = х^, вибираемо ak+¡ э

умови qa к <,а <ак, ак -> + 0. Кшець ¡терацн.

, Якщо в задач 1 (1), (4), (22) похщна Р (х) задовшьняе

умов! Лшшиця, то 0 к (со ) -* О, со к -> {.V,; Л.} для к -> со, а

кожна ггеращя процесу закшчуеться за скшченне число обчислень, яке р1виом1рно обмежене по к —> оо.

Трети! роздш присвячений алгоритмам другого порядку для розв'язання вар!ащйних нер1вностей. >

В §3.1 на основ1 щдходу, яхнй було запропоновано в роздии I, сформульовано нелокально зб1жний квазиньютошвський метод для розв'язання вар1ац1йних нер1вностей з сильно мо тоним оператором та сильно опуклими обмеженнями-нер1вностями. На кожшй ¡терацц алгоритму для знаходження напрямку спуску розв'язуеться допом1жна задача квадратичного програмування в простор! прямих змшних

л+/+1

(©;.£) е и

Ш1П

»■4

(фт(С0(1),(С0-С0^) + ^(^(со-юДсо-со^ + Л^ ' ~ +

И) (хк ) + (А. (хк ),х - хк ) <, ' е / к , X е Л ,

(23)

де/4 = {/ е 0, 1...../| И.(хк) * А (xk)-Ь/Nk },»4(х) а. 0,а

^ еЯ -додатковазмшна.

Догюм1жна задача квадратичного програмування з додатковою змшною використовуеться замйгть задач! (14) для того, щоб дво\'ст1 змшш оптим1зацшно1 задач 1 були обмежеш значениями коефнцента штрафу N. На вщмнгу вщ (14), задача (23) завжди мае розв'язок, нашть тод1, коли функцп обмежень не е опуклими.

Задач! (14), (23) будемо називати екв1валентними в точщ со ^,

якщо стацюнарш точки цих задач сшвпадають по компонентах со.

Дема 5. Якщо матриця Ак задовшьняе умов1 (15) та Nк > 0, то умова к = 0 е достатньою для екв!валентносп задач (14), (23).

Якщо, окрм того, 0 е / к , то вона е також 1 необхщною.

Для побудови алгоритму ньютошвського типу в допом1жнш задач! (23) матриц! Ак вибирают>-ся так, щоб Ак -> Фи(1) (а.) Л'1Я

т

со к —> со,. Такш умов1 задовшьняють матриц! (со к (со к )■

п +

Формулювання_алгоритму. Нехай о) д е II х Л , 5>0,

С > 0, д е С" 1), б е (О, 1), N > 0, г > 0 - достатньо мала

R R

величина, виберемо Ф = Ф(со 0; Лг0), де Ф - позначення

поточного рекордного значения функцц Ф(со; N).

Опишемо к -у ¡теращю методу со = ю 4 а крк в точщ сок * со,, к = О, 1, ... .

I. 3находимо розв'язки задач1 квадратичного програмування (15), (23) та двокто! до не! - рк , ц , 9 .

IL Обчислюемо а к як найбшыпе серед чисел

-S

а=2 , i = 0, 1 , .... ям задовшьняють HepißHocri Ф(со, + арк; Nk) < Фк - Ua(Akpk,pk).

Знаходимоточку =* к + акрк*

R Н

Якщо Ф^ > Ф , то йдемо на III, шакше(Ф4 <. Ф )- HalV.

R

Ш(Ф|1 > Ф ). Якщо виконуються HepiBHOcri

шах \\\рк\\,\\лкркII,|(е4,Р])|,|(Х4,(лкРк)*)

* с, (24)

о

ц, йгЫк, (25)

то покладемо N к+1 = 2Л^ , ¡накше при порушенш хоча б одше! з умов (24), (25) - = Nк . Кшець ¡тераци.

1У(Ф4^ФЯ).

О А

а) Якщо < М к, то покладемо Ф = дФ(со^+1; Л^),

= Nк ; кшець ¡тераци.

о я

б) Якщо ц 4 ¿1 гЛ^, то покладемо Ф = Ф(ш4 ; N к) та

обчислюемо N к+] за правилом: = N к, якщо а^ = 1;

= Nк / 2, якщо ак < 1; кшець ¡тераци.

Теорема 6. Якщо виконуються припущення а) - в) задач1 (1), та умова (13), то ш( ~> со,, рк -> 0, ц^ -> 0, 84 -» 0, величина

Nк = N > 0 е сталою теля деяко! ¡тераци, а задач 1 (14), (23)

екв1валентш. Якщо, окр1м того, X, > О V / 6 /,, то в окол1 розв'язку со, виконуеться р1вшсть а к = 1 та справедлива оцшка \\рк II * ^Нр,.,!!, де о для к -> со.

Вщмггимо, що для задач! оптим1зацн min {/0(х) | hj (х) 5 О,

+

i = 1, ..., /} релаксащя функцн /0(х) + Nh (х) не призводить до одержання а ^ = 1 в метод1 Ньютона з допом1жною задачею (16), в

ямй Ак = ¿^(хk i), F(x) = /fl (х). Тому методи ньютошвського

типу, як1 використовують релаксацно функцй /0(х) + Nh+ (х), не е

надлннйно збЬкшши (ефект Маратоса). Теорем.-. 6 показуе, що для

випадку F(x) = /0(х) при 3aMiHi вихвдно'! задач i оптимшацц

екв!валентною задачею (9) бшьшого BiiMipy ефект Маратоса не виникае в запропонованому метод!.

В §3.2 побудовано комбшований метод для розв'язания вар1ащйних нер1вностей. Bin базуеться на сполученш глобально збЬкиого методу першого порядку для розв'язания Bapianiftnnx nepißHOCTeft та методу ньютошвського типу для розв'язания системи необхщних умов першого порядку.

Такий шдоод до побудови прискореного методу лшеар1зацй в задачах умовно! оптим1зацп був запропонований Б.М.Пшеничиим та Л.О.Соболенко.

Позначимо J(x) = {/' е 1, / | (х) + (Л/(х),р) = 0}, де

л

р £ Л , | J(x)| - кшьк!сть елемен^в множини J(x).

п

Формулювання алгоритму. Виберемо eR , у, в, тар.де

+

е б "1; 1), у € (0; 1), ß > h (xQ); CQ > 0 - достатньо велике

число. Опишемо к -у ¡терацш методу.

L Розв'язуемо задачу квадратичного програмування (16) та двокту до ue'i. Позначимо розв'язок задач! (16) р(х к ) через рк, а

множникиЛагранжу X (хк) ' = •••>

Якщо \\рк || > Ск , то покладемо С<+1 = Ск та йдемо на IV, якщо \\рк || й. Ск - на II.

IL Знаходимо ук , розв'язуючи систему piBnocreft

lxx(xk,Xk)y + F(xk) + fl(xk)W=0, (26)

НТ(хк)у + h(xk) = О,

\J(*k )l -

де h(xt ) e R ; H(xk ) - матриця BUMipy я x | J(xk )|, стовбщ

»

яко1 e вектори A/ (x^), i e J(x ), у e R , w e R

Якщо система (26) не мае розв'язку, то покладемо С4+| = l\\pk || та йдемо на IV, якщо розв'язок системи у к знайдено, то - на III.

ILL Обчислюемо

* = + (27)

В точц1 х знаходимо р(х), розв'язуючи задачу (16). Якщо

Нр(х)|| * у|1я4 II. (28)

то покладемо *i+| = х, С1+| » у||р(х)||, Nk = Nд , (N0 >

„ / .

£ XQ , i = 1, .... I). Юнець ¡терацп.

Якщо умова (28) не виконуеться, то обчислюемо » l\\pk II та йдемо на IV.

IV. Обчислюемо Nк - max {Nk 2 £ Xf }.

<-i

V. Вибираемо a k з нер1вностей (17), (18), та обчислюемо

= xi+akPf

Теорема 7. Якщо, окрш умов а) - в) задач! (1), матриц! F (х),

ftj (х), = 1, ..., / задовшьняють умов! Лшшиця, множина П^

/

обдежена, X, > 0 для ecix »' е 1(х,), то в комбшованому алгоритм!

х4 —► х., к —► оо. В окол1 розв'язку х, наближення xi+J

обчислюються за формулою (27) i справедлива оцшка

2

||х1+! - x.ll * c\\xt - x.ll , С > 0.

Перевагою комбшоваиого методу в порюнянш э квазиньютошвським алгоритмом (§3.0 етс, що вж використовуе

к

¡терацшний процес в простор! прямих змшних R . Однак, для забезпечення зб1жносп вш потребуе виршеиня на кожшй ¡терацп двох допом1жних задач.

У додатку наведен! результати чисельних експерименпв. Регуляризований метод першого порядку (§2.2) та методи другого порядку - квазиньютошвський та комбшований (роздал III) - були випробуван! на прикладах Bitpiulemw як варшщйних иершностей, так i

оптим!зафйних задач. При знаходженш розв'язку вар!ац1йних нер!вностей запропоноваш алгоритми поршнювались з ¡снуючими методами першого та другого порядку (без апроксимацн множини П^). Результати обчислень шдтвердили перевагу запропонованих

метод1В другого порядку перед ¡сиуючими алгоритмами першого порядку. При розв'язанш оптим1зац!йних задач запропоноваш методи квазиньютошвський та комбшований -. пор!внювались з прискореним методом лшеарпаци. Результати обчислень показали, що запропоноваш методи другого порядку не поступаються перед оптим!зацшними методами вщповщного порядку I можуть бути використаш також для розв'язання задач оптнм133ци.

ОСНОВЫ! РЕЗУЛЬТАТИ РОБОТИ

1. Для розв'язання вар1ащйних нершностей з сильно монотонннм оператором та опуклими обмеженнями-нер1вностями запропоновано оптим1зацшний шдхщ, який базуеться на переход! до екв!валентних задач оптим!зацп. Вивчеш властивосп екв!валентних задач оптим1зацй. На основ*! математичного апарату метод1в посладовного квадратичного програмування з використанням недиференшйовно! штрафно! функца сформульоваш глобально зб1жш алгоритми розв'язання сильно опуклих вар1ацшних нершностей першого та другого порядку. Доведена глобальна зб1жшсть методш та встановлеш оцшки липино! та надлЫйно!' швидкосп зб1жноат ¡терашйних послщовностей метод1в в1дпов1дно першого та другого порядку в окол1 розв'язку.

2. Побудована модифжацш методу Б.М.Пшеничного для розв'язання варшшйних нер1вностей з сильно монотонним оператором на опуклш множини Доведена лнийна швидкГсть збгжносп моднфжованого алгоритму та методу Б.М.Пшеничного.

3. Сформульовано регуляризований алгоритм першого порядку для розв'язання вар1ащйних нер1вностей з монотонним оператором на обмеженому багатограннику.

4. Побудовано комбшований алгоритм розв'язання сильно опуклих варшийних нер1вностей. Метод базуеться на сполученш глобально зб1жиого методу першого порядку з методом ньютошвського типу для розв'язання системи необхщних умов першого порядку.

5. Запропоноваш алгоритми реал!зоваш та випробуваш на розв'язанш прнклад1в як вар1ац!йних нершностей з несиметричним оператором, так 1 оптим!за1ийних задач. Наведен! пор1вняльш характеристики запропонованих методов з ¡снуючими методами розв'язання вар!ашйних нершностей та задач оптим!заш1.

1. Пакет прикладных программ "МЕТЛИН-ПЭВМ" для решения задач нелинейного программирования /Б.Н.Пшеничиый, Л.А.Собояенко, А.А.Сосновский, В.М.Александрова и др. II Кибернетика и системный анализ. - 1993. - № 5. - С. 79 - 92.

2. Панин В,М., Александрова В.М. Линейная сходимость метода решения вариационных неравенств // Там же. - 1994. - № 3. - С. 175 -179.

3. Панин В.М., Александрова В.М. Нелокальный квазиньютоновский метод решения вариационных неравенств II Там же. - N» 6. - С. 78 -91.

4. Панин В.М., Александрова В.М. О одном подходе к решению вариационных неравенств II Кибернетика и вычисл. техника. - 1995. - Вып. 105. - С. 45 - 54.

5. Александрова В.М. Ускоренный метод решения вариационных неравенств // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М.Глушкова HAH Украины. - 1995. - С. 8-13.

6. Панин В. М., Александрова В. М. Асимптотические свойства метода линеаризации в задачах выпуклого программирования // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М.Глушкова АН Украины. - 1992. - С 13 - 23.

7. Panin V.M., Alexandrova V.M. A method for solving variational inequalities with monotone operator // Тез. докл. II Укр. конф. "Автоматика-95", г. Львов, 26-30 сент. 1995. - гЛьвов, 1995. - С. 38.

Особистий внесок автора. На 6a3i ¡дей оптимиацшного пщходу до розв'язку вар1ацшних нер1вностей, запропоноваиих науковими кершииками, автором самоспйно одержан» результати, яю складають основний змкгг дисертацш В (3, 4] вивчеш та встановлеш властиeocri екв1валентно1 задач1 оптим1зацй, до яко! зводиться вюидна вар1ацшна HepiBHicTb, побудований метод першого порядку розв'язання опуклих вар!ащйних nepieHocreü та встановлеш його властивосп. В [7] доведена зб1жшсть регуляризованого методу для розв'язання BapianiüHitx нер1вностей з вироджеиим оператором. В [2, 6] на баз1 оцшки, одержано! Паншим В.М. для модифисованого методу лшеар!заци, доведена оцшка лшшно! швидкост1 зб1Ж1 jcri методу Пшеничного Б.М. для розв'язання вар^ацшних неровностей э сильно монотонним оператором. Реал!зован> на ПЕОМ Bei запропоноваш в дисертацн метода розв'язку Bapiauifiinix нер'шностей та системна частина ППП "МЕТЛ1Н-ПЕОМ" (1], складовою част. лою одше! з верай якого е щ алгоритми.

Александрова В. М. Численные методы решения конечномерных вариационных неравенств.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 — математическое моделирование и вычислительные методы в научных исследованиях. Институт кибернетики им. В. М. Глушкова НАН Украины, Киев, 1996.

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

Alexandrova V. М. Numerical methods for solving finite-dimensional inequalities.

Candidate of Phys. & Math. Sci. thesis, speciality 01.05.02 — Mathematical Modeling and Numerical Methods in Scientific Research. V. M. Glush-kov Institute of Cybernetics NAS Ukraine, Kiev, 1996.

An approach for solving variational inequalities with strongly monotone operator on convex set of constraints has been proposed. On the base of the approach and sequential quadratic programming methods the first-and the seconde- order methods for solving stfongiy convex variational inequalities have been elaborated. Linear rate of convergence of method proposed by B. N. Pshenichny has been established. An accelerated algorithm for solving variational inequalities with strongly monotone operator has been formulated based on the idea of combining a global method for solving variational inequalities with Newton's type one for solving the first-order necessary conditions system. A regularizaron first-order method for solving variational inequalities with monotone operator has been suggested. As the examples of the testing proposed algorithms the variational inequalities and the optimization problems have been considered.

Ключов! слова: Bapiauimri HepiBiiocTi, монотонний оператор, методи пос.и'д .вного квадратичного програмування, недиференцшоваш штрафш

ф\ IIKIlií.

- Пщп. до друку 23.04.96. Формат 60X84/16. Пашр для розмнож. апар. Офс. друк. Ум. друк арк. 0,93. Ум. фарбо-вадб. 1,16. Обл.-вид. арк. 1,0. Зам. 238. Тир. 100 прим.

Редакшйно-видавничий в!дд1л з пол1граф1чною дмьницею 1нстнтуту юбернетики ¡меш В. М. Глушкова HAH УкраТин 252022 Ки1в 22, проспект Академжа Глушкова, 40