ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alex Cvetkov                         2:5030/1334    15 Feb 2003  02:20:38
 To : Evgenij Masherov
 Subject : Минимум
 -------------------------------------------------------------------------------- 
 

 
 14 Фев 03 09:45, Evgenij Masherov писал(ла) Alex Cvetkov:
 
  EM>>> Хотел бы видеть рекомендации достаточно общие, но, разумеется,
  EM>>> не столь общие, как полный перебор пространства параметров... И
  EM>>> приходится разбираться во всяких условиях Липшица и т.п.
  AC>> ну например основаные на знании переменной этого самого липшица.
  EM> Пожалуйста - рекомендации по определению. Ждем-с...
 
 рекомендации по определению глобального минимума?
 ок, способ простой на какую либо эффективность не претендует.
 Рассмотрим для простоты одномерную минимизацию. Изначально мы имеем отрезокна
 котором нам надо минимизировать функцианал. Выберем несколько точек
 (x[1],..,x[N]) и посчитаем в них значения функцианал (y[1],...,y[N]) (конци
 отрезкак входят в это множество).
 
 пусть xm=Arg(Min(y[i])
           i из (0..N)
 
 Из неравенства Липшеца |y[i]-y(x)]|<L*|x[i]-x|
 Предположим x[i]<x (для x[i]>x все будет выглядеть анналогично, x[i]=x
 рассматривать не будем)
 
 y(x) > y[i]-L*(x[i]-x) (учитывая что нас интересуют лишь те x при
 
 которых y(x) < y[i] )
  нас интересуют только те x при которых
 y(x)<y[xm]
 
 получаем y[xm] > y[i]-L*(x[i]-x)
 или что тоже самое x>x[i]+(y[xm]-y[i])/L
 
 Для точки x[i+1] соотношение будет выглядеть так x<x[i+1]-(y[xm]-y[i+1])/L
 
 Что дает нам в результате отрезок на котором может находиться минимум (или
 пустое множество)
 произведем все вышеперечисленные операции для всех i
 
 В результате получим множество отрезков на которых может находиться минимум.
 Повторим для каждого из них те же действия (только с учетом того что y[xm] надо 
 принимать равным минимальному наиденому на данный момент значению)
 
 Повторять все это безобразие до наступления момента когда длинна наибольшего из 
 отрезков не станет меньше необходимой точности.
 
 Уверен что существуют и более эффективные алгоритмы, с учетом того что на
 практике значения L велики этот будет медленнее черепахи.
 
 ps: знали бы мои одногрупники чем я занимаюсь в три часа ночи засмеяли бы.
 
  AC>> чтото я не вижу чем случайный поиск в такой ситуации лучше. если
  AC>> ситуация не осложнена высокой овражностью то любой метод
  AC>> основанный на квадратичной апроксимации будет иметь приимущество
  AC>> так как будет усреднять ошибку и если распределение вероятности
  AC>> ошибки симметрично то ошибки будут взаимоуничтожаться.
  EM> Для начала - тем, что работает и дает вполне удовлетворяющий
  EM> результат. Квадратичная аппроксимация в таких случаях также применима
  EM> ("эволюционное планирование"), но перестает работать при росте уровня
  EM> шума, когда случайный поиск еще эффективен.
 
 ну тут бы неплохо привести результаты тестов.
 
  EM>>> Hу, иногда нужна сбалансированная диета с выпиской о витаминном
  EM>>> составе, а иногда кусок хлеба - но сейчас...
  AC>> както не радует меня такой кусочек хлеба.
  EM> Боюсь, что ситуации, когда не вполне оптимальное решение и сейчас
  EM> стоит куда больше самого оптимальнейшего - но неизвестно когда, не
  EM> столь редки...
 
 ну вобщемто если наплевать на результат то зачем его вообще получать?
 
  AC>> ну вобщем могу резюмировать: звания уневерсальный этот метод не
  AC>> достоин.
  EM> унЕверсальный - безусловно. А вот известной унИверсальностью все же
  EM> обладает.
 
 к моему счастью мы находимся не в эхе по русскому языку, поэтому проигнорирую
 этот выпад.
 а универсальность эта весьма ограничена. Если нужно минимизировать овражный
 функционал или быстро точно посчитать значение минимума у параболы то он нервно 
 курит в сторонке.
 
                                            Alex Cvetkov
 
 --- Клиент морга
  * Origin: Life suxx (2:5030/1334)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Минимум   Alexander Shevchenko   06 Feb 2003 15:18:35   Минимум   Evgenij Masherov   07 Feb 2003 10:55:49   Re: Минимум   Sergiy Kanilo   07 Feb 2003 23:07:08   Re: Минимум   Evgenij Masherov   04 May 2003 08:44:55   Минимум   Alex Cvetkov   08 Feb 2003 15:00:30   Минимум   Ilya Rogov   09 Feb 2003 05:43:26   Минимум   Alex Cvetkov   10 Feb 2003 00:23:50   Минимум   Evgenij Masherov   09 Feb 2003 20:56:40   Минимум   Alex Cvetkov   10 Feb 2003 10:51:24   Минимум   Alexander Shevchenko   10 Feb 2003 17:07:24   Минимум   Evgenij Masherov   12 Feb 2003 12:27:00   Минимум   Alex Cvetkov   13 Feb 2003 01:28:15   Минимум   Evgenij Masherov   13 Feb 2003 10:43:32   Минимум   Alex Cvetkov   14 Feb 2003 02:35:06   Минимум   Evgenij Masherov   14 Feb 2003 10:45:09   Минимум   Alex Cvetkov   15 Feb 2003 02:20:38   Минимум   Evgenij Masherov   15 Feb 2003 10:31:55   Минимум   Alex Cvetkov   16 Feb 2003 02:14:46   Минимум   Evgenij Masherov   17 Feb 2003 10:57:59   Минимум   Alex Cvetkov   18 Feb 2003 02:25:18   Re: Минимум   Anatoly Saveliev   18 Feb 2003 09:17:03   Минимум   Alex Cvetkov   19 Feb 2003 11:48:43   Re: Минимум   Anatoly Saveliev   20 Feb 2003 09:20:04   Минимум   Alex Cvetkov   21 Feb 2003 11:40:38   Минимум   Evgenij Masherov   18 Feb 2003 10:23:37   Re: Минимум   Sergei Zubkov   13 Feb 2003 22:00:48   Минимум   Nick Poroshin   14 Feb 2003 23:48:45   Re: Минимум   Sergey Andrianov   14 Feb 2003 21:46:08   Минимум   Alexander Shevchenko   13 Feb 2003 18:18:37   Минимум   Evgenij Masherov   14 Feb 2003 11:53:04   Минимум   Boris Sivko   07 Feb 2003 01:32:02   Минимум   Alexander Shevchenko   07 Feb 2003 12:30:33   Минимум   Boris Sivko   08 Feb 2003 05:19:50   Минимум   Alexander Shevchenko   10 Feb 2003 17:23:41   Минимум   Boris Sivko   12 Feb 2003 14:03:47   Минимум   Ilya Rogov   09 Feb 2003 05:45:09   Минимум   Alexander Shevchenko   10 Feb 2003 17:32:53   Минимум   Ilya Rogov   28 Feb 2003 03:10:30   Re: Минимум   Anatoly Saveliev   28 Feb 2003 09:19:24   Минимум   Ilya Rogov   06 Mar 2003 02:39:02   Re: Минимум   Anatoly Saveliev   06 Mar 2003 12:31:36   Минимум   Alexander Shevchenko   03 Mar 2003 17:51:49   Re: Минимум   Valentin Davydov   09 Feb 2003 12:12:33   Минимум   Alexander Shevchenko   11 Feb 2003 15:57:43   Re: Минимум   Valentin Davydov   12 Feb 2003 20:21:50   Минимум   Stanislav Shwartsman   07 Feb 2003 00:08:07   Минимум   Alexander Shevchenko   07 Feb 2003 10:53:42   Re: Минимум   Sergiy Kanilo   07 Feb 2003 23:37:13   Минимум   Alexander Shevchenko   10 Feb 2003 17:21:03   Re: Минимум   Sergiy Kanilo   13 Feb 2003 00:53:59   Минимум   Alexander Shevchenko   13 Feb 2003 18:32:03   Минимум   Evgenij Masherov   14 Feb 2003 21:03:33