[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ] [ 17 ] [ 18 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ] [ 26 ] [ 27 ] [ 28 ] [ 29 ] [ 30 ] [ 31 ] [ 32 ] [ 33 ] [ 34 ] [ 35 ] [ 36 ] [ 37 ] [ 38 ] [ 39 ] [ 40 ] [ 41 ] [ 42 ] [ 43 ] [ 44 ] [ 45 ] [ 46 ] [ 47 ] [ 48 ] [ 49 ] [50] [ 51 ] [ 52 ] [ 53 ] [ 54 ] [ 55 ] [ 56 ] [ 57 ] [ 58 ] [ 59 ] [ 60 ] [ 61 ] [ 62 ] [ 63 ] [ 64 ] [ 65 ] [ 66 ] [ 67 ] [ 68 ] [ 69 ] [ 70 ] [ 71 ] [ 72 ] [ 73 ] [ 74 ] [ 75 ] [ 76 ] [ 77 ] [ 78 ] [ 79 ] [ 80 ] [ 81 ] [ 82 ] [ 83 ]
заўсёды будуць у працоўным спісе; актыўнасць зыходных няроўнасцей у дадзеным выпадку вызначаецца тым, звяртаюцца Ці ў нуль адпаведныя дапаможныя зменныя.
Заўвагі і абраная бібліяграфія да падзелу 6.3
Ідэя «прывядзення» або «праектавання» градыентаў першапачаткова выказвалася ў дачыненні да задач з лінейнымі абмежаваннямі. Спасылкі на адпаведныя работы дадзены ў заўвагах да разд. 5.1 і 5.2. Для задач з нелінейнымі абмежаваннямі першы метад «праекцый градыентаў» быў прапанаваны Розен (1961), які абагульніў сканструяваны ім жа аналагічны метад мінімізацыі пры лінейных абмежаваннях (Розен, 1960). Для вызначэння ў алгарытме Розена няяўна выкарыстоўваецца Артаганальная матрыца Zj.
Аўтарамі схемы абагульненых прыведзеных градыентаў з'яўляюцца Абадзі і Карпентье (1965, 1969). У яе першай рэалізацыі матрыца (6.18) будавалася ў відавочным выглядзе. Праграма, распрацаваная Абадзі і яго калегамі па Electricite de France, шырока ўжывалася для вырашэння практычных задач (гл., Напрыклад, Абадзі і Гигу (1970)). Эксперыментальнае супастаўленне розных метадаў, праведзенае Колвиллом (1968), паказала, што метады абагульненых прыведзеных градыентаў былі аднымі з самых надзейных і эфектыўных. Да цяперашняга моманту іх сямейства папоўнілася вялікай колькасцю новых алгарытмаў: як ужо было адзначана ў разд. 6.3.1, для канкрэтызацыі кожнага пункта схемы тыпу прыведзеных градыентаў ёсць намана магчымасцяў.
У апошнія гады иад метадамі тыпу прыведзеных градыентаў у ліку іншых працавалі Сарджэнт і Муртаф (1973), Абадзі (1978), Лэсдон і Уорен (1978),
Вядома, што пры істотна нелінейных абмежаваннях метады тыпу прыведзеных градыентаў працуюць дрэнна, паколькі моцна искривлеитшге мяжы допустгшого мноства адсочваць цяжка (гл. Разд. 6.3.2). У сувязі з гэтым вылучаліся розныя прапановы, і ў прыватнасці прапаноўвалася прыніжаць патрабаваную дакладнасць выканання абмежаванняў. Праўда, апошняе азначае пересмсгтр прынцыповых пазіцый і пераход у клас метадаў спраектаванага лагранжиана (гл. Разд. 6.5). Агульны агляд метадаў тыпу прыведзеных шматспынавыя некаторымі меркаваннямі адносна іх сувязяў з метадамі спраектаванага лагранжиана чытач знойдзе ў артыкуле Сарджэнт (1974),
6.4. МЕТАДЫ мадыфікавалі ФУНКЦЫЙ Лагранжа
Да класа метадаў мадыфікаваных функцый Лагранжа можцо ісці рознымі шляхамі. Аднак канчатковую мэту заўсёды фармулююць аднолькава: звесці пошук рашэння задач NEP або NIP да минимиза-
цыі без абмежаванняў, прычым дапаможную функцыю падабраць так, каб (i) не было непазбежнай дрэнны абумоўленасці (як у метадах гладкіх штрафных і бар'ерных функцый з разд. 6.2,1) і (ii) Ф мела бесперапынныя першыя вытворныя (у адрозненне ад негладкой штрафных функцый нз разд. 6.2.2).
6.4.1. ВЫЗНАЧЭННЕ мадыфікавалі ФУНКЦЫІ Лагранжа
Метады, якія мы будзем разглядаць тут і ў разд. 6.5, будуць атрыманы з разгледжаных раней умоў аптымальнасці (гл. Разд. 3.4) і істотна выкарыстоўваюць множнікі Лагранжа, а дакладней НХ ацэнкі. Спачатку выкладзем асноўныя ідэі, не спыняючыся на дэталях рэалізацыі. Падрабязнае апісанне спосабаў ацэньвання множнікаў ў задачах з нелінейнымі абмежаваннямі будзе дадзена ў разд. 6.6.
Метады мадыфікаваных функцый Лагранжа можна выкарыстоўваць і для задач з роўнасці, і для задач з няроўнасць. Прынцып уліку роўнасцяў заўсёды адзін і той жа, а для няроўнасцей магчымыя варыянты. Звычайна выкарыстоўваецца якая-небудзь стратэгія прагназавання актыўнага набору, і тады ў пачатку кожнага цыклу безумоўнай мінімізацыі па няма каму правілу вызначаецца, якія абмежаванні ўвойдуць у з "(гл. Разд. 6.5.5). Іншыя схемы ўліку няроўнасцей ў метадах мадыфікаваных функцый Лагранжа абмяркоўваюцца ў заўвагах. Пакуль жа дзеля прастаты выкладу выкажам здагадку, што загадзя вядомы правільны спіс актыўных у х * абмежаванняў, і праз з {х) будзем пазначаць вектар, складзены з іх функцый.
У далейшым лічыцца, што ў шуканай кропцы х * выкананы дастатковыя ўмовы аптымальнасці нз разд. 3.4, у прыватнасці
g {x) = A {xfX.
(6.22)
Тут А-матрыца, чые t радкоў ўяўляюць сабой градыенты актыўных у X * абмежаванняў. Калі Л (х *) мае поўны ранг, вектар X "вызначаецца роўнасцю (6.22) адназначна. Увядзем функцыю Лагранжа
L {x, Ц = Р {х) - 1с {х).
(6.23)
(Заўважце, што вызначэнне (6.23) залежыць ад таго, як фармуецца вектар с.) Суадносіны (6.22) азначае, што пры К = да * х * будзе яе стацыянарнай (па х) кропкай. Калі б гэтая стацыянарнай азначала экстрэмальнасць, функцыю Лагранжа можна было б выкарыстоўваць у якасці Ф. Аднак увогуле выпадку х * не дастаўляе мінімуму L {x, X *) (гл. Другі фрагмент мал. 6Ь). Значыць, нават маючы X *, разлічваць на тое, што X * ўдасца знайсці безумоўнай мінімізацыяй функцыі Лагранжа, нельга.
гл. 6. Задачы з нелінейнымі абмежаваннямі
Абазначым праз Wix.k) матрыцу другое вытворных па х ад L {x, X), т. Е.
W (x, X) cw-XM, w. i = i
у tt (x *, X *) могуць быць і адмоўныя, і нулявыя ўласныя значэння, але спраектаваную матрыцу Гесэ (х ") W (х", X *) Z (х) у сілу сказанага раней мы лічым станоўча оп-редетеннок ( праз Z (х) прынята пазначаць матрыцу, слупкі якой фармуюць базіс прасторы вектараў, артаганальных радках А (х)). Такім чынам, х * будзе кропкай мінімуму L (х, X) па X на разнастайнасці, орпюгональном градыент актыўных у х * абмежаванняў.
Азначанае ўласцівасць аптымальнасці х * азначае, што прыдатную функцыю Фу можна атрымаць, дадаўшы да лагранжиану складнік, якое, не парушыўшы стацыянарнага х *, зменіць ўласцівасці матрыцы Гесэ адносна вектараў з подпространство, нацягнутага на слупкі А (x »). Часцей за ўсё ў якасці такой папраўкі выкарыстоўваюць квадратычнай штраф, атрымліваючы тым самым мадыфікаваную функцыю Лагранжа выгляду
L (x. I, p) F (x) - kc (x) -i {xfc {x). (6.24)
Тут р-станоўчы параметр штрафу.
У кропцы X * і сам квадратычнай штраф, і яго градыент звяртаюцца ў нуль (паколькі з складаецца з функцый актыўных у X абмежаванняў). Такім чынам, ПРВ Х = К * кропка х * з'яўляецца стацыянарнай (па х) для (6.24). Матрыца Гесэ штрафнога тэрма роўная Ci (x) G, {x) -iA {xy А {х). Пры х = х * ненулявога ў гэтым
выразе будзе толькі другое складнік А {Хуа (х). Гэта-станоўча полуопределенная матрыца, прычым ўсе яе ўласныя значэння, якія адказваюць уласным вектарах нз ранг-прасторы A (xY, большай за нуль. Значыць, папраўка да функцыі Лагранжа ў (6.24) прыводзіць да павелічэння (магчыма, адмоўных) уласных значэнняў матрыцы W для вектараў з ранг-прасторы А (xV, у той час як ўласцівасці матрыцы Гесэ ў дачыненні да вектараў, артаганальных А {xY, захоўваюцца. Няцяжка даказаць існаванне канчатковага значэння р, такога, што для любога р> р матрыца Гесэ V}., i (х *, Х- *, р) будзе станоўча вызначаная і СОО тветственно ў л * рэалізуецца моцны лакальны мінімум Lix, X *, р). Пры гэтым незалежна ад р для любой матрыцы Z (х *), артаганальнай радках Л (х *), справядліва роўнасць
Z (x) VLL>, p) Z (x) = Z (x «) W {х; i.) Z {x).
6.4. Метады мадыфікаванне функцый Лагранжа
т. е. на спраектаваную матрыцу Гесэ штрафная дадатак не ўплывае.
Праілюструем эфект апісанай мадыфікацыі функцыі Лагранжа іа простым прыкладзе.
Прыклад 6.4. Разгледзім аднамерную задачу
знайсці minx
пры абмежаванні х -) - 1 = 0.
Яе адзінай дапушчальнай і, такім чынам, аптымальнай кропкай з'яўляецца х * = - 1, прычым>. * = 3. Такім чынам,
L (x,?. *) = X »-3 (х - 1).
Гэтая функцыя ў х мае лакальны максімум. У той жа час пры любым р> р (р = 6) мадыфікаваная функцыя Лагранжа
La (X, Х>, р) = х-3 (х + 1) (х-1- 1) "
ў X * дасягае лакальнага мінімуму. Графікі для х і L (x,?. *) Намаляваныя на мал. 6h суцэльны і нунктирнон лініямі. Модифи-
Мал. eh. Суцэльная лінія - графік мэтавай функцыі иэ прыкладу 6.4, f (х) -х; пункцірнай - графік функцыі Лагранжа; штрыхавыя - графік молифициро-ваннай функцыі Лагранжа Lix, л, 9).
цированная функцыя Лагранжа з р = 9 паказаная штрыхавой лініяй. Адзначым, што оиа не абмежавана знізу пры любым значэнні параметру штрафу р.
6.4.2. СХЕМ.А алгарытмаў з мадыфікаванымі функцыю Лагранжа
Са сказанага ў разд. 6.4.1 вынікае, што ў ідэальным выпадку X * можна знайсці аднаразовай безумоўнай мінімізацыяй гладкай функцыі (6,24). Аднак гэты выпадак практычнага цікавасці не ўяўляе, паколькі мяркуе веданне вектара X *, а, не маючы рашэння х *, яго вылічыць нельга. У рэальнай сітуацыі замест сапраўдных множнікаў Лагранжа выкарыстоўваюцца іх ацэнкі. Цэнтральная роля, якую яны граюць у метадах мадыфікаваных функцый Лагранжа, тлумачыць, чаму гэтыя метады часта называюць таксама MetnoikiMU множнікаў.
Вядома некалькі спосабаў прымянення функцый тыпу (6.24) для пошуку ўмоўнага мінімуму. Адзіныя яны ў тым, што заўсёды ўзнікае п-мерная подзадача безумоўнай мінімізацыі духавых станаў, якая мае ў якасці параметраў ацэнкі множнікаў Лагранжа і якую ўваходзяць штраф, прызначэнне якога ператварыць х * з безумоўна стацыянарнай кропкі ў безумоўна опт1шальную.
6.4.2.1. Мадэльная схема. У дадзеным раздзеле схематычна апісаны адзін са спосабаў пошуку мінімуму пры ограниченияч-няроўны-ствах з выкарыстаннем мадыфікаванай функцыі Лагранжа. Ён мяркуе заданне пачатковага спісу ўключаюцца ў з абмежаванняў, пачатковай ацэнкі вектара множнікаў Лагранжа Л », пачатковага набліжэння Хо, пачатковага значэння параметру штрафу і станоўчага цэлага ліку Да, якое паслужыць верхняй мяжой колькасці ітэрацый. Вызначыўшы усё гэта і зрабіўшы прысваенне А - * - 0, трэба выканаць наступныя дзеянні.
Алгарытм AL (Мадэль метаду мадыфікаванай функцыі Лагранжа)
ALI. [Праверка выканання правілаў супыну.] Калі х задавальняе умовам аптымальнасці або А> / З, вылічэнні спыніць. У першым выпадку Xj бярэцца ў якасці иско-. мого рашэння; у другім выдаецца прыкмета няўдачы.
AL2. [Мінімізацыя мадыфікаванай функцыі Лагранжа.] Выкарыстаўшы Xj ў якасці пачатковай кропкі, прымяніць працэдуру вырашэння подзадачи
(6.25)
якая прадугледжвае магчымасць неабмежаванасці Lj знізу. Лепшае нз знойдзеных ёю набліжэнняў ўзяць у якасці Xfi + i.
AL3. [Пералік адзнак множнікаў Лагранжа.] Калі гэта дарэчы, змяніць склад с. Вылічыць новы вектар адзнак множнікаў Лагранжа X + j.
знайсці minL (x, Xj, р).
AL4. [Павелічэнне, калі гэта неабходна, параметру штрафу.] Калі ў кропцы х +, невнзки абмежаванняў: идачп істотна менш, чым у х ,, перайсці да наступнага кроку, а інакш павялічыць р.
AL5. [Пераклад лічыльніка ітэрацый.] Зрабіць прысваенне ft. і вярнуцца да кроку AL1.
6.4.2.2. Ўласцівасці мадыфікаванай функцыі Лагранжа. Мяркуючы испапьзовать якой-небудзь метад з мадыфікаванай функцыяй Лагранжа 1л, трэба мець на ўвазе наступныя акалічнасці.
- * - 1-1
Лакальнага мінімуму. Як і для штрафных функцый, апісалі-иых ў разд, 6.2 (у адсутнасць у зыходнай задачы спецыяльных уласцівасцяў), у пункце х * у лепшым выпадку рэалізуецца толькі лакальны мінімум La- Пры гэтым La можа быць не абмежаванай знізу для любога значэння параметру штрафу р . Такім чынам, ужываючы да подзадаче (6.25) стандартны алгарытм безумоўнай мінімізацыі, трэба прадугледзець у ім адпаведныя меры засцярогі (на што і паказана ў п. AL2 мадэльнай схемы). Звычайна павелічэннем р у рэшце рэшт атрымоўваецца атрымаць настолькі шырокую вобласць прыцягнення л: *, што неабмежаваных 1. становіцца неопасной. Аднак поўных гарантый збежнасці да х * увогуле выпадку даць нельга.
Цяжкасці выбару параметру штрафу. Падабраць падыходны параметр р часам бывае няпроста нават у такіх сітуацыях, калі праблема неабмежаванасці знізу мадыфікаванай функцыі Лагранжа не ўзнікае. Справа ў тым, што сярод значэнняў р. обеспе-чивающих існаванне ў х * лакальнага безумоўнага мінімуму La, нароўні са «занадта вялікімі» звычайна ёсць і «занадта малыя». , І тыя і іншыя даюць дрэнна абумоўленыя La. Пры завышаных р функцыя La становіцца дрэнна абумоўленай па тых жа прычынах, што і гладкія штрафныя функцыі. Прычынай дрэннай обус.1; оБлеино-насці La пры заніжаных р з'яўляецца звод яе матрыцы Гесэ (еслн матрыца Гесэ звычайнай функцыі Лагранжа знаконеопределеиа) пры мінімальным дапушчальным р.
На мал. 61 намаляваныя лініі ўзроўню La (х, р) пры трох значэннях параметру р для задачы з прыкладу 6.2, абмежаванне якой трактуецца як роўнасць. Другая функцыя (рО.2) обуслсшлена добра. Першая (р = 0.075) і трэцяя (р = 100) ілюструюць наступствы выбару занадта малых і занадта вялікіх р.
Крытычная ролю адзнак множнікаў Лагранжа. Паколькі xf будзе кропкай мінімуму мадыфікаванай функцыі Лагранжа толькі калі для збежнасці які выкарыстоўвае яе л1етода пры огра-
ниченном р неабходна забяспечыць збежнасць генераваных адзнак множнікаў да X *.
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ] [ 17 ] [ 18 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ] [ 26 ] [ 27 ] [ 28 ] [ 29 ] [ 30 ] [ 31 ] [ 32 ] [ 33 ] [ 34 ] [ 35 ] [ 36 ] [ 37 ] [ 38 ] [ 39 ] [ 40 ] [ 41 ] [ 42 ] [ 43 ] [ 44 ] [ 45 ] [ 46 ] [ 47 ] [ 48 ] [ 49 ] [50] [ 51 ] [ 52 ] [ 53 ] [ 54 ] [ 55 ] [ 56 ] [ 57 ] [ 58 ] [ 59 ] [ 60 ] [ 61 ] [ 62 ] [ 63 ] [ 64 ] [ 65 ] [ 66 ] [ 67 ] [ 68 ] [ 69 ] [ 70 ] [ 71 ] [ 72 ] [ 73 ] [ 74 ] [ 75 ] [ 76 ] [ 77 ] [ 78 ] [ 79 ] [ 80 ] [ 81 ] [ 82 ] [ 83 ]
0.0014
X,?