нальньши Z[GZf (в отношении задач с положительно определенными матрицами Гессе методы Мюррея н Банча - Кауфмана идентичны). Алгоритм решения QP с положительно определенной матрицей С, не требующий запоминания никаких блоков Q, сконструирован Пауэллом (1980). В нем Zj строится по и Л,,. Однофазный алгоритм квадратичного программирования, который может двигаться по недопустимым точкам, читатель найдет у Конца и Синклера (1975). Хорошее сопоставление разных методов решения QP приведено у Джанга (1980).

Описанный в разд. 5.3.3 метод решения условных задч о наименьших квадратах в основном разработан Стоером (1971) (см. также Шиттковски и Стоер (1979)) и включает некоторые модификации, автором которых является Соидерс (1980). С другими методами, предназначенными для этих задач, можно познакомиться по книге Лоусона и Хансона (1974). Методы решения условной задачи минимизации /i-нормы невязки линейных уравнений, использующие обсуждавшуюся технику ортогональных разложений, предлагались Бартелсом и Конном (1980).

*5.4. ЗАДАЧИ С малым ЧИСЛОМ ОГРАНИЧЕНИЙ ОБЩЕГО ВИДА

Методы организации вычисления направлений поиска, описанные в предыдущих разделах (впредь мы будем называть их методами нулъ-npocmpaHcmed), вообще говоря, тем эффективнее, чем больше отношение числа ограничений задачи к числу ее переменных. Когда это отношение мало, предпочтительными могут оказаться схемы иного рода, использующие матрицы, размерность которых не увеличивается, а падает с уменьшением числа ограничений в рабочем списке. Это - так называемые методы ранг-пространства. Они рассматриваются ниже применительно к задачам с критериями двух типов, а именно с положительно определенными квадратичными формами и с нелинейными функциями общего вида.

*5.4.1. квадратичные задачи с положительно определенными матрицами гессе

Возьмем задачу квадратичного программирования с положительно определенной матрицей Гессе С. Пусть -ее допустимая точка, причем (<й<п) ограничений с матрицей Af, выполнены в Хд как равенства. Направление Рд, обеспечивающее допустимость Хд-рд относительно этих ограничений п доставляющее минимум целевой функции на соответствующем подпространстве, есть решение квадратичной подзадачи вида

найтн min glp + P Gp

«6»>

при ограничениях Лдр = 0,

(5.53)

где gA=Cxд-f с. Обозначим через >.д отвечающий ему вектор множителей Лагранжа. Тогда необходимые условия оптимальности рд можно будет записать в виде следующего (п+(д)-мерного векторного равенства:

G -/

(.°.-.*)G)47)

В силу положительной определенности С при Лд, имеющей полный ранг, матрица

невырожденна. В этом случае система (5.54) однозначно разрешима относительно пары Рд, ?.д, причем обратная к (5.55) матрица имеет вид

-{А,С~Ч1)-%0-

(.А,С-А1)-

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

Метод нуль-пространства Метод ранг-пространства

Рд=гд (гд GZf,)-ziq„ к„=(ЛдС-м1)- ЛдС-& А„ (Срд+ы рд=с-члДд-ы

Вновь полученные выражения для рд, Хд сами по себе для практических вычислений непригодны. Как обычно, нужны некоторые преобразования. Обозначим через/.д нижний треугольный фактор /.-разложения Лд (см. (5.15)), и пусть Кд-матрица, составленная из первых /д столбцов ортогонального фактора Сд. Тогда подстановкой Лд=/,дК в уравнения метода ранг-пространства получим

Pk = 0-y,f)-g„). (5.56)

е = (KjC-Кд)- nc-gj. (5.57)

Это и есть формулы, используемые на практике.

Поскольку Кд представляет собой блок ортогональной матрицы, число обусловленности у КСгКд будет хуже, чем у G. Расчет Рд по формулам (5.56) и (5.57) можно организовать, храня факторы Холесского для О (нх придется вычислить один раз) и пересчитывая при вводе и выводе ограничений из рабочего списка матрицы Lд, Кд и факторы Холесского для КСКд. Если принять, что запись Уд и факторов С требует примерно

