Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
x ? ) < 0, т.е. если ограничение h j неактивно, то, очевидно, можем при- нять µ ? j = 0. џ4. Выпуклое программирование 101 Если для задачи (3) выполнены условия теоремы Куна Таккера, то точку x ? называют регулярной точкой минимума в регулярной задаче выпуклого программирования. Таким об- разом, теорема Куна Таккера утверждает, что в случае ре- гулярной точки минимума найдутся такие неотрицательные множители Лагранжа µ ? , удовлетворяющие условию допол- няющей нежесткости, что при µ = µ ? функция L достигает минимума на множестве Q в точке x ? . При этом, как и ра- нее, задача с ограничениями фактически сводится к задаче без ограничений. Замечание. Если условие Слейтера не выпоняется, то допустимое множество может оказаться слишком тощим. В этом случае теорема 9 может и не быть верной. Пример 8. Рассмотрим задачу о минимизации функции 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, 0). Поэтому условие Слейтера здесь не выполняется. Если к данной задаче применить теорему Каруша Джо- на, то в условиях этой теоремы нельзя принять ? ? 0 = 1 (см. џ2, упражнение 2). Следовательно, функцию Лагранжа здесь нельзя строить по формуле (5) и потому теорема 9 здесь неверна. Часто теорему Куна Таккера записывают в несколько ином виде, используя при этом понятие седловой точки. Пусть Q ? R n и P ? R r некоторые два множества и пусть ?: Q Ч P ? R некоторая числовая функция. Пара x ? ? Q, y ? ? P называется седловой точкой функции ? на 102 Гл. 2. Математическое программирование множестве Q Ч P , если для всех значений (x, y) ? Q Ч P вы- полнены неравенства ?(x ? , y) ? ?(x ? , y ? ) ? ?(x, y ? ). (6) Другими словами, неравенства (6) означают, что точка x ? яв- ляется точкой минимума функции ? по x на множестве Q, а точка y ? точкой максимума по y на P . При этом, если выра- жения min x?Q max y?P ?(x, y) и max y?P min x?Q ?(x, y) определены, то неравенства (6) эквивалентны цепочке ра- венств min x?Q max y?P ?(x, y) = max y?P min x?Q ?(x, y) = ?(x ? , y ? ). Таким образом, существование седловой точки позволяет менять местами операции минимизации и максимизации. Бо- лее того, существование седловой точки позволяет дать теоре- ме Куна Таккера следующую формулировку. Теорема 10 (Кун Таккер). В условиях теоремы 9 точ- ка x ? является точкой минимума в задаче (3) тогда и толь- ко тогда, когда пара (x ? , µ ? ) при некотором µ ? ? 0 является седловой точкой функции L на множестве Q Ч R r + , где R r + неотрицательный ортант пространства R r , т.е. для всех значений (x ? , µ ? ) ? Q Ч R r + L(x ? , µ) ? L(x ? , µ ? ) ? L(x, µ ? ). (7) Доказательство. Необходимость. Если x ? точка минимума в задаче (6), то в силу теоремы 9 найдется такой вектор µ ? ? R r + , что hµ ? , h(x ? )i = 0 и L(x, µ ? ) ? L(x ? , µ ? ). Но при этом L(x ? , µ ? ) = f (x ? ) + hµ ? , h(x ? )i ? L(x ? , µ) џ4. Выпуклое программирование 103 для всех µ ? R r + , поскольку h i (x) ? 0, i = 1, . . . , r. Таким образом, пара (x ? , µ ? ) является седловой точкой функции L на множестве Q Ч R r + Достаточность. Пусть (x ? , µ ? ) седловая точка. Тогда L(x ? , µ) ? L(x ? , µ ? ), откуда следует, что hµ, h(x ? )i ? hµ ? , h(x ? )i для всех µ ? R r + . Последнее, очевидно, возможно лишь тогда, когда h i (x ? ) ? 0, i = 1, . . . , r и hµ ? , h(x ? )i = 0. Поэтому для любого допустимого значения x L(x ? , µ ? ) = f (x ? ) ? L(x, µ ? ) = f (x) + hµ ? , h(x)i = f (x), т.е. x ? точка минимума в задаче (3). ¤ Теорема двойственности. Легко видеть, что в форму- лировку теоремы 10 прямые и двойственные переменные вхо- дят симметричным образом. Поэтому можно ожидать, что по- добная симметрия существует и для экстремальных задач, т.е. что неравенства (7) являются условием минимума не только для исходной задачи, но и условием максимума для некото- рой другой экстремальной задачи относительно двойственных переменных. Такую задачу можно получить из следующих со- ображений. Пусть ?(x) = sup µ?R r + L(x, µ). Тогда, очевидно, ?(x) = Ѕ f (x), h i (x) ? 0, i = 1, . . . , r, ?, h i (x) > 0. 104 Гл. 2. Математическое программирование Поэтому исходная задача (3) может быть записана в сле- дующем виде: ?(x) ? min, x ? Q. (8) Действуя аналогичным образом, поменяем роль перемен- ных и операций минимизации и максимизации. Для этого по- ложим ?(µ) = inf x?Q L(x, µ) и рассмотрим задачу о максимизации ?(µ) ? max, µ ? R r + . (9) Полученная таким способом задача (9) называется двойствен- ной, а задача (8) прямой. При этом имеет место следующая те- орема, известная как теорема двойственности выпуклого про- граммирования. Теорема 11. Справедливы следующие соотношения двой- ственности: (1) Для всех значений x ? Q и µ ? R r + f (x) ? ?(µ) (10) всякий раз, когда h i (x) ? 0, i = 1, . . . , r. (11) (2) Если прямая задача регулярна, то µ ? решение за- дачи (9), причем f (x ? ) = ?(µ ? ). (12) (3) Если для допустимых x ? и µ ? выполнено неравен- ство (11), то x ? решение прямой задачи, а µ ? двойственной. Доказательство. Последовательно докажем утвержде- ния 1, 2 и 3. (1) Если x ? Q, µ ? R r + и выполнены неравенства (11), то, очевидно, f (x) ? f (x) + hµ, h(x)i = џ4. Выпуклое программирование 105 = L(x, µ) ? inf x 1 ?Q L(x 1 , µ) = ?(µ). (2) Пусть x ? решение прямой задачи, и µ ? соответ- свующие множители Лагранжа, то в силу теоремы 10 ?(µ ? ) = L(x ? , µ ? ) ? L(x ? , µ) ? ? inf x?Q L(x, µ) = ?(µ) для всех значений µ ? R r + . Поэтому µ ? решение двойственной задачи и, следовательно, L(x ? , µ ? ) = f (x ? ). Поэтому имеет место равенство (12). (3) Пусть x ? ? Q, µ ? ? R r + и пусть выполнены неравен- ства (11). Тогда в силу неравенства (10) для произ- вольных допустимых x и µ f (x ? ) ? ?(µ ? ). Но согласно равенству (12) при этом f (x ? ) = ?(µ ? ), т.е. f (x) ? ?(µ ? ) = f (x ? ) ? ?(µ). ¤ В отличие от теорем 9 и 10 теорема двойственности 11 мо- жет оказаться чрезвычайно полезной в следующей достаточно типической ситуации. Если размерность n вектора x существенно больше числа r , то размерность r двойственной задачи существенно ниже размерности n прямой. Более того, неравенство (10) позволяет получить оценку снизу для минимума прямой задачи. Поэтому в ряде случаев, например, в задачах линейного программиро- вания (см. џ5) двойственный подход оказывается достаточно эффективным. Пример 9. Ряд важных задач в различных областях че- ловеческой деятельности (поиск неисправностей, обнаружение цели, планирование эксперимента и т.д.) естественым образом 106 Гл. 2. Математическое программирование укладывается в следующую простую схему, связанную с при- водимой ниже экономической задачей, известной как задача об оптимальном распределении ресурсов. Предположим, что име- ется некоторый ресурс и его следует наилучшим образом рас- пределить между n объектами. При этом эффективность ис- пользования ресурсов на i-ом объекте характеризуется функ- цией f i С математической точки зрения данная задача представ- ляет собой задачу о минимизации функции f (x 1 , . . . , x n ) = f 1 (x 1 ) + . . . + f n (x n ) (13) при ограничениях x 1 + . . . + x n = 1 (14) и x i ? 0, i = 1, . . . , n. (15) Обозначим через Q множество точек, для которых выполнено условие (14) и предположим, что все функции f 1 , . . . , f n выпуклы. Составим функцию Лагранжа L(x 1 , . . . , x n , ?) = f (x 1 , . . . , x n ) + ?(x 1 + . . . + x n ? 1), где ? некоторое действительное число, и введем в рассмот- рение одномерные числовые функции ? i (?) = inf x i ?0 (f i (x i ) + ?x i ), i = 1, . . . , n. (16) Тогда ?(?) = inf x?0 L(x, ?) = ? 1 (?) + . . . + ? n (?) ? ?, (17) где x = (x 1 , . . . , x n ) . Поскольку при этом Q по определению, очевидно, выпуклое множество, то в силу теоремы 10 каждая точка максимума функции ? является множителем Лагранжа для задачи (13)(15). Таким образом, для нахождения решения x ? исходной за- дачи следует прежде всего построить функции (16), затем най- ти точку максимума ? одномерной вогнутой функции (17). По- сле этого величину x ? определяют как x ? = arg min x i ?0 (f i (x i ) + ? ? x i ). џ4. Выпуклое программирование 107 Подобную процедуру часто можно осуществить простыми средствами. Например, если f i (x i ) = a i 2 (x i ? b i ) 2 , где a i > 0 , то ? i (?) = ? µ 1 2a i (a i b i ? ?) 2 + ¶ + a i (b i ) 2 2 , где (a i b i ? ?) + = max{0, a i b i ? ?}. Поэтому ? 0 (?) = Г n X i=1 1 a i (a i b i ? ?) + ! ? 1, т.е. ? 0 (?) кусочно-линейная функция. Заметим теперь, что корни уравнения Г n X i=1 1 a i (a i b i ? ?) + ! ? 1 = 0 легко найти следующим способом. Во-первых, следует упоря- дочить числа a i b i . Во-вторых, следует последовательно вычис- лять величины ? 0 (a i b i ) до тех пор, пока выражение ? 0 (a i b i ) не переменит знак. После этого величину ? ? можно найти с по- мощью линейной интерполяции. Классическая формулировка теоремы Куна Так- кера. Для восстановления исторической справедливости, рас- смотрим случай, когда задача (2) имеет вид f (x) ? min, g i (x) = 0, i = 1, . . . , m, h i (x) ? 0, i = 1, . . . , r, (18) где функции f, g 1 , . . . , g m , h 1 , . . . , h r выпуклые функции, определеные в пространстве R n Пусть x ? некоторая точка пространства R n и пусть I ? множество активных ограничений задачи (18) в этой точ- ке. Предположим, что все функции f, g 1 , . . . , g m и h 1 , . . . , h r 108 Гл. 2. Математическое программирование непрерывно дифференцируемы в некоторой окрестности точ- ки x ? , а вектора Ѕ ?g i (x ? ), i = 1, . . . , m, ?h i (x ? ), i ? I ? (19) линейно независимы. Тогда имеет место следующая Теорема 12. Точка x ? является точкой глобального ми- нимума в задаче (18) тогда и только тогда, когда найдутся такие действительные числа ? ? 1 , . . . , ? ? m и µ ? 1 ? 0, . . . , µ ? r ? 0 , что Ѕ g i (x ? ) = 0, i = 1, . . . , m, µ ? i h i (x ? ) = 0, i = 1, . . . , r (20) и ?L(x ? , ? ? 1 , . . . , ? ? m , µ , 1 . . . , µ ? r ) ?x i = 0, i = 1, . . . , n, где L(x, ? 1 , . . . , ? m , µ 1 , . . . , µ r ) = f (x) + m X i=1 ? i g i (x) + r X i=1 µ i h i (x). Доказательство. Достаточность. Применяя к функ- ции L теорему 14 главы 1, для всех x ? R n имеем L(x, ? ? 1 , . . . , ? ? m , µ ? 1 , . . . , µ ? r ) ? L(x ? , ? ? 1 , . . . , ? ? m , µ ? 1 , . . . , µ ? r ). Отсюда в силу условий (20) при этих x можем записать f (x) ? f (x ? ). Необходимость. Поскольку f, g 1 , . . . , g m и h 1 , . . . , h r дифференцируемые выпуклые функции, согласно предложе- нию 3 главы 1 для всех x ? R n имеет место неравенство L(x, ? ? 1 , . . . , ? |