Ограничения

Большинство задач оптимизации ставятся вместе с ограничениями, о чем говорилось в предыдущем разделе. Ограничения могут быть трех типов. Ограничения первого типа задают область определения переменных оптимизации. Эти ограничения легко выполнить, потребовав, чтобы в процессе поиска переменные не выходили за установленные рамки. Ограничения второго типа — равенства — сокращают размерность пространства решений. Лучшим методом обработки этих ограничений является исключение переменных алгебраическим путем. Однако метод исключения переменных применим только до тех пор, пока уравнения ограничений допускают решение относительно независимых переменных. При наличии нескольких ограничений процесс исключения может стать достаточно громоздким. В некоторых случаях явное решение уравнений может оказаться невозможным. Альтернативой является использование штрафных функций (penalty function), о которых речь пойдет ниже [6].

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

Ограничения

где Rn — подмножество Rn, соответствующее только допустимым конструкциям, то есть таким, которые удовлетворяют всем ограничениям. Теперь мы можем без ограничений решать задачу минимизации дополненной целевой функции, или функции спуска (descent function) D(X):

Ограничения

Однако оптимизация без ограничений в данном случае невозможна (за исключением, быть может, некоторых тривиальных случаев) из-за разрывов в D(X) на границе Rn , а также бесконечности значений вне Rn. Замена бесконечности на «большой», но конечный штраф не упростила бы задачу, поскольку все равно остались бы численные трудности. Для решения этих проблем предложено было использовать две штрафные функции: внутреннюю и внешнюю.

 

Смотрите также