Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Оптимизация
| Харчистов Б.Ф.. Методы оптимизации, 2004 | |
методы внешней точки |
|
|
Для методов внешней точки штрафные функции должны обладать следующими свойствами: во всех точках допустимого множества X внешние штрафные функции равны нулю; при выходе за пределы допустимого множества X внешние штрафные функции становятся положительными и достаточно быстро возрастают. В качестве внешней штрафной функции часто используется штрафная функция типа квадрата "срезки" Q(R, g (х)) = Rt t{gi (x})2. i=1 Здесь l^gi(x)) - "срезка" функции gi (x), определяемая следующим образом: , , чх fg,(x) если g,(x) > 0, Для того чтобы обеспечить сходимость последовательности точек x[t] к точке x , в качестве последовательности Rt, t = 0,1,2,..., для методов внешней точки следует выбирать монотонно возрастающую последовательность положительных чисел, т.е. Rt ^^ при t ^^. Для вычисления Rt используется рекуррентное сооотношение Rt = Rt-i Х с, t = 1,2,!, где R0 > 0 (часто R0 = 1), с > 1 (часто с = 10). Метод штрафных функций позволяет в простых случаях явно (аналитически) решить задачу условной оптимизации. Рассмотрим в качестве иллюстрации аналитического решения следующий пример. Пример. Дана задача условной минимизации f (x) = x ^ min, x > 2. Легко видеть, что решением данной задачи является точка x =2, при этом f=2. Рассмотрим аналитическое решение задачи: а) методом внешней точки, б) методом внутренней точки (логарифмическая штрафная функция), в) методом внутренней точки (обратная штрафная функция). Решение. Преобразуем ограничение исходной задачи к виду g^)<0: g(х)= 2 -х < 0. а) Метод внешней точки. Штрафная функция типа квадрата лсрезки имеет вид a(R, g (х )) = R 2 - х)2. Получаем задачу безусловной минимизации Р(х, R)= х + R(2 - х)2 ^ min. При этом предполагается, что x - внешняя точка, т.е. х < 2, g(х) = 2 - х > 0. Уравнение, определяющее стационарные точки Р(х,Я), имеет вид Ч = 1 - 2R( 2 - х) = 0. дх N ' Поскольку 2 - х > 0 , то по определению лсрезки получим (2 - х) = 2 - х. Находим стационарную точку х^)^): 1 -2R(2 -х) = 0 ^ х(1) (R) = 2 -1/(2R). При этом g(х(1)(R)) = 1/(2R)> 0 при R>0, т.е. при любом конечном R>0 соответствующая стационарная точка является недопустимой (внешней) точкой и сделанное предположение не нарушается. * Точка х , являющаяся решением исходной задачи, определяется следующим образом: х* = Ь. х0) (R) = fc(2 - V(2R)) = 2. б) Метод внутренней точки. Логарифмическая штрафная функция имеет вид a(R, g (х )) = - R ln (х - 2). Получаем задачу безусловной минимизации Р(х,R) = х-Rln(х-2) ^min. При этом предполагается, что x - внутренняя точка, т. е. х > 2, g(х) = 2 - х < 0. Уравнение, определяющее стационарные точки Р(х, R), имеет вид дР=1 -_л_=0. дх х - 2 Находим стационарную точку х^)^): х(1) (R) = 2 + R. При этом g(х(1) (R)) = -R < 0 при R > 0, т. е. при любом R>0 соответствующая стационарная точка является допустимой (внутренней) точкой и сделанное предположение не нарушается. * Точка х , являющаяся решением исходной задачи, определяется следующим образом: х* = lim хт(R) = lim (2 + R) = 2. R ^0 (1) R ^0 в) Метод внутренней точки. Обратная штрафная функция имеет вид R a(R, g (х )) = - R-l_ = . 2-х х-2 Получаем задачу безусловной минимизации Р(х, R ) = х +ЧR min. х-2 При этом предполагается, что х - внутренняя точка, т. е. х > 2, g(х) = 2 - х < 0. Уравнение, определяющее стационарные точки Р(х, R), имеет вид дР=1 --^Ц.=0. дх (х - 2)2 Находим стационарные точки х(1;2)(^): x (1,2) (R) = 2 VR. При этом g(x(1) (R)) = -JR < 0 при R > 0, т.е. при любом R>0 стационарная точка x(1)(R) является допустимой (внутренней) точкой и сделанное предположение не нарушается. С другой стороны g(x(2) (R)) = JR > 0 при R > 0, т.е. при любом R>0 сделанное предположение нарушается, ста-ционарная точка x(2)(R) является недопустимой (внешней) точкой и должна быть отброшена. Решение x исходной задачи определяется следующим образом: x* = lim x(1)(R) = lim (2 + VR) = 2. R ^0 (1) R ^0 Алгоритм численного решения задачи условной миними-зации методом штрафных функций заключается в следующем. Задаются е, 81, д2, R0, с и x[0]; определяется тип x[0] (внутренняя или внешняя); выбирается штрафная функция Q; строится расширенная функция P; полагается t=1. Решается одним из численных методов задача безусловной минимизации P(x, Rt-1) ^ min, x e Rn. < е. P( ^), Rt-J Результатом решения задачи безусловной минимизации является точка x[t], в качестве которой используется оценка x(k) точки минимума задачи безусловной минимизации. 3. Проверяется условие t=1. При этом начальная точка x(0) = x[t-1], условие окончания вычислений п.4. Если оно выполняется, то осуществляется переход к п.5. Если условие не выполняется, то осуществляется переход к 4. Проверяются условия окончания решения исходной зада- чи: P( x[t ], Rt-1) - P( x[t-1], Rt-2) P( x[t- ж1], Rt-2) xj] - xj -1] x[t-1] xj <д2, j = 1 п. At ] Если они выполняются, то полагается x f = f (x[t ]) и вычисления завершаются. Если условия не выполняются, то осуществляется переход к п.5. 5. Определяется R, полагается t=t+1 и осуществляется переход к п.2. Пример. Решить методом штрафных функций задачу условной минимизации f (x) = (Х1 - 4)2 + (Х2 - 4)2 ^ min, x1 + x2 < 5 при е = 0,2, 8Х = 0,4, д2 = 0,1, R0 = 10, с = 10, x[0] = (1,1). Для решения задачи безусловной минимизации применить градиентный метод с дроблением шага (а = 1, в = 1/4). Решение. Преобразуем ограничение исходной задачи к виду g (x) < 0: g(x) = x1 + x2 - 5 < 0. Определяем тип x[o]: g(x[0]) = 1 +1 - 5 = -3 < 0. Поскольку ограничение выполняется, то точка x[0] явля- ется внутренней (допустимой). Выбираем обратную штрафную функцию, т.е. Q(R, g (х)) = - R/g (х). При этом расширенная функция P(x,R) имеет вид P(х, R) = f (х) - R/g(х). Первый этап Решаем градиентным методом с дроблением шага (МДШ) задачу безусловной минимизации 2 2 10 P(х,R0) = (х -4)2 + (х2 - 4)2 + > min. 5 х*1 х2 Начальная точка х(0) = х[0] = (1, 1), а = 1, в = 4, е = 0,2 . Отметим, что в процессе решения нужно контролировать знак штрафной функции Q(R, g(х)) . Если окажется, что на к-м шаге Q(R, g(х)) < 0, следует уменьшать (дробить) Хк . Находим первые частные производные P(х, R0 ) : dP . Дч 10 dP Дч 10 :2(х1 -4) + - -у, тЧ= 2(х2 -4) + дх1 41 (5 -х1 -х2)2 ' дх2 v 2 (5 -х1 -х2)2 Результаты вычислений заносим в табл. 9.1. Таблица 9.1 Ном. итер. X Ах1 Ах2 х1 х2 Q P dP дх1 dP дх2 И 0 1 1 3,33 21,3 -4,89 -4,89 6,92 1 1 0,707 0,707 1,71 1,71 6,33 16,82 -0,57 -0,57 0,806 2 1 0,707 0,707 2,42 2,42 62,5 67,5 P( х(2)) > P( х (1)) ^X = X$= 0,25 2 0,25 0,177 0,177 1,89 1,89 8,20 17,1 P( х(2)) > P( х(1)) ^Х = Хв= 0,0625 2 0,0625 0,044 0,044 1,75 1,75 6,67 16,79 -0,055 -0,055 0,078 Поскольку условие окончания вычислений выполнено (0,078<0,2), то вычисления завершаются. В результате решения задачи безусловной минимизации получаем x[i] ^ х(2) = (1,75; 1,75), Р(x[1],R0) = P(x(2),R0) = 16,79. Определяем R1 = Я0/c = 1^/10 = 1 и выполняем второй этап. Второй этап Решаем МДШ задачу безусловной минимизации P(х, R1) = (х1 - 4)2 + (х2 - 4)2 + > min. 5 Х1 Х2 Начальная точка х(0) = х[1] = (1,75; 1,75), а = 1, в = 4, ? = 0,2. Находим первые частные производные P(х, R1) : dP 1 dP , Дч 1 :2(х1 -4) + - -у, - = 2(х2 -4) + дх1 41 ' (5 - х1 - х2)2 ' дх2 v 2 (5 - х1 - х2)2 Результаты вычислений заносим в табл. 9.2. Таблица 9.2 Ном. итер. Я Ах1 Ах2 х1 х2 Q P dP дх1 dP дх2 И 0 1,75 1,75 0,67 10,79 -4,06 -4,06 5,74 1 1 0,707 0,707 2,46 2,46 12,5 17,24 P(х(1)) > P(х(0 ) ^ Я = Яв = 0,25 1 0,25 0,177 0,177 1,93 1,93 0,88 9,45 -3,37 -3,37 4,77 2 0,25 0,177 0,177 2,10 2,10 1,25 8,47 -2,24 -2,24 3,17 3 0,25 0,177 0,177 2,28 2,28 2,27 8,19 1,72 1,72 2,43 4 0,25 -0,177 -0,177 2,10 2,10 1,25 8,47 P( х (4)) > P( х(3)) ^Я = Яв = 0,0625 4 0,0625 -0,044 -0,044 2,23 2,23 1,85 8,12 -0,11 -0,11 0,156 Поскольку условие окончания вычислений выполнено (0,156<0,2), то вычисления завершаются. В результате решения задачи безусловной минимизации получаем х[2] = х(4) = (2,23; 2,23), P(х[2], R1) = P(x(4), R1) = 8,12. Проверяем условия окончания решения исходной задачи P( х[2], Ri) - P( х[1], Ro) = |8,12 -16,79| 0,516 >8, = 0,4. P( х[1], Ro) 16,79 1 Поскольку условия не выполняются, то определяем R2 = R1 / c = 1/10 = 0,1 и выполняем третий этап. Третий этап Решаем МДШ задачу безусловной минимизации 2 2 01 P(х,R2) = (х1 -4)2 + (х2 -4)2 + Ч-i- > min. 5 - х1 - х 2 Начальная точка х(0) = х[2] = (2,23;2,23), а = 1, в = 4, ? = 0,2. Находим первые частные производные P(х, R2 ) : dP . Дч 0,1 dP ^ Дч 0,1 Ч = 2(х1 - 4) + - ^ , __ = 2(х2 - 4) + - ^ , дх1 (5 - х1 - х2) дх2 (5 - х1 - х2) Результаты вычислений заносим в табл. 9.3. Таблица 9.3 Ном. итер. Я Ах1 Ах2 х1 х2 Q dP дх1 dP дх2 И 0 2,23 2,23 0,185 6,45 -3,2 -3,2 4,52 1 1 0,707 0,707 2,94 2,94 -0,114 Q( R2, g (х)) = - -0,114 < 0 ^Я = Яв = 0,25 1 0,25 0,177 0,177 2,41 2,41 0,556 5,61 -0,09 -0,09 0,127 Поскольку условие окончания вычислений выполнено (0,127<0,2), то вычисления завершаются. В результате решения задачи безусловной минимизации получаем х[3] = х(1) = (2,41; 2,41), P(х[3],R2) = P(x(1),R2) = 5,61. Проверяем условия окончания вычислений исходной задачи P( х[3], R2) - P( х[2], Rj| = |5,61 - 8,12| 0,309 < 8. = 0,4, 8,12 P( х[2], Rj) = 0,081 <82 = 0,1, J = 1,2. 2,41 - 2,23 2,23 х[3] - х[2] J J х J2] J Поскольку условия выполняются, то полагаем х = хL3J = (2,41; 2,41), f = f (хL3J) = 5,06 и вычисления завершаются. Ответ: х = (2,41; 2,41), f = 5,06. |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "методы внешней точки" |
|
|