Книги по разным темам Pages:     | 1 | 2 | 3 | 4 |   ...   | 9 |

Достаточное условие локальной оптимальности. Пусть f(x) дважды дифференцируема в точке x Rn, причем f (x) = 0, т.е. x - стационарная точка. Тогда, если матрица f (x) является положительно (отрицательно) определенной, то x - точка локального минимума (максимума); если матрица f (x) является неопределенной, то x - седловая точка.

Если матрица f (x) является неотрицательно (неположительно) определенной, то для определения характера стационарной точки x требуется исследование производных более высокого порядка.

Для проверки знакоопределенности матрицы, как правило, используется критерий Сильвестра. Согласно этому критерию, симметричная матрица А является положительно определенной в том и только том случае, если все ее угловые миноры положительны. При этом угловым минором матрицы А называется определитель матрицы, построенной из элементов матрицы А, стоящих на пересечении строк и столбцов с одинаковыми (причем первыми) номерами. Чтобы проверить симметричную матрицу А на отрицательную определенность, надо проверить матрицу (-А) на положительную определенность.

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

1. Находится f (x).

2. Решается система f (x) = 0, j = 1,n.

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

3. Находится f (x), полагается i=1.

4. Находится f (x(i)).

5. Вычисляются угловые миноры матрицы f (x(i)).

Если не все угловые миноры ненулевые, то для определения характера стационарной точки x(i) требуется исследование производных более высокого порядка. При этом осуществляется переход к п.8.

В противном случае осуществляется переход к п.6.

6. Анализируются знаки угловых миноров f (x(i)).

Если f (x(i)) является положительно определенной, то x(i) является точкой локального минимума. При этом осуществляется переход к п.8.

В противном случае осуществляется переход к п.7.

7. Вычисляются угловые миноры матрицы [- f (x(i))] и анализируются их знаки.

Если [- f (x(i))] является положительно определенной, то f (x(i)) является отрицательно определенной и x(i) является точкой локального максимума.

В противном случае f (x(i)) является неопределенной и x(i) является седловой точкой.

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

Если оно выполняется, то вычисления завершаются.

Если условие не выполняется, то полагается i = i +1 и осуществляется переход к п.4.

Пример. Определить точки локальных экстремумов 3 функции f (x) = x1 - 2x1x2 + x2 - 3x1 - 2x2.

Решение.

Находим первые частные производные f(x):

f f = 3x1 - 2x2 - 3, = -2x1 + 2x2 - 2.

x1 xРешаем систему уравнений 3x1 - 2x2 - 3 = 0, (1) -2x1 + 2x2 - 2 = 0. (2) Разрешаем уравнение (2) относительно x1:

2x1 = 2x2 - 2 x1 = x2 -1.

Подставляя полученное выражение в уравнение (1), находим x2:

3(x2 -1)2 - 2x2 - 3 = 3x2 - 8x2 = x2(3x2 - 8) = x(1)2 = 0, x(2)2 =.

Соответственно x(1)1 = -1, x(2)1 =.

Таким образом, получили две стационарные точки ( N = 2 ):

5 x(1) = (-1, 0), x(2) = (, ).

3 Находим вторые частные производные f(x):

2 f 2 f 2 f = 6x1, = -2, = 2.

2 x1xx1 xСоставляем матрицу Гессе 6x - f (x) =.

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

-6 f (x(1)) =.

-2 Вычисляем угловые миноры f (x(1)) :

M1 = - 6 = -6 < 0, - 6 - M = = (-6)2 - (-2)(-2) = -16 < 0.

- 2 Поскольку все угловые миноры ненулевые, то характер x(1) определяется с помощью f (x).

Поскольку матрица f (x(1)) не является положительно [- определенной, то рассматриваем матрицу f (x(1) )] :

6 - f (x(1)) = 2 - 2.

Вычисляем угловые миноры [- f (x(1))]:

M1 = 6 = 6 > 0, 6 M = = 6(-2) - 2 2 = -16 < 0.

2 - Поскольку матрица [- f (x(1))] не является положительно определенной, то матрица f (x(1)) не является отрицательно оп ределенной. Следовательно, матрица f (x(1)) является неопределенной и x(1) является седловой точкой.

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

- f (x(2) ) =.

-2 Вычисляем угловые миноры f (x(2)) :

M1 = |10| = 10 > 0, 10 - M = = 10 2 - (-2)(-2) = 16 > 0.

- 2 Поскольку все угловые миноры ненулевые, то характер x(2) определяется с помощью f (x).

Поскольку матрица f (x(2)) является положительно определенной, то x(2) является точкой локального минимума.

3 Ответ: функция f (x) = x1 - 2x1x2 + x2 - 3x1 - 2x2 имеет в точке x = (5 3, 8 3) локальный минимум.

Задачи 1. Определить точки локальных и глобальных экстремумов функции f (x) = 1- x3.

