Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [ 40 ] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

представления спроектирсванион матрицы Гессе используется факторизация Холесского, и учитывая (5.49), эту систему можно запи. сать так:

RRPz = -Y«„-,+i. (5.50)

где y = i:gk. Первый этап процедуры решения (5.50) состоит в расчете корня векторного уравнения с нижней треугольной матрицей R и той же правой частью, что у (5.50). В силу особой структуры этого уравнения искомым корнем будет вектор, кратный Значит, будет решением треугольной системы

вида

RPz = P„-,+i. (5-51)

где 3 - некоторое число.

В действительности векторы Pz всегда (а не только в условно стационарных пючках) будут решениями верхних треугольных систем типа (5.51). Последние проще систем, которые приходится решать в общем случае. Таким образом, для QP расчет рг можно организовать экономнее, чем в нькггоновских методах для неквадратнчиых задач, и это - хороший пример использования специфики QP для упрощения вычислений в схеме активного набора.

5.3.2.2. Задачи квадратичного программирования с знаконеопределенными спроектированными матрицами Гессе. В данном разделе речь по[дет о за.чачах QP, в которых для какнх-то из возможных Zj матрицы ZfCZ оказываются знаконеопределенными. С алгоритмической точки зрения они сложнее задач, обсуждавшихся в предыдущем разделе. В них встречаются условно стационарные точки, где нет минимума критерия на соответствующем нуль-пространстве, н потому системы (5.47) могут давать направления возрастания целевой функции.

Для задач рассматриваемого типа нужен ньютоновский метод, обеспечивающий правильную ориентацию направлений поиска даже в тех точках, где матрица Gz ие является знакоопределешюй, причем желательно обойтись минимальными модификациями Gz. Последнее существенно, так как иначе пропадет возможность эффективной организации вычислений с использованием квадратичное™ целевой функции. Таким образом, стандартные приемы корректировки знаконеопределенной матрицы (см. разд. 4.4.2) здесь не подходят. В то же время надо помнить, что, если не принять специальных мер, операции пересчета симметричных разложений знаконе-определенных матриц будут численно неустойчивы-Общие соображения, лежащие в основе предлагаемого ниже метода, таковы. Коль скоро в очередной точке поиска спроектированная матрица Гессе стала знаконеопределенной, можно найти указывающий в сторону убывания F вектор pz (направление отрицательной кривизны), для которого piZ,GZi,p-/:<0. Если бы никаких ограничений, кроме содержащихся в текущем рабочем списке.

не было, большие шаги вдоль Pt=ZtPz приводили бы в допустимые точки со сколь угодно большими по модулю отрицательными значениями критерия. Мы же предгюлагаем, что .задача имеет конечное решение. Значит, при движении вдоль Ptt оби.зательно обратится в равенство какое-то из ограничений, которых не было в рабочем списке к-й итерации. Сделав соответствующий шаг, его надо ввести туда, и после этого спроектированная матрица Гессе, возможно, станет положительно определеыюн. Тогда очередное направление спуска будем строить обычным образом. Еслн же этого не произойдет, надо иайти новое направление отрицательной кривизны и т. д.

Для поиска решения произвольной задачи QP можно воспользоваться слегка усложненной версией метода, описанного в разд. 5.3.2.1. Прн этом требуется, чтобы начальная допустимая точка была либо вершиной, либо условно стационарной точкой с положительно определенной спроектированной матрицей Гессе. В данном случае эта матрица может стать знаконеопределенной только в момент вывода какого-то ограничения из рабочего списка на первой или одной из последующих итерации. Здесь в факторе R ее разложения по Холесскому должен появиться новый спэлбец, причем новый (последний) диагональный элемент R окажется квадратным корнем нз отрицательного числа. Последнее означает, что обычным путем 1тересчет R не провести. Однако система (5.51) для вычисления Pz такова, что последний диагонал]>ный элемент R влияет только на длину этого вектора и не влияет на его направ.1е-нне. Следовательно, в операции взятия квадратного корня при вычислении [юследнего диагонального элемента R мы можем, ие изменив ориентации pz, иСюльзовать вместо аргумента его модуль. Тогда в рассматриваемой ситуации пересчет R пройдет нормально. Результатом будет разложение, верное с точностью до последнего дна-гональною элемента, а решение системы (5.51) даст вектор Pz, определяющий направление отрицательной кривизны.

Спуск по найденному после сокращения рабочего списка на-Г]равлению отртщательной кривизны приведет в точку, где в этот список будет введено новое ограничение. Можно показать, что число отрицательных собственных значений спроектированной матрицы Гессе при этом не увеличится и что пересчитанное после такого «об. мена» ограинченнй разложение Холесского по-прежнему будет верным с точностью до последнего диагонального элемента. Значит, если обл:сн приведет к положительно определенной спроектированной матрице Гессе, для восстановления истинного разложения потребуется вычислить заново только последний диагональный элемент R.

