Ф.П. Васильев - Методы оптимизации (1125241), страница 86
Текст из файла (страница 86)
Далее, иа (25) при й -с оо с учетом (22) имеем (/'(е,)+ ~ ргд,.'(е,), х — е,) > 0 !УхЕХо, р,*дс(е„) =О, 1=1,,тп. (26) с' = 1 Как следует иа леммы 4.9.2 и теоремы 4.9.2, соотношения (26) означают, что е, Е Х„. Вспомним, что неравенство (23) было получено при любых ж, Е Х,. В' частности, (23) верно и при ж„ = е,. Но е, — предельная точка последовательностй (хй). Согласно лемме 2.6.10 тогда (хй) -с е„, Теорема доказана. 13 Замечание 1. Если в (5) ай — — О, то согласно (9) тогда хй „! — — ей, й т0,1, ..
с и неравенство (23) можно записать в виде [Хй + 1 — Х„[ + у[Хй + ! — Хй) ( [жй — Х,!', й т О, 1,..., !Уж, Е Х,. Польауясь произволом в выборе х„е Х„отсюда имеем [Хй — Е[> [Хй+! — Е[, р(Хй, Х) > р(Ха+1,Х ), й т0,1,. причем равенство здесь возможно лишь при хй ! —— хй — — е, Е Х„, Таким образом, при точной реализации описанного метода линеаризации расстояние от точки хй до множества Х, нли до точки е, монотонно убывает. В то же время можно отметить, что хотя и (/(хй )) с /(е ) = /, но (/(хй)) не обязательно монотонно убывает и не обязательно хй Е Х. Непрерывные и дрттие различные варианты метода линеаризации описаны и исследованы, например, в [24; 27; 29; 286; 304; 603; 606; 670, 738; 774[.
Таким образом, последовательность («й) ограничена. Отсюда и иэ (22) следует ограниченность (« /ай). Перепишем (13), (14) в виде 289 Упражнении 1. Рассмотрим задачу (3) Л* Е Ао (4) (5) 1О Ф.П Ввсввьвв 288 Гл. б. МЕТОДЫ МИНИМИЗАПИИ ФУНК1ЯИИ МНОГИХ ПЕРЕМЕННЫХ 1. Доказать, что если в (4) окамгется о„= хь при некотором й >О, то точка хь удовлетворяет необходимым условиям оптимальности. У к а з а н и е; применить теорему 4.8.! к задаче (4), затем принять мь = оь. 2. Доказать, что если выполнены условия теоремы 1, еь —— Ц й = О, 1,..., и в (4) оь — — хь при некотором й >О, то мь еХ„.
Указание: положить в (28), (1б) оь — — хь и воспользоваться леммой 4.9.2 и теоремой 4.9.2, 3. Рассмотреть метод линеаризации для задачи (1) при Хо - -Я+, гп = О. 4. Описать метод линеаризации для задачи (1) с дополнительными линейными ограничениями (аз, х) = Ь', в = ов ч- 1,..., в. 9 8. Квадратичное программирование Г(х) = -(Сх, х) + (с, х) — ~ 1и(, х Е Х, (1) Х=(хЕЕ": (а,,х) (Ь', в=1,,пц (а„х)=б', в=то+1,...,г), (2) где С вЂ” симметричная неотрицательно определенная матрица размера тв х х и, т.
е. С > 0; с, а, Е Е", Ь' Е й, в =1,..., а, (возможности туз= О, или з = тгь, или з = тть = 0 не исключаются). Задачу (1), (2) принято называть задачей квадратичного программирования: в ней квадратичная выпуклая функция минимизируется на многогранном множестве. Такие задачи возникают в различных приложениях. Задачи определения расстояния от точки до многогранного множества, проектирования на такое множество также представляют примеры задачи квадратичного программирования, когда в (1) С = 1 — единичная матрица.
Задачи вида (1), (2) часто возникают как вспомогательные при описании различных методов минимизации (см., например, $6). Поэтому важно иметь достаточно простые методы решения задачи квадратичного программирования. Оказывается, для задачи (1), 2), как и для задачи линейного программирования, существуют конечные конечношаговые) методы их решения. Для построения таких методов сначала нужно выявить некоторые специфические особенности этой задачи.
В частности, здесь полезно рассмотреть двойственную к (1), (2) задачу. Введем функцию Лагранжа задачи (1), (2): Ь(х, Л)=к(Сх, х)+(с, х)+(Л, Ах — Ь)=2(Сх, х)+(с+А Л, х) — (Л, Ь), х Е Хо — — Е, Л Е Ло — — (Л=(Л„..., Л,) Е Е" Л, > О,..., Л„> О), где А — матрица размера в х ть со строками а„..., а„б = (Ь1,, Ь').
Если ,7, > — оо, Х, ~ И, то согласно теореме 4.9.3 функция 5 (х, Л) имеет седловую точку (х„Л*), причем в силу леммы 4.9.2 Е,(х„Л*) = Сх, + с+ АтЛ' = О, Л,*((а„х„) — Ь') = О, з = 1,..., тть, х„Е Х„, Тогда двойственная к (1), (2) задача тб(Л)= )п( у (х, Л) — взьгр, Л ЕЛо, зев" 4 8. кВАДРАтичнОе пРОГРАммиРОВАние согласно теореме 4.9.5 также имеет решение, причем ,Г„=тб'= зцртб(Л)=тб(Л*)=Г(х ), х„Е Х„, Л* Е Л=(Л ЕЛ,; тб(Л)=тб*). гч При дополнительном предположении положительной определенности матрицы С, т.
е. С > О, функция тб(Л) может быть выписана явно, В самом деле, тогда С невырождена и точка минимума х = х(Л) футнкции 5(х, Л) по х Е Е однозначно определяется из системы Сх+ с+ А Л =О, так что х(Л) = — С '(с+ АтЛ). Поэтому тб(Л) = 5(х(Л), Л) = — -(с + АтЛ, С '(с + АтЛ)) — (Л, Ь) = — 2((АС 'А )Л, Л) — (АС 'с+ Ь, Л) — 2(С 'с, с), Л Е Ло, где АС 'Ат > О.
Таким образом, при С > 0 двойственная задача (5), записанная в виде — тб(Л) — +1п(, Л Е Л„ (6) также является задачей квадратичного программирования вида (1),(2), но множество Ло по сравнению с (2) имеет более простую структуру. Зная какое-либо решение Л* задачи (6), можно записать решение исходной задачи 1, 2 в виде ()() *„= — С-'(с+ АГЛ'). (7) В самом деле, при С > 0 функция 7(х) сильно выпукла и согласно теореме 4.3.1 задача (1), (2) имеет единственное решение х„, которое обязательно будет решением системы (3), (4), где Л' — решение задачи (6). И поскольку система (3) при фиксированном Л* однозначно определяет точку х., то необходимо, приходим к формуле (7).
Особенно проста задача (6) в том случае, когда в исходной задаче (1), (2) отсутствуют ограничения типа неравенств (тн = 0) и множество Х имеет вид Х =(х ЕЕ": (аг, х>=б', в =1,..., а). (8) Тогда Ло = Е', и задача (6) запишется в форме — ф(Л) в!п(, Л Е Е". (9) Множество Л решений задачи (9) в силу теоремы 4.2,3 совпадает со множеством решений системы — тб'(Л*) = АС 'АГЛ'+ АС 'с+ Ь =О.
(10) В общем случае система (10) может иметь более одного решения. Если матрица А невырожденная, т. е. векторы а„..., а, в (8) линейно независимы, то из С > 0 следует А С 'А т > О, и тогда задача (9) и, следовательно, система (10) будут иметь единственное решение. Таким образом, при С > 0 для решения задачи (1), (8) достаточно решить две системы линейных алгебраических уравнений (10), (3), Здесь могут быть использованы известные методы линейной алгебры 159; 74; 89; 192; 353).
Поскольку для линейных систем имеется принципиальная возможность получить решение за конечное число арифметических операций (например, методом исключения Гаусса), то такая возможность имеется и для задачи (1), (8) при С > О. 2. Следуя 1670), покажем, что исходная задача (1), (2) при С > 0 может быть сведена к решению конечного числа задач вида (1), (8). Здесь важную роль играет понятие особой точки задачи (1), (2). 291 290 Гк 5, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ Ь 8. КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ О п р ед ел е н и е 1.
Точка и называется особой точкой задачи (1), (2), если и Е Х и и является решением задачи 1(х) — !и1, х Е Ъ'=(х ЕЕ": (а!, х) =Ь', 1 61!)(та+1,..., з)), (11) где 1 — какое-либо подмножество индексов (1,..., гп) (возможность 1 = И не исключается). Лемма 1. Пусть в задаче (1),(2) С >О, 1„> — оо, Х, ~И. Тогда каждое решение х, задачи (1), (2) является особой точкой этой задачи. Доказательство.
Положим Х(х,) =(1: 1 < 1 < гп, (а,, х,) = Ь*') и рассмотрим задачу (11) с 1 = Х(х,). Заметим, что х, е Ъ'. Так как (а,, х,) < < Ь' при Ь ф Х(х„), 1 <1 < гп, и функция (а!, х) непрерывна, то существует такая окрестность о'(х„, г) = (х е Е": )х — х,( < е), г > О, точки х„что (а,, х) < Ь' при всех Ь ф Х(х,), 1 < Ь < гп, и х Е Я(х„г). Это значит, что и' П о(х„, с) С Х. Тогда 1(х) > 1(х„) = Х„при всех х е Ъ' Г) Я(х„е).
Таким образом, х„— точка локального минимума выпуклой задачи (11) с Х = 1(х„). По теореме 4.2.1 тогда х, является точкой глобального минимума функции 1(х) на множестве Ъ'. Следовательно, х, — решение задачи (11) с 1 = 1(х„), так что х, — особая точка задачи (1), (2). П Теорема 1. Пусть С>0, множество (2) непусто. Тогда существует конечный метод решения задачи (1), (2). Доказательство, Так как множество (1,...,гп1 имеет конечное число подмножеств 1, а всякая задача (11) при С > 0 имеет одно решение (теорема 4.3.1), то и число особых точек задачи (1), (2) конечно.
Согласно лемме 1 для отыскания решения задачи (1), (2) достаточно перебрать все ее особые точки н найти ту из них, в которой функция (1) принимает меньшее значение. Так как задача (11) имеет вид (1), (8), то каждая особая точка может быть найдена за конечное число арифметических операций. Значит, поиск решения задачи (1), (2) закончится за конечное число шагов. С) 3. Установленная в теореме 1 принципиальная возможность получения решения задачи (1), (2) за конечное число шагов имеет лишь теоретический интерес. Дело в том, что полный перебор особых точек задачи (1), (2) на практике требует слишком большого объема вычислений уже при не очень больших значениях и, в.
Опишем один из методов упорядоченного перебора особых точек задачи (1), (2), более экономичного по сравнению с полным перебором 1670). При описании этого метода можно выделить три этапа. На 1-м начальном этапе определяется, будет ли множество (2) непустым, и, если Х ф И, то находится какая-либо точка и Е Х. Здесь может быть использован, например, симплекс-метод, описанный в гл. 3. 2-й этап состоит в переходе от какой-либо точки и е Х к особой точке ш Е Х со значением 1(ш) < 1(и). Для построения такой точки ю можно воспользоваться следу!ощим итерационным процессом.
В качестве начального приближения берется и = и. Пусть известно й-е приближение и, Е Х, 1(и,) < 1(и). Определим вспомогательное приближение й, как решение задачй (11) при Х= 1(и„) =(Ь: 1 <1 < т, (а!, и„) = Ь!). Поскольку и„Е Ь', то 1(й ) < 1(и ) < 1(и). Поэтому, если й„Е Х, то в качестве требуемой особой точки можем взять ю = й„. Допустим, что й, ф Х. Тогда (а,, й,) > Ь! хотя бы для одного )' !ь 1(и„), 1 < у < тп, так что множество индексов 1, =()': (а„й ) > Ь!, )' ~ 1(и„), 1 < у' < гп) фИ, Положим и„, =и„+ о„(й, — и„), а„= ш)п[(Ь' — (а,, и„))/(аз, й„— и„)'Ь (12) 3 Из определения Х, и включения и„е Х следует, что Ь~ — (а, иь) Ь' — (а, иь) (а., йь — иь) (ЬЗ вЂ” (а., и ))+ ((а и иь) — Ь! ) поэтому 0 < а„< 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
