Ограничение из (5.63) становится активным, когда соответствующая переменная принимает граничное значение. Задать для (5.63) рабочий список -значит расчленить вектор переменных на «свободную» и «фиксированную» составляющие а>д и Хрх- Согласно терминологии разд. 5.2.1, число компонент а>х (фиксируемых переменных) на очередной итерации будем обозначать через Отвечающая им матрица состоит из строк единичной матрицы, взятых с нужными знаками; в качестве столбцов можно использовать остальные строки единичной матрицы.

Ниже рассмотрена типовая итерация поиска решения задачи (5.63) по схеме активного набора. Как обычно, чтобы не загромождать формул, индекс итерации k опущен. Компоненты направления поиска с номерами фиксируемых переменных (нх число равно I) должны быть нулевыми. Таким образом, определить надо только п-t его «свободных» компонент. Индексом FR будут помечаться отвечающие им (п - /)-мерные векторы и матрицы; через gp будем обозначать ZJ и т. д.

В приложении к задаче (5.63) формулы всех алгоритмов из разд. 5.1.2 становятся особенно простыми. Например, ньютоновская система принимает такой вид:

GfrPfk-Sfk- (5.64)

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

BFGS-формула пересчега матрицы Врд (прн сохранении рабочего списка неизменным) выглядит следующим образом:

-Bfr-V

SfRPfp

-УекУрн-

Специфика матрицы А ограничений рабочего списка задачи (5.63) сильно упрощает расчет оценок множителей Лагранжа. Допустим, что у-й фиксируемой переменной является к-,. Тогда любой из рассмотренных в разд. 5.1.5.1 методов вычисления оценок первого порядка даст для /-го множителя одно и то же значение - взятую с соответствующим знаком i-ю компоненту градиента целевой функции. Если Xi = li, эта оценка равна gi, а прн Xi=u, линейной оценкой /-ГО множителя Лагранжа будет -g,. Оценки второго порядка для (5.63) вычисляются по формуле вида

Ць=>+СРгн-

Здесь I - вектор линейных оценок, pf, - ньютоновское направление (т. е. решение системы (5.64)), а G - матрица, состоящая из элементов С, которые принадлежат строкам, отвечающим фиксированным переменным, и столбцам, соответствующим свободным. Следовательно, как линейное, так н квадратичное оценивание множителей Лагранжа для задачи (5.63) не требуют решения никаких систем уравнений.

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

Применяя для решения задачи (5.63) алгоритм с гонечно-раз-ностной аппроксимацией производных, вычисления легко организовать так, чтобы обращения к процедуре расчета значений целевой функции в Ведопустимых точках были исключены. Последнее важно, когда эта функция определена только в допустимой области. Соответствующие модификации касаются лишь формул, по которым строятся оценки первых и вторых производных от F. Предположим, к примеру, что на очередной итерации /-я переменная Xj имеет одно из своих граничных значений. Чтобы решить, следует ли зафиксировать ее на этом значении, нужна оценка множителя Лагранжа. Коль скоро используемый метод оперирует конечно-разностными приближениями градиента, в качестве такой оценки можно взять приближение его /-й компоненты с подходящим знаком. Если значение Xj равно верхней границе Uj, для вычисления конечно-разностной аппроксимации величины gj подойдет формула

g,=-(F(x)-F{x~h,e,)).

При Uj-Ijhj в ней фигурируют только допустимые точки; в отсутствие этого неравенства точка x-IijBj вышла бы за нижнюю границу по /-н компоненте. Чтобы не выйти при оценивании производных за пределы допустимого множества, специфичные конечно-разностные формулы надо применять и для свободных переменных, еслн их значения близки к граничным. Шаги в таких случаях делают в сторону от ближайшей границы. Например, центральную конечно-разностную аппроксимацию производной вблизи нижней границы следует вычислять по формуле

ei = W,-f(:+<j)-f(x)-F{x + 4hi)).

причем должно быть щ-lj2hj.

Выбор направлений спуска в процедурах поиска оптимума при простых ограничениях фактически осуществляется теми же способами, что п в методах безусловной минимизации. Поэтому последние

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

•5.5.2. задача со смесью простых ограничений и ограничений общего вида

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

На типичной итерации решения задачи со «смешанными ограничениями» рабочий список будет содержать и простые ограничения, и ограничения общего вида. Допустим, что число первых равно г, а вторых /-г; все векторы и матрицы, относящиеся к свободным и фиксируемым переменным, будем помечать индексами FR и FX соответственно. Тогда в предположении (которое делается ради наглядности выкладок), что фиксируются последние переменные, матрицу А к можно представить следующим образом:

(5.65)

Здесь Ард есть {I-)v(n-г)-матрнца. Специальная структура (5.65) позволяет организовать расчет направления поиска и оценок множителей .Лагранжа экономнее, чем в общем случае.

Начнем с техники вычисления направлений поиска. В силу специфики А„ любая пх(п-<)-матрица векторов базиса

нуль-пространства Лд должна выглядеть так:

7 Л

