Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Яма на плоскости - найти минимум, производные не считаются 
:(
    Опции темы
_Y_
Дата 22.8.2007, 12:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1651
Регистрация: 27.11.2006

Репутация: 8
Всего: 34



Задача на первый взгляд тривиальная, но я заткнулся. Надо найти минимум функции двух аргументов (X и Y). Проблема в том, что функция включает экспоненты. Это приводит к тому, что ее численные значения (в силу конечной машинной точности) выглядят как горизонтальная плоскость с ямкой в каком-то месте. Известные мне численные методы (типа метода Ньютона) требуют хорошего начального приближения. Т.е. если начальные значения X и Y попадают на "плоскость", результат не считается. А вот с начальным приближением-то и проблема :(

Еще одно ограничение - из-за тех же экспонент рассчет производной еще больше страдает от  конечности машинной точности. Поэтому считать надо саму функцию, а не производную.

Подскажите, пожалуйста, как решить проблему? Пойдет и случай для функции одной переменной - я как-нибудь разберусь.

Спасибо


--------------------
Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:)
PM MAIL WWW   Вверх
Einwill
Дата 22.8.2007, 16:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 21.8.2007

Репутация: нет
Всего: нет



А может достаточно будет подействовать на функцию каким-нибудь преобразованием, чтобы она перестала быть плоской ямой? Например, использовать логорифмическую шкалу по оси ординат.
PM MAIL   Вверх
VictorTsaregorodtsev
Дата 23.8.2007, 10:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 274
Регистрация: 28.7.2006

Репутация: 3
Всего: 8



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

Ну и непонятно, как вообще задача решалась - Ваша собственная программа или что-нибудь готовое типа Mathcad, Maple и т.д.
PM MAIL WWW   Вверх
_Y_
Дата 23.8.2007, 12:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1651
Регистрация: 27.11.2006

Репутация: 8
Всего: 34



Einwill, логарифмировать я бы попробовал, но в функции суммы, так что не помогает.

VictorTsaregorodtsev. 1. Программа собственная. 2. Символьная арифметика это здорово, но, в моем случае, сьест слишком много процессорного времени. И так ожидается, что каждый вариант задачи будет считаться "до утра". 3. Я, к сожалению, мало знаю о генетических алгоритмах, но Ваше краткое обяснение, видимо, совпадает с тем, что я сотворил сам к данному моменту. А именно:
  • Имею функцию, которую хочу минимизировать: f(X,Y)=min.
  • Задаю интервалы Xmin<X<XmaxYmin<Y<Ymax.
  • Проверяю равенства f(Xmin,Ymin)=f(Xmax,Ymin)=f(Xmin,Ymax)=f(Xmax,Ymax). Если какое-то из этих значений меньше других - ура! - попал на "склон ямы" Но
    это врядли. Обычно значения соответствуют "плоскости".
  • Генератором случайных чисел генерирую X и Y в заданных интервалах и считю для них f(X,Y) пока не попаду на значение "ниже плоскости". Ограничиваю число попыток, чтобы не завесить программу в случае неправильно выбранных интервалов поиска.
  • Значения X и Y, найденные в одном из двух предидущих пунктов (соответствуюшие "склону ямы") использую как начальное и тупо "качу шарик на дно".
Алгоритм рабортает, но, к сожалению, требует вручную "бороться" с подбором интервалов поиска для каждого рассчета. Ну да ладно, если ничего лучше нет - сойдет.

Это сообщение отредактировал(а) _Y_ - 23.8.2007, 12:15


--------------------
Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:)
PM MAIL WWW   Вверх
Dims
Дата 24.8.2007, 07:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1016
Регистрация: 21.11.2006

Репутация: 1
Всего: 11



Цитата(_Y_ @ 23.8.2007,  12:13)
Einwill, логарифмировать я бы попробовал, но в функции суммы, так что не помогает.

Непонятно, почему? Добавьте просто в конце функции численное взятие логарифма и ищите минимум уже этой функции, тоже численно. 
PM MAIL   Вверх
_Y_
Дата 24.8.2007, 09:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1651
Регистрация: 27.11.2006

Репутация: 8
Всего: 34



Цитата(Dims @ 24.8.2007,  07:47)
Цитата(_Y_ @ 23.8.2007,  12:13)
Einwill, логарифмировать ... в функции суммы ... не помогает.

Добавьте в конце функции численное взятие логарифма и ищите минимум уже этой функции, тоже численно.

В конце безсмысленно. Например:

A1 = S + D1
A2 = S + D2
D1 <> D2


Но! И  D1 и D2 меньше машинной ошибки S.

Поэтому A1 == A2==S в пределах машинной ошибки, естествено, т.е. получаю плоскость. Чем мне легче, если я считаю
A1 = log(S + D1)
A2 = log(S + D2)

? Все равно в пределах ошибки получаю A1 == A2==log(S + D1)==log(S + D2)==log(S)


--------------------
Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:)
PM MAIL WWW   Вверх
HistoryEarth
Дата 26.8.2007, 12:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 71
Регистрация: 23.8.2007

Репутация: нет
Всего: нет



