Метод оврагов

Ставится задача найти минимум для овражной функции. Для этого выбираются две близкие точки и , и осуществляется спуск из этих точек (любым методом), причем высокой точности сходимости не требуется. Конечные точки спуска и будут лежать вблизи дна оврага. Затем осуществляется движение вдоль прямой, соединяющей и в сторону уменьшения (как бы вблизи дна оврага). Движение может быть осуществлено только на один шаг ~ h, направление выбирается из сравнения значения функции в точках и . Таким образом, находится новая точка . Так как возможно, что точка уже лежит на склоне оврага, а не на дне, то из нее снова осуществляется спуск в новую точку . Затем намечается новый путь по дну оврага вдоль прямой, соединяющей и . Если – процесс прекращается, а в качестве минимума в данном овраге используется значение .

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

10 Проблемы поиска минимума в задачах с большим числом измерений

Пусть в n -мерном векторном пространстве задана скалярная функция . Наложим дополнительные условия , 1 ≤ i ≤ m; , 1 ≤ j ≤ p. Условия типа равенств выделяют в пространстве некоторую (n – m)-мерную поверхность, а условия типа неравенств выделяют n -мерную область, ограниченную гиперповерхностями . Число таких условий может быть произвольным. Следовательно, задача inf есть поиск минимума функции n переменных в некоторой (n – m)-мерной области E. Функция может достигать минимального значения как внутри области, так и на ее границе. Однако перейти к (n – m)-мерной системе координат практически никогда не удается, поэтому спуск приходится вести во всем n -мерном пространстве.

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

Дата добавления: 2014-01-07