XIV Аттетков и др. Методы оптимизации (1081420), страница 50
Текст из файла (страница 50)
Матрицу Якоби целевой функции в некоторой точке хо Е й представим в виде блочной матрицы-строки (дВ д~ ), где дн и д матрицы-строки длины т и и — т. Элементами этих Х матриц-строк являются частные производные —,, з = 1, и, по ого дх, базисным и свободным переменным соответственно (дн и дм называют матрицами Якоби функции ?0(х) по части переменных). Тогда, используя (8.9), .для полного дифференциала целевой функции получаем е()0(хО) (8гас?(0(хО) дх) дндхн+дкд = — д Хдх +д дх =(дм — д ?з')дх~ =идх~, (8.10) где и =д — д Х -. матрица-строка длины и — т, называемая приведенным ерадиентпом целевой функции Д(х) относительно свободных переменных в точке хв Е ??.
Возможны разные стратегии поиска точки минимума в задаче оптимизации с линейными ограничениями, основанного на использовании приведенного градиента. Простейшая из них базируется на методе покоординатного спуска в пространстве свободных переменных.
Последовательный перебор этих пере- 848 8. ИИСЛЕЕШБ1К МЕТОДЪ| — и, <О; РУ= 00 — и,:г, и > О,. (8.11) Чтобы при движении точки к=а +нр, н>0, (8.12) менных проводят по тем же правилам, что и при решении задачи линейного программирования симплекс-методом, а метод, основанный на этой стратегии, называют выпуклым симплекс-методом. Рассмотрим другую стратегию поиска точки минимума с использованием приведенного градиента.
На каждой итерации процесса минимизации будем изменять все свободные переменные. Метод, основанный на подобной стратегии, называют методом приведенноео врадиента. Из (8.10) следует, что значение целевой функции быстрее всего уменьшается при изменении свободных переменных в направлении, противоположном приведенному градиенту. Но при этом может быть нарушено условие их неотрицательности. Чтобы этого избежать, приведенный градиент можно спроектировать на неотрицательный ортант й„" '™ допустимое множество для этих переменных. Поскольку К", ~ является достаточно простым по структуре множеством, проектирование на него выполнить несложно.
Это позволяет сформировать возможное направление спуска,. т.е. найти координаты р, у Е,7, вектора р Е Р', определяющего это направление. При и, < О, у Е,У~, увеличение свободного переменного ж в окрестности рассматриваемой точки х Е й приведет к уменьшению значения целевой функции. Поэтому для этого индекса принимаем р: = — и .
Если же и > О, з Е У~, то увеличение свободного переменного х в окрестности рассматриваемой точки может привести к ее возрастанию. В этом случае положим ,(о) р~ — — — и и . Таким образом, для координат вектора р Е Б'.", соответствующих свободным переменным и составляющих вектор рк Е К" ~, имеем 8.2. Иеполваование приведенного градиента 349 в направлении, которое задано вектором р б К", не были нарушены ограничения Ат = Ь, определяющие допустимое множество Й вида (8.8), необходимо, чтобы выполнялось условие Ах = Ахо + х(В К)р = Ь, или Ври = — басри поскольку Ашо = = Ь. Отсюда находим вектор (8.13) с координатами р, ) Е .с = с ~,7 (здесь,У = 11, ..., и)), соответствующими базисным переменным.
Значение ас в (8.12) выбираем, минимизируя функцию ср1тс) = 1о1.во+ аер), те > О, но при выполнении условия а Е К",, приводящего с учетом (8.12) для всех 2 6,7 к соотношениям О < л = х + асрз где х. и со) со) тт. — координаты точек х и ж~ соответственно. Отсюда, если множество Х* = 12 е,Х: р < 01 не пусто, получаем ограничение на максимально возможное значение тс в виде со) ас < ас = шш 1ет с р с (8.14) Ь(х, Л,ссе) = Д(ж)+ (Л, Аж — Ь) — (р, ж), где Л Е К™ и 1а Е 11" - векторы множителей Лагранжа, соответствуя>щие ограничениям Аа — Ь = О типа равенства и — а < О типа неравенства (последнее неравенство означает, что — т.
< О для всех 2 = 1, и, т.е. х Е К", ). Согласно теореме 7.6 и замечанию 4.1, если ш* Е Й --- стационарная точка этой функции, то существуют такие координаты Л, г = 1, т, и д, > О, с = 1, и, Если же Х' = О, то допустимо значение те Е (О, .+со). Покажем, что если в некоторой точке ж' Е Й выполнено равенство ра = О, то это равносильно выполнения> необходимого условия того, что ш* Е Й .—.
точка минимума функции уо1.в) на множестве Й. Для рассматриваемой задачи оптимизации запишем функцию Лагранжа 350 8. численные а|ехОды векторов Л и р соответственно, что справедливы равенства ягабЦх',Л,|л) =8гао|о(в')+А Л вЂ” р=О, (р,~") =О. (8.15) Эти равенства при рн = 0 будут выполнены, если положить Л = — д В ', и =(|лв ||'), |ли=О,,иж=и.
В самом деле, в соответствии с (8.11) из равенства рк = 0 следует и >О для всех| 6,7ь, откуда р >О, д =1, п. Наоборот, в тех случаях, когдаи >О, для всех| Е,У имеемр:= — и;я*= = — р,х* = О. Так как ||в = О, то р т| — — 0 для всех | 6,7 т.е. второе равенство (8.15) справедливо. С учетом выражений для Л и р~, а также равенств В 'В =1, В 'Х = Х и и = = до — двХ получаем для матрицы Якоби целевой функции в стационарной точке х* Е Й тождество (8гас1 Я(х*)) = (д д ) =д (1,„Х) + (О д — д Я) = =д В ~(В Д|)+(О и)= — Л А+у . Следовательно, рн = О равносильно выполнению обоих равенств (8.15).
Это позволяет построить алгоритм поиска точки а' Е Й минимума целевой функции |о(т) на множестве Й с использованием приведенного градиента. На начальном этапе задаем параметр сз > 0 тонности поиска, полагаем к = 1, выбираем начальную точку х~ ' = х Е Й, формируем множества ,7,, и,7~ индексов (например, располагаем координаты точки хв в порядке убывания и выбираем из них в качестве базисных переменных ш первых'), а затем записываем матрицу А в блочном виде А = (Вя Д|я). Вычисляем матрицу В„" и переходим к основной части этого алгоритма.
1. На |с-й итерации находим матрицу Хя = В ' Д|в и в точке ак ' е Й вычисляем матрицы Якоби д~ь и д~~ целевой функции по части переменных с элементами " при |' Е,7, и дс, я Смэ Рскляйтис Г., Ряйвнндран А., Рэясдея Л. 351 8.2. ИСпОльЗОваниЕ припвдвннпго градиЕнта з е „зй' соответственно, а затем — приведенный градиент и й = дйь — дйнЯй. По формулам — и (йз и.' <О; (й'з и. >О, (й) (й) З е,'з'й, 18.16) (й) (й-з ) — и х 18.17) 1в случае Хй* = Я значение Яй можно принять сколь угодно большим) и, минимизируя в полуинтервале 10, згй1 функцию Рй1зг) = Яхй 1+ згр ), находим значение згй Е 10, згй1 и новую точку хй = хй '+ згйрй е 11.
Если згй = згй, то переходим к п.3. В противном случае полагаем й: = й+ 1 и возвращаемся к и. 1. (й) 3. Устанавливаем индекс з е,'з', для которого — х~й з);/р, = згй. Таких индексов может быть несколько. Если все они принадлежат множеству,7й~, то полагаем Й; = Й+ 1 и возвращаемся к п.1. В противном случае равно нулю хотя бы одно (й) базисное переменное х;, з, е,з н, и мы переходим к и. 4. 4. Индекс г е,зй 1если их несколько, то один из них) переводим из множества,7й в множество,7й~, заменяя индексом 1 е,за наибольшего по значению свободного переменного хь Для новых множеств индексов,ф~ и,7йз' разделяем матрицу А на блоки Вй и Хй, вычисляем обратную матрицу В ', используя рекуррентные соотношения, связывающие ее с прежней обратной матрицей 1см.
Д.8.1), и, полагая й: = й+ 1, переходим к и. 1. аналогичным 18.11), находим координаты вектора р~~, е Б'." Если ~р~у~ < ез, то итерации прекращаем, полагая х* хй ' и Д(х*) — Ях~ 1). В противном случае переходим к и.2. 2. ИспользУЯ 18.13), вычислЯем вектоР Рйн —— — ХйРйу Е К™ и фоРмиРУем вектоР Рй = '11Рййв) (Р~) ), опРеделЯющий возможное направление спуска из точки хй '. Формируем множество л.й — — (2 6,7: р < О) и вычисляем значение 352 3. ЧИСЛЕЕШЪ|Е МЕХОДЪ| Если в течение нескольких итераций состав базисных переменных не изменяется., то это означает., что достигнута достаточно близкая окрестность искомой точки х* Е Й, причем в отличие от задачи линейного программирования х* может быть и внутренней точкой множества Й.
В этом случае для ускорения сходимости можно применить спуск по сопряженным направлениям в пространстве Б'." ~ свободных переменных'. Пример 8.2. Минимизируем функцию |с(хм из,хз) = хз1— — 2х|хз+х~~+хз зпРи огРаничениЯх х1+ 2хз+ха = 3 и х ) О, 1 = 1, 3. Сначала используем модифицированный алгоритм метода приведенного градиента, выполняя спуск по сопряженным направлениям в двумерном пространстве свободных переменных.
Представим целевую функцию в виде Ях) = — Ях., х), где 1 2 |д= — 2 2 0 неотрицатсльно определенная матрица. Примем сз = 0,1 и выберем удовлетворяющую ограничениям начальную точку х" = = 11, 1/2, 1) и х| в качестве базисного переменного, т.е. |,Н = = (1),,71~ = (2, 3), В1 = 1, Х1 = (2 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
