Re: Методы поиска глобального минимума.

From

Anatoly Saveliev ()

To

Alex Cvetkov

Date

2002-12-05T07:46:34Z

Area

RU.ALGORITHMS

From: Anatoly Saveliev <Anatoly.Saveliev@ksu.ru>

Alex Cvetkov wrote:
> 
> О сходимости в любых условиях? или всетаки в какихто конкретных.
> Не говоря уж о том что эта сходимость по вероятности.
> 
> У меня есть обратных примеров. Все вероятностные методы плохо работают в
> условиях высокой овражности. (Есть даже определение овражных функционалов как
> неоптимизируемых вероятностными методами)
> 
> Нахождение глобального экстремума возможно лиш при выполнении условия Лившица.
> Причем необходимо знание коэфициэнта лившица (или ее оценки сверху)
> Но все известные методы работают крайне медленно. Не говоря уж о том что
> вычеисление этого коэфициэнта задача не из простых.
 
Лифшиц фамилия знакомая, но на память приходит матанализ. А в anealing
все сводится к Марковской цепи без финальных состояний (и финальных
циклов), проще говоря вероятность перехода из любого состояния в любое
больше нуля, и имея конечную разрядность представления чисел в
компьютере, получаем Марковскую цепь, которая побывает в КАЖДОМ
состоянии и найдет минимум. Управляя разрядностью, управляем точностью
решения, а зная рапределение вероятностей положения минимума (априорное
или оцененное по ходу дела) повышаем скорость сходимости. И если
температуру понижать со скоростью не быстрее установленной законом (см.
соотв. литературу, наибольшая скорость - у Инбера), то процесс сходится
(по вероятности) к глобальному минимуму.

Анатолий Савельев 
Казанский университет
--- ifmail v.2.15dev5
 * Origin: MELT InterNetNews site (2:5020/400)