Глава VI. ВЫЧИСЛЕНИЕ ОЦЕНОК II: ЗАДАЧИ С ОГРАНИЧЕНИЯМИ

А. ОГРАНИЧЕНИЕ ТИПА НЕРАВЕНСТВ

6.1. Штрафные функции

Ограничения типа неравенств вида определяют область значений параметров, внутри которой должна находиться оценка. Такие ограничения часто возникают из априорной информации о значении этих параметров (см. раздел 2.16). Наличие ограничений типа неравенств — обычно в виде верхних и нижних границ по каждому параметру — часто отражается благоприятно на сходимости алгоритма оптимизации. За исключением немногочисленных задач сходимость к корректному минимуму достигается обычно как результат назначения некоторых довольно произвольных границ, вне которых алгоритмы «вязнут в болоте» не относящихся к делу областей параметрического пространства. Мы можем пойти дальше и рекомендовать такое назначение достаточно широких, хотя и в пределах разумного, границ во всех задачах оценивания нелинейных параметров.

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

мы назначим штрафную функцию

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

Пусть будут точки, в которых и достигают соответственно своего минимума внутри допустимой области. Фиакко и Мак-Кормик [72] доказали, что при соответствующих условиях

В методе последовательной максимизации без ограничений (МПМБО), представленном первоначально в статье Кэрролла и затем расширенном Фиакко и Мак-Кормиком, используются эти представления следующим образом:

1) выбрать и начальное приближение 6,

2) найти 0. применяя какой-нибудь из методов оптимизации без ограничений;

3) уменьшить величину и вернуться к пункту 2, используя О как начальное приближение. Процесс продолжается до тех пор, пока не начинает меняться, незначительно при уменьшении величины Тогда мы принимаем 0 за нашу оценку 0.

Поиск минимума для в пункте 2 должен по-прежнему ограничиваться допустимой областью. Поэтому может показаться, что мы ничего не выиграли Почему прямо не минимизировать Ответ в том, что мы создали ситуацию, когда целевая функция всегда начинает расти раньше, чем возникнет возможность выйти за допустимую область. Счедовательно, процедуры определения длины шага всегда благополучно приводят к получению приемлемого допустимого шага. Если мы случайно оказываемся вблизи какого-то ограничения, то для метода оптимизации, который применяется к вполне возможно, что будет указано направление в сторону недопустимой области, даже если существуют допустимые направления, для которых функция убывает. Добавляя штрафные функции, мы отклоняем наш шаг в допустимом направлении. Такая точка зрения иллюстрируется рис. 6.1, на котором изображены контуры целевой функции. Минимум достигается в точке А. Если исходить из точки В, то метод наискорейшего спуска приведет нас к минимуму по пути Если допустимая область ограничена тем, что расположена слева от линии то этот путь блокируется в точке С. Введение штрафной функции (рис. 6.2) оставляет контуры в окрестности точки А почти нетронутыми, но искажает их вблизи ограничения, как это показано на рисунке. Теперь мы имеем допустимый путь к минимуму Хотя пример дается здесь в рамках метода наискорейшего спуска, все сказанное в равной степени применимо к другим методам оптимизации.

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

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

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

Рис. 6.1. Контуры функции Ф: минимизация без штрафных функций

Рис. 6.2. Контуры функции минимизация со штрафными функциями

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

при всех итерациях, кроме последней, и неравенство

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

Если мы используем для оптимизации метод градиента, то нам надо вычислять первые, а иногда и вторые производные от

штрафных функций. Из равенства получаем:

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

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

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

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

что соответствует границам то мы могли бы положить «у Если же начальное приближение было «хорошим» в пределах допустимой области, то для величины хорошим выбором могло бы служить значение

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

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

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

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

В качестве примера предположим, что 0 1, и будем считать, что . В этом случае

так что

а это есть плотность бета-распределения.