|
| |
|
Слаботочка Книги при условиях ipi{xi,..., Хт) О, г=1,...,1, (4) ipi{xi,..., Хт) О, i = l,...,q. (5) При решении этой задачи возникают дополнительные трудности по сравнению с решением задачи отыскания безусловного минимума, в которой иш;ется inf Ф{Х1,...,Хт) (х-1,...,ж )ек,п - нижняя грань Ф(ж1,..., ж г) по всему пространству R ,. Непосредственное использование многих из описанных выше методов становится невозможным, и возникает необходимость в их модификации. В то же время задача минимизации функции при ограничениях типа (4), (5) является весьма актуальной для приложений. Например, суш;е-ствует целый раздел математики - линеймое программирование, - занимающийся решением задачи (3)-(5) в случае, когда Ф, (pi, Vi -линейные функции аргументов Xj. Среди других методов, связанных с решением задачи (3)-(5), упомянем метод штрафа. Строится последовательность функций Фх(хх,...,Хт), удовлетворяющая следующим условиям: 1) Фх{х1,..., Хт) определена при всех {xi,..., Хт), 2) inf Фх{х1,..., Хт) = Ах А при А -> оо; 3) если существуют точки {xi,...,Xm) и {х,...,х) такие, что Ф{х1,Хт) = А, Фх{х, ...,х) = Ах, то (х, Хт) -> (xi, Хт) Щ>Н А -> оо. Вместо решения исходной задачи (3)-(5) решается задача отыскалия минимума inf Фл(а;1,..., а; г) при достаточно больших А. Часто вместо первого условия на функцию Ф> требуют выполнения более слабого условия. Функция Фд опреде :ена в точках некоторой од-носвязной области Gx, Фх{х1, , Хт) ос при приближении точки (ж1,..., Хт) к границе области или при т -Ь -Ь х -> оо (в случае, когда область Gx неограниченная). В отдельных случаях условие 3) также несколько модифицируется. Приведем пример построения такой функции Фд- Для этого соотношения (4), (5) записываются в таком виде, что (pi, ipi будут определены при всех (а;1,...,Жто) (или при всех xi,...,Xm из Gx). Вводится некоторая невозрастающая функция h{i), определенная при -оо < t < оо, такая, что Иш h(t) > О, lim hit) = 0. Например, можно взять hif) =---arctgi. § 4. Другие методы сведения многомерных задач к задачам меньшей размерности Иногда полезно рассмотреть следующую формальную процедуру сведения многомерных задач к одномерным. Пусть ищется минимум А функции Ф{х1,...,Хт) в области ipi{xi,Хт) О, г = 1,..., /, Tpj{xi,..., Хт) =QJ = 1,..., д. Можно написать равенство А = min Ф(жь..., Хт) = ттФт{хт), Xi,...,Xm Хт т{Хт) = min Ф(Ж1, . . . , Хт); Х1,...,Хт-1 Минимум каждый раз берется по области определения минимизируемой функции в соответствии с условиями (1). Таким образом, исходная задача минимизации функции тп переменных свелась к минимизации функции одной переменной, каждое значение которой определяется минимизацией функции (т-1)-й переменной. В свою очередь минимизацию функ-Фгп(.Хт) сведем к минимизации фунции одной переменной, каждое В качестве Фх{х1,..., х) берется функция Ф(Ж1,..., Xs) + XYTpfixi,...., Х г) + XhiXifiixi,..., Хт)). i=l i=l Наличие слагаемого А?(ж1,..., заставляет смещаться точку экстремума (ж,..., жг) в область, где i{xi,..., Хт) = 0; в то время как наличие слагаемого Xh{X(pi{xi,..., х.)) заставляет смещаться точку экстремума (ж,..., Хт) в область, где ,;(Ж1, . . . , Хт) 0. Метод нгтрафа обладает следуюнщм недостатком. Оказьшается, что при больших А структура линий уровня Ф>, как правило, такова, что сходимость методов минимизации существенно замедляется. Искусство применения метода штрафа нри решении конкретных задач состоит в удачном выборе функции Фд такой, что нри заданной близости значений нижней грани Л -Л> замедление скорости сходимости применяемого итерационного метода будет минимальным. В связи с отмеченными недостатками метода штрафа разработано большое число других методов решения задачи условной минимизации (ЗН5). значение которой определяется минимизацией функции от {т - 2)-х переменных, и т.д. Получим цепочку соотношений А = штФ г(.Тт), Фш{Хш) = min Ф 1-1{Хгп-1, х г), Фз(жЗ, . . . , .Т г) := шinФ2(ж2, . . . , Ж, ), Ф2(.т2, . . . , Хщ) = Ш1ПФ1(гс1, . . . , Х г)- Кажуш;ейся простоте метода сопутствует его большая трудоемкость. Предположим, что каждая минимизация функций одцой переменной потребует вычисления s значений минимизируемой функции. Тогда минимизация Фт{хт) требует нахождения min Ф г-1(ж г-1, х Л Хт~1 при S значениях параметра Хщ, т.е. вычислений значений функции Фт-iixm-i, Хт)- Это В СВОЮ очерсдь потробует вычисления значений Фт~2(х т~2-1 Xrti-ii x i) И Т.Д. В конечном счете потребуется вычисление значений функции Ф. Уже при умеренных s и т, например S = 10, ттг = 10, такой объем вычислений окажется недопустимо большим. Однако при малых т некоторые модификации рассматриваемой идеи оказываются полезными. Например, возможен такой вариант. Задаются начальным приближением {xi,..., х). Реализуют указанный алгоритм при не очень большом значении s, например s - 3 или s = 4. При этом значения функции вычисляются в точках некоторого параллелепипеда \хг - х\А. Получаемую точку минимума {х\,..., х},) принимают за следующее приближение; приближение {а;,..., х) находят аналогичным образом, но значения функции Ф вычисляются в точках параллелепипеда \xi - xjl Aj и т.д. Рассмотрим еще один метод, общая структура которого похожа на структуру описанного выше. Если линии уровня функции Ф похожи на сферы, то при применении методов спуска происходит быстрое смещение в направлении минимума (рис. 7.4.1). Однако практически более типичен случай, когда эти линии похожи на эллипсоиды с большим разбросом полуосей. Тогда при движении по градиенту смещение в направлении точки минимума будет довольно медленным (рис. 7.4.2). Предположим, что оси этих эллипсоидов естественным образом разбиваются на две группы: первая группа состоит из тпх осей одного порядка и относительно малых, вторая группа состоит из 777,2 осей одного порядка и относительно больших. При решении некоторых задач такого рода хорошо зарекомендовал себя следуюпщй метод, называемый методом оврагов. Задаются какими-то приближениями х и и производят несколько шагов метода спуска, исходя из каждого из этих приближений. Будут получены прибли- 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 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 [112] 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 |