Оптимизация, градиент, штрафная функция, локальный и глобальный минимум

Решается оптимизационная задача по поиску минимума функции.Целевая Функция S зависит от переменной U4, k: S(U4,k).
Глобальный минимум функции будет достигаться при значении k=oo U4=0. Однако на различных интервалах будут присутствовать локальные минимумы функции. Необходимо их найти.
График функции похож на график функции f(x)=-(x+cos2x) с ограничением х=4,2.

В Маткаде реализован метод приведенного градиента, заданы ограничения k=2.4 и U4 = 106. При этом в рамках кривой реализации расчет останавливается при достижении одного из ограничений, которое зависит от дополнительных коэффициентов подбираемых вручную, но это уже немного другой вопрос. После каждого шага итерации происходит пересчет множества переменных, влияющих на целевую функцию. Программа сложная, просто так в ней не разобраться, поэтому формулирую задачу в обобщенном виде.

Из данной ситуации думал выкрутиться путем применения метода штрафных функции, который заключается в том, чтобы в целевую функцию S добавить множитель, который будет обращаться в большое число при достижении значения одной из переменной k или U4 заданного ограничения.
Например новая ЦФ S2: S2(U4,K)=S(U4,K)*(Umin/U4)^n
Тогда по логике при достижении U4 предела, равному Umin значение ЦФ будет значительно увеличиваться, а значит на следующем шаге итерации U4 вернется в значение, удовлетворяющее условию U4>U min.
Однако вид штрафной функции Kш=(Umin/U4)^n на интервале U4>Umin влияет на значение целевой функции и может вносить недопустимые погрешности в расчеты.

Собственно вопрос: есть ли штрафная функция, которая может быть эффективна в данном случае или же нужно сменить подход к решению задачи, и если так, то куда копать?

0

Сообщение от SAsp от дополнительных коэффициентов подбираемых вручную,

Сообщение от SAsp пересчет множества переменных, влияющих на целевую функцию.

Как это? У вас 2 переменных S(U4,k)=0
Либо неправильно целевая.

Сообщение от SAsp Программа сложная, просто так в ней не разобраться, поэтому формулирую задачу в обобщенном виде.

Представляю примерно так:
Min f(a,b,c…)=0
a0<a<a1
b0<b<b1…

Сообщение от SAsp куда копать?

Думаю так:
Выписать все переменные которые влияют на целевую.
Определить пределы всем переменным.
Придумать расчет целевой.
Задать достаточную точность расчета.
Поискать готовые методы выдающие все локальные минимумы а не делать велик.

0

Excalibur921,
Расчет электрического режима энергосистемы. Есть 6 узлов. В двух задаются напряжения. В остальных считаются исходя из этих двух. Потом по полученным напряжениям в шести узлах считается целевая функция мощности. Свести каждое напряжение в зависимость от других двух нельзя т.к. расчет напряжений производится итерационными методами.
Брал за основу методы, описанные в Идельчик В.И. - Электрические системы и сети глава 13.5
Исходя из его терминологии имеем: две независимые переменные, которые мы задаем и которые мы изменяем: U1,U2
Есть целевая функция S=f1(U1)+f2(U2)+...f6(U6). Зависимые переменные U3-U6 зависят от U1, U2 и определяются методом Ньютона.
В итоге имеем алгоритм:
Расчет режима для определения зависимых переменных U3-U6
Определение градиента для U1 U2
Определение новых значений U1 U2
Расчет режима для определения новых значений зависимых переменных U3-U6
Повторить сколько нужно.

Проблемы две.
1. В одной из версии расчета вместо переменной U2 используется переменная k, которая влияет на зависимые переменные, но в целевой функции не фигурирует. В этом случае я не уверен что алгоритм работает правильно. Для проверки необходимо решить проблему 2
2. Целевая функция имеет прямую зависимость от переменных U1 U2 в результате чего стремится к 0. Но нужно найти ее значение при определенных ограничениях. Как я понимаю градиент видит глобальный минимум и идет к нему поэтому несмотря на наличие локальных минимумов их поиск будет невозможен. Данная проблема решится вводом штрафного коэффициента, который будет приводить целевую функцию к несоизмеримо бОльшему значению при выходе за ограничения. Данный способ также описан в Идельчике. Однако проблема в формулировании штрафной функции. Самый близкий пример это (Umin/U2)^n, но тогда штрафная функция будет влиять на целевую функцию до достижения ей предела и расчеты будут неверные. Поэтому необходима такая функция которая обращается в единицу при соотношении Umin/U2<1 и в бесконечность при соотношении Umin/U2>1. Либо что то похожее, но с такой же логикой. Данную проблему уверен можно решить и непосредственно в программе, но это уже отдельный вопрос.

