Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
имела минимум? Максимум? (2) Принимая во внимание результаты упражнения 1, найди- те необходимое и достаточное условия минимума функ- ции f (x) = hAx, xi/2 ? hb, xi. Будет ли найденный минимум глобальным? (3) Пусть функция f : R ? R дифференцируема и пусть эта функция имеет два максимума. Тогда, как легко видеть, f имеет по крайней мере один минимум. Покажите, что в случае дифференцируемой функции f : R 2 ? R это утвер- ждение уже неверно. (4) Пусть функция f : R ? R четырежды дифференцируема в точке x ? ? R и пусть f 0 (x ? ) = 0 и f 00 (x ? ) = 0 . Пока- жите, что если f 000 (x ? ) = 0 и f IV (x ? ) > 0 , то x ? точка минимума, а если f 000 (x ? ) = 0 и f IV (x ? ) < 0 , то x ? точка максимума. (5) Предположим, что в условиях упражнения 4 f IV (x ? ) = 0 Что дальше? (6) Распространите результаты упражнений 4 и 5 на случай функции f : R n ? R Указание: Используйте упражнение 2 џ3. Глава 2 Основы общей теории математического программирования Настоящая глава посвящена изучению одного из основопо- лагающих разделов теории экстремальных задач математи- ческому программированию. Математическое означает, что оперировать здесь приходится, главным образом, математиче- ским инструментарием, а программирование говорит о том, что исследование осуществляется строго по некоторым уста- новленным правилам. И, хотя, термин математическое про- граммирование исторически сложился достаточно давно, его, видимо, нельзя считать самым удачным, поскольку он, вообще говоря, может привести к разночтениям. 1 Открывает главу џ1, в котором рассматривается простей- шая задача математического программирования задача на условный экстремум. Данная задача имеет огромное методи- ческое значение, поскольку, несмотря на ее локальный харак- тер, здесь наиболее наглядно демонстрируется общий принцип решения экстремальных задач, заключающийся в сведении за- дачи с ограничениями к задаче исследования функции на без- условный экстремум. Идея этого принципа принадлежит Ла- гранжу и потому используемый здесь прием носит название метода множителей Лагранжа. Непосредственным развитием задачи на условный экстре- мум является задача нелинейного программирования, рас- смотренная в џ2. Данная задача является наиболее общей из задач математического программирования. Приведенная в џ2 1 Именно, иногда приходится слышать, что лучшими специалистами в области математического программирования являются специалисты в области компьютерного программирования вычислители (!?). 59 60 Гл. 2. Математическое программирование теорема Каруша Джона является органичным обобщением метода множителей Лагранжа, позволяющим, вообще говоря, с единых позиций исследовать экстремальные задачи различ- ной природы. Отметим, что в џ2 доказательство теоремы о необходимом условии минимума в задаче нелинейного про- граммирования осуществляется почти теми же методами, что и доказательство аналогичных теорем в задаче на условный экстремум. Необходимые условия экстремума в задачах математи- ческого программирования приводят к некоторым системам уравнений, как правило нелинейных. Поэтому истинным на- значением необходимых условий экстремума следует считать не только получение системы уравнений, позволяющей найти минимум. Часто необходимое условие может быть использо- вано для конструирования некоторых специальных методов, приводящих к эффективным вычислительным процедурам на- хождения экстремума. Одна из таких процедур, базирующа- яся на использовании метода Ньютона, достаточно подробно описана в џ3. В џ4 рассматривается важнейшая из задач математиче- ского программирования задача выпуклого программиро- вания. Использование конкретных особенностей этой задачи (выпуклость функций и множеств, с которыми здесь прихо- дится иметь дело) позволяет получить существенно более за- конченные результаты, чем результаты џ2. В частности, основ- ной результат теории выпуклого программирования теоре- ма Куна Таккера в отличие от теоремы Каруша Джона дает не только необходимое, но и достаточное условия экстре- мума. Более того, выпуклость функций и множеств позволя- ет несколько продвинуться в исследовании задачи выпуклого программирования получить теорему о седловой точке и рас- смотреть двойственную задачу. Частным случаем задачи выпуклого программирования является задача линейного программирования, рассмотренная в џ5. Отличительной особенностью этой задачи является то, что здесь необходимое и достаточное условие экстремума (те- орема Куна Таккера) не позволяет свести экстремальную задачу к поиску решения некоторой системы уравнений, как џ1. Задача на условный экстремум 61 это было в џ1џ4. Однако конкретные особенности этой зада- чи приводят к эффективной вычислительной процедуре зна- менитому симплекс-методу, позволяющему во многих практи- ческих случаях легко найти ее решение. Описание симплекс- метода, а также некоторые вопросы его реализации приведены в џ6. И, наконец, заметим, что в џ4 и џ5 рассматриваются неко- торые приложения основных результатов џ1џ5 к задаче о рас- пределении ресурсов. џ1. Задача на условный экстремум В подавляющем большинстве практических ситуаций в различных областях человеческой деятельности исследование функций на экстремум приходится осуществлять с учетом некоторых дополнительных ограничений, учитывающих ре- альные особенности той или иной экстремальной задачи. Про- стейшей из таких задач является задача на условный экс- тремум, т.е. задача, заключающаяся в минимизации числовой функции f : R n ? R при выполнении условия g(x) = 0, где g : R n ? R m некоторая заданная функция. Задачу на условный экстремум обычно записывают в сле- дующем виде: f (x) ? min, g i (x) = 0, i = 1, . . . , m. (1) Сформулированная таким образом задача, очевидно, пред- ставляет интерес только в случае, когда n > m, что и предпо- лагается в дальнейшем. При этом необходимо отметить, что хотя задача (1) и является частным случаем общей задачи нелинейного программирования, которая будет рассмотрена в џ2, представляется более чем уместным провести ее подробное изучение, поскольку используемые здесь идеи имеют общий характер и более наглядны. Метод множителей Лагранжа. Пусть Q = {x ? R n : g i (x) = 0, i = 1, . . . , m} 62 Гл. 2. Математическое программирование множество точек, называемых допустимыми точками в за- даче (1). Точка x ? ? Q называется точкой минимума (или точ- кой локального минимума) в задаче (1), если для всех x ? Q, достаточно близких к x ? , выполнено неравенство f (x ? ) ? f (x). Необходимое условие минимума в задаче (1) дает следую- щая важнейшая для понимания предмета Теорема 1. Пусть x ? точка минимума в задаче (1) и пусть функции f и g 1 , . . . , g m непрерывно дифференцируемы в некоторой окрестности E точки x ? . Тогда найдутся та- кие действительные числа ? ? 0 , ? ? 1 , . . . , ? ? m , не все равные нулю одновременно, что ? ? 0 ?f (x ? ) + m X i=1 ? ? i ?g i (x ? ) = 0. (2) Настоящая теорема восходит еще к Лагранжу. Поэтому функцию L(x, ? 0 , ? 1 , . . . , ? m ) = ? 0 f (x) + m X i=1 ? i g i (x) будем называть расширенной функцией Лагранжа 2 а числа ? 1 , . . . , ? m множителями Лагранжа. Условие (2) вместе с системой g i (x ? ) = 0, i = 1, . . . , m образуют систему n + m уравнений относительно n + m + 1 неизвестного ? ? 0 , ? ? 1 , . . . , ? ? m , x ? . При этом велик соблазн при- нять ? ? 0 = 1 и, таким образом, замкнуть систему. Последнее, однако, мож- но делать далеко не всегда. 2 Смысл подобной терминологии станет ясен чуть ниже (см. также гл. 3, џ2). џ1. Задача на условный экстремум 63 Пример 1. Рассмотрим весьма простую и занимательную задачу о минимизации функции f (x 1 , x 2 ) = x 1 при ограничении (x 1 ) 2 + (x 2 ) 2 = 0. (3) Действуя формально, положим L(x 1 , x 2 , ? 0 , ? 1 ) = ? 0 x 1 + ? 1 ((x 1 ) 2 + (x 2 ) 2 ) и ? 0 = 1. Отсюда в силу теоремы 1 имеем 1 + 2? 1 x 1 = 0 (4) и 2? 1 x 2 = 0, (5) где ? 1 6= 0 , поскольку в противном случае ограничение (3) не учитывается функцией L. Дополнив систему (4), (5) уравне- нием (3), из уравнений (5) и (3) имеем x 1 = 0, x 2 = 0. Тогда уравнение (4) превращается в равенство 1 = 0. (!?) Возникает естественный вопрос: когда же можно записать функцию L в виде L(x, ? 1 , . . . , ? m ) = f (x) + m X i=1 ? i g i (x)? Ответ на этот вопрос часто связывают с понятием регулярно- сти точки минимума. Точка x ? ? Q называется регулярной точкой минимума, если функции f, g 1 , . . . , g m дифференцируемы в некоторой ее окрестности E, а вектора ?g 1 (x ? ), . . . , ?g m (x ? ) линейно неза- висимы. 64 Гл. 2. Математическое программирование Теорема 2. Если x ? регулярная точка минимума, то найдутся такие действительные числа ? ? 1 , . . . , ? ? m , что ?f (x ? ) + m X i=1 ? ? i ?g i (x ? ) = 0. (6) Теорему 2 принято называть теоремой о методе множи- телей Лагранжа, а функцию L функцией Лагранжа. Рас- смотренный выше пример 1 показывает, что метод множите- лей Лагранжа наверняка может быть справедлив лишь при выполнении условия регулярности, поскольку в этом приме- ре точка x 1 = 0, x 2 = 0 хотя и была точкой минимума, но не регулярной. Заметим теперь, что теорема 2 непосредственно следует из теоремы 1. В самом деле, в регулярном случае ? ? 0 6= 0 , так как иначе m X i=1 ? ? i ?g i (x ? ) = 0, где, очевидно, множители Лагранжа ? ? 1 , . . . , ? ? m не все рав- ны нулю, что противоречит линейной независимости векторов ?g 1 (x ? ), . . . , ?g m (x ? ) . Поэтому, разделив равенство (2) на ? ? 0 , с точностью до обозначений получим равенство (6). С другой стороны, если справедлива теорема 2, то справедлива также и теорема 1. Действительно, если вектора ?g 1 (x ? ), . . . , ?g m (x ? ) линейно зависимы, то по определению имеем m X i=1 µ i ?g i (x ? ) = 0, где m X i=1 µ 2 i 6= 0. Тогда равенство (2) справедливо при ? ? 0 = 0 и ? ? i = µ i , i = 1, . . . , m. Таким образом, теорема 2 следует из теоремы 1 и обратно, т.е. достаточно доказать одну из теорем 2 или 1. Ниже приво- дится доказательство теоремы 1. џ1. Задача на условный экстремум 65 Замечание. Несложно заметить, что для всех значений x ? R n и ? 1 , . . . , ? m ?L(x, ? 1 , . . . , ? m ) ?? j = g j (x), j = 1, . . . , m. Поэтому в регулярном случае необходимое условие экстрему- ма для задачи (1) иногда записывают в следующем эквива- лентном виде: ?L(x, ? 1 , . . . , ? m ) ?x i = 0, i = 1, . . . , n, ?L(x, ? 1 , . . . , ? m ) ?? i = 0, i = 1, . . . , m. (7) Доказательство теоремы 1. В настоящее время из- вестно несколько доказательств теоремы 1. Здесь приводится доказательство, которое, вообще говоря, нельзя назвать луч- шим. Основное его достоинство состоит в том, что используе- мый при данном доказательстве математический аппарат, не предполагает использования никаких дополнительных сведе- ний, не содержащихся в главе 1. Пусть ? некоторое положительное число и пусть U мно- жество точек x ? R n , для которых |x ? x ? | ? ?. Выберем число ? столь малым, что все функции f и g 1 , . . . , g m были непрерывно дифференцируемы на множестве Q?U ? E. Наряду с задачей (1) введем в рассмотрение задачу о миними- зации функции f k : R n ? R , задаваемой равенством f k (x) = f (x) + k 2 m X i=1 (g i (x)) 2 + 1 2 |x ? x ? | 2 , (8) где k некоторое натуральное число. Функция f k , очевидно, непрерывна, а множество Q ? U компактно. Поэтому согласно теореме 7 главы 1 задача о минимизации функции f k при всех значениях k имеет на мно- жестве Q ? U решение x k , т.е. существует такое x k ? Q ? U , что f k (x k ) ? f k (x ? ). 66 Гл. 2. Математическое программирование Отсюда в силу равенства (8) имеем f (x k ) + k 2 m X i=1 (g i (x k )) 2 + 1 2 |x k ? x ? | 2 ? f (x ? ) или, что эквивалентно, m X i=1 (g i (x k )) 2 ? 2 k µ f (x ? ) ? f (x k ) ? 1 2 |x k ? x ? | 2 ¶ . Поскольку для всех значений 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 = 0, т.е. lim k?? g i (x k ) = 0, i = 1, . . . , m. Выберем некоторую неограниченно возрастающую последова- тельность k 1 , k 2 , . . . , k i , . . . , lim i?? k i = ? натуральных чисел. Легко видеть, что последовательность x k 1 , x k 2 , . . . , x k i , . . . (9) ограничена. Поэтому в силу теоремы 4 главы 1 без какой-либо потери общности можно считать, что существует предел lim i?? x k i = Ї x, где Їx некоторая точка множества U. При этом g i (Ї x) = 0, i = 1, . . . , m и f (Ї x) + 1 2 |Ї x ? x ? | 2 ? f (x ? ). (10) Поскольку x ? точка минимума на Q, то f (x ? ) ? f (Ї x). |