Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
i , . . . (6) ограничена. Поэтому в силу теоремы 4 главы 1 без какой-либо потери общности можно считать, что существует предел lim i?? x k i = Ї x, где Їx некоторая точка множества U. При этом g i (Ї x) = 0, i = 1, . . . , m, ? i h i (Ї x) = 0, i = 1, . . . , r и f (Ї x) + 1 2 |Ї x ? x ? | 2 ? f (x ? ). (7) Поскольку x ? точка минимума на Q, то f (x ? ) ? f (Ї x). Поэтому из неравенства (7) следует, что Ї x = x ? , 76 Гл. 2. Математическое программирование т.е. предельная точка всякой последовательности вида (6) сов- падает с точкой 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 ) + r X i=1 ? i h i (x k )?h i (x k ) ! + +x k ? x ? = 0. (8) Положим ? 0 (k) = 1 v u u t1 + k 2 Г m X i=1 (g i (x k )) 2 + r X i=1 ? i (h 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 + r X i=1 ? i (h i (x k )) 2 ! , i = 1, . . . , m и µ i (k) = k? i h i (x k ) v u u t1 + k 2 Г m X i=1 (g i (x k )) 2 + r X i=1 ? i (h i (x k )) 2 ! , i = 1, . . . , r. Тогда равенство (8) можно переписать в следующем эквива- лентном виде: ? 0 (k)?f (x k ) + m X i=1 ? i (k)?g i (x k ) + m X i=1 µ i (k)?h i (x k )+ +? 0 (k)(x k ? x ? ) = 0. (9) џ2. Нелинейное программирование 77 Поскольку, очевидно, m X i=0 (? i (k)) 2 + r X i=1 (µ i (k)) 2 = 1 для всех значений k = 1, 2, 3, . . . , то существует такая неогра- ниченно возрастающая последовательность k 1 , k 2 , . . . , k j . . . , lim j?? k j = ? (10) натуральных чисел, что lim j?? ? i (k j ) = ? ? i , i = 1, . . . , m и lim j?? µ i (k j ) = µ ? i , i = 1, . . . , r, где m X i=0 (? ? i ) 2 + r X i=1 (µ ? i ) 2 = 1. Поэтому, переходя в равенстве (9) к пределу при k ? ? вдоль множества (10), получим равенство (4), в котором по постро- ению ? ? 0 ? 0 и µ ? i ? 0, i = 1, . . . , r. ¤ Условия дополняющей нежесткости. При доказате- льстве теоремы 3 использовался тот факт, что в точке x ? мини- мума некоторые из ограничений типа неравенств обращаются в равенства, а некоторые другие в строгие неравенства. Что- бы ясно различать указанные два возможных случая, введем следующее определение. Предположим, что при некотором значении i = 1, . . . , r имеет место равенство h i (x ? ) = 0. 78 Гл. 2. Математическое программирование Тогда будем говорить, что ограничение h i активно. Аналогич- ным образом, если при некотором значении j = 1, . . . , r имеет место неравенство h j (x ? ) < 0, то будем говорить, что ограничение h j неактивно. Обозначим через I ? множество активных ограничений в задаче (3) I ? = {i : h i (x ? ) = 0, i = 1, . . . , r}. Просматривая доказательство теоремы 3, несложно заметить, что если i /? I ? , то µ ? i = 0. Если же i ? I ? , то по определению h i (x ? ) = 0, т.е. в любом случае µ ? i h i (x ? ) = 0, i = 1, . . . , r. (11) Равенства (11) называются условиями дополняющей нежест- кости и используются следующим образом. Легко видеть, что условие (4) дает n уравнений относи- тельно n+m+r +1 неизвестного x ? , ? ? 0 , ? ? 1 , . . . , ? ? m и µ ? 1 . . . , µ ? r Дополнив условие (4) уравнениями g i (x ? ) = 0, i = 1, . . . , m и (11), получим систему n + m + r уравнений относительно n + m + r + 1 неизвестного x ? , ? ? 0 , ? ? 1 , . . . , ? ? m и µ ? 1 , . . . , µ ? r . При этом по прежнему велик соблазн принять ? ? 0 = 1 (12) и, таким образом, замкнуть систему. Последнее, как и в случае задачи на условный экстремум, можно делать далеко не все- гда, даже если ограничения типа равенств отсутствуют (см. упражнение 2). Таким образом, условия дополняющей нежесткости поз- воляют привести необходимое условие минимума в задаче (3) к системе уравнений, весьма близкой к системе, получавшей- ся при решении задачи на условный экстремум в џ1. Чтобы џ2. Нелинейное программирование 79 замкнуть эту систему, нужно получить условия, позволяющие, например, наверняка принять равенство (12). Замечание. Необходимо отметить, что в условиях теоре- мы 3 принципиальным является следующий момент: либо ? ? 0 6= 0, (13) либо ? ? 0 = 0. Последнее, конечно, оъясняется тем, что множители ? ? 1 , . . . , ? ? m и µ ? 1 , . . . , µ ? r определены с точностью до неотрицательного мно- жителя ? 0 и потому при выполнении условия (13) без какой- либо потери общности можно принять равенство (12). Условия регулярности. Для получения некоторых ус- ловий, гарантирующих справедливость условия (13) или, что эквивалентно, (12), по аналогии с џ1 введем в рассмотрение функцию L(x, ? 1 , . . . , ? m , µ 1 , . . . , µ r ) = f (x) + m X i=1 ? i g i (x) + r X i=1 µ i h i (x), (14) которую будем называть функцией Лагранжа. При этом по аналогии с џ1 множители ? 1 , . . . , ? m и µ 1 , . . . , µ r будем назы- вать множителями Лагранжа. Принимая очевидные обозначения, перепишем равенство (14) в следующем эквивалентном виде: L(x, ?, µ) = f (x) + h?, g(x)i + hµ, h(x)i. Если условие (12) выполняется, то в силу теоремы 3 необхо- димое условие минимума в задаче дает равенство ?L(x, ?, µ) ?x i = 0, i = 1, . . . , n, которое совместно с условиями g(x) = 0 и µ i h i (x) = 0, i = 1, . . . , r 80 Гл. 2. Математическое программирование образует замкнутую систему, решение которой дает искомые значения переменных. Условия, при которых справедливо равенство (12), приня- то называть условиями регулярности. Простейшее из условий регулярности, которое будем называть первым условием ре- гулярности, выглядит следующим образом: если x ? точка минимума в задаче (3), то функции f, g 1 , . . . , g m и h 1 , . . . , h r непрерывно дифференцируемы в некоторой ее окрестности, а вектора Ѕ ?g i (x ? ), i = 1, . . . , m, ?h i (x ? ), i ? I ? (15) линейно независимы. Теорема 4. Пусть в некоторой точке x ? выполнено пер- вое условие регулярности. Тогда найдутся такие ? ? ? R m и µ ? ? R r , что ?L(x ? , ? ? , µ ? ) ?x i = 0, i = 1, . . . , n (16) и µ ? i h i (x ? ) = 0, i = 1, . . . , r, (17) где µ ? i ? 0 Доказательство. Прежде всего, заметим, что условие (17) есть условие дополняющей нежесткости и выполняется в точке x ? всегда. Далее, для всех i /? I ? запишем µ ? i = 0. Тогда, поскольку вектора (15) линейно независимы, то в силу теоремы 3 следует принять ? ? 0 6= 0, например, ? ? 0 = 1, откуда и следует равенство (16). ¤ Замечание. Легко видеть, что первое условие регуляр- ности полностью аналогично условию регулярного минимума в задаче на условный экстремум. Другими словами, теорема џ2. Нелинейное программирование 81 4 является очевидным аналогом теоремы 2. При этом следу- ет иметь ввиду, что проверку линейной независимости векто- ров (15) необходимо проделывать в точке минимума (заранее неизвестной) со всеми вытекающими отсюда последствиями. Все это, однако, не снижает исторической ценности теорем 2 и 4 (а также и теоремы 12), поскольку именно с них собственно и начиналось математическое программирование. Сформулируем теперь более тонкое условие, которое бу- дем называть вторым условием регулярности: если x ? точка минимума в задаче (3), то функции f, g 1 , . . . , g m и h 1 , . . . , h r непрерывно дифференцируемы в некоторой ее окре- стности, вектора ?g 1 (x ? ), . . . , ?g m (x ? ) линейно независимы и существует такой вектор s ? R n , что h?g i (x ? ), si = 0, i = 1, . . . , m и h?h i (x ? ), si < 0, i ? I ? . Замечание. Легко видеть, что геометрически второе ус- ловие регулярности означает следующее. В точке x ? найдется элемент s касательного пространства к ограничениям типа ра- венств, который направлен внутрь каждого из множеств h i (x ? ) ? 0, i ? I ? активных в этой точке ограничений. Теорема 5. Пусть в некоторой точке x ? выполнено вто- рое условие регулярности. Тогда найдутся такие ? ? ? R m и µ ? ? R r , что ?L(x ? , ? ? , µ ? ) ?x i = 0, i = 1, . . . , n (18) и µ ? i h i (x ? ) = 0, i = 1, . . . , r, (19) где µ ? i ? 0 Доказательство. Как и в случае теоремы 4, заметим, что условие (19) выполняется в точке x ? всегда. Далее, для всех i /? I ? положим µ ? i = 0. 82 Гл. 2. Математическое программирование Тогда, предположив, что ? ? 0 = 0, и умножив равенство ? ? 0 ?f (x ? ) + m X i=1 ? ? i ?g i (x ? ) + r X i=1 µ ? i ?h i (x ? ) = 0 (20) скалярно на s, получим X i?I ? µ ? i h?h i (x ? ), si = 0. Отсюда в силу условий µ ? i ? 0 и h?h i (x ? ), si < 0, i ? I ? имеем µ ? i = 0, i = 1, . . . , r. Поэтому равенство (20) принимает вид m X i=1 ? ? i ?g i (x ? ) = 0, где в силу теоремы 3 не все ? ? 1 , . . . , ? ? m одновременно равны нулю. Это, однако, противоречит принятой линейной незави- симости векторов ?g 1 (x ? ), . . . , ?g m (x ? ) и, значит, ? ? 0 = 1, откуда и следует равенство (18). ¤ Замечание. Теорема 5, вообще говоря, выглядит мало- привлекательно для практического использования. Однако, как будет показано в џ4, из этой теоремы можно получить очень сильное необходимое условие минимума одного важней- шего класса экстремальных задач, в котором помимо условия регулярности будет автоматически выполняться и достаточ- ное условие минимума. џ2. Нелинейное программирование 83 Существование и единственность минимума. В от- личие от задачи на условный экстремум, в задаче нелинейно- го программирования (3) достаточно просто устанавливают- ся условия существования решения. Объясняется это следую- щим. Легко видеть, что множества ограничений как в задаче на условный экстремум, так и в задаче (3) замкнуты. При этом в случае задачи на условный экстремум даже в простейших ситуациях множество Q допустимых точек не ограничено (см. примеры 2 и 3). Это приводит к тому, что вопрос о существо- вании решения задачи на условный экстремум часто остается открытым. В случае задачи нелинейного программирования (3) дело обстоит несколько иначе: добавление к ограничению (1) ограничения (2) часто приводит к тому, что множество Q допустимых точек становится ограниченным и, следовательно, компактным. Поэтому задача (3) обычно находится в услови- ях применимости теоремы Вейерштрасса (см. теорему 7 главы 1) и, значит, вопрос о существовании ее решения часто снима- ется. Что касается единственности решения задачи (3), то этот вопрос является гораздо более тонким. Как уже отмечалось ранее, в силу теорем 4 и 5 точкой минимума может быть толь- ко точка x ? Q, удовлетворяющая системе ? ? ? ? ? ?L(x, ?, µ) ?x i = 0, i = 1, . . . , n, g(x) = 0, µ i h i (x) = 0, i = 1, . . . , r, (21) где неизвестными наряду с x являются ? и µ, причем µ i ? 0. (22) Тогда, если система (21) имеет единственное решение, удовле- творяющее условию (22), то в силу теоремы 7 главы 1 и тео- рем 4 и 5 главы 2 это решение и будет единственной точкой минимума в задаче (3). На практике, однако, единственность решений системы (21) имеет место далеко не всегда, даже ес- ли минимум единственный. Последнее, например, объясняется тем, что решение системы (21) не обязано удовлетворять усло- вию (22). |