Не совсем понятна задача, если честно. Существует плоскость и на ней узкая яма (если функции экспоненциальные, то будет не яма, а воронка, кстати), так? И надо найти склон по отличию значения функции?
Плоскость идеально ровная и область различимого склона очень мала?
Если так, тогда либо тупо перебираем (скажем, оцениваем площадь области склона и задаем шаг сканирования чуть меньше). Либо нужно поисследовать теоретические свойства функции и поискать "дальние" признаки склона (и тогда применять все, что угодно).
PM MAIL   Вверх
_Y_
Дата 26.8.2007, 20:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1651
Регистрация: 27.11.2006

Репутация: 8
Всего: 34



Цитата(HistoryEarth @ 26.8.2007,  12:03)
Не совсем понятна задача

Попытаюсь нарисовать двухмерную иллюстрацию
user posted image
В аналитическом виде функция выглядит как А. Но когда мы пытаемся посчитать ее численно, из-за машинной ошибки возникает некий шум - красная линия на В. В результате, попав в зону, обозначенную зеленым, мы не можем сказать с какой стороны от ямы мы находимся, т.к. "уклон" спрятан шумом.

Цитата(HistoryEarth @ 26.8.2007,  12:03)
тупо перебираем (скажем, оцениваем площадь области склона и задаем шаг сканирования чуть меньше)
 Собствено это я и сделал, только методом Монте Карло.

Цитата(HistoryEarth @ 26.8.2007,  12:03)
Либо нужно поисследовать теоретические свойства функции и поискать "дальние" признаки склона
 Как это сделать я не знаю. Не математик, к сожалению.




--------------------
Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:)
PM MAIL WWW   Вверх
imageman
Дата 29.8.2007, 19:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 66
Регистрация: 30.9.2004

Репутация: нет
Всего: 1



Цитата(_Y_ @  24.8.2007,  08:19 Найти цитируемый пост)
Поэтому A1 == A2==S в пределах машинной ошибки, естествено, т.е. получаю плоскость. Чем мне легче, если я считаю A1 = log(S + D1); A2 = log(S + D2)

а если A2 = log(S) + log(D2) ?

а если A1 = S - B + D1 где B константа, почти (в идеале точно) равная S
PM MAIL   Вверх
_Y_
Дата 31.8.2007, 12:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1651
Регистрация: 27.11.2006

Репутация: 8
Всего: 34



Цитата(imageman @ 29.8.2007,  19:04)
а если A2 = log(S) + log(D2) ?

А разве log(S + D2) = log(S) + log(D2) ?

Цитата(imageman @ 29.8.2007,  19:04)
а если A1 = S - B + D1 где B константа, почти (в идеале точно) равная S

Над этим надо подумать. 



--------------------
Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:)
PM MAIL WWW   Вверх
Severyanin
Дата 31.8.2007, 13:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Исследователь
**


Профиль
Группа: Участник
Сообщений: 554
Регистрация: 31.7.2007
Где: Россия, Омск

Репутация: нет
Всего: 9



А если экспоненты, то проще всего быдет сделать преобразование Лапласа, рассчитать в частотной области, а потом - обратное преобразование. 


--------------------
"Звонким вереском скроются наши следы, и не вспомнят о них. Кто поверит нам, рыцарям павшей звезды из отвергнутых книг? Пусть в узоре времен ни стихов. ни имен, но напомнит забывшим их полуночный крик." Тэм Гринхилл
"Ужели суслик твоего коварства нагадит в плов доверья моего?". Л.Филатов 
PM MAIL WWW ICQ   Вверх
esperanto
Дата 3.9.2007, 22:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 31.5.2003

Репутация: 2
Всего: 4



Цитата(Severyanin @ 31.8.2007,  13:52)
А если экспоненты, то проще всего быдет сделать преобразование Лапласа, рассчитать в частотной области, а потом - обратное преобразование.

Проще все не будет. Да и вообще утверждение если экспонента то надо Лапласа не верное

Это сообщение отредактировал(а) esperanto - 3.9.2007, 22:33
--------------------
B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET
PM MAIL   Вверх
Severyanin
Дата 10.9.2007, 05:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Исследователь
**


Профиль
Группа: Участник
Сообщений: 554
Регистрация: 31.7.2007
Где: Россия, Омск

Репутация: нет
Всего: 9



esperanto, да, не всегда это оптимальное решение, но чаще всего


--------------------
"Звонким вереском скроются наши следы, и не вспомнят о них. Кто поверит нам, рыцарям павшей звезды из отвергнутых книг? Пусть в узоре времен ни стихов. ни имен, но напомнит забывшим их полуночный крик." Тэм Гринхилл
"Ужели суслик твоего коварства нагадит в плов доверья моего?". Л.Филатов 
PM MAIL WWW ICQ   Вверх
esperant0
Дата 10.9.2007, 07:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14



Цитата(Severyanin @ 10.9.2007,  05:19)
esperanto, да, не всегда это оптимальное решение, но чаще всего

Да ну, на неизмеримых множествах утверждение чаще всего не имеет смысла


--------------------
 
 Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer 

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором  а затем стерто и которое он - пользователь не мог видеть. 
PM MAIL   Вверх
imageman
Дата 16.9.2007, 12:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 66
Регистрация: 30.9.2004

Репутация: нет
Всего: 1



Цитата(_Y_ @ 31.8.2007,  11:19)
Цитата(imageman @ 29.8.2007,  19:04)
а если A2 = log(S) + log(D2) ?

А разве log(S + D2) = log(S) + log(D2) ?

не равно :( , но пропорционально.... Или нет? Может сгодится просто пропорционально?  (тут уж тебе нужно подумать 7 раз)
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1360 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.