Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
f (x 1 , x 2 ) = (x 1 ) 2 + (x 2 ) 2 (23) при ограничениях x 1 + x 2 = 1, (24) x 1 ? 0 (25) и x 2 ? 0. (26) Положим g(x 1 , x 2 ) = x 1 + x 2 ? 1, h 1 (x 1 , x 2 ) = ?x 1 и h 2 (x 1 , x 2 ) = ?x 2 . Тогда, поскольку для всех значений x 1 и x 2 ?g(x 1 , x 2 ) = (1, 1), ?h 1 (x 1 , x 2 ) = (?1, 0) и ?h 2 (x 1 , x 2 ) = (0, ?1), то заметив, что только одно из ограничений (25) или (26) мо- жет быть активным, видим, что для задачи (23)(26) будет выполняться первое условие регулярности. Поэтому без какой- либо потери общности можно принять L(x 1 , x 2 , ?, µ 1 , µ 2 ) = (x 1 ) 2 + (x 2 ) 2 + ?(x 1 + x 2 ? 1)+ +µ 1 (?x 1 ) + µ 2 (?x 2 ). В силу теоремы 4 уравнения (21) для рассматриваемой задачи примут вид ? ? ? ? ? ? ? ? ? ? ? 2x 1 + ? ? µ 1 = 0, 2x 2 + ? ? µ 2 = 0, x 1 + x 2 = 1, ?µ 1 x 1 = 0, ?µ 2 x 2 = 0, (27) џ2. Нелинейное программирование 85 где µ 1 ? 0, µ 2 ? 0. (28) Легко видеть, что при выполнении условия (28) система (27) имеет единственное решение x ?1 = 1 2 , x ?2 = 1 2 , (29) ? ? = ?1, µ ? 1 = 0, µ ? 2 = 0. При этом, как несложно заметить, множество, задаваемое со- отношениями (24)(26), компактно, поскольку представляет собой отрезок прямой (24), заключенный между точками (0, 1) и (1, 0). Следовательно, точка (29) является точкой минимума в задаче (23)(26). Пример 6. Рассмотрим задачу о минимизации функции f (x 1 , x 2 ) = ?(x 1 ) 2 ? (x 2 ) 2 (30) при ограничениях (24)(26). Действуя как и в примере 5, по- ложим g(x 1 , x 2 ) = x 1 + x 2 ? 1, h 1 (x 1 , x 2 ) = ?x 1 и h 2 (x 1 , x 2 ) = ?x 2 . Тогда, поскольку для всех значений x 1 и x 2 ?g(x 1 , x 2 ) = (1, 1), ?h 1 (x 1 , x 2 ) = (?1, 0) и ?h 2 (x 1 , x 2 ) = (0, ?1), то заметив, что только одно из ограничений (25) или (26) мо- жет быть активным, видим, что для задачи о минимизации функции (30) при ограничениях (24)(26) будет выполняться первое условие регулярности. Поэтому без какой-либо потери общности можно принять L(x 1 , x 2 , ?, µ 1 , µ 2 ) = ?(x 1 ) 2 ? (x 2 ) 2 + ?(x 1 + x 2 ? 1)+ +µ 1 (?x 1 ) + µ 2 (?x 2 ). 86 Гл. 2. Математическое программирование В силу теоремы 4 уравнения (21) для рассматриваемой задачи примут вид ? ? ? ? ? ? ? ? ? ? ? ?2x 1 + ? ? µ 1 = 0, ?2x 2 + ? ? µ 2 = 0, x 1 + x 2 = 1, ?µ 1 x 1 = 0, ?µ 2 x 2 = 0, (31) где µ 1 ? 0, µ 2 ? 0. (32) Легко видеть, что при выполнении условия (32) система (31) имеет решения x ?1 = 0, x ?2 = 1, ? ? = 2, µ ? 1 = 2, µ ? 2 = 0, x ?1 = 1, x ?2 = 0, ? ? = 2, µ ? 1 = 0, µ ? 2 = 2 и x ?1 = 1 2 , x ?2 = 1 2 , ? ? = 1, µ ? 1 = 0, µ ? 2 = 0. При этом, как уже отмечалось в примере 5, множество (24) (26) представляет собой отрезок прямой (24), заключенный между точками x ?1 = 0, x ?2 = 1 (33) и x ?1 = 1, x ?2 = 0. (34) Следовательно, задача о минимизации функции (30) при огра- ничениях (24)(26) имеет по крайней мере одно решение, т.е. по крайней мере одна из точек (33), (34) или x ?1 = 1 2 , x ?2 = 1 2 (35) является точкой минимума. На самом же деле несложно заме- тить, что каждая из точек (33) и (34) является точкой локаль- ного минимума, а точка (35) точкой локального максимума (см. пример 3). џ2. Нелинейное программирование 87 Упражнения. (1) Точка x ? ? Q называется локально единственной точкой минимума задачи (3), если для всех точек x ? Q, доста- точно близких к x ? , выполнено неравенство f (x ? ) < f (x). Покажите, что если x ? локально единственная точка минимума в задаче (3), то при доказательстве теоремы 3 слагаемое 1 2 |x ? x ? | 2 в правой части равенства (5) можно опустить. (2) Используя теорему 3, рассмотрите задачу о минимизации функции f (x 1 , x 2 ) = x 2 при ограничениях (x 1 ? 1) 2 + (x 2 ) 2 ? 1 ? 0 и (x 1 + 1) 2 + (x 2 ) 2 ? 1 ? 0 и покажите, что здесь нельзя принять ? ? 0 = 1. (3) Пусть Q симметрическая положительно определенная матрица. Найдите минимум функции f (x) = hQx, xi/2 ? hp, xi при ограничениях A 1 x = b 1 и A 2 x ? b 2 . (4) Пусть x + положительная часть вектора x ? R n , т.е. x i + = max{0, x i }, i = 1, . . . , n. Для некоторого натурального числа k положим f k (x) = f (x)+ + K k 2 Г m X i=1 (g i (x)) 2 + r X i=1 (h i + (x)) 2 ! + 1 2 |x ? x ? | 2 , (36) где lim k?? K k = ?. 88 Гл. 2. Математическое программирование Докажите теорему 3, используя штрафную функцию (36) вместо штрафной функции (5). (5) Покажите, что если x ? локально единственная точка минимума в задаче (3), то при доказательстве теоремы 3 в штрафной функции (36) слагаемое 1 2 |x ? x ? | 2 можно опустить. џ3. Метод Ньютона в нелинейном программировании В обычных курсах анализа изучение задач математиче- ского программирования как правило заканчивается выво- дом необходимых и, иногда, достаточных условий экстремума. Дальнейшее их исследование опускается, поскольку считает- ся, что полученные условия позволяют найти решение задачи: К науке, которую я в настоящий момент представляю, это не имеет отношения. Данный бессмертный тезис незабвенного предводителя уездного дворянства К. Воробьянинова 3 ни в коей мере не может удовлетворить ни математика, ни экономиста, ни, тем более, вычислителя. Это объясняется тем, что необходимые условия, как в задаче на условный экстремум, так и в зада- че нелинейного программирования, приводят к многомерным системам уравнений. Поэтому все (или почти все) задачи, ко- торые удается решить до конца, являются специально подо- бранными типами примеров, кочующими из одного учебника в другой (см. примеры 26). Особенно это относится к задачам нелинейного программирования, поскольку теорема Каруша Джона (как, впрочем, и приводимая ниже в џ4 теорема Куна Таккера) всегда приводит к нелинейной системе. Поэтому ис- тинное назначение необходимых условий экстремума состоит не столько в получении некоторой системы уравнений, сколь- ко в их использовании для конструирования некоторых специ- альных методов, приводящих к эффективным вычислитель- ным процедурам нахождения экстремума. К числу одного из 3 Если угодно, он же И.М. Воробьянинов, он же К.К. Михельсон. џ3. Метод Ньютона 89 таких наиболее часто употребляемых в нелинейном програм- мировании методов относится знаменитый метод Ньютона и его многочисленные модификации. Метод Ньютона. Данный метод, являющийся одним из простых и важнейших в идейном смысле, в чистом виде на практике применяется крайне редко. Его основное назначение состоит в том, что он служит некоторым надежным скелетом при построении более реалистичных методов. Метод Ньютона, вообще говоря, связан с проблемой отыс- кания решений уравнения g(x) = 0, (1) где g : R n ? R n функция, определенная и дифференциру- емая в пространстве R n . Обозначим через x 0 некоторое при- ближение к решению x ? уравнения (1). Поскольку функция g дифференцируема в точке x 0 , то по определению имеем g(x) = g(x 0 ) + g 0 (x 0 )(x ? x 0 ) + o(x ? x 0 ). (2) Принимая во внимание уравнение (1), из равенства (2) по- лучим g(x 0 ) + g 0 (x 0 )(x ? x 0 ) + o(x ? x 0 ) = 0. (3) Тогда, если считать, что величина |x ? x 0 | достаточно мала в некоторой окрестности точки x 0 , то уравнение (3) приближен- но эквивалентно линеаризованному уравнению g(x 0 ) + g 0 (x 0 )(x ? x 0 ) = 0. (4) Обозначим через x 1 решение уравнения (4). Тогда можем записать x 1 = x 0 ? g 0 (x 0 ) ?1 g(x 0 ), если, конечно, матрица g 0 (x 0 ) невырождена. Продолжая этот процесс итеративно, на k-ом приближении имеем следующее линеаризованное уравнение g(x k ) + g 0 (x k )(x ? x k ) = 0. Отсюда в предположении, что матрица g 0 (x k ) невырождена, получим рекуррентную формулу x k+1 = x k ? g 0 (x k ) ?1 g(x k ). (5) 90 Гл. 2. Математическое программирование Формула (5) представляет собой один из основных методов отыскания решений уравнения вида (1), известный как метод Ньютона. Сходимость метода Ньютона к какому-либо реше- нию уравнения (1) устанавливает следующая теорема, приво- димая здесь без доказательства 4 : К науке, которую я в насто- ящий момент представляю, это не имеет отношения. Теорема 6. Пусть уравнение (1) имеет решение x ? , та- кое, что функция g дифференцируема в некоторой окрестно- сти M точки x ? , и пусть функциональная матрица g 0 удо- влетворяет условию Липшица на множестве M. Тогда, если матрица g 0 (x ? ) невырождена, то найдется такое значение ? > 0 , что при |x 0 ? x ? | ? ? метод (5) сходится к x ? с квад- ратичной скоростью: |x k+1 ? x ? | ? ?|x k ? x ? | 2 , k = 0, 1, 2, . . . , где ? положительное число, не зависящее от k. Все условия теоремы 6 существенны и усилить ее утвер- ждение, вообще говоря, нельзя. Пример 7. Дифференцируемость функции g и невыро- жденность функциональной матрицы g 0 используются в самой формулировке метода (5). Вместе с тем, отказ от условия Лип- шица для g 0 может привести к снижению скорости сходимости метода. В самом деле, пусть g : R ? R функция, задаваемая ра- венством g(x) = x 3/2 . Тогда при x ? 0 g 0 (x) = 3 2 x 1/2 и, как легко видеть, g 0 не удовлетворяет условию Липшица. При этом метод (5) при x 0 > 0 имеет вид x k+1 = x k ? 2 3 x ?1/2 k · x 3/2 k = 1 3 x k . 4 См. [16], где приводится обширная библиография и комментарий по этому поводу. џ3. Метод Ньютона 91 Поэтому x k = µ 1 3 ¶ k x 0 , т.е. метод сходится к точке x ? = 0 со скоростью геометриче- ской прогрессии, но не с квадратичной скоростью. Замечание. Для сходимости метода (5) не требуется ни симметричности, ни положительной определенности матрицы g 0 , как это иногда ошибочно утверждается. Метод Ньютона в задачах на безусловный экстре- мум. Рассмотрим задачу о минимизации некоторой числовой функции f : R n ? R . При этом будем считать, что функция f дважды дифференцируема. Если f квадратичная функция, т.е. если f (x) = 1 2 hQx, xi ? hp, xi, где Q симметрическая положительно определенная матрица, то решение этой задачи можно получить, используя результа- ты џ4 главы 1 (см. упражнения 1 и 2 к џ4 главы 1). Поэтому в общем случае представляется достаточно уместным исполь- зовать квадратичные аппроксимации функции f. Пусть x k некоторое приближение к точке x ? миниму- ма функции f. Рассмотрим квадратичную аппроксимацию f k функции f в точке x k f k (x) = f (x k ) + h?f (x k ), x ? x k i + 1 2 h? 2 f (x k )(x ? x k ), x ? x k i. Если матрица ? 2 f (x k ) положительно определена, то фун- кция f k достигает в пространстве R n безусловного минимума. Выберем точку x k+1 минимума функции f k в качестве нового приближения к x ? , т.е. x k+1 = arg min x?R n f k (x). Тогда имеем x k+1 = x k ? [? 2 f (x k )] ?1 ?f (x k ). (6) Формула (6) представляет собой метод Ньютона для за- дачи на безусловный экстремум. К этому методу можно прий- ти как изложенным выше путем, так и исходя из того, что 92 Гл. 2. Математическое программирование точка x ? должна быть решением системы ?f (x) = 0. (7) Применяя к уравнению (7) метод (5), получаем формулу (6). Поэтому в силу теоремы 6 главы 2 и теоремы 13 главы 1 имеет место следующая Теорема 7. Пусть функция f дважды дифференцируе- ма в некоторой окрестности M точки невырожденного ми- нимума x ? и функциональная матрица ? 2 f удовлетворяет условию Липшица на множестве M. Тогда найдется такое значение ? > 0, что при |x 0 ? x ? | ? ? метод (6) сходится к точке x ? с квадратичной скоростью. Замечание. Легко видеть, что метод (6) пригоден для отыскания не только точек экстремума функции f, но и дру- гих стационарных точек, например, седловых. Кроме того, здесь как и в случае теоремы 6, выпуклость функции f здесь не предполагается и в чистом виде не используется. Метод штрафных функций. Рассмотрим задачу нели- нейного программирования f (x) ? min, g i (x) = 0, i = 1 |