Здесь ZfR есть некоторая (п-г)х(п-Ц-матрица, составленная из векторов базиса нуль-пространства Арц. Поэтому, например, обычная система для вычисления вектора pz, по которому строится ньютоновское направление р = (ррн, 0), преобразуется к виду

ZfHFrZfrPZ = - ZpngFR

(ср. с (5.12)). По существу, здесь можно говорить о понижении размерности, равном количеству зафиксированных переменных. Расчет оценок множителей Лагранжа тоже можно ориентировать иа специфику Лд. снизив тем самым его трудоемкость. Представим (-мерный вектор \ объединением ((-л)-мерной составляющей (множители ограничений общего вида) н г-мерной Лд (множители, отвечающие фиксируемым переменным). Тогда уравнение для X можно записать так:

(5.66)

Отсюда видно, что для подсчета линейных оценок множителей достаточно найти решение в смысле наименьших квадратов для первых t-г уравнений нз (5.66)

Л ?До » efk

и взять

befx - fka-

Изменения блоков матрицы Лд прн вариациях рабочего списка зависят от типа вводимого или выводимого ограничения. Если это-простое ограничение, поменяются столбцовые размерности матриц Afh и Арх\ в противном случае изменятся их строковые размерности.

Эффективное воплощение представленной техники вычислений возможно только на базе методов пересчета разложений матрицы AfR (при изменении состава ее строк и столбцов), и такие методы существуют. Тем не менее надо сказать, что используют эту технику нечасто. Объясняется это трудностью ее программной реализации. Не желая писать сложных программ, часто отказываются от учета специфики простых ограничений и обрабатывают их так же, как ограничения общего вида. Подобная практика может быть оправданна, когда повышение трудоемкости итерации, с которым она связана, незначительно по отношению к трудоемкости вычисления целевой функции. Для малых задач с целевыми функциями достаточно сложной структуры такое соотношение характерно. Однако если говорить о задачах линейного нли квадратичного программирования, то эффективность методов их решения существенно зависит от качества организации вспомогательных вычислений. В частности.

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

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

Алгоритм решения задач минимизации нелинейной функции при простых ограничен! ях, преде гавленный в разд. 5.5.1, разработан Гиллом и Мюрреем (1976b). Есть и другой подход к решению таких задач. Он заключается в том, чтобы снимать их ограничения, используя специальные замены переменных, т. е. сводить их к задачам безусловной минимизации (см. разд. 7.4.1.1). Однако применять для решения последних обычные методы оптимизации без ограничений не рекомендуется (см. Сиссер (1981)). Следует отметить также, что понижения размерности, характерного для методов активного набора, при использовании схемы замены переменных не будет.

Когда все ограничения задачи простые, а ее целевая функция квадратична, поиск решения можно организовать значительно эффективнее, чем для общей задачи квадратичного программирования (см Флетчер и Джексон (1974), Гилл и Мюррей (1976b, 1977а)). В этом случае ценой незначительных усилий можно выбрать «хороший» начальный список фиксируемых переменных. Кроме того, если матрица G положительно определена, то простому вычислению поддается выигрыш по критерию, обеспечиваемый выводом ограничения из рабочего списка при условии, что на следующей итерации этот список не придется расширить.

Б.6. БОЛЬШИЕ ЗАДАЧИ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ

5.6.1. методы решения больших задач линейного программирования

Задачи линейного программирования принято представлять в следующей стандартной форме:

стандартная форма LP: найти min сл:

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

lxu.

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

Между фор-мой (5.42) и стандартной формой существует очевидная эквивалентность. Точнее говоря, любая задача, представленная в одной нз форм, может быть преобразована в задачу другой формы. Приведение всевозможных задач к стандартному виду выполняют с помощью целого ряда общеизвестных приемов. В частности, чтобы переделать задачу (5.42) в стандартную, надо ввести в каждое из ее ограничений свою вспомогательную переменную определенного знака и заменить неравенства равенствами. Так, напркиер, ограничение ахЬ надо заменить на ах-у=Ь, наложив на у условие неотрицательности {/>0. Хотя прн подобных преобразованиях размерность задачи может существенно возрастать, утяжеление вычислений и увеличение объема памяти, связанные с появлением вспомогательных переменных, будут незначительны (поскольку последние не входят в целевую функцию и ограничены только простыми неравенствами).

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

Отбросим на время индекс k очередной итерации, и пусть х - текущая точка процесса решения стандартной задачи с т равенствами. Не умаляя общности рассуждений, будем считать, что в х на граничных значениях зафиксированы п-т последашх переменных. Тогда X есть решение системы вида

Здесь В есть невырожденная mxm-подматрица, составленная из ряда столбцов А и именуемая базисной. Базисными называют также формирующие В столбцы А и отвечающие им переменные задачи (в (5.67) вектор этих переменных обозначен через Хв). Столбцы, относящиеся к Л, и переменные х, ассоциируемые с ними, принято называть небазисными. Компонентами вектора Ь„ из (5.67) будут граничные значения небазнсных переменных, т. е. соответствующие компоненты либо I, либо и в зависимости от того, на какой из своих границ зафиксирована небазисная переменная.

Точка X является оптимальной для задачи с ограничениями-равенствами (5.67). Чтобы определить, будет ли она оптимальной и для исходной задачи, надо вычислить в ней значения множителей Лагранжа. Разобьем составленный нз них вектор на т-мерный под-вектор л (в него войдут множители исходных ограничений-равенств) и {п-т)-мерный о (отвечающий зафиксированным переменным).