XIV Аттетков и др. Методы оптимизации (1081420), страница 58
Текст из файла (страница 58)
Наименьшего зна сепия на допустимом множе- /36 245 стве целевая функция 16(х) достигает в точке х' = ( —, — )— (,37' 31) 6882 (1,1290, 0,7742), при этом Д(х*) = — — 7.,1613 (см. пример 8.9). Для приближения к точке х* с заданной точностью ел потребуется еще довольно много итераций. фСлучай линейных ограничений. Остановимся на частном случае, когда в задаче оптимизации допустимое множество Й задано при помощи линейных ограничений д,(х) = (аб х) < йо г = 1, пк В этом случае задачу поиска возможного направления спуска можно упростить, видоизменив следующим образом.
На каждой Й-й итерации вектор р Е лс", определяющий это направление, можно искать из условия минимума функции ~ь(р) = = (8гас1 Я(х~ '), р) на множестве Й7ь = (р Е Жв: (сс, р) < О, 1 Е Ху,, !р ! < 1, 7' = 1, и ), (8.77) где Хь — по-прежнему множество индексов, соответствующих активным ограничениям в точке хя 61с.
Можно показать*, Смэ Бизари М., Шэпипи К. 403 8. 7. Метод ноэхсожных нан равнений *сто если минимальное значение функции ~ь(р) на множестве И~а равно нулю, то точка х" ' удовлетворяет необходимому условию минимума целевой функции Ях) на множестве й. Пример 8.12. Вернемся к задаче из примера 8.11 и решим ее, выбирая возможное направление спуска путем минимизации функции ~ь(р) на множестве (8.77). Отметим, что теперь пс = = 8гас1 д;(х), г = 1, 4, причем 6с = 2, 62 = 5, 68 = 64 = О.
Нетрудно установить, что результат выполнения первой итерации останется прежним. В самом деле, если выбрать начальную точку хо = (О. О), то получим ~с (р) = (8гас1 /о(хо), р) = = — 4рс — брз, а множество И~1 будет задано неравенствами — р1 < О, — рз < О, ~рс~ < 1 и ~рз! < 1. Отсюда находим минимальное значение Др ) = — 10 при р = (1 1) и затем точку х' = хо + терс = (5/6, 5/6) (см. рис. 8.16). На второй итерации в точке х~ = (5/6, 5/6) имеем ~2(р) = = (8гас1Ях1), р) = — 7р1/3 — 13рз/3. Эту функцию необходимо минимизировать на множестве И~з, заданном неравенствами рс+5рз < О, ~рг! <1, )р2( <1, (8.78) поскольку в точке х активно лишь ограничение с индексом 1 = = 2. Множество И~2 ограничено трапецией АВСР (рис. 8.17), а линиями уровня функции ~2(р) являются прямые, параллельные прямой 7р1 + 13рз = 0 (прямая с,з = 0 на рис.
8.17), на которой зта функция имеет нулевое значение. Из геометрических соображений ясно, что функция (2(р) принимает на множестве 22 гк Рис. 8лт 404 8. ЧИСЛЕННЫЕ' МЕТОДЫ И12 наименьшее значение в точке р = (1 — 1/5) и это значение равно — 22 1 15. При движении точки х = х + жр в направлении вектора р ограничение дг(х) < О, оставаясь активным, не нарушается. Поэтому необходимо убедиться в выполнении ограничений д1(х) < 0 и д4(х) < О. Это означает выполнение условий д1(х) =х1 +ар1 +хг +жрг 2 — — — ж — — <О, 00 12) (0 60 4 1 5 3 да(х) = — хг — хрг — — х — —, < О.
11) (г) 5 6 Отсюда заключаем, что мг = 5/12. Поскольку г 62 г 22 125 Фг(к) = Ых +кр ) =— 25 15 8 функция д12(х) достигает наименьшего значения на отрезке (О, хг) = (О, 5/12) при ~с = —. Следовательно, мг = — и х 55 55 г В точке хг по-прежнему активно лишь ограничение с индексом 1 = 2. В этой точке в соответствии с (8.74) 8гас17е(хг) = =( ) 32 050 1 — — — — Поэтому на третьей итерации необходимо 51 51,) ' минимизировать функцию 32 160 Сз(р) = Ьг 67е(х'), р) = — —,р — р 31 31 на множестве Игз = Игг, заданном теми жс неравенствами (8.78). Линии уровня функции ~з(р) -- прямые., параллельные прямой р1+ 5рг = О, на которой функция принимает нулевое значение. По прямая р1 + 5рг = 0 проходит по стороне 0С трапеции, ограничивающей множество Игз (см.
рис, 8.17). Значения функции в точках трапеции, не лежащих на стороне ВС, положительны. Таким образом, минимальное значение функции ~з(р) равно 405 8. 7. Метод вовх~ожных направлений 7Зо 2д~ нулю. Поэтому точка х* = х = ~ —, — ) удовлетворяет не~З1' З1) обходимому условию минимума функции ~а(х) на допустимом множестве. А так как функция Ях) является выпуклой и допустимое множество Й является выпуклым, то в точке х* функция 1о(х) Достигает наименьшего значениЯ на множестве Й. ф Случай нелинейных ограничений. На практике при наличии нелинейных ограничений обычно применяют несколько модифицированные варианты метода возможных направлений.
Дело в том, что при малых значениях ~дь~ направление спуска, задаваемое вектором р ', который находят из решения задачи линейного программирования (8.70), хотя и является допустимым с теоретической точки зрения, может быть неприемлемым с практической точки зрения,так как оно может оказаться почти ортогональным направлению антиерадиента шь = — 8гае1Ях~ 1) целевой функции. При близких к нулка значениях (дп, р ) направление спуска р почти „касается" границы дй множества Й. Поэтому значения лев в (8.71), а следовательно и значения хь, будут весьма малыми, а сходимость процесса поиска минимума очень медленной. Более того, возможно, зацикливание" алгоритма или же сходимость последовательности 1х ) к такой точке х Е Й, в которой не выполнены необходимые условия минимума*.
Один из способов ускорения сходимости метода возможных направлений заключается в том, чтобы при выборе возможного направления спуска учитывать все ограничения, а не только активные в точке х~ . Для этого направление спуска р на и-й итерации находят как решение задачи минимизации г1 — ~ пшд 18 био( ' '),р) <д; д,(х" ') + (дгас1д,(х '), р) < Яц, г' = 1,т: ~р,~ < 1, 2 = 1,п, Сыа Полах Э. 4об 8.
ЧИСЛЕЕШЪ|Е МЕТОДЪ| где ~3, > Π— некоторые весовые коэффициенты. Так как в задании допустимого множества Й~ь этой задачи оптимизации участвуют все ограничения типа неравенства исходной задачи., то направление спуска не испытывает резких изменений, когда от итерации к итерации изменяется множество индексов активных ограничений.
Это позволяет избежать зигзагообразной траектории поиска точки х* и уменьшает опасность „зацикливания" алгоритма. Можно показать*,что и для этой модификации метода возможных направлений равенство пь = О равносильно выполнению в точке х~ ~ необходимого условия минимума целевой функции на множестве Й. 11едостаток описанной модификации метода возможных направлений состоит в том, .что задача линейного программирования, на основе которой определяется направление спуска, усложняется, так как в нее включаются все т ограничений. Существует промежуточная модификация метода, в которой учитываются лишь так называемые с-активные ограничения в окрестности точки х, т.е.
такие ограничения, для которых в точке х" ' выполняется неравенство — сь < д,(х~ ') < О. В этой модификации вместо множества индексов Хь используют множество Хь*. — — (|Е (1, ..., т): — сь <д,(х~ ~) < О). (8.79) Значение сь > О следует выбирать так, чтобы оно было существенно больше значения ся. Оно может меняться от итерации к итерации, но можно также считать, что сь = св = сопв$. Множество Х* включает в себя множество Хю но при этом с помощью выбора подходящего значения сь число с-активных ограничений можно заметно уменыпить по сравнению с общим числом ограничений. Поясним смысл введения с-активных ограничений на примере минимизации целевой функции Ях) двух переменных при трех ограничениях д;(х) < О, 1 = 1, 2,3 (рис.
8.18, а). Пусть в Сми Мину М. 407 8.7. Метод воэыожныл направлений Ях1= еопя$ Рис. 8.18 точке х Е Й активно лишь пеРвое огРаничение, т.е. Ха = 1Ц. Тогда из решения задачи линейного программирования (8.70) получим направление спуска, задаваемое вектором р и являющееся промежуточным между направлениями в точке х антиградиентов тяо = — 8гэт1уо(х~ ') и ю", = — 8гае1д1(х~ ) целевой функции и функции д1(х) соответственно. Но выбор значения тер„.
в (8.71) будет существенно ограничен, так как это направление спуска пересекает границу множества Й, определяемую ограничением с индексом т = 2, на малом расстоянии от точки хь 1. Если же учесть е-активные в этой точке ограничения (рис. 8.18, б), то будем иметь ьА*, — — 11, 2). Тогда решением задачи (8.70), в которой Ха заменено на Х~ и учтено влияние антиградиента ш~~ — — — 8гае1дз(х" ), можно получить вектор р '. задающий более удачное направление спуска. Это направление позволяет на й-й итерации сделать более длинный шаг на пути к точке х* минимума целевой функции на множестве Й. В общем случае решение х~ = (р~, щ.„.) задачи линейного программирования (8.70), в которой множество индексов Хь заменено множеством Ха, будет удовлетворять одному из двух Условий: пе < — еа или — ел < дя < О.
Если выполнено пеРвое условие, считают, что соответствующий значению т1ь вектор р~ задает достаточно удачное направление спуска,и этот век- 408 8. ЧИСЛЕННЫЕ МЕХОДЪ| тор используют для нахождения очередной точки в". Если же выполнено второе условие, то полагают, что найденное направление спуска неудачно, и ищут другое направление спуска, уменыпая в (8.79), например вдвое, значение ея. Уменыпение еь приводит, вообще говоря, к сужению множества индексов Х~*,, в результате чего во вспомогательной задаче линейного программирования часть ограничений снимается, а допустимое множество расширяется. Поэтому можно ожидать, что на более широком множестве И~я можно найти более удав ное направление спуска, которое будет удовлетворять первому условию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
