6.2. Проекционные методы

Методы другого класса для оптимизации с ограничениями типа неравенств широко известны как метод проекции градиента и метод приведенного градиента 1167], 1168], [192], [68], [3], 12]. Суть этих методов, которые на рис. 6.1 повели бы нас вдоль пути можно суммировать следующим образом.

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

1) еслй точка 0 лежит внутри допустимой области, то следует применить нормальный шаг (например, на рис. 6,1); если же результат нормального шага окажется в недопустимой области, то этот шаг укорачивается так, чтобы оставить нас на границе допустимой области;

2) если точка лежит на границе — сделать нормальный шаг или часть его, когда-то возможно (например, на рис. 6.1); в

противном случае — трактовать некоторые из активных ограничений как ограничительные равенства и делать шаг вдоль этих ограничении (например, на рис. 6.1).

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

На основе этих методов в сочетании с методами переменной метрики были построены эффективные алгоритмы для получения направлений шага ([86] и [147] — для линейных ограничений, [56] — для нелинейных ограничений). При отыскании минимума, который лежит на границе, эти алгоритмы оказываются обычно лучше метода штрафных функций. Во многих задачах оценивания параметров, там, где мы надеемся найти внутренний минимум, метод штрафных функций в силу своей большей простоты кажется более предпочтительным. Тем не менее исключения из этого правила все же бывают, и поэтому мы укажем, как может быть модифицирована итерация градиентного метода при наличии линейных ограничений типа неравенств (например, в форме ограничений сверху и снизу). Заметим, что когда применяется метод штрафных функций, все итерационные точки в (исключая, возможно, последнюю) лежат внутри допустимой области, и поэтому этот метод можно применятьнепосредственно, даже если некоторые из ограничений вида заданы в форме строгих неравенств Такие ситуации возникают, например, тогда, когда в уравнениях модели появляются члены типа или ввиду чего требуется, чтобы выполнялось неравенство . В методе проекции результаты некоторых итераций могут попадать на границу. Следовательно, неравенство должно быть заменено неравенством где есть малая положительная константа.

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

Значения этой величины близки к значениям если только является хорошей аппроксимацией для матрицы

Предположим, что ограничения имеют вид

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

есть число таких ограничений; размер матрицы А равен Каждый допустимый шаг должен удовлетворять условию

Для нахождения направления будет принята следующая стратегия.

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

Пусть есть решение КП-задачи при итерации. В точке градиент функции в соответствии с равенством получается по формуле —

Согласно условиям Куна — Таккера должен существовать вектор множителей Лагранжа удовлетворяющий условиям которые в нашем случае принимают вид

Пусть величина обозначает вектор-функцию ограничений, вычисленную в точке Тогда соотношения принимают вид:

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

Найти удовлетворяющие условиям:

Она известна как задачу о дополняющих кручениях 149] и может быть решена с помощью алгоритма, предложенного Данцигом и Коттлом 153]. Мы представим здесь более простой и более быстрый алгоритм [1951, [14], для которого сходимость не доказана, но который оправдывал себя в сотнях применений.

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

Пусть

есть соответствующее разбиение матрицы на подматрицы, разбиение вектора Тогда условие переписывается в виде:

Из условия получаем так что согласно имеем Образуем таблицу:

Если бы относительно всех диагональных элементов матрицы был выполнен прием исключения по методу Гаусса — Жордана, то результат преобразования последнего столбца таблицы имел бы вид:

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

чтобы найти это точное разбиение, предлагается следующий алгоритм:

1) образовать таблицу Е, которая содержит строк и столь есть число активных ограничений в точке ;

2) поставить в соответствие строке таблицы индикатор

3) при обозначающем текущее значение последнего элемент в строке, найти Если малая положительная константа, равная, скажем, при вычислениях без двойной точности), то перейти к пункту 5. В противоположном случае:

4) при индексе, для которого выполнить выметание по строке (т. е. применить прием исключения по методу Гаусса—Жордана, используя в качестве опорного элемента) и изменить знак вернуться к пункту 3;

5) теперь решение недалеко. Рассмотрим строку таблицы Если то выметание по строке не выполнялось (или выполнялось четное число раз). Следовательно, ограничение есть несвязывающее. Поэтому и Если то выметание по строке делается, а ограничение оказывается связывающим. Следовательно, Чтобы вычислить (мы теперь восстановим индекс решим уравнение

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

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

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

Мы будем исходить из точки в которой активными являются ограничения:

Эти ограничения и контуры целевой функции показаны на рис. 6.3. Из соотношений мы выводим, что

Рис. 6.3. Метод проекции при —

Образуем вектор и матрицу

Применение описанного алгоритма выглядит следующим образом:

4) , следовательно, мы выполняем кручение на опорном элементе 2,2- В результате получаем таблицу

5) так как второе ограничение будет связывающим, в то время как первое и третье — нет. Следовательно, (второй столбец матрицы А) и (взятый с обратным знаком второй элемент в последнем столбце таблицы Е). Поэтому в соответствий с равенством получаем

т. е., как это очевидно из неравенства (рис. 6.3), корректное решение..

Дальнейшая разработка этого алгоритма на случай нелинейных ограничений сделана Бардом [14].