Достаточное условие локальной оптимальности

. Пусть /(х), g1 (х), g2(х),..., gm(х) дважды дифференцируемы в точке

х* е Rn , причем при некотором X Ф 0 выполняются условия (2.2), т.е. х* - стационарная точка. Тогда, если

(.aLхх(х*X),а) > 0 ((aL(х*Д*),а) < 0)

пП

при всех ненулевых а е R таких, что

g' (х* — 0, i — 1,m,

то х* - точка локального минимума (максимума) /(х) на множестве X.

Алгоритм определения точек условных локальных экстремумов заключается в следующем.

1. Составляется функция Лагранжа L( х, X).

Находится L'x (x, Я).

Решается система

dL( ^Я)

= 0, j = 1,n;

dxj

dL( x, Я)

gi (x) = 0, i = 1,m .

ЭЯг

В результате вычисляются стационарные точки x^i) , l = 1, N, и соответствующие им Я^), l = 1, N.

Находятся (g'(x),a), i = 1,m .

Находится L^ (x, Я), полагается l = 1.

Находится L!^ (x{l ),Я(1 )). Составляется квадратичная форма Ql (а), задаваемая матрицей L"xx (x{l), Я{1)):

Ql(а) = (^4(x(l ),я(1 )),а).

Решается система

(g'(x(l)),а) = 0, i =1,m . В результате вычисляются точки а(r).

Вычисляются значения Ql (а(r)) и анализируются их

знаки.

Если Ql (а(r)) > 0 для всех ненулевых a{r), то x{l) - точка условного локального минимума.

Если Ql (а(r)) < 0 для всех ненулевых a{r), то x^ - точка

условного локального максимума.

Проверяется условие определения характера всех стационарных точек

l = N.

Если оно выполняется, то вычисления завершаются. Если условие не выполняется, то полагается l = l +1 и осуществляется переход к п.6.

Пример. Определить точки локальных экстремумов функции

1 2 1 2 f (x) = ^ axf + ^ bx|, a > 0, b > 0,

при ограничении

x1 + x 2 = 1 .

Решение.

Составляем функцию Лагранжа

L(x, Я) = 2ax^ + 2bx22 + Я(x3 + x2 -1).

Находим L'x (x,Я):

dL( x, Я) = ax1 + зЯХ-12 , dL( x, Я) = bx2 + зЯт?.

1 1 2 2 dx1 dx2

Решаем систему уравнений

ax1 + ЗЯ^2 = x1 (a + 3Яг1) = 0, (1) bx2 + 3Яг22 = x2(b + 3Яг2) = 0, (2) x3 + x23 -1 = 0. (3)

Для выполнения (1) должно выполняться условие x1 = 0 либо a + 3Яг1 = 0 . Для выполнения (2) должно выполняться усло- вие x2 = 0 либо b + 3Яг2 = 0 . Однако в силу (3) одновременно не могут выполняться условия xj = 0 и x2 = 0. Следовательно, система имеет 3 решения.

1) Пусть x1 = 0 . Тогда из уравнения (3) получаем x2 = 1. Поскольку x2 Ф 0, то для выполнения (2) должно выполняться условие b + 3Яг2 = 0, откуда Я = - b/3 .

Таким образом, получили первую стационарную точку x(1) и Я(1):

x(1) = (0, 1), Я(1) =- V 3.

2) Пусть x2 - 0. Тогда из уравнения (3) получаем x1 -1. Поскольку x1 Ф 0, то для выполнения (1) должно выполняться условие a + 3Xx1 - 0, откуда X - — a/3.

Таким образом, получили вторую стационарную точку

x(2) и X(2): (2)

- (1,0), X(2) -- a/3. 3) Пусть x1 Ф 0 и x2 Ф 0. Тогда для выполнения (1) должно выполняться условие a + 3Xx1 - 0, откуда X- — a/ 3x1; для выполнения (2) должно выполняться условие b + 3Xx2 - 0, откуда

ё- — b/3x2 .

Приравнивая выражения для X, получаем x2 - — x1.

a

Подставляя полученное выражение в уравнение (3), нахо-

дим x1 : b3

-x1 a

a

x3 +

13 a3

3 a + b3 1 1 - 0 ^ x3 3— - 1 ^ Xj -

V a3 + b3 ' 3Vor+b7

Находим x2 и X :

a

X- — - 3 x1

bb a

3

1 3a3 + b3 ' Таким образом, получили третью стационарную точку

X (3) и X(3): 3V a3 + b3 3

a

X(3) -

x(3) -

