Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 87
Текст из файла (страница 87)
Введем функцию Лагранжа задачи (1), (2): 1 (х, Л)=2(Сх, х)+(с, х)+(Л, Ах — Ь)=2(Сх, х)+(с+А Л, х)-(Л, Ь), х е Хо = Е", Л е Ло=(Л=(Л„..., Л,) Е Е'! Л, > О,..., Л„> О), где А — матрица размера л х и со строками а„..., а, Ь = (Ь',..., Ь').
Если ,7, > — со, Х„~Я, то согласно теореме 4.9.3 функция 1 (х, Л) имеет седловую точку (х„Л*), причем в силу леммы 4.9.2 Е.(х„Л') = Сх„+ с+ А»Л" = О, Л;((а,, х.) — Ь*)=0, з =1,..., т, х, ЕХ„, Тогда двойственная к (1), (2) задача тР(Л) = !п( Е(х, Л)- зпр, Л еЛо, ел ',Фтх * ц ,) 1 Ь 8. кВАдРАтичнОе пРОГРАммиРОВАние согласно теореме 4.9.5 также имеет решение, причем 1,=ф*= зпр тр(Л)=тр(Л*)=Дх„), х, Е Х„, Л" Е Л*=(Л Е Л: тр(Л)=тЬ*). ла При дополнительном предположении положительной определенности матрицы С, т.
е. С > О, функция тр(Л) может быть выписана явно, В самом деле, тогда С невырождена и точка минимума х = х(Л) фу»нинин 1,(х, Л) по х Е Е" однозначно определяется из системы Сх+ с + А Л = О, так что х(Л) = — С '(с + А»Л). Поэтому тР(Л) = 1 (х(Л), Л) = — — (с + А" Л, С '(с+ А Л))— — (Л, Ь) = — 2((АС 'А")Л, Л) — (АС 'с+ 5, Л) — 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) запишется в форме -тр(Л) — !п1, Л Е Е'. (9) Множество Л* решений задачи (9) в силу теоремы 4.2.3 совпадает со множеством решений системы — тР(Л*) = АС 'А'Л*+ АС 'с+ Ь =О. (10) В общем случае система (10) может иметь более одного решения. Если матрица А невырожденная, т. е. векторы а„..., а, в (8) линейно независимы, то из С > О следует АС-'А» > О, и тогда задача (9) и, следовательно, система (10) будут иметь единственное решение. Таким образом, при С > 0 для решения задачи (1), (8) достаточно решить две системы линейных алгебраических уравнений (10), (3). Здесь могут быть использованы известные методы линейной алгебры [59; 74; 89; 192; 353).
Поскольку для линейных систем имеется принципиальная возможность получить решение за конечное число арифметических операций (например, методом исключения Гаусса), то такая возможность имеется и для задачи (1), (8) при С > О. 2, Следуя [б?0], покажем, что исходная задача (1), (2) при С > 0 может быть сведена к решению конечного числа задач вида (1), (8).
Здесь важную роль играет понятие особой точки задачи (1), (2). 290 Гк 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 291 $ 3. КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ О п р е де лен не 1. Точка и называется особой точкой задачи (1), (2), если и й Х и о является решением задачи ,Х(х) — >!п1, хй Ъ'=(хе Е": (а(, х) = Ь', ! 61О(т+1,..., в)), (11) где 1 — какое-либо подмножество индексов (1,..., т) (возможность 1 =И не исключается).
Лемма 1. Пусть в задаче (1),(2) С>0, Х„> — со, Х,фИ. Тогда каждое решение х, задача (1), (2) является особой точкой этой задачи. Доказательство. Положим Цх) =(>Ч 1 < > < т, (а(, х) = 6(! и рассмотрим задачу (11) с 1 = Цх.). Заметим, что х. Е Ъ'. Так как (а,, х,) < < 6' при ! ~ Цх„), 1 < ! < т, и функция (а(, х) непрерывна, то существует такая окрестность Я(х„, е) = (х е Е: !х — х,~ < г~, е > О, точки х„что (а(, х) < 6' при всех ! ф Цх„), 1 < ! < т, и х Е Я х„, е).
Это значит, что Ъ'Г> 8(х„е) с Х. Тогда Х(х) > Х(х,) = Х, при всех х й Ъ'О Я(х„, в). Таким образом, х. — точка локального минимума выпуклой задачи (11) с 1 = Х(х.). По теореме 4.2.1 тогда х, является точкой глобального минимума функции Х(х) на множестве Ъ". Следовательно, х, — решение задачи (11) с 1 = Х(х.), так что х, — особая точка задачи (1), (2).
0 Теорема 1. Пусть С >О, множество(2) непусто. Тогда существует конечный метод решения задачи (1), (2). Доказательство. Так как множество (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), более экономичного по сравнению с полным пе ебором [670).
При описании этого метода можно выделить три этапа. а 1-м начальном этапе определяется, будет ли множество (2) непустым, и, если Х ~ И, то находится какая-либо точка и й Х. Здесь может быть использован, например, симплекс-метод, описанный в гл. 3. 2-й этап состоит в переходе от какой-либо точки и е Х к особой точке ю й Х со значением Х(ю) < Х(и). Для построения такой точки ю можно воспользоваться следу>ощнм итерационным процессом. В качестве начального приближения берется и = и. Пусть известно й-е приближение и„й Х, Х(и„) < Х(и).
Определим вспомогательное приближение й, как решение задачй (11) при 1 = Х(и„) = (>'; 1 < з' < гп, (а,, и„) = 6(Х. Поскольку и, е Ь', то Х(й„) < 1(и„) <,Х(и). Поэтому, если й„е Х, то в качестве требуемой особои точки можем взять ю = й„. Допустим, что й„ф Х, Тогда (а>ч й„) > Ьз хотя бы для одного >' (р Ци„), 1 < у' < т, так что множество индексов Х, = и: (а,, й„) > Ь', у' ф Ци„), 1 < у' < т) ф И.
Положим и,э, = и„+ а„(й — иь), а„= пнп [(6' — (а,, и„))/(аз, й„— и„)[. (12) > 1 Из определения Х, и включения и е Х следует, что ' — (,,) ' — (, ( —" ) (Π— (,,))+((;»,) — )') поэтому 0 < аь < 1. Покажем, что и,. э, е Х. Из выпуклости множества г' и О из и, е !', й, Е У следует, что и,, Е Тг, где У взято из (11) при 1= 1(и ). стается доказать, что (а,, и„~() < Ьз при всех У ф Ци,), 1 < У < т. Если (( >' й Хо то с учетом определения (12) величины а„имеем (а,, и„,) = (а,, и„) + а,(а,, й — и ) < 6', У Е 1,.
(13) Если Уф 1 ОХ(и„), 1<> < т, то (а,, и„+,) =с(„(аг, йь)+(1 — а )(а,, иь) < Ь', Таким образом, показано, что и.э, й Х. Далее, поскольку Х(йь) < Х(и ) < < Х(о) и функция 1(х) выпукла, то Х(и„„() < с(, Х(йь)+(! — а„)Х(иь) < 1(е). Далее, из включения и„, Е Ь', где !>' взято из (11) при 1 = Ци„), следует, что Ци„) С Ци...) = (Г; (а(, и„,) = Ь', 1 < г < т), В то же время для тех >', й 1„для которых в (12) реализовывается минимальное значение прн определении а„, неравенство (13) превращается в равенство, так что >', й Ци„,), но >' ф Ци,). Следовательно, множество Ци„„) содержит по крайней мере на один элемент больше, чем Х(и,.). Таким образом, следующее приближение и„, е Х со значением Х(и,э,) < Г(о) построено, причем множество Ци,э,) существенно шире Х(и,).
Однако множества Ци,) й (1,..., т) не могут бесконечно расширяться, и поэтому описанный процесс закончится на какой-то й-й итерации, когда и, е Х, причем ю = й, — особая точка задачи (1), (2) со значением 1(ю) < Г(и). Поскольку решаемая на каждой итерации задача (11) с 1 = Ци„) имеет вид (1), (8) и для ее решения существует конечный метод, то и весь переход от точки и к точке ю осуществим за конечное число шагов. На 3-м этапе выясняется, не будет ли особая точка ю, построенная на 2-м этапе, решением задачи (1), (2), и в том случае, если ю ф Х„ осуществляется переход к следующеи точке г й Х, для которой 1(г) < 1(ю), Для этих целей достаточно совершить один шаг несколько модифицированного метода условного градиента, приняв в качестве начальной точку'ю, полученную на 2-м этапе.
А именно, сначала можно решить следующую задачу линейного программирования (Х'(ю), е) =(Сю+с, е) -+!п1, е еб=(е =(е',..., е ) ЕЕ": (а(, е) <О, 4 ЕЦю)=(1: 1 < ! < т, (а,, ю) =Ь()) (а„е) = О, Г = т + 1,..., в, — 1 < е' < 1, У = 1,..., п).
(14) Пусть е = е, — решение задачи (14), которое может быть получено, например, симплекс методом. Так как е = Одаб, то >> = (1(ю), е ) = ш!п(1(ю), е) < еег < (Х'(ю),0) = О. Поэтому имеются две возможности: либо д = О, либо )б < О. Покажем, что в случае !У =0 точка ю — решение задачи (1), (2). С этой целью возьмем произвольную точку и й Х, и ~ ю, и положим е = г(и — ю), где ! > 0 столь мало, что !е') = г !и' — ю'[ < 1, г' = 1,..., и. Если > й Цю), то (а., е) = (а,, и — ю) ! = ((а,, и) — 6')! < О. Если т+ 1 < >' < г, то (а,, е) = т((а(, и) — Ь') = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
