Образовательный блог – всё для учебы

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

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

Ф(х, c_r) = Q(x) + R(х, c_r) = Q (X) + с_r?(х). (7.77)

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

Если x?D, то осуществляется минимизация функции Q (х). При нарушении ограничений (х не принадлежит D) функция Q (х) «штрафуется» на величину R(х, c_r), что и определяет название данного класса алгоритмов — методы штрафных функций. На рис. 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* влияние ограничений на минимизируемую штрафную функцию Ф (х, c_r). Это требование накладывает на индикаторную функцию ?(х) следующие ограничения. Она должна обладать следующими свойствами:

lim {c_r?(x^r)}=0;
lim {Ф(х_r*, c_r)- Q(x*)}=0,

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

Ф(х_r*, с_r) =min Ф(х, c_r) (7.78)

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

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

Представим множители Лагранжа Ui в виде функции от параметра
?_i ? 0:
u_i = ?_i², i = 1, 2, …, m. (7,79)

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

?_ig_i(x) = 0, i = 1, 2, …, m. (7.80)

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

?_ig_i(х) = a_r, i = 1, 2, …, m.

Откуда получаем, что ?_i = a_r/g_i(х)

или, учитывая (7.79), для множителей Лагранжа получаем:
u_i = a_r²/g_i²(х), i = 1, 2, …, m.
.
Подставляя полученные значения u_i в последнее из условий Куна— Таккера, можем записать:

?Q(x) – ?a_r²?g_i(x)/g_i²(x) = 0. (7.81)

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

Ф(х, c_r) = Q(x) + c_r?(1/g_i(x)). (7.82)

Здесь c_r = а_r²— параметр штрафа, который выбирается таким образом, чтобы c_r ? 0 при r ? ? для обеспечения условий (7.80) в точке x* (точка x* является оптимальным решением исходной задачи);
?(х) = ?(1/g_i(x)) — функция, которая при приближении к границе допустимой области D препятствует нарушению ограничений g_i(х), стремясь к бесконечности.

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

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

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

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

Рис. 7.5. Линии уровня штрафной функции Ф(х, c_r) для различных значений c₁ > c₂ > c₃

Другой тип функции штрафа можно получить, если предположить, что первое соотношение условий Куна—Таккера не выполняется:
ug_i (х) = c_r, i = 1, 2, …, m.

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

u_i = c_r/g_i(х).

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

?Q(x) – ?c_r?g_i(x)/g_i(x) = 0. (7.83)

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

Ф(х, c_r) = Q(x) + c_r?ln(1/g_i(x)) = Q(x) – c_r?ln(g_i(x)). (7.84)

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

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

D₀ = {x|g_i(x) > 0, i = 1, 2, …, m}. (7.85)

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

lim Ф(х_r*, с_r) = Ф(х); (7.86)
lim Ф(х_r*, c_r) = Q(x) = min Q(x) (7.87)

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

R(x_r+1*, c_r+1) < R(x_r*, c_r). (7.88)

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

Предположим, что в произвольной точке х’ ограничения типа неравенств (а метод внутренних точек применим только для задач нелинейного программирования) удовлетворяются не для всех индексов j:
g_j(х’) ? 0, j ? J;
g_i(x’) > 0, i ? J, где J?I = {1. 2, …, m}.

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

max ?g_j(x) = min{-? gg_j(x)} (7.89)

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

g_i(x’) > 0, i ? J.

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

min (-?g_j(x) + c_r?(1/g_j(x))}. (7.90)

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

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

?Ф(x°,c₀) = min|?Ф(x°, с)|.

Похожие записи

1. Многомерный случай для задач безусловной минимизации
2. Алгоритм, реализующий метод внутренних точек
3. Некоторые подходы к решению задач невыпуклого программирования
4. Условия оптимальности для задачи условной оптимизации
5. Задача квадратичного программирования
6. Сведение многомерной задачи оптимизации к задаче одномерного глобального поиска
7. Особенности задач поиска и оптимизации проектных решений
8. Постановка задачи поиска и оптимизации проектных решений
9. Геометрическая интерпретация задач поиска и оптимизации
10. Задачи и методы оптимизации в системах имитационного моделирования
11. Условия Куна-Таккера для условной оптимизации
12. Упорядочение векторных критериев оптимальности при помощи обобщенной функции цели
13. Математические модели принятия решений
14. Минимизация функций без вычисления производных
15. Условия оптимальности для некоторых классов моделей принятия решений
16. Использование коллектива независимых стохастических автоматов как некоторой системы поисковой оптимизации
17. Классификация объектов и задач проектирования, подходы к проектированию