Метод случайного спуска (8.1.) — метод, в котором направление спуска выбирается в соответствии с равномерным случайным распределением на n-мерной сфере. [c.344]
Эти утверждения вполне очевидны, и мы их доказывать не будем. Отметим лишь, что чем уже множество стационарных точек, тем надежнее метод поиска. С этой точки зрения предпочтителен случайный поиск. Однако с точки зрения эффективности предпочтительнее метод наискорейшего спуска. Не исключенная в принципе опасность застрять в точке перегиба маловероятна, так как такие точки являются неустойчивыми точками метода наискорейшего спуска, в отличие от точки локального минимума, являющейся устойчивой. [c.395]
Метод случайного поиска. Реализация изложенных выше методов минимизации в общем случае очень трудоемка, кроме простейших случаев, когда множество ограничений обладает простой геометрической структурой (например, является многомерным параллелепипедом). В общем случае весьма перспективным может быть метод случайного поиска, когда направление спуска выбирается случайным образом. При этом мы будем существенно проигрывать в скорости сходимости, однако простота выбора направления может компенсировать эти потери с точки зрения общих затрат труда на решение задачи минимизации. [c.181]
Проблема глобального минимума. Все методы, о которых шла речь, если сходятся, то лишь к точке локального минимума функции. Если таких точек несколько, результат зависит от выбора начального приближения. Разумеется, хотелось бы получить абсолютный минимум, да еще и гарантию, что получен действительно абсолютный (глобальный) минимум. К сожалению, в общем случае эта задача, видимо, неразрешима. Точнее, практически неразрешима. Единственный реальный подход к этой задаче состоит в том, чтобы, начиная из разных начальных точек, алгоритмом спуска найти возможно большее число точек локального минимума и отобрать из них точку с наименьшим значением функции. Что касается выбора стартовых точек спуска, то при отсутствии каких-то частных, связанных с данной задачей содержательных указаний, приходится выбирать их случайным образом. К сожалению, в сложных прикладных задачах поиск локального минимума сам по себе достаточно трудоемок, так что возможности комбинировать его со случайным выбором стартовых точек весьма ограничены. Это, разумеется, относится и к задачам оптимального управления, причем ситуация осложняется еще и тем, что аргументом является функция, и выбор даже не очень плотного множества стартовых точек в функциональном пространстве с последующим спуском приводит к нереальным затратам машинного времени. Поэтому приходится ограничиваться сравнительно небольшим числом проб, до возможности используя для [c.404]
Скорость сходимости метода случайного спуска в п раз ниже, чем у метода градиентного спуска, но в п раз выше, чем у метода случайного покоординатного спуска. Рассмотренные методы спуска применимы и к необязательно выпуклым функциям и гарантируют их сходимость при очень малых на них ограничениях (типа отсутствия локальных минимумов). [c.179]
Разработан ряд стохастических методов решения поставленной оптимизационной задачи распараллеливания вычислений. В первом методе — стохастическом методе попарной оптимизации подграфов — поиск оптимального решения осуществляется за счет взаимного (стохастического) переноса вершин между различными парами подграфов графа алгоритма. Второй метод — метод Монте-Карло случайного блуждания вершин графа алгоритма по подграфам — основан на отождествлении вершин графа алгоритма с некоторыми частицами, совершающими случайные блуждания по областям-подграфам в потенциальном силовом поле, роль потенциала которого играет минимизируемый функционал. Наиболее вероятное состояние подобной системы частиц соответствует минимуму потенциала —-и, следовательно, является искомым решением. Поиск такого состояния осуществляется методом Монте-Карло с использованием специальной процедуры имитации отжига . Третий метод — стохастический метод наискорейшего спуска — основан на использовании дискретного аналога градиента минимизируемого функционала. Все разработанные методы реализованы программно и являются частью системы программ PARALLAX. Проведено тестирование созданных программ и сравнение их работы на простейших примерах. [c.166]
В ыредыдущем пункте условия сходимости метода формулировались в терминах случайной функции < >дП) (ш 1, Я"). Рассмотрим теперь требования к функционалу Q (Я) = Q (Яи) = Мюп ф л) (шп, Я7 ( on 1)), гарантирующие сходимость метода покоординатного спуска. [c.227]