Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

4.4. Методы штрафных функций. Формы учета ограничений задачи

Рассматриваемые методы основаны на идее преобразования оптимизационной задачи с ограничениями в последовательность задач без ограничений. С этой точки зрения первым представителем изучаемой группы методов является классический метод множителей Лагранжа (см. гл. 2), позволяющий исследовать безусловный экстремум Φ(Х, Λ) с целью отыскания условного экстремума f(X).

Пусть дана следующая задача математического программирования: найти Х→min{z = f(Х)} при φi(Х)≥0 (i = 1,...,m); ее областью определения, как обычно, является U⊂Rn. Если положить, например, F(Х) = 0 при X∈U, F(X) = ∞ при X∉U и составить функцию L(X) = f(X) + F(Х), то решение новой задачи об отыскании точки X∈Rn, доставляющей min L(X), будет обладать свойствами X∈U, min L(X) = L(X̂) = f(X̂) и, следовательно, Х̂ ≡ Х*.

Функция F(Х), налагающая бесконечно большой штраф за выход X из U, называется штрафной функцией.

Непосредственное использование F (X) в том виде, как она дана выше, затруднено тем, что приходится оперировать с бесконечно большими величинами, поэтому на практике стремятся аппроксимировать F(X) последовательностью функций Fk(X), приближающейся в пределе (при k→∞) к F(Х).

Существуют две разновидности методов штрафных функций - методы внутренней и внешней точки. В первом случае введение F(Х) препятствует выходу точек последовательности {Хk} из U и нарушению условия


во втором случае присутствие F(Х) должно предотвратить блуждание точек Xk далеко за пределами U при сохранении требований


Особенности организации поиска X*, z* здесь удобно исследовать применительно к приведенной выше задаче минимизации f(X).

Метод внутренней точки

Обозначим множество всех внутренних точек области U как U0 и зададим f(Х) следующими условиями: - F(Х) непрерывна и принимает положительные значения при Х∈U0;


если {Xk} - произвольная бесконечная последовательность точек в U0, сходящаяся к ХΓ, причем φiΓ) = 0 хотя бы для одного номера i.

Пусть S(r) - скалярная функция аргумента r, обладающая свойствами: S(r1) > S(r2) >0 при r1>r2>0;


Произведения вида S(rk)F(Х) могут рассматриваться в качестве "рабочих" значений штрафной функции.

Алгоритм метода внутренней точки включает в себя:

а) выбор начальных X1∈U0, r1>0 и составление функции L (X, r1) = f(X) + S(r1)F(X);

б) решение задачи об отыскании точки X̂ локального безусловного минимума L(X, r1) и принятие ее за X2 (выше отмечалось, что такая X̂ обязательно будет принадлежать U0, иначе она перестанет быть точкой минимума L);

в) выбор нового положительного значения r = r2<r1 и новой функции L(X, r2) = f(Х) + S(r2)F(Х); определение точки X̂ для L(X, r2) и переход в нее (Х3);

г) повторение процедуры в) для Х3, Х4, ... при r3<r2, r4<r3, r5<r4, ... до достижения (с заданной точностью) решения исходной задачи.

Иногда бывает трудно найти X1∈U0 (число ограничений велико и проверять произвольно взятую X1 нецелесообразно или X1 задана сразу как граничная точка и т. п.). В этой ситуации можно применить метод внутренней точки и для поиска приемлемой в указанном смысле X1. Пусть X̄1 удовлетворяет условиям φi(Х)>0 (i∈J+), φi(Х)≤0 (i∈J-), и нужно построить такую последовательность {Х̄1k}, чтобы величина


возрастала, но ни одно из ограничений φi(Х)>0(i∈J+) не нарушалось. Очевидно, желаемого результата можно достичь, минимизируя функцию


при строго убывающих положительных rk. Здесь по мере перехода от одной точки X̂ к другой элементы множества J- переходят в J+ признаком окончания процесса является J- = ∅.

Метод внешней точки

Предположим, что функция (X) обладает теперь следующими свойствами: она непрерывна и строго положительна везде в Rn, кроме точек Хе?/; в них она равна нулю. Функция S(r) вводится в таком виде: S(r2)>S(r1)>0 при r2>r1>0,


Алгоритм метода внешней точки включает:

а) выбор начальных r1>0, X1∈C и составление функции L(X, r1) = f(X) + S(r1)F(X) (здесь G - произвольное компактное множество, содержащееся в Rn, причем U⊂G);

б) решение задачи об отыскании точки X̂ локального безусловного минимума L (X, r1) и принятие ее за Х2;

в) выбор нового r = r2>r1 и новой L(X, r2) = f(Х) + S(r2)F(Х); определение течки X̂ для L(X, r2) и переход в нее (Х3);

г) повторение процедуры в) при строго возрастающих rk→∞; можно показать, что при rk→∞ последовательность точек X̂ стремится к X* (удаление Xk от U с ростом k привело бы к увеличению штрафа, поскольку rk→∞ и для Х∉U).

