2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Методы минимизации дискретных функций
Сообщение25.03.2008, 11:09 
Здравствуйте! Есть следующая задача:
Имеется дискретная функция, заданная на конечном числе элементов:
$F(u)$, где $u=(u_1,...u_N)$
Необходимо найти $u$,при котором функция достигает минимума.
Сейчас это решается так: Заменяем $F(u)$ на непрерывную фунцкию $F(u,S)$. $F(u,S) \rightarrowF(u)$, при $S\rightarrow0$.
Постепенно уменьшая $S$, находим на каждом шаге локальный минимум $F(u,S)$ , для каждого нового $S$ стартуем с предыдущего минимума. Этот метод очень напоминает GNC(Graduated non-convexity)...
Вопрос: какие существуют еще методы ? ( без перехода к непрерывной функции) Где можно об этом почитать?
То, что было найдено: Алгоритм имитации отжига (Simulated annealing) не подходит (уж оч медленно считается).

 
 
 
 
Сообщение26.03.2008, 14:10 
Можно ли чуть-чуть по-подробнее ? Дискретная функция принимает дискретное множество значений ? Аргумент $u$ насколько я понимаю тоже выбирается из приведённого набора, или это вектор из $N$ компонент ?

 
 
 
 
Сообщение26.03.2008, 17:09 
Да, функция принимает $F(u)$ принимает конечное значений.
Значения аргумента $u_i \in [0,255] \subset N$ (например, если мы говорим, о пространстве $RGB$) - значения пикселей в изображении,
функция (точнее, функционал - т.к. значения в пикселах зависят от их(пикселей) пространственного расположения) - энергия картинки, содержащая дельты Кронекера (от цвета пиксела и цвета его соседа), вот эти-то дельты и заменяются непрерывной функцией.

 
 
 
 
Сообщение26.03.2008, 17:35 
Т.е. в Ваших терминах задача состоит в том, чтобы подобрать изображение(т.е. матрицу пикселей), обладающее минимальной энергией, так ?

 
 
 
 
Сообщение26.03.2008, 17:46 
Да.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group