Вложения

Идельчик В.И. - Электрические системы и сети - копия - копия.rar (8.44 Мб, 8 просмотров)

0

Сообщение от SAsp функция которая обращается в единицу при соотношении Umin/U2<1 и в бесконечность при соотношении Umin/U2>1.

If then else
Например так: Если Umin/U2<1 то 0 иначе 1.

Неужели нет готовых функций поиска всех корней или с определенным порогом?
Не понимаю причем тут градиент или вообще определенный метод поиска…
Построите ландшафт функции посчитав поверхность сеткой точек например 1000 на 1000: карта 2д x это U1, y это U2, цвет пикселя это f(U1,U2)
Или 3д поверхность: поверхность x это U1, y это U2, z это f(U1,U2)
Установите какое значение целевой считать локальным минимумом.
Профильтруйте карту с порогом получите точки локальные минимумs и их пределы поиска U1,U2.
Уточните любым методом каждую.

Добавлено через 14 минут
Величина штрафа зависит от того насколько далеко вышли за допустимые пределы.
Штраф=Если Umin/U2<1 то 0 иначе Umin/U2-1
Можно штраф в квадрате брать это дело вкуса =).

0

Excalibur921, "если то иначе" прописанные в алгоритме не будут определятся функцией и оптимизация градиентом не будет работать. Нужна именно штрафная функция, которую будет видеть градиент.
Градиент - потому что я нашел только этот способ оптимизации с разобранными примерами.
Зачем мне строить карты? мне цифры нужны, а не изображение. Кроме того это сейчас в примере 2 неизвестных. В теории их много больше будет. В следующей схеме, будет с десяток неизвестных.

Дык я и брал бы в квадрате. Даже в десятой степени лучше, но при значениях удовлетворяющих условию на функцию будет оказано ненужное влияние.
Допустим минимум S(u1,u2) будет достигаться при u1=108 u2=109, но если в формуле S будет присутствовать штрафной коэффициент U/Umin^x то минимум будет достигать уже при других значениях, что не будет отражать истину.
Насколько далеко не нужно. Нужно либо да либо нет.

Добавлено через 3 часа 11 минут
Сейчас прикинул задать в алгоритме условие "если то " - получилось как я и думал - алго не видит, оптимизации нет.
Попробовал Umin/U в качестве штрафной функции - на первых же шагах считает не правильно. Алгоритм начинает увеличивать переменные U1 U2, а должен уменьшать их.
Если бы можно было математически описать условие "если то иначе"...

0

Сообщение от SAsp будет с десяток неизвестных.

Зачем писать велик оптимизации когда они есть в мат пакетах?

Сообщение от SAsp "если то иначе" прописанные в алгоритме не будут определятся функцией

Считать градиент нужно на сумме целевую + штраф. Целевая= f(a,b)+штраф(a,b).
Вы запутались в методе.

0

Excalibur921,
Попробовал Umin/U в качестве штрафной функции - на первых же шагах считает не правильно. Алгоритм начинает увеличивать переменные U1 U2, а должен уменьшать их.

0

Говоря градиентный метод вы подразумеваете антиградиент? Т.е. поиск наибыстрейшего убивания? Ведь ищете min.

Сообщение от SAsp начинает увеличивать переменные

И что? Алгоритм ищет минимум целевой а не минимум значений переменных.
Может правильно сказать алгоритм ищет ближайший локальный минимум, кто вам сказал что там сразу попались малые значения переменных? Смотрите значение целевой было и стало а не переменные.

Мне кажется нужно взять например 100 случайных u1 u2 комбинаций начальных параметров и поискать каждому из 100 вариантов т.к. у вас я так понял локальный поиск который скатывается в ближайший минимум?

0

