Минимизация функционала

[SYROTENKO]

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

Как можно численно найти минимум функции, которая задана в аналитическом виде?
Вид фунции достаточно сложный(когда я его расписал, получился на 4 страницы А4), он завсист от 5 аргументов, но мы знаем в каких интервалах может менятся каждый из аргументов.

Всем ответившим, большое спасибо!
Если знаете или есть мысли, поделитесь пожалуйста!:up:

P.S:Взять частные производные по каждому из аргументов и приравнять к нулю и решать систему 5 уравнений не представляется возможным.Система получается огромная и компьютеру она не по зубам..

[Brukvalub]

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

[juna]

Мне кажется, что метод случайного поиска, как метод безусловной минимизации, Вам может подойти (если еще априори известно, то минимум один) . Для него даже аналитическое выражение минимизируемой функции знать не обязательно, нужно лишь уметь ее вычислять.
Только вот если ваша функция действительно такая архибезобразная, может, стоит задуматься о точности той модели, которой она служит. Известно, что чрезмерное усложнение не повышает точность.

[SYROTENKO]

Артамонов Ю.Н. писал(а):

Мне кажется, что метод случайного поиска, как метод безусловной минимизации, Вам может подойти (если еще априори известно, то минимум один) . Для него даже аналитическое выражение минимизируемой функции знать не обязательно, нужно лишь уметь ее вычислять.
Только вот если ваша функция действительно такая архибезобразная, может, стоит задуматься о точности той модели, которой она служит. Известно, что чрезмерное усложнение не повышает точность.

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

Добавлено спустя 12 минут 27 секунд:

Brukvalub писал(а):

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

Идея хорошая и досточно простая, мне и самому она в голову уже приходила. Но здесь возникает 2 вопроса.
На сколько густю сетку брать! С каким шагом.
Мы знаем что каждый из параметров у нас измерется в таких интервалах [1,3]. Если взять шаг 0,1 и по каждому аргументу, то имеем ((3-1)/0,1)^5=3200000 раз нужно вызывать ф-цию. Ну а если взять шаг поменьше по сетке, то вобще кошмар получится. Отсюда вопросы какой шаг всё-таки брать и считать минимумом ф-ции там где получился минимум для аргументов, которые прогнали по сетки? (може стоит как-то сгладить эти табулированые точки по стеке, чтоб найти более объективный минимум? тогда как такое кол-во точек можно сгладить?)
А вобще идея хорошая..

[reader_st]

SYROTENKO писал(а):

Цитата:

но мы знаем в каких интервалах может менятся каждый из аргументов.

Я знаю точно в Matlab'e 7 есть функции которые позволяют находить экстремумы функций, если переменные меняются в заданных интервалах, т.е. не решать систему.

[juna]

Данный метод изложен В.В Лесин, Ю.П. Лисовец Основы методом оптимизации.
Можно также посмотреть алгоритм Хука-Дживса http://djvu.504.com1.ru:8019/WWW/d76017 ... 45cc9.djvu
Алгоритм метода случайного поиска очень простой:
1. Задать параметр точности $\epsilon>0$, начальный шаг $\alpha>0$, коэффициент уменьшения шага $\gamma$, предельное число неудачных попыток $N$ (обычно данный параметр устанавливается равным $3n$, где $n$ - число переменных целевой функции) и начальную точку $(x_1^1,x_2^1, ...x_n^1)$
2. Установить счетчик числа неудачных попыток $j=1$
3. Получить реализацию случайного вектора $(\epsilon_1, \epsilon_2,...,\epsilon_n)$, где $\epsilon_i$, $i=1..n$ - независимые случайные величины, равномерно распределенне на отрезке $[-1,1]$
4. Найти пробную точку
$y_i=x_i+\frac{\alpha \cdot \epsilon_i}{\sqrt{\sum\limits_{i=1}^n\epsilon_i^2}}$
и по полученным значениям пробной точки вычислить значение функции $f(y_1,y_2,...,y_n)$
5. Сравнить полученные результаты:
если $f(y_1,y_2,...y_n)<f(x_1,x_2,...,x_n)$, то вектор $(y_1,y_2,..,y_n)$ принять за следующее приближение и перейти к шагу 4.
если $f(y_1,y_2,...y_n)>f(x_1,x_2,...,x_n)$ то перейти к шагу 6
6. Положить $j=j+1$, если $j\leqslant N$, то перейти к шагу 3, если $j> N$, то перейти к шагу 7
7. Если $\alpha<\epsilon$, то поиск решения завершить, в качестве решения положить последнее найденное приближение, если $\alpha>\epsilon$, то положить $\alpha=\alpha/\gamma$ и перейти к шагу 2.

P.S. только нужно иметь в виду, что алгоритм может застревать на локальном минимуме, тогда можно запускать его по нескольку раз от найденных значений.
P.P.S. Если Ваши вычисления одноразовые, то может и стоит воспользоваться простой сеткой.

[SYROTENKO]

Артамонов Ю.Н. писал(а):

P.S. только нужно иметь в виду, что алгоритм может застревать на локальном минимуме, тогда можно запускать его по нескольку раз от найденных значений.
P.P.S. Если Ваши вычисления одноразовые, то может и стоит воспользоваться простой сеткой.

Спасибо за алгоритм! Я его попробую!
На счет кол-во локальніх минимумов я не знаю! Но так как ф-ция очень сложная думаю их будет много. Что значит запускать по несколько раз?(в окрестности кадого локального минимума? как его тогда найти? если их моежт быть много?)

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

Добавлено спустя 2 минуты 55 секунд:

reader_st писал(а):

SYROTENKO писал(а):
Я знаю точно в Matlab'e 7 есть функции которые позволяют находить экстремумы функций, если переменные меняются в заданных интервалах, т.е. не решать систему.

