Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
, т.е. предельная точка всякой последовательности вида (9) сов- падает с точкой x ? . Следовательно, lim k?? x k = x ? , т.е. для всех достаточно больших значений k точка x k лежит внутри множества U. Но на множестве U ?f k (x k ) = 0 или, что эквивалентно, ?f (x k ) + k m X i=1 g i (x k )?g i (x k ) + x k ? x ? = 0. (11) Положим ? 0 (k) = 1 v u u t1 + k 2 m X i=1 (g i (x k )) 2 и ? i (k) = kg i (x k ) v u u t1 + k 2 m X i=1 (g i (x k )) 2 , i = 1, . . . , m. Тогда равенство (11) можно переписать в следующем эквива- лентном виде: ? 0 (k)?f (x k ) + m X i=1 ? i (k)?g i (x k ) + ? 0 (k)(x k ? x ? ) = 0. (12) Поскольку, очевидно, m X i=0 (? i (k)) 2 = 1 для всех значений k = 1, 2, 3, . . . то существует такая неогра- ниченно возрастающая последовательность k 1 , k 2 , . . . , k j . . . , lim j?? k j = ? (13) 68 Гл. 2. Математическое программирование натуральных чисел, что lim j?? ? i (k j ) = ? ? i , i = 1, . . . , m, где m X i=0 (? ? i ) 2 = 1. Поэтому, переходя в равенстве (12) к пределу при k ? ? вдоль множества (13), получим равенство (2). ¤ Замечание. Приведенное доказательство наиболее на- глядно эксплуатирует основную идею метода множителей Ла- гранжа применение необходимого условия экстремума в за- даче без ограничений для получения необходимого условия экстремума в задаче с ограничениями. Для достижения этой цели строится последовательность задач безусловной миними- зации (8), отличающихся одна от другой все большим штра- фом k 2 m X i=1 (g i (x)) 2 за нарушение ограничений. Данный метод, известный как ме- тод штрафных функций, широко используется в теории экс- тремальных задач. Примеры. Прежде всего, приведем два простейших при- мера использования теоремы 2. Пример 2. Рассмотрим задачу о минимизации функции f (x 1 , x 2 ) = (x 1 ) 2 + (x 2 ) 2 (14) при ограничении x 1 + x 2 = 1. (15) Положим g(x 1 , x 2 ) = x 1 + x 2 ? 1. Тогда, поскольку для всех значений x 1 и x 2 ?g(x 1 , x 2 ) = (1, 1), то без какой-либо потери общности можно принять L(x 1 , x 2 , ?) = (x 1 ) 2 + (x 2 ) 2 + ?(x 1 + x 2 ? 1). џ1. Задача на условный экстремум 69 Поэтому в силу теоремы 2 имеем равенства 2x 1 + ? = 0 (16) и 2x 2 + ? = 0, (17) которые совместно с уловием (15) образуют замкнутую систе- му относительно неизвестных x 1 , x 2 , ? Легко видеть, что решение x ?1 , x ?2 , ? ? системы (15)(17) имеет вид x ?1 = 1 2 , x ?2 = 1 2 , ? ? = ?1. При этом, очевидно, точка x ?1 = 1 2 , x ?2 = 1 2 является точкой минимума в задаче (14), (15). Пример 3. Рассмотрим задачу о минимизации функции f (x 1 , x 2 ) = ?(x 1 ) 2 ? (x 2 ) 2 (18) при ограничении x 1 + x 2 = 1. (19) Действуя как и в примере 2, несложно показать, что для задачи (18), (19) выполнены условия теоремы 2, причем имеют место равенства ?2x 1 + ? = 0 (20) и ?2x 2 + ? = 0. (21) Разрешая теперь систему (19)(21) относительно неизвестных x 1 , x 2 , ? , запишем x ?1 = 1 2 , x ?2 = 1 2 , ? ? = 1. При этом заменив функцию (18) функцией f 1 (x 1 , x 2 ) = (x 1 ) 2 + (x 2 ) 2 , в силу примера 2 видим, что точка x ?1 = 1 2 , x ?2 = 1 2 является точкой максимума. 70 Гл. 2. Математическое программирование В заключение приведем пример, показывающий, что ми- нимум функции Лагранжа не обязан совпадать с минимумом исходной задачи с ограничениями (см. [10]). Пример 4. Рассмотрим задачу о минимизации функции f (x 1 , x 2 ) = (x 2 ) 2 ? x 1 (22) при ограничении x 1 + (x 1 ) 3 = 0. (23) Легко видеть, что решение задач (22), (23) достигается в точке x 1 = 0, x 2 = 0. (24) Функция Лагранжа L при этом имеет следующий вид: L(x 1 , x 2 , ? 0 , ? 1 ) = ? 0 ((x 2 ) 2 ? (x 1 )) + ? 1 (x 1 + (x 1 ) 3 ). (25) В силу теоремы 11 главы 1 необходимое условие минимума функции L дают уравнения ?? 0 + ? 1 (1 + 3(x 1 ) 2 ) = 0, 2? 0 x 2 = 0. Если ? 0 = 0, то ? 1 6= 0 и, следовательно 1 + (3x 1 ) 2 = 0, что невозможно. Поэтому полагаем ? 0 = 1. Тогда функция (25) примет вид L(x 1 , x 2 , ?) = (x 2 ) 2 ? x 1 + ?(x 1 + (x 1 ) 3 ). (26) Легко видеть, что ни при каких значениях ? функция (26) в точке (24) не имеет даже локального минимума. Последнее, вообще говоря, еще раз показывает, что формально методом множителей Лагранжа следует пользоваться с большой осто- рожностью. џ1. Задача на условный экстремум 71 Упражнения. (1) Точка x ? ? Q называется локально единственной точкой минимума задачи (1), если для всех x ? Q, достаточно близких к x ? , выполнено неравенство f (x ? ) < f (x). Покажите, что если x ? локально единственная точка минимума в задаче (1), то при доказательстве теоремы 1 слагаемое 1 2 |x ? x ? | 2 в правой части равенства (8) можно опустить. (2) Покажите, что если x ? регулярная точка минимума в задаче (1), то при доказательстве теоремы 1 существует предел lim k?? kg i (x k ) = ? ? i ? ? 0 , i = 1, . . . , m. (3) Найдите необходимые условия минимума в задаче f (x) ? min, Ax = b. (4) Пользуясь необходимыми условиями минимума, найдите решения следующих задач: N X i=1 (x i ) 2 ? min, N X i=1 x i = 1, (A) N X i=1 x i ? min, N X i=1 (x i ) 2 = 1, (B) hQx, xi/2 ? hp, xi ? min, Ax = b, (C) где Q симметрическая положительно определенная мат- рица. (5) Проверьте, имеют ли данные задачи решения и, если да, найдите эти решения: N X i=1 ?(x i ) 2 ? min, N X i=1 x i = 1, (A) N X i=1 ?x i ? min, N X i=1 (x i ) 2 = 1. (B) 72 Гл. 2. Математическое программирование џ2. Нелинейное программирование Задача нелинейного программирования отличается от за- дачи на условный экстремум наличием дополнительных огра- ничений, имеющих вид h(x) ? 0, (1) где h: R n ? R r некоторая заданная функция, и называемых ограничениями типа неравенств. Поэтому ограничения g(x) = 0, (2) где g : R n ? R m , в задаче нелинейного программирования на- зываются ограничениями типа равенств. Таким образом, за- дача нелинейного программирования заключается в миними- зации числовой функции f : R n ? R при выполнении ограни- чений (1) и (2). Задачу нелинейного программирования часто записывают в следующем виде: f (x) ? min, g i (x) = 0, i = 1, . . . , m, h i (x) ? 0, i = 1, . . . , r, (3) объединяя тем самым функцию f, подлежащую минимиза- ции, и ограничения (1) и (2), которые следует учитывать при выполнении минимизации. Как и в случае задачи на услов- ный экстремум, сформулированная таким образом задача (3) нелинейного программирования представляет интерес только в случае, когда n > m, что и предполагается в дальнейшем. При этом множество Q точек, для которых выполнены усло- вия (1) и (2) замкнуто, т.е. если множество Q ограничено, то в силу теоремы 7 главы 1 задача (3) будет иметь решение, что также предполагается. Таким образом, исследование за- дачи (3) сводится к отысканию необходимых и достаточных условий минимума, чему частично и посвящен џ2. Легко видеть, что задача (3) содержит в себе задачу на условный экстремум и потому реалистичнее ее. При этом необ- ходимо отметить, что в каждой из этих задач приходится иметь дело с нелинейными функциями, чем и объясняется тер- мин нелинейное программирование. џ2. Нелинейное программирование 73 Теорема Каруша Джона. Пусть Q 1 = {x ? R n : g i (x) = 0, i = 1, . . . , m} множество точек, для которых выполнены ограничения типа равенств (1), и пусть Q 2 = {x ? R n : h i (x) ? 0, i = 1, . . . , r} множество точек, для которых выполнены ограничения типа неравенств (2). Пересечение Q = Q 1 ? Q 2 множеств Q 1 и Q 2 дает точки x ? R n , называемые допусти- мыми точками в задаче (3). Точка x ? ? Q называется точкой минимума (или точкой локального минимума) в задаче (3), если для всех x ? Q, достаточно близких к допустимой точке x ? , выполнено неравенство f (x ? ) ? f (x). Необходимое условие минимума в задаче (3) дает следую- щая важнейшая для теории экстремальных задач Теорема 3 (Каруш Джон). Пусть x ? точка миниму- ма в задаче (1) и функции f, g 1 , . . . , g m и h 1 , . . . , h r непрерывно дифференцируемы в некоторой окрестности E точки x ? . То- гда найдутся такие действительные числа ? ? 0 , ? ? 1 , . . . , ? ? m и µ ? 1 , . . . , µ ? r , не все равные нулю одновременно, что ? ? 0 ?f (x ? ) + m X i=1 ? ? i ?g i (x ? ) + r X i=1 µ ? i ?h i (x ? ) = 0, (4) где ? ? 0 ? 0 и µ ? i ? 0, i = 1, . . . , r. Доказательство. Пусть ? некоторое положительное число и пусть U множество точек x ? R n , для которых |x ? x ? | ? ?. Выберем число ? столь малым, чтобы все функции f, g 1 , . . . , g m и h 1 , . . . , h r были непрерывно дифференцируемы на множестве 74 Гл. 2. Математическое программирование Q ? U ? E , причем каждая из функций h 1 , . . . , h r не меняла знак на множестве U ? (R n \ Q) . Далее, пусть M подмноже- ство множества индексов i = 1, . . . , r, таких, что h i (x) ? 0 на замыкании R множества U ? (R n \ Q) . Если множество M пусто, то теорема 3 справедлива в силу теоремы 1, поскольку здесь можно принять µ ? i = 0, i = 1, . . . , r. Исключив этот тривиальный случай, наряду с задачей (3) вве- дем в рассмотрение задачу о минимизации функции f k : R n ? R , задаваемой равенством f k (x) = f (x) + k 2 Г m X i=1 (g i (x)) 2 + r X i=1 ? i (h i (x)) 2 ! + 1 2 |x ? x ? | 2 , (5) где k некоторое натуральное число, а ? 1 , . . . , ? r действи- тельные числа, задаваемые равенством ? i = Ѕ 1, i ? M, 0, i / ? M. Функция f k , очевидно, непрерывна, а множество R ком- пактно. Поэтому согласно теореме 7 главы 1 задача о миними- зации функции f k для всех значений k имеет на множестве R решение x k , т.е. существует такое x k ? R , что f k (x k ) ? f k (x ? ). Отсюда в силу равенства (5) имеем f (x k )+ k 2 Г m X i=1 (g i (x k )) 2 + r X i=1 ? i (h i (x k )) 2 ! 1 2 |x k ?x ? | 2 ? f (x ? ) или, что эквивалентно, m X i=1 (g i (x k )) 2 + r X i=1 ? i (h i (x k )) 2 ? ? 2 k µ f (x ? ) ? f (x k ) ? 1 2 |x k ? x ? | 2 ¶ . џ2. Нелинейное программирование 75 Поскольку для всех значений k = 1, 2, 3, . . . |x k ? x ? | ? ?, то lim k?? 2 k µ f (x ? ) ? f (x k ) ? 1 2 |x k ? x ? | 2 ¶ = 0. Следовательно, lim k?? Г m X i=1 (g i (x k )) 2 + r X i=1 ? i (h i (x k )) 2 ! = 0, т.е. lim k?? g i (x k ) = 0, i = 1, . . . , m и lim k?? ? i h i (x k ) = 0, i = 1, . . . , r. Выберем некоторую неограниченно возрастающую последова- тельность k 1 , k 2 , . . . , k i , . . . , lim i?? k i = ? натуральных чисел. Легко видеть, что последовательность x k 1 , x k 2 , . . . , x k |