Excalibur921, Да, антиградиент.

Да, я понимаю что алгоритм ищет минимум целевой функции. Суть в том, что для конкретного примера я знаю ответ. Ответ будет получатся при значениях переменных значительно ниже исходных. Т.е. U1исх>U1ответ. Когда я добавляю штрафную функцию в виде umin/u1 получается что U1исх<U1ответ, т.е. алгоритм считает неверно, поэтому штрафная функция в виде umin/u1 не подходит.
Мне нужно найти локальный минимум на отрезке, однако алгоритм скатывается в поиск глобального минимума. Алгоритмы поиска локальных минимумов я разбирал и на данный момент особых успехов не достиг. Поэтому я хочу сделать так, чтобы глобальный минимум был в нужном мне интервале. Например с помощью штрафных функций.

Насчет 100 случайных значений.Я правильно понял, что Вы предлагаете решить задачу методом перебора переменных с некоторым шагом? Если так, то к сожалению перебором нельзя достигнуть решения. Точнее можно, но время вычислений будет очень большим, ввиду большого количества комбинаций. Конкретно для моего примера где есть 2 переменных, шаг изменения которых можно задать как 0.1 и ограничение 106<u<126 данный способ реализуем, но в дальнейшем - нет т.к. данных переменных будет значительно больше двух и количество возможных комбинаций будет где-то в районе 100^n*19^t, где 1<n,t<10...100+

0

Сообщение от SAsp Когда я добавляю штрафную функцию в виде umin/u1

Второй раз говорю…нужен штраф “Если то иначе” в виде функции от (u1,u2).

Сообщение от SAsp Мне нужно найти локальный минимум на отрезке, однако алгоритм скатывается в поиск глобального минимума.

0_0
Как это? У вас локальный поиск или специальный глобальный?

Сообщение от SAsp Вы предлагаете решить задачу методом перебора переменных с некоторым шагом?

Нет. Это один из методов поиска всех локальных. Разбрасывают точки на допустимом поле XY случайно или сеткой с одинаковыми ограничениями и каждый поиск независимо ищет свой минимум. Получим массив локальных минимумов, найдя в нем минимальное число получим глобальный. Вот вам и нужен весь массив.

0

Оставили расчет? Можете написать книгу в которой нашли описание градиентного и стр?
Вот в Mathematica 8 есть 10 готовых.
локальный
NMinimize
"NelderMead",
"DifferentialEvolution",
"SimulatedAnnealing"
"RandomSearch".
глобальный
FindMinimum
"ConjugateGradient",
"PrincipalAxis",
"LevenbergMarquardt",
"Newton",
"QuasiNewton",
"InteriorPoint"
"LinearProgramming"
Можно ли показывать все локальные не знаю.

0

Excalibur921, нет не оставил, сделал перерыв небольшой. Книгу скидывал выше: Идельчик гл. про оптимизацию №13. стр 565 пример, по которому сделан алгоритм.
С Mathematica не знаком. Знаком с маткадом немного. Встроенные в него функции готового решения не выдали.

Добавлено через 5 минут
Приведите пожалуйста пример функции, в которой содержится условие "если то иначе".
По поводу метода из сотни рандомных точек - пока что он мне не очень нравится, но буду думать.

0

Сообщение от SAsp пример функции, в которой содержится условие "если то иначе".

В математике упоминают логику:

А если ваша многопараметрическая функция имеет такой ландшафт?

Если таки хотите свой поиск а он не пашет, то наверно единственный метод проверить это построить карту вашей функции 2 переменных, сделать визуализацию шагов поиска. Или взять готовые известные задачки типа Функция розенброка и т.п.

