1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 48
Текст из файла (страница 48)
(37) Следовательно, направление, соединя>ощее точки минимума на двух параллельных прямых, сопряжено направленгио этих прямых. Таким образом, всегда можно построить вектор, сопряженный произвольному заданному вектору х. Для этого достаточно провести две прямые, параллельные эс, и найти на каждой прямой минимум квадратичной формы (30). Вектор е1 — т„соединяющий эти минимумы, сопряжен х. Заметим, что прямая касается линии уровня в той точке, где функция на данной прямой принимает минимальное значение; с этим связано название способа. Пусть имеются две параллельные т-мерные плоскости, порожденные системой сопряженных векторов эс„ 1 == 1:- т (и. Пусть квадратичная функция достигает своего минимального значения на этих плоскостях соответственно в точках е; и гт.
Аналогичными рассуждениями можно доказать, что вектор г; — г„, соединяющий точки минимума, сопряжен всем векторам х>. Следовательно, Если задана неполная система сопряженных векторов эс>, то этим способом всегда можно построить вектор г',— г', сопряженный всем векторам этой системы. Р а с с м о т р и м од и н ц и к л процесса построения сопряженного базиса. Пусть уже построен базис, в котором последние т векторов взаимно сопряжены, а первые и — т векторов не сопряжены последним. Найдем минимум квадратичной функции (30) в какой-нибудь т-мерной плоскости, порожденной последними т векторами базиса. Поскольку эти векторы взаимно сопряжены, то для этого достаточно произвольно выбрать точку т; и сделать из нее спуск поочередно по каждому из этих направлений (до минимума!).
Точку минимума в этой плоскости обозначим че- РЕЗ г'1. Теперь из точки г1 сделаем поочередный спуск по первым и — т векторам базиса. Этот спуск выведет траекторию из первой плоскости и приведет ее в некоторую точку т,. Из точки гз МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМеННЫХ 2!3 снова совершим по последним и направлениям спуск, который приведет в точку г'„. Этот спуск означает точное нахожденне минимума во второй плоскости, параллельной первой плоскости.
Следовательно, направление г,— г, сопряжено последним т векторам базиса. Если одно из несопряженных направлений в базисе заменить направлением ге — вм то в новом базисе уже и + 1 направление будет взаимно сопряжено. Начнем расчет циклов с произвольного базиса; для него можно считать, что т = 1. Описанный процесс за один цикл увеличивает на единицу число сопряженных векторов в базисе. Значит, за п — 1 цикл все векторы базиса станут сопряженными, и следующий цикл приведет траекторию в точку минимума квадратичной функции (30). в) Хотя понятие сопряженного базиса определено только для квадратичной функции, описанный выше процесс построен так, что его можно формально применять для произвольной функции.
Разумеется, что при этом находить минимум вдоль направления надо методом парабол, не используя нигде формул, связанных с конкретным видом квадратичной функции (30). В малой окрестности минимума приращение достаточно гладкой функции обычно представимо в виде симметричной положительно определенной квадратичной формы типа (18). Если бы это представление было точным, то метод сопряженных направлений сходился бы за конечное число шагов. Но представление приближенно, поэтому число шагов будет бесконечным; зато сходимость этого метода вблизи минимума будет квадратичной. Благодаря квадратичной сходимости метод сопряженных направлений позволяет находить минимум с высокой точностью. Методы с линейной сходнмостью обычно определяют экстремальные значения координат менее точно.
Замечание 1. Реально даже для квадратичной функции процесс не всегда укладывается в и циклов. Построение сопряженного базиса означает ортогонализацию в метрике, порожденной матрицей А. Ранее отмечалось, что в процессе ортогонали.зации теряется точность; при большом числе переменных погрешность настолько возрастает, что процесс приходится повторять. Замечание 2.' Теоретически безразлично, какое из несопряженпых направлений выкинуть из базиса в конце цикла. Обычно выкидывают то направление, при спуске по которому на данном цикле функция изменилась менее всего. Поскольку для произвольной функции понятие сопряженности ввести нельзя, то направление наиболее слабого убывания выкидывают независимо от того, под каким номером оно стоит в базисе. Любопытно, что это оказывается выгодным даже для квадратичной функции, хотя 2!4 1гл.
Ми ПОИСК МИНИМУМА на основании этого критерия иногда можно выкинуть сопряженное направление, оставив несопряженные; зато уменьшается потеря точности при ортогонализации. Замечание Э. Описанный выше цикл метода включает два спуска по сопряженным направлениям и один — по несопряженным. Более выгоден цикл, при котором сразу после нахождения нового сопряженного направления по нему делают спуск из точки т„, приходя в некоторую тачку т;. Тогда спуск из т', в г4 будет спуском в плоскости всех новых сопряженных направлений, т. е. его можно считать первой группой нового цикла спусков. Поэтому из точки г, сразу можно спускаться по несопряжениым направлениям. При этом новое направление ставят в базис на последнее место и выкидывают то направление, на котором функция слабее всего уменьшилась при спусках от точки г, до точки т4.
Наименее выгодным может оказаться и новое направление; тогда следующий цикл спусков будет сделан со старым базисом. Метод сопряженных направлений является, по-видимому, наиболее, эффективным методом спуска. Он неплохо работает и при вырожденном минимуме, и при разрешимых оврагах, и при наличии слабо наклонных участков рельефа — <плато»; и при большом числе переменных — до двух десятков.
6. Случайный поиск. Методы спуска неполноценны на неупорядоченном рельефе. Если локальных экстремумов много, то спуск из одного нулевого приближения может сойтись только к одному из локальных минимумов, не обязательно абсолютному. Тогда для исследования задачи применяют случайный поиск. Предполагают, что интересующий нас минимум (или все минимумы) лежит в некоторой замкнутой области; линейным преобразованием координат помещают ее внутрь единичного и-мерного куба, Выбирают в этом кубе У случайных точек способами, описанными в ~ 4 главы 1Ъ', если о расположении экстремумов зара-' нее ничего не известно, то наилучшие результаты дают ЛП; последовательности точек.
Даже при миллионе пробных точек вероятность того, что хотя бы одна точка попадет в небольшую окрестность локального минимума, ничтожно мала. В самом деле, пусть диаметр котловины около минимума составляет 10О.' от пределов изменения каждой координаты. Тогда объем этой котловины составляет 0,1" часть объема и-мерного куба. Уже при и ~ б ни одна точка в котловину не попадет. Поэтому берут небольшое число точек л1 — (5 — 20) п и каждую точку рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска сильно укорачиваются, его прекращают, не добиваясь высокой точности. Этого уже достаточно, 215 МИНИМУМ В ОГРАНИЧБННОИ ОБЛАСТИ $ 31 чтобы судить о величине функции в ближайшем локальном минимуме с удовлетворительной точностью.
Сравнивая (визуально или при помощи программы) окончательные значения функции на всех спусках между собой, можно изучить расположение локальных минимумов функции и сопоставить их величины. После этого можно отобрать нужные по смыслу задачи минимумы и провести в них дополнительные спуски для получения координат точек минимума с высокой точностью.
Обычно в прикладных задачах нужно в первую очередь добиться того, чтобы исследуемая функция приняла минимальное или почти минимальное значение. Но вблизи минимума значение функции слабо зависит от изменения координат. Зачем 1тогда нужно находить координаты точки миниыума с высокой точностью? Оказывается, что это имеет не только теоретический, по и практический смысл. Пусть, например, координаты — это размеры деталей механической конструкции, а минимизируемая функция есть мера качества конструкции.
Если мы нашли минимум точно, то мы находимся в самом центре котловины около минимума. Б этом случае вариации координат влияют на функцию слабее, чем в точках, расположенвых ближе к краям котловины. А безопасные вариации координат имеют в данном примере смысл допусков на точность обработки деталей. Значит, при аккуратном вычислении координат минимума мы можем разрешить ббльшие допуски, т. е. удешевить обработку деталей.
Метод случайного поиска зачастую позволяет найти все локальные минимумы функции от 1Π— 20 переменных со сложным рельефом. Он полезен и при исследовании функции с единственным минимумом; вэтом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Если мы зададим слишком широкую область, то ее труднее детально исследовать, а если выберем слишком узкую область, то многие локальные минимумы могут оказаться вне ее.
Правда, положение несколько облегчается тем, что при спусках траектории могут выйти за пределы заданной области и сойтись к лежащим вне этой области минимумам. $ 3. Минимум в ограниченной области 1. Формулировка задачи. Пусть в ц-мерном векторном пространстве задана скалярная функция Ф (х). Расслютрим задачу на минимум с дополнительнымн условиями двух типов: Ф (х) = ппп, ср; (х) =О, 1 =--(==-т, фу(х)=-0, 1 =1 — Р. (38) Условия типа равенств выделяют в пространстве некоторую (л — т)- мерную поверхность; поэтому должно выполняться неравенство т ( и.
Условия типа неравенств выделяют и-мерную область, ограниченную гиперповерхностями ф (х) = 0; число таких условий 216 1гл. Уп ПОИСК МИНИМУМЛ может быть произвольным. Следовательно, задача (38) есть поиск минимума функции и переменных в (и — т)-мерной области 6. Функция может достигать минимального значения как внутри области, так и на ее границе. Зта задача и особенно последний случай трудны для расчета. Вид дополнительных условий в любой реальной задаче не слишком прост, так что явно ввести в области 6 собственную (и — т)-мерную систему координат практически никогда не удается.
Значит, при численном расчете мы вынуждены вести спуск не на (и — т)-мерной поверхности, а во всем л-мерном пространстве. Тогда даже если нулевое приближение лежит в области 6, естественная траектория спуска сразу выходит из этой области; особенно сложно «заставить» траекторию идти вдоль границы области. В математических задачах экономики поиск минимума при дополнительных условиях называют (в зависимости от типа функций) линейным, нелинейным и т. д. программированием.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