2. Определить точки локальных и глобальных экстремумов функции f (x) = 1- x4.

3.Определить точки локальных и глобальных экстремумов функции f (x) = x4 - 4x3 + 4x2 -1.

4. Определить точки локальных экстремумов функции f (x) = x1 x2 -3x1x2 - x1 + 2x2 + 5.

5. Определить точки локальных экстремумов функции 3 f (x) = x1 + x2 -3x1x2.

6. Проверить, что точки x(1) = (0, 3, 1), x(2) = (0,1,-1) и x(3) = (1, 2,0) являются стационарными точками функции 2 2 f (x) = 2x1x2 x3 + x1 + x2 + x3 - 4x1x3 - 2x2 x3 - 2x1 - 4x2 + 4x3.

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

7. Определить, являются ли точки x(1) = (0, -1) и 3 x(2) = (2,1) точками экстремумов функции f (x) = x1 + x2 - 3x1 - 3x1x2 + 3x1 + 3x2 -1.

2. ЗАДАЧА УСЛОВНОЙ ОПТИМИЗАЦИИ Задача оптимизации (минимизации) f (x) min, x X называется задачей условной оптимизации, если X - собственное подмножество пространства Rn (X Rn, X Rn ).

На практическом занятии рассматривается так называемая классическая задача на условный экстремум. Это задача оптимизации с допустимым множеством X, заданным системой конечного числа уравнений:

X = {x Rn : gi (x) = 0, i = 1, m}.

Здесь предполагается, что m < n.

Обычно эта задача записывается в виде f (x) min, (2.1) gi (x) = 0, i = 1,m.

Для решения задачи (2.1) используется метод множителей Лагранжа. Основная идея метода заключается в переходе от задачи на условный экстремум исходной функции f (x) к задаче на безусловный экстремум некоторой специально построенной функции Лагранжа L(x,) m L(x,) = f (x) + gi (x), i i=где x Rn, = ( 1, 2,..., m ) Rm.

Необходимое условие локальной оптимальности. Пусть f(x), g1(x), g2(x),..., gm (x) дифференцируемы в точке x Rn. Если x - точка локального экстремума, то существует вектор = (,,..., ), компоненты которого не равны нулю одно1 2 m временно, такой, что Lx (x,) = 0, (2.2) L (x,) = 0, где Lx (x,), L (x, ) - соответственно векторы первых частных производных функции Лагранжа по x, j = 1,n, и i, i = 1,m.

j При этом должны выполняться условия регулярности: гра диенты g1( x), g2 (x),..., gm (x) должны быть линейно незави симы. Это означает, что ранг матрицы G, строками которой яв ляются градиенты gi (x), должен быть равен m.

юбая точка x, удовлетворяющая при некотором ненулевом условиям (2.2), называется стационарной точкой задачи (2.1).

Для определения характера стационарных точек используется достаточное условие оптимальности с привлечением матри цы Lxx (x,) вторых частных производных функции Лагранжа по x, j = 1,n.

j Достаточное условие локальной оптимальности. Пусть f(x), g1(x), g2(x),..., gm(x) дважды дифференцируемы в точке x Rn, причем при некотором 0 выполняются условия (2.2), т.е. x - стационарная точка. Тогда, если Lxx(x,), > 0 ( Lxx (x,), < 0) при всех ненулевых Rn таких, что gi (x), = 0, i = 1,m, то x - точка локального минимума (максимума) f(x) на множестве X.

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

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

2. Находится Lx (x, ).

3. Решается система L(x,) = j = 0, 1,n;

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

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

4. Находятся gi (x),, i = 1,m.

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

6. Находится Lxx (x(l),(l ) ). Составляется квадратичная форма Ql (), задаваемая матрицей Lxx (x(l),(l) ) :

Ql () = Lxx (x(l),(l)),.

7. Решается система gi (x(l) ), = 0, i = 1,m.

В результате вычисляются точки (r ).

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

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

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

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

Если оно выполняется, то вычисления завершаются.

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

Пример. Определить точки локальных экстремумов функции 1 2 f (x) = ax1 + bx2, a > 0, b > 0, 2 при ограничении 3 x1 + x2 = 1.

Решение.

Составляем функцию Лагранжа 1 2 2 3 L(x,) = ax1 + bx2 + (x1 + x2 -1).

2 Находим Lx (x,) :

L(x,) L(x,) 2 = ax1 + 3x1, = bx2 + 3x2.

x1 xРешаем систему уравнений ax1 + 3x1 = x1(a + 3x1) = 0, (1) bx + 3x2 = x2 (b + 3x2 ) = 0, (2) x3 + x2 -1 = 0.

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

1) Пусть x1 = 0. Тогда из уравнения (3) получаем x2 = 1.

Поскольку x2 0, то для выполнения (2) должно выполняться условие b + 3x2 = 0, откуда = -b 3.

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

x(1) = (0, 1), (1) = -b 3.

