Ф.П. Васильев - Методы оптимизации (1125241), страница 70
Текст из файла (страница 70)
Решить задачи геометрического программирования: а) д(х) = с>х'> + сзт ч -> !п( при х > О, где с! > О, а! > 0 — заданные числа; б) д(т, у) = т !у+ 2тзр+Зх >у з->1п1 при т >О, у>0; в)д(х,вз)=4т р з +ху+4хз+2рз->!а!при т>0, у>О,х>0; г) д(т у) = у -> >п1 п]>и т > О, у > О, хзу 4 + х ! р ! >з < 1; д) д(туз)=т+ д з ! — >!и! прил>0, у>0, л>О, х у+х я<1.
5. Найти решение задачи: 70>)=-т — у — >!п(, н=(т, у) еХ=(не Ез; д(м)=ха+уз — 2<0) и двойственной к ней задачи. Убедиться, что здесь множество Л из (80) выпукло и открыто. В. Показать, что двойственная задача к задаче нз примера 5 является задачей линейного программирования, и решить ее. 7. Доказать, чта выпуклая квадратичная функции 7(х) = — (Сх, т)+ (с, т) либо достигает 1 своей нижней грани на Е", либо не ограничена снизу [84]. 3. пусть гго — выпуклое множество из е", функции д>(и),..., д„,(м) выпуклы на Ц>, дг(н) = (а„м) — Ьг, ! = гп+ 1,..., з. Доказать, что если система нера™венств д(о) < О, ! = = 1,, т, д,.
(н) = О, т = >и + 1,..., з, ие имеет РешениЯ на (го, то сУществУют числа л ! ) О, ..., Л >О, Лю >,..., Л, такие, что Л>д>(н)+...+ Л,д (о) >0 при всех и с Гуа. Ук™а ванне: построить множества, аналогичные множествам А и В из доказательства теоремы 2, и применить к ним теорему отделимости 5.2.
В. Пользуясь теоремой Фаркаша, доказать, что для иесовместности системы линейных нера- венств (е„х) < м, ! = О,..., и>, необходимо и достаточно, чтобы существовали такие числа Ло)0, Л>>0,..., Л >О, что Лаео+Л>е>+... +Л е =О, Лоуа+Л>м>+... +Лхм < 0 [752]. 10. Доказать, что два непУстых многогРанных множества А = (т Е Еоп (е„х) < Рг, ! = = О,..., й ) и В = (т е е Гч (е„х) < мч т = ь -1- 1,..., и>), ие имеющие общих точек, сильно отделимы. ь ь Указание: РвссмотРеть гипеРплоскость (с, т) =7, где с= ~„Л>ег, т= А,' Лад!, числа Ло,..., Л,„взяты из упражнения 9.
;=о г=о П. Доказать, что если системз линейных неравенств (еа, т) < О, (е>, х) < О,..., (е, т) < 0 несовместна, та существуют такие числа Л! > О,..., Л,„> О, что ео —— -Л! е! —... — Л,„е У к а з а н и е: воспользоваться теаремои Фаркаша. 12. Пусть система (ео, х) <да, (ез, т) <м! ! =1,..., гп, несовместна, а подсистема (е„т) < < мг, ! = 1,..., т, совместна.
Доказать, что тогда существуют числа Л ! > О,..., Л ) 0 такие, что ео — — -Л>е! —... — Л е, Ма+ Л>М>+...+ Л Гг <О [54; 670]. У к а з а н и е: в пространстве переменных (т, $) ЕБ"" ' рассмотреть систему (еа, т)-зло < < О, (ег, х)-тмг < О, т=1,..., и>, (О, х)-з < 0 и воспользоваться утверждением из упражне- ния 11.
13. Рассмотрите задачу (1), (2) при Хо — — (хеЕ'! хмО), 7(х)=х, Х=(х>0: д(т)=та мО] и убедитесь, что функция Лагранжа 5 (х, Л ) = а+ Л т, т ) О, Л > О, этой задачи имеет бесконечно з много седлавых точек (ср. с примером 1), Сформулируйте двойственную задачу. 9 1, ГРАДИЕНТНЪ|Й МЕТОД 235 ГЛАВА 5 Методы минимизации функций многих переменных Выше в гл. 3 был рассмотрен симплекс. метод для решения задач линейного программирования. Перейдем к изложению других методов минимизации функций конечного числа переменных, не предполагая линейности рассматриваемых задач.
К настоящему времени разрабатано и исследовано большое число методов минимизации функций многих переменных. Мы ниже остановимся на некоторых наиболее известных и часто используемых на практике методах минимизации, будет дано краткое описание каждого из рассматриваемых методов, исследованы вопросы сходимасти, обсуждены некоторые вычислительные аспекты атнх методов. При этом мы ограничимся рассмотрением лишь одного-двух основных вариантов излагаемых методов, чтобы ознакомить читателя с основами этих методов, полагая, что знание основ методов облегчит читателю изучение литературы, позволит ему без особога труда понять суть того или иного метода и выбрать подходящии вариант метода или самому разработать более удобные ега модификации, лучше приспособленные для решения интересующего читателя класса задач.
В конце главы будут высказаны некоторые общие замечания по методам минимизации. Из обширной литературы, посвященной методам минимизации функций конечного числа переменных и их приложениям, мы мажем здесь упомянуть лишь весьма незначительную ее часть [1; 13; !6; 18-20; 24-30; 32; ЗЗ; 52; 53; 56; 61; 62; 66; 70; 71; 73; 74; 76-78; 83-85; 89-92; 941 102; 109; 116; 117; 128; 131; !34; 135; 140; !43; 148; 154; 161; 179; 183; 184; 194; 203-205; 214; 2!6; 218; 222; 226; 227; 231; 232; 234; 243; 250-252; 255-257; 259-266; 272; 273; 281; 286; 292; 294-299; 301; 302; 304-309; 314; 316-320; 326; 330; 341-345; 347; 356; 358; 361; 368-370; 372-375; 377; 386-388; 390; 396; 398; 401; 410; 422; 423; 426; 437; 442; 447; 448; 465; 466; 470; 471,' 4811 "491; 493-495; 499; 506; 511; 516-5!8; 520; 521; 523; 525; 527," 539; 541; 542; 548-550; 561-566; 572; 580-582; 586; 590; 591; 601; 603; 606; 608; 610; 612-614; 620; 623; 624; 635; 639; 652; 657; 661; 662,' 670; 671; 675; 676; 678; 681; 684; 686-688; 695; 697; 704; 709-7!1; 713; 718-721; 725; 732; 737; 738; 742; 743-747; 750-752; 759; 760; 765; 769; 774-777; 786; 792; 793; 795; 799; 803; 807; 8!1; 813; 8181.
9 1. 1радиентный метод 1. Будем рассматривать задачу у(х) ч !и[, 'х Е Х: — Я", (1) предполагая, что функция у(х) непрерывно дифференцируема на Е", т. е 7" (х) е С'(Я ), Согласно определению 2.2.1 дифференцируемой функции Х(х+Ь) — Их) =(У(х), Ь)+.(Ь;,), (2) где [пп о(Ь; х)[Ь/ ' =О. Если 7"'(х) ф О, то при достаточно малых [Ь[ главрй а ная часть приращения (2) будет определяться величиной (7'(х), Ь). В силу неравенства Коши — Буняковского -Т(*)!!Ч < (Г(*), Ь) <!Г(*)! !Ч, причем, если у'(х) фО, то правое неравенство превращается в равенство только при Ь = сту'(х), а левое неравенство — только при Ь = — стг'(х), где ст = сопз! > О.
Отсюда ясно, что при У'(х) уй 0 направление наибыстрейшего возрастания функции у(х) в точке х совпадает с направлением градиента 7"'(х), а направление наибыстрейшего убывания — с направлением антиградиента ( — 7"'(х)). Это замечательное свойство градиента лежит в основе ряда итерационных методов минимизации функций, Одним из таких методов является градиентный метод, к описанию которого мы переходим. Этот метод, как и все итерационные методы, предполагает выбор начального приближения— некоторой точки х .
Общих правил выбора точки х в градиентном методе, как, впрочем, и в других методах, к сожалению, нет. В тех случаях, когда из геометрических, физических или каких-либо других соображении может быть получена априорная информация об области расположения точки' (нли точек) минимума, то начальное приближение х стараются выбрать поближе к этой области.
Будем считать, что некоторая начальная точка х уже выбрана. Тогда гРадиентный метод заключаетсЯ в постРоении последовательности Тхь) по правилу х, = х„— гхьу'(хь), гхь > О, Ь =0,1, (3) Число аь из (3) часто называют длиной шага или просто шагом градиентного метода. Если 7"'(х ) фО, то шаг оь > 0 можно выбРать так, чтобы у'(хь„,) < у(хь). В самом деле, из равенства (2) имеем У(хь„) — У(хь) = ь( — Т(хь) ~'+ о(оь)оьу') < О при всех достаточно малых оа > О.
Если у'(хь) = О, то х, — стационарная точка. В этом случае процесс (3) прекращается, и при необходимости проводится дополнительное исследование поведения функции в окрестности точки х для выяснения того, достигается ли в точке хь минимум функции 7'(х) или не достигается, В частности, если 7"(х) — выпуклая функция, то согласно теореме 4.2.3 в стационарной точке всегда достигается минимум.
Существуют различные способы выбора величины ссь в методе (3). В зависимости от способа выбора гхь можно получить различные варианты градиентного метода. Укажем несколько наиболее употребительных на практике способов выбора сть. 1) На луче х= х — сту'(хь), ст > О, направленном по антиградиенту, введем функцию однои переменнои дь(ст) = У'(хь — стг"'(хь)), ст > О, и определим аь из условий д.(аь) гч!п1 дь(ст) =даю ась > О. (4) эо Метод (3), (4) принято называть методом скорейшего спуска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
