Преобразование задачи нелинейного программирования при помощи функций штрафов в последовательность задач безусловной оптимизации

Рассмотрим класс алгоритмов, которые позволяют решение задачи нелинейного программирования свести к решению последовательности задач безусловной оптимизации.

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

Ф(х, cr) = Q(x) + R(х, cr) = Q (X) + сrψ(х). (7.77)

где cr > 0 — параметр штрафа; ψ(х) — индикаторная функция, R (х, cr) = сrψ(х) — штраф.

Если x∈D, то осуществляется минимизация функции Q (х). При нарушении ограничений (х не принадлежит D) функция Q (х) «штрафуется» на величину R(х, cr), что и определяет название данного класса алгоритмов — методы штрафных функций. На рис. 7.4 показаны одномерная задача min(αх+β) (рис. 7.4, а) и эквивалентная ей задача минимизации функции штрафа Ф (х, сr) при A = ∞ (рис. 7.4, б).



Рис. 7.4. Пример штрафной функции с бесконечно большим штрафом A = ∞

Штрафная функция, определяемая выражением (7.77), для больших значений A оказывается плохо обусловленной, т. е. вблизи оптимального решения х* ее гессиан имеет ряд собственных значений, стремящихся к бесконечности о ростом A. Это приводит к тому, что структура минимизируемой функции Ф(х, сr) приобретает овражный характер. Следует отметить, что чем меньше значение A, тем менее ярко выражен овраг. Но, с другой стороны, с уменьшением A снижается точность определения оптимального решения х* исходной задачи (7.1). В связи G этим при преобразовании задачи нелинейного программирования к последовательности задач безусловной оптимизации целесообразно рассматривать не постоянное значение штрафа R(х, сr), а менять его постепенно, увеличивая при приближении к точке минимума X* влияние ограничений на минимизируемую штрафную функцию Ф (х, cr). Это требование накладывает на индикаторную функцию ψ(х) следующие ограничения. Она должна обладать следующими свойствами:

lim {crψ(xr)}=0;
lim {Ф(хr*, cr)- Q(x*)}=0,

т. е. влияние штрафа R(х, сr), удовлетворяющего этим условиям штрафной функции Ф(х, cr), должно постепенно ослабевать, а последовательность решений задач безусловной минимизации:

Ф(хr*, сr) =min Ф(х, cr) (7.78)

должна сходиться к точке минимума х* исходной задачи.

Конкретный вид штрафа R (х, сr) нетрудно получить из условий оптимальности решения х* задачи выпуклого программирования (условий Куна—Таккера (1.76)—(1.79)).

Представим множители Лагранжа Ui в виде функции от параметра
λi ≥ 0:

ui = λi2, i = 1, 2, …, m. (7,79)

Очевидно, что условие uigi(х) = 0 эквивалентно условию:

λigi(x) = 0, i = 1, 2, …, m. (7.80)

Предположим, что условия (7.80) не выполняются и их левая часть равна некоторой положительной величине аr. Тогда можем записать:

λigi(х) = ar, i = 1, 2, …, m.

Откуда получаем, что λi = ar/gi(х)

или, учитывая (7.79), для множителей Лагранжа получаем:
ui = ar2/gi2(х), i = 1, 2, …, m..

Подставляя полученные значения ui в последнее из условий Куна— Таккера, можем записать:

∇Q(x) — ∑ar2∇gi(x)/gi2(x) = 0. (7.81)

Выражение (7.81) соответствует условию существования минимума (первые производные равны нулю) многопараметрической функции
без ограничений следующего вида:

Ф(х, cr) = Q(x) + cr∑(1/gi(x)). (7.82)

Здесь cr = аr2— параметр штрафа, который выбирается таким образом, чтобы cr → 0 при r → ∞ для обеспечения условий (7.80) в точке x* (точка x* является оптимальным решением исходной задачи);
ψ(х) = ∑(1/gi(x)) — функция, которая при приближении к границе допустимой области D препятствует нарушению ограничений gi(х), стремясь к бесконечности.

Таким образом, если начальное приближение х° является внутренней точкой, т. е. такой, в которой, все ограничения gi(х) выполняются как строгие неравенства:

gi (х°) > 0, i = 1, 2, …, m,

