|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 15 Feb 2003 10:31:55
To : Alex Cvetkov
Subject : Минимум
--------------------------------------------------------------------------------
Sat Feb 15 2003 01:20, Alex Cvetkov wrote to Evgenij Masherov:
EM>>>> Хотел бы видеть рекомендации достаточно общие, но, разумеется,
EM>>>> не столь общие, как полный перебор пространства параметров... И
EM>>>> приходится разбираться во всяких условиях Липшица и т.п.
AC>>> ну например основаные на знании переменной этого самого липшица.
EM>> Пожалуйста - рекомендации по определению. Ждем-с...
AC> рекомендации по определению глобального минимума?
AC> ок, способ простой на какую либо эффективность не претендует.
AC> Рассмотрим для простоты одномерную минимизацию. Изначально мы имеем
AC> отрезокна котором нам надо минимизировать функцианал. Выберем несколько
AC> точек (x[1],..,x[N]) и посчитаем в них значения функцианал
AC> (y[1],...,y[N]) (конци отрезкак входят в это множество).
AC> пусть xm=Arg(Min(y[i])
AC> i из (0..N)
AC> Из неравенства Липшеца |y[i]-y(x)]|<L*|x[i]-x|
AC> Предположим x[i]<x (для x[i]>x все будет выглядеть анналогично, x[i]=x
AC> рассматривать не будем)
y(x) >> y[i]-L*(x[i]-x) (учитывая что нас интересуют лишь те x при
AC> которых y(x) < y[i] )
AC> нас интересуют только те x при которых
AC> y(x)<y[xm]
AC> получаем y[xm] > y[i]-L*(x[i]-x)
AC> или что тоже самое x>x[i]+(y[xm]-y[i])/L
AC> Для точки x[i+1] соотношение будет выглядеть так
AC> x<x[i+1]-(y[xm]-y[i+1])/L
AC> Что дает нам в результате отрезок на котором может находиться минимум
AC> (или пустое множество) произведем все вышеперечисленные операции для всех
AC> i
AC> В результате получим множество отрезков на которых может находиться
AC> минимум. Повторим для каждого из них те же действия (только с учетом того
AC> что y[xm] надо принимать равным минимальному наиденому на данный момент
AC> значению)
AC> Повторять все это безобразие до наступления момента когда длинна
AC> наибольшего из отрезков не станет меньше необходимой точности.
AC> Уверен что существуют и более эффективные алгоритмы, с учетом того что на
AC> практике значения L велики этот будет медленнее черепахи.
AC> ps: знали бы мои одногрупники чем я занимаюсь в три часа ночи засмеяли
AC> бы.
Только вот для этого метода хорошо бы и каким-то образом знать константу
Липшица...
AC>>> чтото я не вижу чем случайный поиск в такой ситуации лучше. если
AC>>> ситуация не осложнена высокой овражностью то любой метод
AC>>> основанный на квадратичной апроксимации будет иметь приимущество
AC>>> так как будет усреднять ошибку и если распределение вероятности
AC>>> ошибки симметрично то ошибки будут взаимоуничтожаться.
EM>> Для начала - тем, что работает и дает вполне удовлетворяющий
EM>> результат. Квадратичная аппроксимация в таких случаях также применима
EM>> ("эволюционное планирование"), но перестает работать при росте уровня
EM>> шума, когда случайный поиск еще эффективен.
AC> ну тут бы неплохо привести результаты тестов.
Интересная задача для академического исследования - но я могу, увы, привести
только скромный практический опыт...
EM>>>> Hу, иногда нужна сбалансированная диета с выпиской о витаминном
EM>>>> составе, а иногда кусок хлеба - но сейчас...
AC>>> както не радует меня такой кусочек хлеба.
EM>> Боюсь, что ситуации, когда не вполне оптимальное решение и сейчас
EM>> стоит куда больше самого оптимальнейшего - но неизвестно когда, не
EM>> столь редки...
AC> ну вобщемто если наплевать на результат то зачем его вообще получать?
Hу зачем же доводить до абсурда? Есть реальная задача, есть употребляемый
сейчас набор параметров, есть желание подобрать лучший. При это известно, что
при практической реализации параметры будут выставлены с известной
погрешностью, так что дополнительная точность определения оптимума и не
востребуется. И случайный поиск дает быстрый ответ за время, пока метод
сколько-нибудь более продвинутый будет записываться...
AC>>> ну вобщем могу резюмировать: звания уневерсальный этот метод не
AC>>> достоин.
EM>> унЕверсальный - безусловно. А вот известной унИверсальностью все же
EM>> обладает.
AC> к моему счастью мы находимся не в эхе по русскому языку, поэтому
AC> проигнорирую этот выпад.
AC> а универсальность эта весьма ограничена. Если нужно минимизировать
AC> овражный функционал или быстро точно посчитать значение минимума у
AC> параболы то он нервно курит в сторонке.
Hу, если мне нужно будет найти минимум параболы - то я им, вестимо, не
воспользуюсь. А вот с овражными был положительный опыт. Разумеется, это не
случайный наброс, а адаптивный случайный.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Минимум |
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 |
|
|