Я думал в вашей книге вы нашли где без воды описан метод градиента в общем виде с детальной схемой и поведением поиска и всеми формулами...
Тоже недавно хотел попробовать сделать расчет на основе градиента с нуля, сделал целевую из книжки и сразу ошибка целевой -21 а должно быть 52.
То градиент не описали как численно искать… там то забыли там се.. куча воды =(.

Пока что лидер 2 книги:
Базара М., Шетти К.-Нелинейное программирование. Теория и алгоритмы (1989).djvu
Стр 303. Наискорейший спуск.

Химмельблау Д. (Himmelblau)-Прикладное нелинейное программирование-Мир (1975).djvu
Стр 79 как найти численно градиент
+ в каждой нужно выбрать и описан метод одномерного поиска.
Сами книги выложить стремно все-таки авторское право.

0

Сообщение от Excalibur921 В математике упоминают логику:

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

Да с этими авторами это мрак конечно. Взять того же Идельчика. В одном месте он пишет формулу в одном виде, а в примере эту же формулу раскладывают. И так не понятно ничего, еще подляны такие. Но это единственная книга с примером расчета, которую я найти смог. Крайне трудно материал найти с примерами и цифрами.
Осложняет все что это не мой профиль, и решение данной задачи является приложением к основному материалу. Так то можно было и столбиком решать, главное чтобы ответ был хоть какой то. Но чем лучше решение - тем лучше.

Сообщение от Excalibur921 карту вашей функции 2 переменных

Данный способ можно использовать для конкретного примера, для например правильности решения именного этого примера. А если уже 3 переменных будут?

Добавлено через 34 минуты
проверки*

0

Сообщение от SAsp этими авторами это мрак конечно.

+опечатки.

Сообщение от SAsp А если уже 3 переменных будут?

Предлагайте альтернативы. Во всех книгах 2 переменных. Даже не одной нет хотя бы 10 переменных поискать и экстремум ее.
В mathematica тоже порядка 20 функций и все примеры в 2д.

Может это все тонкий намек на: не стройте вообще и считайте что вот оно решение.
А мы вам тут повтираем на 900 страницах с опечатками как решать 2 переменных через 40 методов.
В ведь выбор метода решения + его настройки определяют скорость расчета или вообще возможность его использования.

Как визуализировать поверхность целевой из N параметров получают?
Создал тему...молчат.
10 мерное пространство представить на 2 мерном

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

0

Придумал простую 6 параметрическую нелинейную функцию с независимыми переменными поиск глобального мин чисто протестировать Mathematica 8.
Пределы от 0 до 10 каждой переменной.
Функция это сумма значений 6 нелинейных функций корень которых найден у каждой NMinimize с визуальным контролем корня. Причем NMinimize даже с 1 переменной ошибалась =)).
Решение ищется элементарно по каждой переменной независимо.

В итоге почему то все методы наврали.
Самый близкий по значению корня "DifferentialEvolution" -11.0426.
Нашел все корни но соврал на первом f1 непонятно почему и ругается только на x1.
f7[x1_,x2_,x3_,x4_,x5_,x6_]:=
Sin[x1 *1.6]+Sin[x1 *2.97]+
Sin[x2 *2.6]+Sin[x2 *3.6]+
Sin[x3 *2.5]+Sin[x3 *3.]+
Sin[x4 *3.7]+Sin[x4 *5.9]+
Sin[x5 *2.5]+Sin[x5 *4.3]+
Sin[x6 *3.]+Sin[x6 *4.3]
Корень -11.2321 грубо
Корни функций
f1[3.5478396287469876]+
f2[6.5794478867783495]+
f3[1.6986563431573805]+
f4[2.940778165279156]+
f5[6.933346961006747]+
f6[9.890997707149284]

По времени расчета тоже непонятно что там считает страшное всеми методами… элементарно разбросать точки на отрезке и уточнить по каждой переменной независимо.

Самый тормазный RandomSearch, считает так долго будто там чисто по точкам ищет на кривой корень потом сортирует огромные массивы и наврал в итоге.

Может я неправильно сделал простой тест.. не знаю =).
А ведь еще не добавил разрывы в значения функций или связь оптимизируемых переменных на целевую и функции очень гладкие и слабые волны но лень усложнять.

Mathematica 8

Вложения

экстрем мин функц 6 пермен4.zip (21.8 Кб, 2 просмотров)

0

Excalibur921, в общем тянет на еще одну диссертацию...

0

Попробуйте разбивать на части ваше пространство поиска N переменных на поиск 2 переменных. Но это наверно актуально если они независимы(как в моем примере).
Или сделайте так целевую чтобы они были независимы.
Это позволит прикинуть как сильно разбивать ваше пространство поиска N переменных на куски. По другому я не знаю как. Или рубите на части отбалды =).

0