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

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

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

Спасибо

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

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

Ну и непонятно, как вообще задача решалась - Ваша собственная программа или что-нибудь готовое типа Mathcad, Maple и т.д.

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

VictorTsaregorodtsev. 1. Программа собственная. 2. Символьная арифметика это здорово, но, в моем случае, сьест слишком много процессорного времени. И так ожидается, что каждый вариант задачи будет считаться "до утра". 3. Я, к сожалению, мало знаю о генетических алгоритмах, но Ваше краткое обяснение, видимо, совпадает с тем, что я сотворил сам к данному моменту. А именно:

• Имею функцию, которую хочу минимизировать: f(X,Y)=min.
• Задаю интервалы Xmin<X<Xmax; Ymin<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

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

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

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)

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

Попытаюсь нарисовать двухмерную иллюстрацию

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

 Собствено это я и сделал, только методом Монте Карло.

 Как это сделать я не знаю. Не математик, к сожалению.

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

а если A1 = S - B + D1 где B константа, почти (в идеале точно) равная S

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


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

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

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

Это сообщение отредактировал(а) esperanto - 3.9.2007, 22:33

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

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

не равно :( , но пропорционально.... Или нет? Может сгодится просто пропорционально?  (тут уж тебе нужно подумать 7 раз)

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

Или используйте библиотеки для вычислений с произвольной точностью. 

Автор! Приведите пожалуйста Вашу функцию, а то тут все в небо тыкают, а попасть не могут.

Да, Вы правы, конечно.

Функция, с которой я пытался играть - сумма из N гауссовых кривых, аппроксимирующая некоторые экспериментальные кривые. Я, соответственно, пытался что-то сделать с методом наименьших квадратов. Специфические отличия именно моей задачи заключаются в том, что характеристики гауссовых кривых не совсем независимы. Кроме того, одновременно надо обрабатывать несколько наборов данных. Уравнение у меня получилось такое:

В нем C число наборов данных, I - число точек в одном наборе данных, G - число гауссовых кривых в одном наборе данных. Оптимизируются только два параметра: сигма и a. Остальное известно.

Возможны и другие решения - мне совершенно не обязательно бороться именно с гауссовыми кривыми - набор любых "куполов" меня устроит.

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






Это сообщение отредактировал(а) _Y_ - 19.10.2007, 20:54

Есть такой метод: 

http://en.wikipedia.org/wiki/Gradient_descent

смысл в том что величина шага меняется в зависимости от величины производной;

то есть чем ближе к яме тем меньше шаги чтобы её не проскочить

проблема в том что при этом нет разницы между локальным и глобальным минимумом -

если попадёт в яму то уже не выберется

Как известно, ln(1+dX) = dX при весьма малых dX... соответственно при S >> D2
ln(S+D2) = ln(S*(1+D2/S)) = ln(S) + ln(1+D2/S) = ln(S) + D2/S