Главная > Математика > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2. Метод штрафных функций.

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

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

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

где величина константы зависит от конкретных свойств функций (38). Поэтому если взять последовательность и найти для нее минимумы вспомогательной функции то .

Задачу (39) на безусловный экстремум удобнее всего решать методом случайного поиска со спуском по сопряженным направлениям: здесь естественно задана область, где надо выбирать случайные точки.

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление