Лекция 13. Задачи с нелинейными ограничениями


Содержание лекционного занятия:

· Методы штрафных функций

· Методы барьерных функций

Этот класс задач значительно сложнее задач с линейны­ми ограничениями. Методы их решения основываются на идеях сведения задачи к безусловной оптимизации или к локальной аппроксимации нелинейных функций линейны­ми для поиска направления спуска с последующим возвра­том в допустимую область. Есть методы, в которых все ограничения делятся на две группы: линейные и нелиней­ные. Ограничения второй группы — учитываются преобра­зованием целевой функции, а ограничения первой группы как описано в разделе 2.4.

Методы штрафных функций

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

Общая формулировка задачи следующая. Найти min F(x) при ограничениях

где все или часть функций-ограничений cj(x) могут быть нелинейны.

Идея метода штрафных функций, называемого также методом внешней точки, состоит в таком преобразовании целевой функции, чтобы в допустимой области ее значения не изменились, а за пределами допустимой области были очень велики по сравнению с исходной F(x). Тогда мини­мум новой функции и минимум исходной будут близки. Такое преобразование целевой функции может выполняться различными способами. Один из обычных приемов состоит в том, что к исходной F(x) прибавляется сумма штрафов gj(x) за нарушение ограничений. Если в текущей точке х j-oe ограничение выполнено (т.е. cj(x) <= 0), то штраф равен нулю, иначе, чем больше нарушение, тем больше штраф.

Часто принимают в качестве штрафов функции

Такая функция представляет собой квадрат невязки в j-ом ограничении, а общий штраф равен сумме штрафов. Так что преобразованная функция имеет вид

(2.13)

Далее решается задача поиска безусловного минимума Ф(х). Если взять коэффициент kn очень большим, то теоре­тически минимумы Ф(х) и F(x) близки. Но этого делать нельзя, так как введение штрафа порождает овраг. В на­правлениях вдоль границ ОДР функция меняется медленно, но при малом изменении невязок в ограничениях функция меняется очень сильно. В такой ситуации методы безуслов­ной оптимизации работают плохо. Поэтому сначала реша­ется задача с малым значением коэффициента штрафа (на­пример, k1 = 1), полученное решение используется как на­чальное приближение для следующей задачи с к2 = 2, затем решается задача с к3 = 4 и так далее при все большем значе­нии к. Фактически решается последовательность задач. Процесс останавливается, когда ограничения выполнены с требуемой точностью. Последняя точка минимума считает­ся решением исходной задачи.

Если в исходной системе были ограничения-равенства, то штрафуются как положительные, так и отрицательные значения cj(x), т.е. gj(x) = сj2(х).

Естественно, что в самом лучшем случае метод может дать точку, близкую к одному из локальных минимумов F(x).

Методы барьерных функций

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

и в целом преобразованная функция имеет вид

(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.

После пересчета параметров повторяется процесс без­условной минимизации или, как говорят, делается очередная внешняя итерация. Счет прекращается в следующих случаях:

1. Получено решение с приемлемыми невязками. При этом можно для контроля сделать еще одну внешнюю
итерацию и убедиться, что решение практически не из­менилось.

2. После исчерпания заданного лимита внешних итера­ций решение не получено. При этом есть все основания усомниться в совместности системы ограничений и, следовательно, в существовании решения исходной задачи.

Вопросы для самоконтроля:

1.Метод штрафных функций (для задач с ограничениями),

2.Метод линеаризации.

3. Стратегии глобализации сходимости: одномерный поиск, методы доверительной области.

Рекомендуемая литература:

1.Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. М.: Физматлит, 2003.

2.Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988.