b ( x) dx2

- 3 x12

- 3 x 22

Находим (g'(x), a): (x)

dx1 3x1 ,3x-2 ),(Й1, 4)) - 3X1^1 + 3X2 32. Находим Lxx (x, Я) : d2 L( x, Я) d2 L( x, Я) d2 L( x, Я) b

dxf

V • = A + 6Яг1, _ V = 0, —_ 2 ' = B + 6Яг2

dx2

0

b + 6Яx7

dx1dx2 a + 6Яx1

L'xx (X, Я)

0 Определяем характер стационарной точки x(1). Находим

Lxx (x(1) , Я(1) ) : b 3

0

0

a 0 0 - b

a + 6

/ г. \

b

Lxx (x(1), Я(1))

3

V У

0 b + 6 Составляем квадратичную форму Q1(a) : a 0 0 - b

¦ (aa1 ,-ba2),

^"xx (X(1), Я(1)) = (а1 ,а2) Q1 (a) = ((aa1 ,-ba2),(a1,a2)) = aa12 -ba^. Решаем уравнение (g'(x(1)),^ = 0:

3• 0 a1 + 3-1-a2 = 0 ^ 3a2 = 0. Решением являются точки a(r) = (a1,0). Вычисляем значения Qj (a(r)) :

Q1(a(r)) = aa12 > 0 при a1 Ф 0. Поскольку Q1 (a(r)) > 0 для всех ненулевых a{r), то x^

является точкой условного локального минимума.

Отметим, что матрица L^ (x^, Я^ ) не является положительно определенной.

Определяем характер стационарной точки x(2). Находим

Lxx (x(2), Я(2) ): a

v4

0

a 0 0 b

a + 6

a

Lxx (X(2) , Я(2) )

V 3,

0 b + 6 Составляем квадратичную форму Q2 (a) : a 0 0 b

(-aa1, ba2),

axx (x(2), Я(2)) = (ai, a2 ) Q2(a) = ((-aa1, ba2),a ,a2)) = -aaj2 + ba^. Решаем уравнение (g'(X(2)),a^ = 0 :

3•1-a1 + 3• 0 a2 = 0 ^ 3a1 = 0. Решением являются точки a^r) = (0, a2 ) . Вычисляем значения Q2(a{r)) :

Q2(a(r)) = ba^ > 0 при a2 Ф 0. Поскольку Q2 (a(r)) > 0 для всех ненулевых a{r), то X(2) является точкой условного локального минимума.

Отметим, что матрица LXx (Х(2), Я(2)) не является положительно определенной.

Определяем характер стационарной точки Х(3). Находим

LXX ( Х(3) , ^(3) ) :

3a3 + b3 Л

a

a + 6

3 a3 + b3

Lxx (Х(3),Я(3))

V a3 + b3

b + 6

3 a3 + b3

-a 0 0 -b

Составляем квадратичную форму Q3 (а) :

а 0 0 - b

¦ (-аа1 ,-Ьа2),

аxx (Х(3), ^(3)) = (а1, а2 )

Q(3)(a) = {(-aа1-bа2),(а1,а2)) = -аа? - Ьа2, =-(аа2 + Ьа2).

Поскольку Q3 (а) < 0 для всех ненулевых а (в том числе и для а{г), являющихся решением уравнения (g'(Х(3)),^ = 0), то Х(3) является точкой условного локального максимума.

1 2 1 2

Ответ: функция f (x) = ax1 + bx2, а > 0, b > 0, в допустимой области X = {x е R2 : xj + x2 = l} имеет в точках x = (0, 1) и x = (1, 0) условные локальные минимумы, а в точке ^ и Л

а b

х

- условный локальный максимум.

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

Еще по теме Достаточное условие локальной оптимальности:

  1. Достаточное условие локальной оптимальности.
  2. Достаточное условие локальной оптимальности
  3. Необходимое условие локальной оптимальности.
  4. Необходимое условие локальной оптимальности.
  5. Необходимое условие локальной оптимальности.
  6. § 2. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ БЕЗУСЛОВНОГО ЭКСТРЕМУМА
  7. § 3. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ УСЛОВНОГО ЭКСТРЕМУМА
  8. 7.4. ОПТИМАЛЬНАЯ КОМБИНАЦИЯ РЕСУРСОВ И ОПТИМАЛЬНЫЙ ПУТЬ РОСТА
  9. Формулы для оптимального размера заказа и оптимальной величины дефицита
  10. 9. Достаточность доказательств
  11. 2. Достаточность доказательств
  12. Методы локальной оптимизации