методы внешней точки

Для методов внешней точки штрафные функции должны обладать следующими свойствами:

во всех точках допустимого множества X внешние штрафные функции равны нулю;

при выходе за пределы допустимого множества X внешние штрафные функции становятся положительными и достаточно быстро возрастают.

В качестве внешней штрафной функции часто используется штрафная функция типа квадрата "срезки"

Q(R, g (х)) = Rt t{gi (x})2. i=1

Здесь l^gi(x)) - "срезка" функции gi (x), определяемая следующим образом:

, , чх fg,(x) если g,(x) > 0,

=i0 () < 0 [0, если gt (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.

<< | >>
Источник: Харчистов Б.Ф.. Методы оптимизации. 2004

Еще по теме методы внешней точки:

  1. методы внут-ренней точки
  2. Метод «мертвой точки»
  3. Метод «мертвой точки».
  4. 1. Принципы и методы регулирования внешней торговли
  5. 2.7. Роль нетарифных методов регулирования внешней торговли
  6. РЕГУЛИРОВАНИЕ ВНЕШНЕЙ ТОРГОВЛИ ТОВАРАМИ: ТАРИФНЫЕ МЕТОДЫ
  7. РЕГУЛИРОВАНИЕ ВНЕШНЕЙ ТОРГОВЛИ ТОВАРАМИ: НЕТАРИФНЫЕ МЕТОДЫ
  8. ГЛАВА 11 ВНЕШНЕТОРГОВАЯ ПОЛИТИКА И МЕТОДЫ ГОСУДАРСТВЕННОГО РЕГУЛИРОВАНИЯ ВНЕШНЕЙ ТОРГОВЛИ
  9. Вопрос 2. Тарифные методы регулирования внешней торговли. Таможенная пошлина и таможенный тариф
  10. ДВЕ ТОЧКИ ОТСЧЕТА: ЛША И кШ
  11. Расходы с экономической точки зрения
  12. Кризисные точки социализации
  13. 3.Фокальные точки.
  14. 7.3. Золотовалютные резервы. Финансовая помощь и внешние заимствования. Внешний долг
  15. Вопрос 50. Внешние эффекты и внешние издержки.
  16. Неоптимальность равновесия Курно с точки зрения олигополистов
  17. 24.2. Внешние факторы развития Внешняя торговля
  18. Структура продаж и расчет точки безубыточности