Появление мнимого корня при пересчете фактора R означает, что обычные ограничения на модули элементов R (см. разд. 2.2.5.2) теряют силу. Соответственно появляется риск потери точности разложений из-за дефектов машинной арифметики. Однако угроза численной неустойчивости в действительности невелика, так как



относится лишь к последнему столбцу R.. В конце концов, когда спроектированная матрица Гессе станет (в результате очередного расширения рабочего списка) положительно определенной, этот столбец можно будет построить заново.

Итак, допуская проявление знаконеопределенностн в очень ограниченной форме, ыы получаем достаточно надежный алгоритм, принцип которого состоит в том, чтобы сохранять спроектированную матрицу Гессе «настолько положительно определенной, насколько возможно». Формальным воплощением этой установки служит принятая стратегия формирования рабочего списка, в соответствии с которой при знаконеопределенной Gz его моокно только дополнять.

Требование, чтобы начальная точка была вершиной или условно оптимальной при ограничениях-равенствах, не сужает возможностей применения описанного метода. На самом деле, его можно запустить с любой допустимой точки (отыскав ее, если она заранее не известна, процедурой, описанной в разд. 5.7). Коль скоро имеющаяся допустимая точка х не удовлетворяет указанному требованпю, дело легко поправить ценой введения в рабочий список нескольких временных искусственных ограничений вида yiXi илн у,;. Параметры у, в этих ограничениях полагаются равными значениям соответствующих компонент X, а их состав подбирается так, чтобы х стала вершиной. Искусственные ограничения «помечаются» и выводятся из рабочего списка в первую очередь, после чего забываются. Возможность исключения в условно стационарной точке любого из искусственных ограничений обеспечивается свободой выбора в них знаков неравенств. Отметим, что реализация предлагаемого приема не требует выделения дополнительной памяти. Его суть удобно пояснить на примере, когда в начальной допустимой точке все t (i<n) ограничений задачи обращаются в равенства и матрица ZGZ положительно определена. В этом случае основным содержанием первых n-t итераций поиска, иа каждой нз которых снимется одно из искусственных ограничений, будет п-t шагов процедуры столбцовой факторизации Холесского для матрицы ZGZ.

Описанный подход позволяет решать задачи с знаконеопределен-ными матрицами Гессе алгоритмом, который очень близок к применяемому для задач с положительно определенными матрицами. В отношении последних эти алгоритмы просто идентичны.

5.3.3. линейная задача о наименьших квадратах с ограничениями

К задачам квадратичного программирования, рассмотренным в разд. 5.3.2.1, очень близки задачи миними-зацнн евклидовой нормы вектора невязок системы линейных уравнений при ограничениях типа линейных неравенств. Их называют условными линейными за-

дачами о наименьших квадратах. Общая постановка такова:

найти min ir\\Hx-d

при ограничениях АхЬ.

Здесь И есть sxn-матрица. Типична ситуация с s>n; более того, как правило, sn.

С формальной точки зрения задача LLS есть частный случай задачи QP из разд. 5.3.2 с C = WW и c = Hd. Соответственно, сформировав эти G и с явным образом, для ее решения можно воспользоваться любым из универсальных методов квадратичного программирования. Однако этого не делают, а применяют к LLS специальные методы, в которых нет операций с матрицей, чье число обусловленности равно квадрату числа обусловленности Н.

Имея допустимую для LLS точку Хд, в которой линейно независимые ограничения с матрицей Лд обращаются в равенства, для определения шага рд из Хд в точку минимума невязки при условии сохранения этих равенств надо решить аналогичную (5.47) систему

zгHЙZдp = -ZfЯdд. где йд-=Яхд-d. Это - обычная ньютоновская система для безусловной задачи о наименьших квадратах вида

найти min -IWZjpz-dt!l.