Практическое применение рассматриваемых методов может быть осложнено присутствием ограничений-равенств φi(Х) = 0, определенностью f(X) не во всех точках X∈Rn и т. п. Это вызывает необходимость формирования комбинированных алгоритмов, к которым обычно предъявляется требование гарантировать соблюдение одних ограничений на протяжении всего вычислительного процесса, а других - только при приближении к оптимуму. Такой подход расширяет круг задач, решаемых предложенным способом.

При исследовании сходимости методов штрафных функций удобно представить соответствующие алгоритмы общим отношением Xk+1∈Wk(Xk). Это облегчает использование следующей теоремы (14):

если для некоторых k множество Wk(Xk) пусто, то алгоритм указывает, что или Xk = X*, или U=∅;

если алгоритм вырабатывает бесконечную последовательность точек Xk и ни одна из них не является решением задачи,то в Rn должно существовать компактное подмножество, которому принадлежат все Xk, а непрерывная функция z = f(X) удовлетворяет на этих Xk условиям: a) f(Xl)≥f(Xk) для всех l≥k+vk (здесь vk-некоторое число, относящееся к данному Xk), б) для любой подпоследовательности {Xk}, сходящейся к Х'≠Х*, либо существует такое k=k', что f(Xk')<f(Х'),либо существует сходящаяся подпоследовательность {f(Хk')},имеющая своим пределом f(X̂)<f(X').

Опуская доказательство, заметим, что сформулированные положения относятся к задаче минимизации f(X) на множестве U; вместо строгого улучшения f(X) на каждом шаге требуется улучшение лишь после vk шагов; вместо замкнутости алгоритмического отображения Wk(Xk) требуется выполнение условий а), б).

Сходимость того или иного метода (из рассмотренных в этом разделе) сравнительно легко устанавливается в случаях, когда f(X) и φi(Х) (i = 1,..., m) непрерывны, а множество U - компактно; может также понадобиться, чтобы X1∈U0 и в любой окрестности X* существовали точки Х∈U0 (т. е. X* не была бы изолированной от указанных X). Ниже даны примеры использования штрафных функций.

Пример: найти х12→min {z-x1+x2} при x1≥0, -x21+x2≥0.

Решение: ориентируясь на применение метода внутренней точки, введем в рассмотрение функции


S (r) = r; тогда L (X, r) = х1 + х2 - r[ln (- х21 + х2) + ln х1]; существование точек X̂ для произвольных r связано с равенствами


(достаточные условия min L здесь выполняются); следовательно,

всегда точки X будут принадлежать кривой х21+3х21, которая целиком лежит внутри области -x21+x2≥0, х1≥0 (исключение

составляет только Х̂ = (0, 0)); каждую такую X можно принять за X1 (условие X1∈U0 выполнено); далее следуют обычные операции:

а) принимается X1 = (1,4) и r1 = 1; L (X, r1)=x1+x2-ln [х1221)];

б) решается система dL(Х, r1)/dx1=0, dL(Х, r1)/dx2= 0, что дает Х̂ = (0,5; 1,25) = Х2;

в) принимается r2 = 0,5; L(Х, r2)=x1+x2-0,5ln [x1(x2-x21)]; точкой минимума L здесь является Х̂ = (0,31; 0,59) = Х3;

г) процедура отыскания X̂ повторяется для r3 = 0,25 r4 = 0,1,...; это позволяет получить Х4 = (0,18; 0,28) и т. д.; нетрудно видеть, что последовательность {Х*} стремится к X = (0, 0), которая становится подозрительной на экстремум;

д) в тех точках окрестности Х, которые принадлежат U, функция f(X) = x1+x2 положительно определена (достаточное условие минимума), поэтому Х* = (0, 0) и z* = 0.

Выбор другой последовательности {r} привел бы лишь к появлению новой последовательности {Хk}; конечный результат решения задачи сохраняется.

Пример: найти х1, х2→min{z = -х1х2} при х12≥0, 1- х1 + х22 ≥ 0.

Решение: ориентируясь на применение метода внешней точки положим


и S(r) = r; учитывая, что


получим


поиск точек X̂ здесь несколько усложняется (производные dL/dхj разрывны), но допускается практически произвольный выбор Х1; в остальном вычислительная схема сходна с той, что рассмотрена в предыдущем примере, поэтому можно взять X1 = (1,1), r1 = 1 и построить последовательность {(0,89; 0,64), (0,77; 0,62), (0,73; 0,61); (0,67; 0,58)...} для r, равных соответственно 1, 2, 3, 10,...; предельной точкой здесь является Х = (2/3, 3/3); проверка достаточных условий минимума f(X) подтверждает ее оптимальность, т. е. Х* = (2/3, √3/3), z* = 2 √3/9.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"