столько же памяти, сколько запись несимметричной матрицы Q,, то для сопоставления запросов на память от двух методов расчета рд надо сравнивать размерности матриц ZJCZj и VlG~ V. Когда ожидаемые значения близки к п, метод нуль-пространства будет экономнее. При малых ожидаемых экономнее и, следовательно, предпочтительнее в условиях дефицита памяти оказывается метод ранг-пространства. В диапазоне л* Чп выбор делают из иных соображений. В частности, следует иметь в виду, что метод ранг-пространства менее надежен с вычислительной точки зрения, так как при расчете р по формуле (5.56) могут возникать существенные ошибки компенсации. Это обстоятельство нередко становится решающим. Правда, если матрица G имеет специальную структуру заполнения, позволяющую очень экономно хранить ее факторы Холесского, им обычно пренебрегают.

Во многих случаях максимальные размеры матриц ZIGZ и УlG- Yf. удается хорошо оцепить заранее. К примеру, в задаче с пятью от-раниченняни общего вида размеры YICY никогда не превысят 5x5. Допустим далее, что матрица Гессе имеет вид

где Cjj есть невырожденная гхг-матрица. Тогда, если известно, что подзадача (5.53) всегда будет однозначно разрешимой, т. е. ZftCZft всегда будет положительно определенной, можно утверждать, что число ограничений в рабочем списке ие станет меньше п-г н соответственно число столбцов Z не превзойдет г,

5.4.2. МЕТОДЫ ВТОРЫХ ПРОИЗВОДНЫХ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОБЩЕГО ВИДА

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

S.4.2.I. Метод, основанный на квадратичной подзадаче. Рассмотренный ранее ньютоновский метод нуЛ].-пространства в обь1ч-нон ситуации дает в качестве направления поиска решение задачи QP вида (5.53) с С=С,,. Здесь не важно, будет матрица С,, положительно определенной или нет. Чтобы в отсутствие положитетыюй определенности С,, получить то же направлеине методом ранг-пространства, его формулы надо несколько усложнить.

Решение задачи (5.53) не изменится, если заменить Сд матрицей

G„G„ + vAlA,,. (5.58)

Данное утверждение следует из равенства ZrGvZj = ZJGsZj. При этом, когда ZlGfZ положительно определена, существует число v.

такое, что G„ будет положительно определенной при всех v > v. Таким образом, чтобы применить метод ранг-пространства при знаконеопределенной Сд, надо подобрать подходящий параметр v и использовать в (5.56) и (5.57) вместо Gj матрицу G„. факто-ризуя ее по модифицированной схеме Холесского (см. разд. 4.4.2.2). Когда F хорошо отмасштабирована (см. разд. 8.7) н ограничения отнормированы так, что ЛдЦ есть число порядка единицы, как правило, в качестве v подойдет

