2. Лекции Практические и лабораторные занятия
жүктеу/скачать 0,77 Mb.
|
| Методы барьерных функций
Недостаток метода внешней точки в том, что обычно не удается с абсолютной точностью выполнить все ограничения. От этого недостатка свободны методы внутренней точки, иначе называемые методами барьерных функций. В этих методах также строится последовательность точек минимума некоторых функций, которая сходится к точке минимума исходной целевой функции, но не извне, а изнутри ОДР. Добавки к исходной целевой функции служат барьерами, удерживающими точку внутри допустимой области. В качестве барьерной может использоваться функция и в целом преобразованная функция имеет вид (2.14) Начальная точка должна быть внутренней точкой ОДР, где все cj(x) < 0. Когда она приближается к границе, к функции F(x) прибавляется большая положительная величина. Последовательность коэффициентов kn в методе барьерных функций стремится не к бесконечности, а к нулю, начиная с достаточно больших положительных значений. Метод барьерных функций применяется при решении задач, в которых целевые функции за пределами допустимой области не определены или их трудно вычислить. Кроме того, он предпочтителен, когда не нужна высокая точность достижения минимума, но важно выдержать ограничения. Одним из эффективных методов решения задач с нелинейными ограничениями является разработанный в 70-х гг. XX в. метод модифицированной функции Лагранжа (МФЛ). Метод базируется на той же идее штрафных функций, но вместо одного параметра kn в формуле (2.13) вводится несколько параметров, управляя которыми по ходу решения задачи можно улучшить сходимость. Существует несколько вариантов метода, отличающихся видом штрафной функции и методами изменения ее параметров. При решении практических задач хорошие результаты были получены по алгоритму Пауэлла (Powell M.J.D.), в котором для поиска минимума исходной целевой функции F(x) при ограничениях cj(x) <= 0 используется функция Векторы σ и θ имеют по m компонент (по числу ограничений) и представляют собой набор параметров штрафной функции, которая отличается от рассмотренной выше тем, что вместо одного параметра теперь два параметра на каждое ограничение. Знак + означает, что в сумму включаются только те слагаемые, для которых cj(x) + θj > 0. Здесь θj > 0 — «запас» в j-ом ограничении, т.е. штрафуется не только настоящее нарушение при cj(x) > 0, но и cj(x) > - θj. Если в системе ограничений были равенства, то соответствующие им слагаемые всегда присутствуют в сумме. При θj = 0 и σj = k (j = 1,2, ..., m) штрафная функция та же, что в (2.13). Недостаток (2.13) в том, что ее вторые производные по х разрывны на границе допустимой области, причем разрывы тем больше, чем больше к, который приходится увеличивать в каждом новом итерационном цикле безусловной минимизации. Иное дело, когда σj постоянны, а варьируются только θj. В этом случае поверхности разрывов вторых производных удалены от точек безусловного минимума, определяемых при решении задач в каждом цикле оптимизации. Начальные значения параметров θj > 0 и σj > 0 выбирают, ориентируясь на смысл и важность соответствующих ограничений и величины невязок в ограничениях в точке начального приближения. Затем решается задача на безусловный минимум Ф(х, σ, θ). Наилучшие результаты для задач с нелинейными ограничениями были получены при использовании методов второго порядка с последовательным формированием обратной матрицы Гессе, т.е. DFP-процедуры (см. раздел 2.3.5). При этом на начальных этапах не требуется высокая точность поиска безусловного минимума. После того как задача на безусловный минимум решена, проверяются ограничения и, если есть нарушения, меняются параметры σ и θ. При этом используется правило: если j-oe ограничение выполнено с «запасом», т.е. cj(x) > - θj, то новое значение θj1 = 0, а если нет, то θj1 = θj + cj(x). И так по всем ограничениям. Для пересчета σj действует другое правило: если в j-ом ограничении в результате решения задачи на безусловный минимум невязка уменьшается быстро, то σj не меняется, а если медленно, то увеличивается. Обычно используются такие константы: если невязка уменьшилась меньше, чем в четыре раза, то соответствующее σj умножается на 10 и при этом θj делится на 10.
Получено решение с приемлемыми невязками. При этом можно для контроля сделать еще одну внешнюю итерацию и убедиться, что решение практически не изменилось. После исчерпания заданного лимита внешних итераций решение не получено. При этом есть все основания усомниться в совместности системы ограничений и, следовательно, в существовании решения исходной задачи. жүктеу/скачать 0,77 Mb. Достарыңызбен бөлісу:
|