Посоветуйте алгоритм оптимизации

stm7583298

Есть равномерная трехмерная сетка со значениями некоторой функции, не очень большая (около 100 точек на каждой стороне). Функция аналитически непредставима. Задача - найти там локальные минимумы, желательно все Каким алгоритмом это лучше делать? Поградиентному спуску на такой задаче я что-то не очень доверяю, т.к. расстояние между узлами не слишком маленькое.

koly

А чем не подходит простой перебор?
Рассматриваем каждую из точек Аi, в которых определена функция (их около 1000000). Дальше рассматриваем все соседние точки (их от 6 до 26, в зависимости от того, что считать экстремумом). Если значение Ai минимально среди своих соседей, то это локальный минимум.
Сложность процедуры - от 6*10^6 до 26*10^6

vall

а про функцию что-нить вобще известно?
соседей 4 или 8?

disna

помнится, есть еще метод Ньютона
почитать можно тут с 13 страницы

koly

4или 8 это не для трехмерной

vook

Берем начальную точку и спускаемся туда, где значение меньше. Если функция дискретная, то других алгоритмов и не придумаешь.

margadon

Simulated Annealing?

stm7583298

thx! Завтра попробую bruteforce-метод Градиентными методами не захотелось именно из-за дискретности.

stm7583298

А как можно SA-алгоритм применить к такой задаче?

koly

Есть оптимизация брутфорса. Она позволит снизить сложность брутфорса с 6*n^3 до 3*n^3. Но это вряд ли понадобится

stm7583298

Может и понадобиться, сложность конкретной задачи - 26*10^6

vall

лучше тогда наверно с начала смотреть на минимальность по одному направлению.
получится что-то вроде n^3 + 24*m
(m - точек минимальных по выбранному направлению)
их наверняка будет не сильно больше чем искомых, если конечно функция не вида (-1)^(x+y+z)