Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

пределенных случайных величин. При г = 2, е = 0 ,0 0 2 среднее число вычислений значений функции оказалось равным 29. При этом

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

2 . Кратко остановимся на методах минимизации, когда на зна­ чения функции /(и ) в каждой точке и накладываются случайные ошибки или, как говорят, помехи. Такая ситуация, в частности, имеет место в том случае, когда значения функции J (и) получают­ ся в результате измерений какой-либо физической величины. При наличии помех многие рассмотренные выше методы непригодны для поиска минимума функции, и здесь целесообразно пользовать­ ся методом стохастической аппроксимации [45], [230].

Опишем один из вариантов этого метода. Наблюдаемые в экс­

ошибок. Тогда для поиска минимума функции /(«) при — о о < ц < <-|-оо может быть использована следующая процедура Кифера— Вольфовица [45], [230]:

точно широких предположениях относительно функции J (и) и вероят­

ностных характеристик случайной величины z{u) можно доказать схо­ димость по вероятности последовательности {и,,}, определяемой фор­ мулами ( 1), к точке глобального минимума J (и) [45].

Практическое применение метода (1) показало, что его схо­ димость, вообще говоря, сильно замедляется в тех случаях, когда слева от точки минимума и* график функции имеет крутой спуск, справа от и* — крутой подъем, а на остальных участках функции /(«) изменяется медленно. Тогда на пологих участках шаги поис­ ка |мп+1— «п| могут стать очень малыми, а на крутых участках, наоборот, достаточно большими, и в результате большая часть вре­ мени на поиск может быть затрачена на чрезмерно медленные спуски на пологих участках и последующие большие скачки че­ рез точку минимума с попаданием на другой пологий участок. В таких ситуациях может оказаться полезной следующая так на­

строгое обоснование этого метода и различные приложения можно найти в работе [45]. Другой метод поиска минимума при наличии помех описан в работе [213].

Г л а в а 2

Минимизация функций многих переменных

Г

§ 1. ПОСТАНОВКА ЗАДАЧИ. ОБОЗНАЧЕНИЯ. ВСПОМОГАТЕЛЬНЫЕ СВЕДЕНИЯ

1.Пусть на некотором множестве U /n-мерного евклидов

точку u * e U y в которой /(и*) = / *; 3) если нижняя грань не дости­ гается на U, то указать последовательность {un}czU , для которой

lim J(u n) = J* . Точку u *^ U со свойством J ( u * ) = J * называют

—»оо

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

Точка и*, являющаяся решением системы уравнений (1), назы­ вается стационарной точкой функции /(и ). Если стационарные точки найдены, то среди них нужно выбрать те точки, в которых в самом деле достигается минимум. Для этого нужно провести дополнительное исследование поведения функции в окрестности стационарной. точки. Если функция J(u) дважды непрерывно

52 МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ [Гл. 2

дифференцируема, то наряду с системой ( 1 ) рассматривается квадратичная форма

у»/(«*) « у

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

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

ход просто незаменим и дает полное решение задачи минимиза­ ции в аналитическом виде через различные параметры задачи.

К настоящему времени разработано и исследовано на сходи­ мость довольно много методов минимизации функций многих пере­ менных. В наших лекциях будут рассмотрены некоторые наиболее часто используемые на практике итерационные методы, позволяю­ щие при определенных условиях строить последовательности {и„}, которые являются минимизирующими или сходятся к точке мини­ мума. Част*? из этих методов пригодна для поиска минимума функции на всем пространстве Ет, часть — на ограниченных мно­ жествах U, а некоторые методы нетрудно приспособить к поиску минимума как при U = E m, так и при и ф Е т, причем может быть

всем пространстве Ет, — здесь речь идет о так называемом методе штрафных функций. Будет изложена вычислительная схема каж ­ дого из этих методов, при некоторых предположениях на функции и множество U будет доказана их сходимость, а в ряде случаев по­ лучим оценку скорости сходимости и дадим краткую характе­ ристику методов. При этом рассмотрим лишь основные ва­