Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
, . . . , m, h i (x) ? 0, i = 1, . . . , r, (8) считая, что все функции f, g 1 , . . . , g m и h 1 , . . . , h r дважды диф- ференцируемы. Если для задачи (8) выполнено какое-либо условие регулярности, то соответствующее необходимое усло- вие экстремума приводит к системе уравнений ? ? ? ? ? ?L(x, ?, µ) ?x i = 0, i = 1, . . . , n, g(x) = 0, µ i h i (x) = 0, i = 1, . . . , r, (9) где L(x, ?, µ) = f (x) + h?, g(x)i + hµ, h(x)i функция Лагранжа и неизвестными наряду с x = (x 1 , . . . x n ) являются ? = (? 1 , . . . , ? m ) и µ = (µ 1 , . . . , µ r ) . При этом долж- ны выполняться условия µ i ? 0, i = 1, . . . , r, џ3. Метод Ньютона 93 вообще говоря, означающие, что система (9) может иметь мно- жество решений. Еще одна неприятная отличительная особенность системы (9) связана со следующими обстоятельствами. Во-первых, на практике вычисление матрицы вторых про- изводных функций f, g 1 , . . . , g m и h 1 , . . . , h r и ее обращение весьма обременительно, поскольку размерность системы (9) часто достаточно велика, а функции f, g 1 , . . . , g m и h 1 , . . . , h r достаточно сложны. Во-вторых, условия теоремы 6 имеют локальный харак- тер. Поэтому сходимость метода Ньютона может зависеть от выбора начального приближения. При этом, очевидно, подо- брать начальные приближения для векторов ? и µ более, чем затруднительно. Перечисленные выше обстоятельства во многих практиче- ских ситуациях оказываются весьма существенными. Поэтому непосредственное применение метода Ньютона здесь обычно связано с огромной дополнительной работой, если вообще воз- можно. Ситуация, однако, становится существенно более бла- гоприятной, если несколько изменить исходную задачу. Имен- но, следуя идеологии, использованной при доказательстве тео- рем 1 и 3, применим для нахождения решения задачи (8) метод штрафных функций. Обозначим через h + положительную часть вектора h и заменим задачу (8) последовательностью вспомогательных за- дач безусловной минимизации f k (x) = f (x) + K k 2 Г m X i=1 (g i (x)) 2 + r X i=1 (h i + (x)) 2 ! , (10) где lim k?? K k = ?. Тогда имеет место следующая теорема, приводимая здесь без доказательства ввиду тривиальности последнего (см. џ2, упражнения 5 и 6). Теорема 8. Пусть x ? локально единственное решение задачи (8) и пусть функции f, g 1 , . . . , g m и h 1 , . . . , h r диффе- ренцируемы в некоторой окрестности M точки x ? . Тогда для 94 Гл. 2. Математическое программирование каждого достаточно большого значения k в окрестности M найдется точка x k локального минимума функции f k . При этом lim k?? x k = x ? . Легко видеть, что в силу теоремы 8 условия сходимости метода (10) более чем скромны не требуется ни особой глад- кости функций f, g 1 , . . . , g m и h 1 , . . . , h r , ни выполнения усло- вий регулярности задачи (8). Единственным ограничением яв- ляется требование локальной единственности минимума. Од- нако, этот весьма скромный (с практической точки зрения) недостаток с лихвой перекрывается тем, что метод (10) не предполагает задания начального приближения для векторов ? и µ. Более того, на каждом шаге метод штрафных функций дает не только приближение для x ? , но и для векторов ? ? и µ ? , соответствующих x ? . Последнее следует из того обстоятель- ства, что при выполнении какого-либо условия регулярности справедливы равенства lim k?? K k g(x k ) = ? ? 0 ? ? и lim k?? K k h + (x k ) = ? ? 0 µ ? , в которых ? ? 0 = lim k?? 1 v u u t1 + K 2 k Г m X i=1 (g i (x k )) 2 + r X i=1 (h i + (x k )) 2 ! , причем последний предел существует (см. доказательство те- оремы 3 и упражнение 5 џ2). Поэтому метод (10) в некоторых случаях, оговоренных теоремой 6, можно применять в сочета- нии с методом Ньютона. Существенным недостатком метода штрафных функций является то, что при больших значениях K k задача безуслов- ной минимизации становится плохо обусловленной. Последнее приводит к тому, что с ростом k процесс отыскания реше- ний последовательности вспомогательных задач многократно џ3. Метод Ньютона 95 усложняется с вычислительной точки зрения. В качестве вто- рого недостатка метода (10) отметим то, что вспомогатель- ные задачи, вообще говоря, многоэкстремальны. Теорема же 8 только лишь утверждает, что среди минимумов фукнций f k найдется ко крайней мере один, достаточно близкий к мини- муму функции f. Упражнения. (1) Пусть g : R n ? R n дифференцируемая функция и пусть x ? неподвижная точка отображения g, т.е. x ? = g(x ? ) (11) и пусть x k+1 = g(x k ) (12) метод последовательных приближений для уравнения (11). Предположим, что на множестве M = {x : |x ? x ? | ? |x 0 ? x ? |} функциональная матрица g 0 удовлетворяет условию Лип- шица с постоянной L и матрица g 0 (x ? ) состоит из нулей. Покажите, что если L|x 0 ? x ? | 2 < 1, то метод (12) сходится к точке x ? , причем с квадратичной скоростью. Указание: Используйте равенство x 1 ? x ? = g(x 0 ) ? g(x ? ) ? g 0 (x ? )(x 0 ? x ? ) и упражнение 5 џ2 главы 1. (2) Пусть x ? невырожденная точка минимума гладкой функции f : R n ? R и пусть ? 2 f удовлетворяет условию Липшица в некоторой окрестности точки x ? . Покажите, что в этом случае метод x k+1 = x k ? [? 2 f (x ? )] ?1 ?f (x k ) локально сходится к x ? с квадратичной скоростью. Указание: Используйте упражнение 1. 96 Гл. 2. Математическое программирование џ4. Выпуклое программирование При использовании теоремы 3 в задаче нелинейного про- граммирования возникают вопросы, ответ на которые требует дополнительного исследования. К числу таких вопросов сле- дует отнести вопрос о том, будет ли найденный минимум гло- бальным. Ответ на этот вопрос, а также на вопросы, скажем, об условиях регулярности и достаточных условиях, вообще го- воря, нетривиален. Однако, существует одна задача матема- тического программирования, в которой ответ на все эти во- просы уже содержится в необходимых условиях экстремума. Эта задача, известная как задача выпуклого программирова- ния, имеет огромное практическое значение, поскольку полу- ченные здесь результаты носят весьма общий и законченный характер. Задача выпуклого программирования, как будет показа- но ниже, имеет большое сходство с задачей нелинейного про- граммирования. Одно из важнейших отличий состоит в том, что в задаче выпуклого программирования приходится иметь дело с выпуклыми функциями, заданными на выпуклых мно- жествах. Выпуклые функции и множества. Ранее в џ4 главы 1 изучались выпуклые функции, определенные в пространстве R n . Последнее условие представляется достаточно обремени- тельным и отказ от него позволяет, вообще говоря, существен- но расширить класс доступных для рассмотрения выпуклых функций. Подобное обобщение обычно связывают с поняти- ем выпуклого множества, формальное определение которого имеет следующий вид. Множество Q ? R n называется выпуклым, если оно це- ликом содержит каждый отрезок, концы которого лежат в Q. Другими словами, множество Q ? R n называется выпуклым, если для точек всех x, y ? Q и любого действительного числа 0 ? ? ? 1 точка ?x + (1 ? ?)y принадлежит Q. Некоторые простейшие примеры выпуклых (см. a), b)) и невыпуклых (см. c), d) ) множеств приведены на рис. 1. Пусть теперь Q некоторое подмножество пространства R n и пусть f некоторая числовая функция, определенная на џ4. Выпуклое программирование 97 &% '$ a) &% '$ m c) ' & $ % b) ' $ % $ d) Рис. 1 множестве Q. Функция f называется выпуклой на множестве Q , если для всех x, y ? Q и любого действительного числа 0 ? ? ? 1 имеет место неравенство f (?x + (1 ? ?)y) ? ?f (x) + (1 ? ?)f (y). (1) Множество Q, на котором определена выпуклая функция f, обычно обозначают D(f) и называют областью определения f. При этом из неравенства (1) следует, что область определения D(f ) выпуклой функции f есть выпуклое множество. Если множество D(f) компактно, то можно определить граничную точку множества D(f) как точку x ? D(f), каж- дая окрестность которой содержит точки, не принадлежащие D(f ) . Совокупность всех D(f) 0 точеества D(f), отличных от граничных, будем называть внутренностью множества D(f). Математический аппарат, созданный для работы с выпук- лыми функциями, заданными на выпуклых множествах, на- зывается выпуклым анализом. Выпуклый анализ, созданный сравнительно недавно, представляет собой мощное и, одновре- менно, удобное средство, позволяющее исследовать на экстре- мум не только дифференцируемые, но и просто непрерывные 98 Гл. 2. Математическое программирование выпуклые функции. Использование в полной мере техники вы- пуклого анализа, однако, требует достаточно высокой матема- тической культуры. Поэтому в дальнейшем будут рассматри- ваться только дифференцируемые функции. Теорема Куна Таккера. Рассмотрим задачу выпук- лого программирования, т.е. задачу, заключающуюся в мини- мизации выпуклой функции f : Q ? R при ограничениях типа неравенств h i (x) ? 0, i = 1, . . . , r, где Q ? R n выпуклое множество и h i : Q ? R выпуклые функции. Действуя по аналогии с џ2, запишем эту задачу в следую- щем виде f (x) ? min, h i (x) ? 0, i = 1, . . . , r, x ? Q (2) и заметим, что задача выпуклого программирования отлича- ется от задачи нелинейного программирования, рассмотрен- ной в џ2, не только выпуклостью функций f и h 1 , . . . , h r , но и формальным отсутствием ограничений типа равенств g i (x) = 0, i = 1, . . . , m. Более того, в задаче (2) весьма важным оказывается выполне- ние на множестве Q условия Слейтера: найдется такая точка x 0 ? Q , что h i (x 0 ) < 0, i = 1, . . . , r. Выполнение этих ограничений позволяет говорить об отыс- кании глобального минимума x ? задачи (2), т.е. такой точки x ? ? Q , что f (x ? ) ? f (x) для всех x ? Q. При этом условие глобального минимума ока- зывается необходимым и достаточным. Теорема 9 (Кун Таккер). Пусть f и h 1 , . . . , h r вы- пуклые функции и пусть Q выпуклое множество, такое, что Q ? D(f ) ? D(h 1 ) ? . . . ? D(h r ), џ4. Выпуклое программирование 99 причем на множестве Q выполнено условие Слейтера. Ока- зывается, что точка x ? ? Q является точкой глобального минимума в задаче (2) тогда и только тогда, когда найдут- ся такие действительные числа µ ? 1 ? 0, . . . , µ ? r ? 0 , что µ ? i h i (x ? ) = 0, i = 1, . . . , r (3) и при x ? Q L(x, µ ? 1 , . . . , µ ? r ) ? L(x ? , µ ? 1 , . . . , µ ? r ), (4) где для всех µ 1 , . . . , µ r и x ? Q L(x, µ 1 , . . . , µ r ) = f (x) + r X i=1 µ i h i (x). (5) Доказательство. Достаточность. Используя очевид- ные обозначения, перепишем неравенство (4) в следующем эк- вивалентном виде: L(x, µ ? ) ? L(x ? , µ ? ). Необходимость. Доказательство необходимости усло- вий теоремы 9 проведем лишь для случая, когда множе- ство Q представляет собой пространство R n , а все функции f, h 1 , . . . , h r дифференцируемы. 5 Пусть x ? точка минимума в задаче (3). Поскольку все функции h 1 , . . . , h r выпуклы и выполнено условие Слейтера, то, приняв s = x ? x ? , получим второе условие регулярности (см. џ2). Поэтому в силу теоремы 5 выполняются оба условия (3) и (4), причем функ- ция L имеет вид (5). Что же касается глобальности миниму- ма, то она непосредственно следует из выпуклости функций f, h 1 , . . . , h r В самом деле, пусть S i = {x ? R n : h i (x) ? 0, i = 1, . . . , r} и S = D(f ) ? S 1 ? . . . ? S r . 5 Относительно доказательства в общем случае см., например, [16]. 100 Гл. 2. Математическое программирование Каждое из множеств S i , как легко видеть, выпукло. Следова- тельно, множество S также выпукло (см. упражнение 2). То- гда, поскольку все функции f, h 1 , . . . , h r выпуклы в простран- стве R n , они также выпуклы и на множестве S (см. упражне- ние 3). Поэтому функция L, очевидно, выпукла и в простран- стве R n , и на множестве S. Следовательно, согласно предло- жению 3 главы 1 для всех x ? S имеет место неравенство L(x, µ) ? L(x ? , µ) + h?L(x ? , µ), x ? x ? i. Но в силу теоремы 5 ?L(x ? , µ ? ) = 0, причем выполнены условия (3). Тогда поскольку f (x) ? f (x ? ) для всех x ? Q, то выполнено также и условие (4). ¤ Каждую точку x, удовлетворяющую условиям h i (x) ? 0, i = 1, . . . , r, x ? Q, будем называть допустимой точкой в задаче выпуклого про- граммирования. Далее, функцию L, как и в задаче на услов- ный экстремум, здесь будем называть функцией Лагранжа, а числа µ ? 1 , . . . , µ ? r множителями Лагранжа. По причинам, которые будут указаны ниже, вектор x называют вектором прямых переменных, а вектор µ ? вектором двойственных переменных. И, наконец, как и в случае теоремы Каруша Джона, в условиях теоремы Куна Таккера условия (3) на- зываются условиями дополняющей нежесткости, а ограниче- ния, удовлетворяющие условию h i (x ? ) = 0, активными ограничениями. При этом, если h j ( |