XIV Аттетков и др. Методы оптимизации (1081420), страница 49
Текст из файла (страница 49)
Подставляя х = хй 1+ кр в квадратичную функцию и учитывая, что матрица О симметрическая и в данном случае Ях +с,р ) = (8гас17е(х ), р ) = — 1то .р ), где то = — 8тас11" (х" )., получаем 'фй(к) = — Яр', р ) — к(1о ',р")+ — Ях" ",х' ')+(с,х" '). Случай (Яр~, р ) = О для положительно определенной матрицы соответствует равенству рй = х" — хй ' = О и уже рассмотрен выше.
При Яр~, рй) > О имеем относительно к квадратный трехчлен, достигайощий минимума при значении ( й й) нй. — — >О, (8.7) поскольку для направления спуска р (и~, р ) = — (8таоЯх ), х — х ) > О Спуск в возможном направлении из точки хй б Й позволяет на каждой й-й итерации продолжить построение релаксационной последовагпельносьчи 1хй), для которой последовательность 17е(хй)) ЯвлЯетсЯ невозРастающей. Рассмотрим теперь вопрос о выборе значения кй Е (О, 1] в 18.5). Один из возможных вариантов — это поиск минимума функции 342 8. е|ИСЛЕЕШЪ|Е М|Е7 ОДЪ| и в данном случае 8гае||о(х~ ~) и р~ не являются ортогональными векторами.
Если ве~ > 1, то точка минимума лежит за пределами множества й и в (8.5) следует принять лег = 1, т.е. х~ = х~. В противном случае в (8.5) принимаем век = ве„'. Для произвольной выпуклой функции |о(х) выбор значения вея из условия минимума функции фь[ве) потребует применения методов одномерной минимизации (см. 2). Отметим, что если целевая функция Ях) выпукла, то и функция фо(ве) выпукла (см. теорему 3.7) и в любой стационарной точке ве' этой функции в силу теорем 3.14 и 3.15 она достигает наименьшего значения. Если |о(х) — строго выпуклая функция, то, согласно теореме 3.7, и функция (8.6) строго выпукла на отрезке [О, Ц. В этом случае, согласно теоремам 3.14 и 3.15, стационарная точка функции фа [ее), если она существует, единственна и в этой точке функция достигает наименьшего значения.
Можно избежать минимизации функции фа[ве) (8.6), выбирая значение вег б (О, Ц в (8.5) так, чтобы Яхв) < |о(х~ ), т.е. чтобы последовательность 1х") была релаксационной. Тогда, согласно теореме 4.2, справедлива оценка вида (4.12) 1о(х'") — 1о[х') < ( 1 ~ Уо(х ') — 1о[х ) ч) |о[хо) — |о(х*) ' ), и ~-; [8гас1|о(х" ')[ (' где и = е11аш й — диаметр ограниченного множества й. Условием прекращения итераций может быть выполнение одного или всех неравенств [4.18) и [4.19). Нри некоторых ограничениях метод условного градиента работоспособен и в случае, когда целевая функция не является выпуклой*.
Пример 8.1. Найдем решение задачи квадратичного програх иироваиия на множестве й = ((хм ха) е Кл: х| е [О,. Ц, тг е [О, 2) ) Смл Пиеильев Ф.П., а также: Пшеничный Б.И., Данилин Ю.М. 8.1. Метод услооиого градиента для целевой функции «о(х1,хв) = х1~ — 4х1+ хе ~— 2хз, которую представим в виде «о(х) = — Ях, х) + (с, х), где вектор с = 1 т = ( — 4 — 2) и матрица В качестве начальной точки возьмем хо = (О, 0), а условие прекращения итераций примем в виде )Ьх ~ = ~х~ — хь ~ ( е = = 0,1. Рассмотрим подробнее первую (Ь = 1) итерацию при решении этой задачи методом условного градиента. 1.
Вычислим в начальной точке х = (х1, хз ) =(О, 0) гра<о1 00 т диент ягас! «о(х ) = Цх +с = с = ( — 4 — 2) целевой функции и найдем в соответствии с (8.2) главную линейную часть приращения этой функции в указанной точке: «1 (х) = (8тай «о(х ), х — хо) = (с, х) = — 4х1 — 2хз. Функция «1(х) является линейным приближением к целевой функции в гжрестности точки х . ит 2.
Вспомогательное приближение х най- 2 х дем, минимизируя функцию «1(х) на задан- й':; ном множестве й, являющемся прямоугольником (рис. 8.2), причем в (8.4) а1 = аз = = О, Ь1 = 1 и Ьз = 2. Так как производные Р' ) = — 4и .'( ) = — 2отрицательны.то дх~ дхе -(11 0 х 1 в соответствии с (8.4) имеем х1 — — Ь1 = 1 и Рис.
8.2 х1 — — Ьз = 2, так что х1 = (1, 2). 3. На первой итерации направление спуска определяется вектором р1 = х1 — х" = (1 2) . Учитывая выражение для т антиградиента то1 = — яга(1«о(х") = (4 2) целевой функции в точке хо и используя формулу (8.7), находим точку и1 8, ЧИСЛЕННЫЕ МЕТОДЫ минимума функции ир1(х) (8.6): (ш',р') (4 2)(1 2) 8 ЯР Р ) 2 0 1 10 Результаты расчетов на первой и последующих итерациях приведены в табл. 8.1, а графическая иллюстрация решения задачи методом условного градиента представлена на рис. 8.3. Описанный алгоритм за восемь итс" раций с заданной точностью приводит к точке х* = (1, 1), являющейся точным решением задачи. В точке х~ = (0,957, 0,953) значение ~я(хя)— — — 3,910 отличается от минимального значения Та(х*) = — 4 менее чем на 0,1.
Рис. 8.3 Таблица 8.1 Поскольку рр1 < 1, принимаем рр1 = рр~~ — — 0,8 и при помощи (8.5) находим точку х1 = ха+ х1Р1 = 0,8(1 2) = (0,8 1,6) . Ясно, что х Е Й (см. рис. 8.2). 4. Проверяя условие прекращения итераций, убеждаемся, /рд)~ р (р рр р рро р и р , р .рр точность еще не достигнута и поиск точки х* е Й минимума целевой фУнкции Ти(х) на множестве Й следУет пРодолжить, заменив в п. 1 точку х на найденную на первой итерации точку х1 = (0,8, 1,6).
345 а2. Использование приведенного градиента Характерное зигзагообразное движение на рис. 8.3 в направлении искомой точки х' связано с тем, что в данном случае при решении задачи (8.3) минимизации линейной функции 1ь(х) на выпуклом множестве й вспомогательными приближениями поочередно являются крайние точки (1, 2) и (1, О) этого множества.
Поиск вспомогательного приближения хь е й на й-й итерации метода условного градиента можно вести не только на основе линеаризации целевой функции )в(х) в окрестности точки х" ' е й. Если Ях) — выпуклая функция, дважды дифференцируемая на выпуклом ограниченном замкнутом множестве й, то ее приращение в окрестности точки х~ ~ приближенно можно представить квадратичной функцией Ях) = (бга<)Ях~ 1), х — хь 1) + (Н1 х~ 1)(х — х~ '), х — х~ ~), где Ероха ') матрица Гессе функции Ях), вычисленная в точке х" ~. Такое представление приводит к необходимости вместо решения задачи (8.3) минимизации линейной функции на допустимом множестве й решать на том же множестве зада<у минимизации квадратичной функции.
Это существенно усложняет поиск точки х~, но благодаря более точной аппроксимации целевой функции в окрестности точки хь ' может уменьшить общее число итераций. 8.2. Использование приведенного градиента Если допустимое множество П с Ка задано при помощи линейных ограничений, то для минимизации на нем дифференцируемой нелевой функции )в(х), х Е Ка, можно использовать подход, аналогичный покоординатному спуску в случае безусловной минимизации. При этом ограничения удобно привести к форме, соответствующей стандартной задаче линейного программирования и содержащей ограничения типа равенства 346 8.
ЧИСЛЕННЫЕ' МЕТОДЫ в виде Ах = Ь с известными матрицей А размера т х и и вектором Ь Е К"' и условие неотрицательности наражетпров оптимизации в виде х Е К„", где Кн — неотрицательный ортант размерности п. Итак, необходимо минимизировать дифференцируемую целевую функцию )о(х), х б К"', на множестве Й = (х Е К,: Ах = Ь) . (8.8) Без ограничения общности можно считать, что ранг матрицы А в (8.8) равен числу пь ее строк и меньше числа и ее столбцов, т.е.
КяА = ~п < и. В самом деле, если ВдА = г < т, то в матрице можно выделить г линейно независимых строк. Остальные строки матрицы будут линейными комбинациями этих т строк ~11Ц. В этом случае либо система Ах = Ь несовместна и задача оптимизации не представляет интереса (допустимое множество пусто), либо из системы можно удалить п — г уравнений, не меняя множества ее решений.
В результате удаления мы приходим к аналогичной задаче, в которой ранг матрицы равен количеству ее строк. Если К8А = т = п, то система линейных уравнений Ах = Ь имеет единственное решение, которое можно записать в виде х = А Ь. Значит, допустимое множество рассматриваемой задачи оптимизации состоит из одного элемента, а сама задача не представляет интереса.
Итак, полагаем, что К8А = т < и. Выберем в матрице А базисный минор В. Для удобства будем считать, что этот минор расположен в первых т столбцах матрицы А (этого можно добиться, изменив при необходимости порядок переменных а н 1 = 1, н). Тогда матрицу А можно записать как блочную матрицу (В Х), где В квадратная матрица, составленная из первых т столбцов матрицы А, а матрица Х объединяет оставшиеся н — т столбцов. Матрица В, соответствующая базисному минору, является невырожденной. Выбор базисного минора в системе линейных алгебраических уравнений (СЛАУ) Ах = Ь приводит к разделению неизвестных х,, 1 = 1, п, на базисные 8.2. Использование припеденного градиента 347 неизвестные.
хы ..., хп, и свободные. неизвестные хтз м ..., ха. Первую группу неизвестных сгруппирусм в векто?з-столбец хн, а вторую — в вектор-столбец х . Введем также множества ин- Х дексов,7В = (1, 2, ..., т) и,7~ = (за+1, ..., и). С учетом введенных обозначений С,??АУ Ах = Ь можно записать в виде матричного уравнения Вхн + Хх~ = Ь. Поскольку матрица В невырождена, то это матричное уравнение можно преобразовать к виду хВ=Ь-Ахк, (8.9) где Ь = В Ь, Х = В ~Х. Параметры оптимизации, составляющие векторы хВ и х'с, называют обычно базисными и свободными переменными соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