Значит, Pz можно искать как оптимальный для этой задачи вектор. Данное соображение и приводит к эффективному способу вычисления Pz. Каким образом - показано ниже, причем ради упрощения выкладок мы предположим, что у Лд достаточно сгрок, чтобы матрица Я2д имела [юлный столбцовый ранг (это эквивалентно предположению о единственности решении сформулированной задачи безусловной минимизации).

Какова бы ни была ортонормальная матрица Рд размера sxs, справедливо равенство

II "Z,pz-d, i = II Рд (ЯZдPд-dд) . (5.52)

В частности, в качестве Рд можно взять матрицу, преобразующую Ягд к верхнему треугольному виду (см. разд. 2.2.5.3), т. е. подобрать Рд так, чтобы выполнялось равенство

1 где /?д-невырожденная верхняя треугольная (п-(д)Х(/г-<д)-матрица. Тогда получим

li. т,Рг-4) Й = ) Pz-P, [



Отсюда видно, что невязка вспомогательной задачи минимальна, когда компоненты вектора Rupz равны первым п-компонентам Рдйд, т. е. искомый Pz будет единственным решением невырожденной линейной системы Ri,Pz = dt- Через обозначен вектор, образованный первыми п - компонентами Pjiu (см. разд. 2.2.5.3).

Представленный способ определения pz не требует запоминания матрицы Рд, поскольку, применяя образующие Рд элементарные ортогональные преобразования параллельно к Я2д и d, их можно тут же забывать. При sn такой способ организации вычислений сулит значительную экономию памяти.

Если матрица генерн руется ортогональной факторизацией Лц, построение новых R и при изменениях рабочего списка нетрудно реализовать по принципу пересчета. Когда рабочий список пополняется каким-то ограинченнем, Z+j получается последовательным умножением Z справа на несколько матриц плоского поворота (см. разд. 5.2.4.1). Эти повороты приведут к появлению под диагональю R ненулевых элементов. Чтобы обнулить последние, надо применить к R слева другой набор плоских поворотов (тем самым неявно определится новая матрица Рд.,,). При сокращении рабочего списка матрица Z,,+, будет получена из Z присоединением к ней нового последнего столбца г,, г+1. Здесь к R тоже надо дописать новый столбец, формируемый по вектору Яг„ ,+,. Для организации вычислений без хранения Я удобнее оперировать разложением вида РдЯд = (У, где Qj = (Zt Уд) (перестановка ортогональной матрицы из L(2-pa3-ложения Лд), а -верхняя треугольная пх «-матрица, В этом случае R будет левым верхним блоком (/.

С практической точки зрения требование полноты ранга матрицы HZt. на всех итерациях является довольно жестким. Однако предлагаемый алгоритм легко обобщить на случаи, когда это требование не выполняется. При этом в основу расчетов ложится полное ортогональное разложение Я2д:

Р,Я2,У.=.

Здесь St-верхняя треугольная гхг-матрнца, где г - ранг HZi, (см. разд. 2.2.5.3).

Замечания и избранная библиография к разделу 5.3

Симплекс-метод решения задач линейного программирования появился на свет в 1947 г. Его автором является Данциг (см. Данциг (1963)). Современные реализации симплекс-метода настолько совершенны, что без особых затруднений удается решать задачи.

ограничения которых исчисляются тысячами. Техника линейного программирования, рассчитанная на большое число ограничений и переменных, будет обсуждаться в разд. 5.6.1.

Линейность целевой функции делает целесообразным применение более тонких, чем в общем случае, правил вывода ограничений из рабочего списка. Обозначим через р направление поиска, получающееся после отбрасывания ограничения с отрицательным множителем Xj. Когда целевая функция F нелинейна, "kj служит оценкой первого порядка для изменения F при единичном шаге вдоль р. При линейной F эта оценка становится точной, т. е. с"р*/Х.

Одна из стратегий сокращения рабочего списка состоит в том, чтобы среди кандидатов на вьшод выбирать ограничение, которому отвечает наилучшая линейная оценка выигрыша за счет единичного шага вдоль соответствующего направления, т.е. минимальная величина Xj. Можно действовать и по-другому, выводя то ограничение, для которого максимальна оценка выигрыша при единичном изменении по X. Для линейных задач эта стратегия оказывается особенно эффективной (см. Гринберг н Кэлан (1975), Гольдфарб и Райд (1977)). В данном случае между собой сравниваются величины

cV"/llp"L = VIIP"lt, причем нормы \\p\i можно пересчитывать от шага к шагу по рекуррентным формулам. Симплекс-метод со второй стратегией сокращения рабочего списка принято называть методом отвесного ребра. Харрис (1973) предложил способ аппроксимации норм векторов р\

Некоторые из ранних методов квадратичного программирования были получены как модификации схем решения линейных .задач. Наиболее удачными среди них оказались метод Била (1959, 1967а) и применительно к случаям с положительно определенной матрицей Гессе метод Данцига и Вулфа (см. Вулф (1959), Данциг (1963)). Авторами первых алгоритмов квадратичного программирования, работающих по схеме «активного набора», являются Мюррей (1971а) и Флст1ер (1971Ь) (алгоритм Флетчера обсуждается в замечаниях к разд. 5.4).

Гилл и Мюррей (1978b) предложили метод решения задачи QP с разложением по Холесскому матрицы Z;(CZs, предполагающий, что фактор <3д нз L(2-paзлoжeния матрицы ограничений рабочего списка будет целиком храниться в памяти машины. Можно конструировать методы, не требующие запоминать всю матрицу <3д. Однако такая экономия всегда достигается ценой снижения численной устойчивости. Мюррей (1971а), например, разработал метод решения задач QP с знаконеопределенными матрицами Гессе, требующий хранения только Y. При этом Z,, выбирается так, чтобы матрица ZlGZ была диагональной. Банч и Кауфман (1980) предложили схожий алгоритм с блочно-диаго-



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [ 40 ] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0012