v = -fi (II (!.-(-£„),

(5.59)

где EjH - относительная машинная точность и6€[ем, ем"*].

5.4.2.2. Метод, основанный на аппроксимации спроектированной матрицы Гессе. Второй способ вычисления рд является эффективным, когда размерность Z близка к п, и основан на использованни следующего предельного соотношения;

lim G-=Z, (ZJGА)-Zf. (5.60)

При этом

liev-z,(ZjGA)-v[=o [-).

Здесь Cv-матрица (5.58).

Указанное свойство матрицы С; позволяет рекомендовать в качестве р направление, рассчитываемое при конечном v по решению р„ системы уравнений

OvPv = -gs- (5.61)

Переход от к /j осуществляется так:

p, = (I~Y,Yl)p,(.Zlp,).

Получающееся направление представимо в впде (5.34) и соответственно является допустимым. Если матрица ZGZf положительно определена и число v достаточно велико, это рь будет направлением спуска. Если же среди собственных значений Z/GZj есть отрицательные, параметра v, обеспечивающего положительную определенность G„ не существует, и тогда р>, из (5.61) может задать направление возрастания f. Однако, когда решение системы (5.61) ищется методом модифицированной факторизации Холесского, в этом случае выполнится необходимая корректировка Gv, и правильная ориентация р будет гарантирована.

В описанном методе ньютоновское направление -Z;(ZftCftZJ-x xZgft аппрокси.мируется вектором -ZfZGg. н ошибка этой аппроксимации имеет порядок 1/v. При выборе v по правилу (5.59) для хорошо отмасштабированной задачи она сравнима с ошибкой конечно-разностного приближения спроектированной матрицы Гессе ZJGZj (см. разд. 5.1.2.3). Когда v увеличивается.

число обусловленности Cv возрастает. Однако отклонение вычисляемого от истинного обычно почти целиком лежит в подпространстве ошибки оценивания ньютоновского направления и потому критического значения не имеет.

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

Схема ранг-пространсгва лежит в основе всех ранних реализаций квазиньютоновского поиска, предназначенных для решения задач с линейными ограничениями. Точнее говоря, все онн опираются на возможности представления обратной к (5.55) матрицы в виде

и аппроксимации ее блоков по значениям градиентов. В (5.62) Я*, С* и К* есть матрицы размеров пхп, txn и <ьХ<д соответственно. В частности, в методе Гольдфарба (1969) квазиньютоновская техника применяется для построения приближений Н*. а линейные оценки множителей Лагранжа вычисляются по схеме наименьших квадратов с использованием обратной к ЛЛд матрицы. Муртаф и Сарджент (1969) предложили алгоритм, основанный на пряьюй квазиньютоновской аппроксимации матриц Gfe* и iAfpkAI). Дальнейшие комментарии по поводу этнх методов можно найти в работе Гилла и Мюррея (1974d).

Методы ранг-пространства для задач с произвольными гладкими и знаконеопределенными квадратичными целевыми функциями пока еще служат предметом исследований. Надо отметить, что схемы этого сорта, рассчитанные на задачи квадратичного программирования с знаконеопределенными матрицами Гессе, более громоздки, чем соответствующие методы нуль-пространства. Причина - отсутствие возможности выяснить по разложению G и AG~Al определенность матрицы ZlGZf,. Из-за этого трудно отличать условно седло-вые точки от условно экстремальных. Однако когда - точка условного минимума и какие-то ограничение выводится в ней из рабочего списка, то гарантировано, что x+Pi, тоже будет точкой условного минимума (иа подпространстве, заданном новым рабочим списком), если только р,, не окажется направлением отрицательной кривизны. Значит, имея в качестве начального приближения хо вершину допустимого М1южества и отслеживая кривизну F вдоль используемых направлений, мы можем держать под наблюдением экстремальность последующих приближений. Коль скоро кривизна F вдоль текущего направления поиска оказалась отрицательной, с дальнейшими сокращениями рабочего списка надо будет повременить до тех пор, пока в него не войдет какое-нибудь новое ограничение (см. разд. 5.3.2.2). Данная стратегия модификаций рабочего списка лежит в основе метода квадратичного программирования.

пред.чоженного Флетчером (1971b). Этот метод предполагает хранение и пересчет матриц И* и С* нз (5.62) в явном виде. Описанный выше метод ранг-пространства для квадратичных задач с положительно определенными матрицами Гессе аналогичен квазиньютоновскому ыс-году, представленному в работе Гилла и Мюррея (1974d).

Методы ранг-пространства для задач квадратичного программирования с положительно определенным критерием можно строить на основе непосредственной факторизации нли обращения расширенной матрицы (5.55) (см., например, Бартелс, Голуб и Соидерс (1970)). Многие из методов такого сорта, разработанные для задач большой размерности, базируются на симплексной технике «ведущего элемента». Томлни (1976) реализовал версию алгоритма Лем-ке (см. Лемке (1965)), в которой используется 1{/-разложение матрицы, аналогичной (5.55).

Подробное обсуждение методов ранг-пространства для задач с произвольными гладкими целевыми функциями приведено в диссертации Гилла (1975).

Более полные сведения относительно правил модификации рабочего списка в методах ранг-пространства читатель может найти в статье Ленарда (1979).

5.5. ЗАДАЧИ С ОГРАНИЧЕНИЯМИ СПЕЦИАЛЬНОГО ВИДА

На практике нередко встречаются задачи со специфичными ограничениями, и, учитывая эту специфику в алгоритмах, можно существенно повышать нх эффективность. Мы рассмотрим два наиболее распространенных тнпа задач такого рода: задачи, где все условия суть простые ограничения на переменные, и задачи, совокупность условий которых представляет собой смесь простых ограничений на переменные и ограничений общего вида,

5.5.1. минимизация при простых ограничениях на переменные

Важным в прикладном отношении частным случаем общей постановки L1P является задача, включающая только простые ограничения на переменные:

найтн min F {х) (5.63)

ЛЕЯ"

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

С формальной точки зрения это - задача с 2п условиями типа линейных неравенств. Ясно, однако, что специфика последних, состоящая в том, что в любой точке в каждой паре двусторонних ограничений равенством может стать не более одного (если /, не совпадает с и,) и что матрица произвольного набора активных ограничений имеет полный ранг, сулит значительные алгоритмические преимущества.