А каким методом там ищется минимум, Вы не в курсе? или там можно выбирать?
Будет ли тот метод сходится, если у нас ф-ция будет иметь много локальных минимумов?
Спасибо за ответ!

[juna]

Порылся в своих программках. Нашел этот метод. Только он реализован на скорую руку в Delphi. От метода правильного симплекса там только вкладка.
Код можете скачать здесь http://slil.ru/23693161
А по поводу сетки все просто: пять вложенных циклов (по пяти переменным), ну и шагаете с выбранным шагом по заданным диапазонам фиксируя минимум. Чем меньше возьмете шаг, тем точнее получите. Но здесь нужно искать компромисс между временем расчета и точностью. Можно итерационно, сначала шаг побольше, потом сужаете диапазоны, шаг поменьше и т.д.
Удачи.

[SYROTENKO]

Артамонов Ю.Н. писал(а):

Порылся в своих программках. Нашел этот метод. Только он реализован на скорую руку в Delphi. От метода правильного симплекса там только вкладка.
Код можете скачать здесь http://slil.ru/23693161
А по поводу сетки все просто: пять вложенных циклов (по пяти переменным), ну и шагаете с выбранным шагом по заданным диапазонам фиксируя минимум. Чем меньше возьмете шаг, тем точнее получите. Но здесь нужно искать компромисс между временем расчета и точностью. Можно итерационно, сначала шаг побольше, потом сужаете диапазоны, шаг поменьше и т.д.
Удачи.

Ага спасибо большое за файл и за советы, сейчас буду изучать код
Срузу вопрос! Как себя будет вести этот метод, если у нас в заданной области будет несколько локальных минимумов? не будет ли он прыгать из одного лок минимума к другому?
И еще вопрос к Вам по табуляции! Если табулировать мою ф-цию с ашгом 0.1(но такая точность меня не удовлетворит, хотябы 0.01), то вычисления занимают около 2 мин (около 16млн раз вычисляется ф-ция), а если брать шаг 0.01 320млрд операций нужно, что займёт в 20000 больше времени.
" Можно итерационно, сначала шаг побольше, потом сужаете диапазоны, шаг поменьше и т.д." Это идея мне очень нравится, только вот как можно итерационно? по какому алгоритму менять шаг.

[juna]

Скакать, в смысле возвращаться к отброшенному ранее минимуму он не будет, а вот останавливаться раньше того, как получен глобальный минимум возможно будет. Поэтому и нужно запускать повторно от найденного значения (задав начальный вектор $x$ найденными значениями - т.е. в программе нужно несколько раз нажимать на кнопку, пока результат не стабилизируется). Можно, кстати, модифицировать метод - на шаге 2 получать несколько реализаций случайного вектора, на шаге 3 расчитывать соответствующее количество векторов $y$ и выбирать минимум $f(y)$.
Бывают особо тяжелые случаи, когда нелинейные ограничения (рваные функции типа Хевисайда) вводятся в целевую функцию в качестве штрафа (т.е. в методе штрафных функций) - тогда метод плывет - количество тыканий на кнопку экспоненциально возрастает.
Но как я понял - для вашей функции можно теоретически найти производную - т.е. она не такая.
По поводу сетки - 666.666 часов - это симптоматично.
Метод полного перебора никогда не имел полиномиальной сложности.
Как выбирать шаг - нужно найти для Вашей конкретной функции подходящую эмпирику, а потом составить алгоритм.

[SYROTENKO]

Артамонов Ю.Н. писал(а):

Скакать, в смысле возвращаться к отброшенному ранее минимуму он не будет, а вот останавливаться раньше того, как получен глобальный минимум возможно будет. Поэтому и нужно запускать повторно от найденного значения (задав начальный вектор $x$ найденными значениями - т.е. в программе нужно несколько раз нажимать на кнопку, пока результат не стабилизируется). Можно, кстати, модифицировать метод - на шаге 2 получать несколько реализаций случайного вектора, на шаге 3 расчитывать соответствующее количество векторов $y$ и выбирать минимум $f(y)$.
Бывают особо тяжелые случаи, когда нелинейные ограничения (рваные функции типа Хевисайда) вводятся в целевую функцию в качестве штрафа (т.е. в методе штрафных функций) - тогда метод плывет - количество тыканий на кнопку экспоненциально возрастает.
Но как я понял - для вашей функции можно теоретически найти производную - т.е. она не такая.
По поводу сетки - 666.666 часов - это симптоматично.
Метод полного перебора никогда не имел полиномиальной сложности.
Как выбирать шаг - нужно найти для Вашей конкретной функции подходящую эмпирику, а потом составить алгоритм.

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

[juna]

Подождите, вот я понял, что четырехстраничную функцию в коде Вы уже набрали. Вставьте ее вместо функции в мою программу, посчитайте и сравните результат с результатом для шага 0.1.
Эмпирика не гарантирует для всех случаем, что выбрав очередной шаг вы не перешагнете через глобальный минимум, особенно если много локальных минимумов и все они близки по значению. Вы это можете проверить пошевелив параметры, например, тот же шаг возьмите 0,3 - если результат близкий к 0,1 - то ваша функция - хорошая, также поварьируйте диапазоны, результаты должны быть близкими. Если это не так, то готовьтесь к худшему - глобальный минимум найти не удастся, нужно довольствоваться квазиоптимальностью.

[Hajam]

SYROTENKO писал(а):

Как можно численно найти минимум функции, которая задана в аналитическом виде?
Вид фунции достаточно сложный(когда я его расписал, получился на 4 страницы А4), он завсист от 5 аргументов, но мы знаем в каких интервалах может менятся каждый из аргументов.

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