Минимизация функции двух переменных

[InnaStratiychuk]

Очень нужна помощь в таком вопросе:
У нас задана функция двух переменных на плоскости(прямоугольник) надо найти ее минимум не используя градиентные методы которые сразу показывают на мин.(макс) функции, а с помощью генератора случайных чисел random(0.1).
То есть первую точку на плоскости задаем сами. Вторую точку вместо направления градиента выдает random и с ее помощью вычисляется минимум функции. Потом из этой точки минимума снова с помощью random генерируется направления градиента, находится точка минимума и итерации продолжаются до тех пор пока расстояние между точками не станет меньше определенного эпсилом=00.1... Проблема в чем: программа(алгоритм) находит 4 точки минимума, а потом просто зацикливается....получается что из-за random точка минимума гуляет по плоскости так и не показывая, где он находится...
Может вы знаете как сузить область поиска точки минимума.....

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

Подскажите может знаете какой то еще алгоритм поиска минимума функции без использования градиента??????????????????????

[ewert]

Ну например так можно. Задаём четыре параметра: количество попыток на шаге $m$, минимально допустимый "процент успешности" $\theta$, начальный радиус поиска $r$ и коэффициент его уменьшения $\alpha$. На каждом шаге озираемся по сторонам, смещаясь от текущей точки $m$ раз по случайно выбираемым направлениям на расстояние $r$ от текущего приближения, параллельно подсчитывая, какой процент попыток оказался успешным в том смысле, что значение целевой функции уменьшилось, а не увеличилось. Если успешными оказались более $\theta n$ попыток, то берём в качестве нового приближения наилучшую попытку. Если нет -- уменьшаем $r$ в $\alpha$ раз и повторяем всё заново. Критерием точности может служить, например, отношение приращения целевой функции в двух последних приближениях к расстоянию между ними (на всякий случай можно ещё усреднить их по нескольким последним итерациям).

Это навскидку. Не помню, как там принято в приличном обществе. Во всяком случае, это будет работать.

[мат-ламер]

Постановку задачи не понял. Метод работает так как и был задуман и сходиться не обязан. Надо предложить другой метод не использующий градиенты или модифицировать первый? Тогда в каких рамках? Если исходить из того, что направление поиска выбирается случайно, а можно выбирать длину шага, то длину шага ограничивайте, чтобы она не превосходила какую-либо константу, причём эта константа должна постепенно стремиться к нулю. Есть книги по случайному поиску. Вроде автор Растригин, но я тут не специалист. Если направление поиска выбирать не случайно и градиентами не пользоваться, то можно воспользоваться методом деформирующего многогранника (Пауэлла). Описание есть в некоторых книгах ( Уайлд "Методы поиска экстремума".Гилл,Мюррей "Практическая оптимизация").

[ewert]

мат-ламер в сообщении #312811 писал(а):

Постановку задачи не понял. Метод работает так как и был задуман и сходиться не обязан.

И я тоже не понял. Как мог работать метод, который и по замыслу-то не обязан был работать?... что ваще понимается под "работой"?...