2) Пусть x2 = 0. Тогда из уравнения (3) получаем x1 = 1.

Поскольку x1 0, то для выполнения (1) должно выполняться условие a + 3x1 = 0, откуда = - a 3.

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

x(2) = (1, 0), (2) = - a 3.

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

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

b a3 + b3 a 3 x1 + x1 -1 = 0 x1 = 1 x1 =.

a a a3 + bНаходим x2 и :

b b a a3 + bx2 = x1 =, = - = -.

a 3x1 a3 + bТаким образом, получили третью стационарную точку x(3) и (3):

a b, (3) = - a3 + bx(3) =,.

a3 + b3 3 a3 + b Находим g (x), :

g(x) g(x) 2 = 3x1, = 3x2, x1 x2 2 2 (3x1,3x2 ),(1,2 ) = 3x11 + 3x22.

Находим Lxx (x, ) :

2L(x,) 2L(x,) 2L(x,) = a + 6x1, = 0, = b + 6x2, 2 x1xx1 xa + 6x1 = Lxx(x, ).

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

b a + 6- a Lxx (x(1),(1) ) = = 0.

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

a Lxx (x(1),(1)) = (1,2) = (a1,-b2), 0 - b 2 Q1() = (a1,-b2 ),(1,2 ) = a1 - b2.

Решаем уравнение g (x(1)), = 0 :

30 1 + 312 = 0 32 = 0.

Решением являются точки (r) = (1,0).

Вычисляем значения Q1((r ) ) :

Q1((r)) = a1 > 0 при 1 0.

Поскольку Q1((r)) > 0 для всех ненулевых (r ), то x(1) является точкой условного локального минимума.

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

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

a a + 6- 3 - a Lxx (x(2),(2) ) = =.

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

- a Lxx (x(2),(2) ) = (1,2 ) = (-a1,b2 ), 0 b 2 Q2 () = (-a1,b2 ),(1,2 ) = -a1 + b2.

g Решаем уравнение (x(2)), = 0 :

311 + 3 02 = 0 31 = 0.

Решением являются точки (r) = (0,2).

Вычисляем значения Q2 ((r)) :

Q2((r)) = b2 > 0 при 2 0.

Поскольку Q2 ((r)) > 0 для всех ненулевых (r ), то x(2) является точкой условного локального минимума.

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

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

a3 + b3 a a + 6 - a3 + b Lxx(x(3),(3)) == a3 + b3 b 0 b + 6 - a3 + b -a = 0 - b.

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

- a Lxx (x(3),(3)) = (1,2) = (-a1,-b2), 0 - b 2 2 2 Q(3)() = (-a1,-b2),(1,2) = -a1 - b2 = -(a1 + b2 ).

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

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

a3 + b3 3 a3 + b Задачи 1. Определить точки локальных экстремумов функции f (x) = x1 + xпри ограничении 2 x1 + x2 = 1.

2. Определить точки локальных экстремумов функции 2 2 f (x) = x1 + x2 + xпри ограничении 4x1 + x2 + 2x3 = 14.

3. Решить задачу условной максимизации f (x) = x1x2x3 max, x1 + x2 + x3 = a.

3. КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ Задачей квадратичного программирования (КП) называется задача оптимизации с квадратичной целевой функцией и линейными ограничениями. Задача КП, в которой целевая функция подлежит минимизации, имеет вид n n n f (x) = c x + d x xk min, j j jk j j =1 j =1 k =n aij x bi, i = 1, m, j j =xj 0, j = 1, n.

Допустимое множество X является выпуклым, матрица D = [d ] предполагается симметричной неотрицательно опредеjk ленной. При этом f (x) является выпуклой на X и задача КП является частным случаем задачи выпуклого программирования.

Для решения задачи КП используются необходимые условия Куна - Таккера, которые в силу выпуклости задачи КП оказываются также достаточными для установления наличия решения.

Предварительно составляется функция Лагранжа m L(x,) = f (x) + igi(x), i=n где g (x) aij x - bi.

j j j =Условия Куна - Таккера имеют следующий вид:

L(x,) 0, j = 1,n; (3.1) xj xj 0, j = 1, n; (3.2) L(x,) x = 0, j = 1, n; (3.3) j x j L(x, ) 0, i =1, m; (3.4) i i 0, i = 1, m; (3.5) L(x, ) i = 0, i = 1, m. (3.6) i Соотношения (3.3) и (3.6) определяют условия дополняющей нежесткости.

Непосредственное решение данной системы очень громоздко. Поэтому используется следующий прием. Неравенства (3.1) и (3.4) преобразуют в равенства, вводя соответственно две группы дополнительных переменных vj, j = 1, n, и wi, i = 1, m, удовлетворяющих требованиям неотрицательности. В результате от системы (3.1)-(3.6) переходят к следующей системе:

Pages:     | 1 | 2 | 3 | 4 |   ...   | 9 |    Книги по разным темам