Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 75
Текст из файла (страница 75)
Указание: положить в (25), (15) и» = и» в воспользоваться лоыыой 4.9.2 в теоремой 4.9.2. 3. Рассыотреть метод лвпеарззацзи для задачи (1) при Пр = Е~+, и< = О. 4. Описать метод лвкеаризацив для задачи (1) с дополпитвльпыыа лзнейныып ограничеппями <а<, и> = Ь< (1 = <и+ 1, ..., »). 3 7. Квадратичное программирование 1.
Рассмотрим задачу г'(и) = — (Си, и) + (с, и)-<-ш1, и~(<'» 1 С=(иыЕ": <аь и><Ь« 1=1, ..., т; <а<, и> = Ь', 1= т+1, ..., з), (2) где С вЂ” симметричная неотрицательно определенная матр<ща размера п><п, т. е.
С~О; с, а<шЕ", Ь'<иВ (1 1, ..., в) (возможности т = О, или з т, или з = т = О не исключаются). Задачу (1), (2) принято называть задачей квадратичного программирования: в ней квадратичная выпуклая функция минимизируется на многогранном множестве. Такие задачи возникают в различных приложениях. Задачи определения расстояния от точки до многогранного множества, проектирования на такое множество также представляют примеры задачи квадратичного программирования, когда в (1) С=1 — единичная матрица. Задачи вида (1), (2) часто возникают как вспомогательные прп описании различных методов минимизации (см., например, 3 6). Поэтому важно иметь достаточно простые методы решения задачи квадратичного программирования. Оказывается, для задачи (1), (2), как и для задачи линейного программирования, существуют конечные (конечношаговые) методы нх решения.
Для построения таких методов сначала нужно выявить некоторые специфические особенности этой задачи. В частности, здесь полеано рассмотреть двойственную к (1), (2) задачу. кВАДРАтичнов пРОРРАммиРОВАНВВ 315 Введем функцию Лагранжа задачи (1), (2): Е (и, Л) = — (Си, и) + (с, и) + (Л, Аи — Ь) = — (Си, и) + (с+ 1 1 + А Л, и) — (Л, Ь), и ен У, = Е", Л ен Лз = (Л = (Лм ..., Л,) ~ ен Е'. Л, ) О, ..., Л ) 0), где А — матрица размера э Х п со строками ап ..., а„Ь (Ь', ..., Ь'). Если У„) — оо, У,.„ФйУ, то согласно теореме 4.9.4 функция Е(и, Л) имеет седловую точку (ие, Л*), причем в силу леммы 4.9.2 )=Си +с+А ЛР=О, ди Л1((а1,иа) — Ь)=0, 1=1, ...,г; из~Се Тогда двойственная к(1), (2) задача зр(Л) = ш1 Е(и, Л)-~-зпр, Л~ Л, ЯЕ Вз (9) (4) (5) согласно теореме 4.9.6 также имеет решение, причем У,„= ф* = впр зР (Л) = ~Р (Ле) = У (и„), иа ~ Уе, Л* ен Ле = л, где АС 'Аг> О.
Таким образом, при С>0 двойственная задача (5), записанная в виде — ф(Л) -~- 1В1, Л ~и Л„ (6) также является задачей квадратичного программирования вида (1), (2), но множество Л, по сравнению с (2) имеет более простую структуру. Зная каное-либо решение Л* задачи (6), можно записать решение исходной задачи (1), (2) в виде и = — С ~(с+А Ле). (7) В самом деле, при С> 0 функция У(и) сильно выпукла и согласно теореме 4.3А задача (1), (2) имеет единственное решение = (Л ен Л: ъР (Л) = Фв). При дополнительном предположении положительной определенности матрицы С, т. е.
С> О, функция ф(Л) может быть выписана явно. В самом деле, тогда С невырождена и точна минимума и =и(Л) функции Е(и, Л) при ишЕ" однозначно определяется из системы Си+ с+А'Л О, так что и(Л)= — С '(с+АтЛ). Поэтому 9 (Л) = Е (и (Л), Л) = — — (с+ А Л, С '(с + А Л)) — (Л, Ь) = = — — ((АС 'А ) Л, Л) — (АС 'с+ Ь,Л) — — (С ~с, с), Лен Л, 316 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ (ГЯ, 5 ив, катаров обязательно будет решением системы (3), (4), где Л* — решение задачи (6).
И поскольку система (3) при фиксиРованном Ле одиозначно опРеделЯет точкУив, то необходимо пРпходим к формуле (7). Особенно проста задача (6) в том случае, когда в исходной задаче (1), (2) отсутствуют ограничения типа неравенств (кг = 0) и множество П имеет вид П (и~Е": <ав и) =Ь', 1 1, ..., з). (8) Тогда Л, =Е', и задача (6) запишется в форме -ф(Л)- ш(, Л~пЕ'.
(9) Множество Лз решений задачи (9) в силу теоремы 4.2.3 совпадает со множеством решений системы — ф'(Л*)= АС 'А'Л*+ АС 'с+ Ь = О. (10) В общем случае система (10) может иметь болев одного решения. Нели матрица А невырожденная, т. е. векторы а„..., а. в (8) линейно независимы, то из С>0 следует АС 'А'>О, и тогда задача (9) и, следовательно, система (10) будут иметь единственное решение. Таким образом, при С>0 для решения задачи (1), (8) достаточно решить две системы линейных алгебраических уравнений (10), (3). Здесь могут быть использованы известные методы линейной алгебры (4, 39, 54, 93, 164).
Поскольку для линейных систем имеется принципиальная возможность получить решение за конечное число арифметических операций (например, методом исключения Гаусса), то такая возможность имеется и для задачи (1), (8) при С>0. 2. Следуя [21), покажем, что исходная задача (1), (2) при С> 0 может быть сведена к решению конечного числа задач вида (1), (8). Здесь важную роль играет понятие особой точки задачи (1), (2).
О и р е д е л е н и е 1. Точка о называется особой точкой задачи (1), (2), если аж П и о является решением задачи 1(и)- 1п(, иж т'= (и~К": <а„и) = Ь', (ж10 (и+1, ..., зП, (11) где 1 — какое-либо подмножество индексов (1, ..., т) (возможность 1 = О не исключается) . Лемма 1. Пусть е задаче (1), (2) С>0, 1в) — оо, П„~ Ф м(. Тогда каждое решение ив задачи (1), (2) является особой точкой втой задачи. Д о к а з а т е л ь с т в о. Положим 1 (и„) = ( 0 1 ~ ~(~ (т, (аи из) = = Ь') и рассмотрим задачу (11) с 1 =1(из).
Заметим, что и,„ее(т. Так как (аь ия) ( Ь' при ( ф 1 (ик) (1 < ( ( т) и функция (а ~в и) непрерывна, то существует такая окрестность Я(и,„, е) = (и еи Е": кВАДРАтичнОе пРОРРАммиРОВАнпе ) и — и, ) (з) (з) О) точки и,что (аь и)(Ь' прп всех гф1(и 1 (1<~1((т) и ия д(и„, е). Это вначит, что Р ПЮ(иэ,е)сУ Тогда г (и) ~)У(и„) = Уэ при всех и е= г Д Я(и„„з). Таким образом, иэ — точка локального минимума выпуклой задачи (11) с 1 =1(иэ).
По теореме 4.2.1 тогда и является точкой глобального минимума функции Х(и) на множестве г'. Следовательно„ и — решение задачи (11) с 1 =1(и ), так что и — особая точка задачи (1), (2). Теорема 1. Пусть С)0, множество (2) непусто. Тогда существует конечный лвтод решения задачи (1), (2). Доказательство. Так как множество И, ..., т) имеет конечное число подмножеств 1, а всякая задача (11) при С~О имеет одно решение (теорема 4.3.1), то и число особых точек задачи (1), (2) конечно.
Согласно лемме 1 для отыскания решения задачи (1), (2) достаточно перебрать все ее особые точки и найти ту из них, в которой функция (1) принимает меньшее значение. Так как задача (11) имеет вид (1), (8), то каждая особая точка может быть найдена за конечное число арифметических операций. Таким образом, поиск решения задачи (1), (2) закончится за конечное число шагов. 3. Установленная в теореме 1 принципиальная возможность получения решения задачи (1), (2) за конечпое число шагов имеет лишь теоретический интерес.
Дело в том, что здесь мы не учли возможную неустойчивость систем (3), (10) по отношению к погрешности задания исходных данных, к погрешности округления при выполнении арифметических операций. Кроме того, полньш перебор особых точек задачи (1), (2) на практике требует слишком большого объема вычислений уже при не очень болыпих значениях и, г. Опишем один из методов упорядоченного перебора особых точек задачи (1), (2), более экономичного по сравнению с полным перебором (21]. Прн описании этого метода можно выделить три этапа.
На 1-м начальном этапе определяется, будет лн множество (2) непустым, н если 0" ФО, то находится какая-либо о~а О'. Здесь может быть использован, например, симплекс-метод, описанный в главе 3. 2-й этап состоит в переходе от какой-либо точки о ~ (7 к особой точке ш ~к У со значением у(ш) ~ у(о). Для построения такой точки и можно воспользоваться следующим итерационным процессом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