то оптимальное решение xr* задачи безусловной минимизации штрафной функции (7.82) будет всегда находиться внутри допустимой области, так как функция R (х, cr) ставит «барьер» против выхода из области D. Это свойство позволяет выделить в методах штрафов класс алгоритмов, реализующих методы внутренней точки (методы барьерных функций). При уменьшении параметра штрафа cr уменьшается влияние штрафа R(х, cr) и возрастает влияние критерия Q(х) на значение штрафной функции Ф(х, cr). В связи с этим при сr → 0 уменьшение Ф (х, сr) возможно только за счет минимизации функции Q(х) без нарушения ограничений gi(х). При r → ∞ точки минимума xr* гиперповерхностей Ф(х, сr) все более плотно подходят к точке минимума x* гиперповерхности соответствующей функции Q (х) = Ф (х, 0).

На pис. 7.5 в качестве иллюстрации приведены линии уровня семейства (пунктирные кривые) параметрических функций
Ф(x, cr) = x + cr(1/х + 1/(1 — x)),
построенные при различных значениях параметра с, для задачи одномерного поиска min {х}.



Рис. 7.5. Линии уровня штрафной функции Ф(х, cr) для различных значений c1 > c2 > c3

Другой тип функции штрафа можно получить, если предположить, что первое соотношение условий Куна—Таккера не выполняется:

ugi (х) = cr, i = 1, 2, …, m.

Тогда множители Лагранжа при условии, что gi(х)≠0 имеют вид:

ui = cr/gi(х).

Подставляя полученные значения ui в последнее соотношение условий Куна—Таккера, получаем

∇Q(x) — ∑cr∇gi(x)/gi(x) = 0. (7.83)

Выражение (7.83) соответствует условию существования минимума многопараметрической функции без ограничений следующего вида

Ф(х, cr) = Q(x) + cr∑ln(1/gi(x)) = Q(x) — cr∑ln(gi(x)). (7.84)

Полученное выражение называется логарифмической функцией штрафа и обладает теми же свойствами, что и штрафная функция (7.82).

В том случае, когда допустимая область D является замкнутым выпуклым множеством, имеющим подмножество внутренних точек

D0 = {x|gi(x) > 0, i = 1, 2, …, m}. (7.85)

а функции Q (х) и gi(х), i = 1, 2, …, m, являются непрерывными функциями, существует такая точка х∈D0, что

lim Ф(хr*, сr) = Ф(х); (7.86)
lim Ф(хr*, cr) = Q(x) = min Q(x) (7.87)

при условии, что

R(xr+1*, cr+1) < R(xr*, cr). (7.88)

В том случае, когда начальное приближение х°, принадлежащее множеству внутренних точек D0, априори задать трудно, для его определения можно применить следующую процедуру.

Предположим, что в произвольной точке х’ ограничения типа неравенств (а метод внутренних точек применим только для задач нелинейного программирования) удовлетворяются не для всех индексов j:

gj(х’) ≤ 0, j ∈ J;
gi(x’) > 0, i ∈ J, где J∪I = {1. 2, …, m}.

Тогда стратегия поиска точки х° ∈D0 заключается в построении последовательности точек {xk} таких, чтобы сумма нарушившихся ограничений уменьшалась по абсолютной величине, но при этом ни одно из уже выполненных ограничений не нарушалось:

max ∑gj(x) = min{-∑ gj(x)} (7.89)

при условии, что

gi(x’) > 0, i ∈ J.

Для задачи (7.89) начальное приближение известно (это точка х’), поэтому применим для ее решения метод внутренних штрафов, который сводится к решению последовательности задач безусловной минимизации вида:

min (-∑gj(x) + cr∑(1/gj(x))}. (7.90)

В процессе решения задачи безусловной оптимизации (7.90) появляются новые точки, в которых удовлетворяются одно или более ограничений из тех, что прежде не удовлетворялись, т.е. индексы из множества J переходят в множество I. При этом изменяется и сама вспомогательная задача (7.89). Точка х° считается определенной, когда множество индексов J становится пустым. Если в точке оптимального решения вспомогательной задачи (7.89) множество индексов J не пусто, то это означает, что ограничения исходной задачи нелинейного программирования (7.1) несовместны.

Эффективность метода внутренних точек в значительной степени зависит от выбранного начального значения параметра штрафа с0. Если c0 велико, то процесс поиска оптимального решения х* исходной задачи нелинейного программирования начинается далеко от границы допустимой области D, при малых значениях c0, наоборот, процесс поиска начинается далеко от оптимального решения х*. В обоих случаях приходится тратить дополнительные усилия на решение последовательных задач безусловной оптимизации. В связи с этим выбор начального значения параметра штрафа c0 можно осуществлять таким образом, чтобы модуль градиента штрафной функции в точке начального приближения имел минимальное значение:

∇Ф(x°,c0) = min|∇Ф(x°, с)|.


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru