Алгоритм, реализующий метод внутренних точек

Алгоритм, реализующий метод внутренних точек, можно представить в виде следующей последовательности действий.

1. Из решения вспомогательной задачи находится начальное приближение х°, принадлежащее множеству внутренних точек D0, и принимается хr0 = х°. (Если априори точка x°∈D0 известна, то этот этап опускается.)

2. По формуле определяется начальное значение параметра штрафа ck = c0. (В общем случае значение c0 > 0 может быть выбрано произвольным образом.)

3. Одним из методов, рассмотренных ранее решается задача безусловной минимизации для фиксированного значения параметра штрафа сr из начальной точки хr°:

min Ф(х, cr) = min {(Q(x) + cr∑(1/gi)}.

Оптимальное решение этой задачи хr* принимается за начальную точку следующей итерации: xr+10 = хr*.

4. Проверяется условие окончания поиска оптимального решения
x* исходной задачи нелинейного программирования:

R(xr*, cr) = |cr∑(1/gi)| < δ.

Если это условие выполняется, то процесс поиска оптимального решения x* закончен и точка xr* принимается за приближенное решение исходной задачи. В противном случае переходим к п. 5.

5. Изменяется значение параметра штрафа cr таким образом, чтобы с ростом номера итерации r его значение уменьшалось, стремясь к нулю (например, можно считать, что cr+1 = cr/β, где β > 1). Весь процесс поиска повторяется с п. 3.

Недостатком рассмотренного алгоритма является то, что он требует существования «внутреннего множества» D0 допустимой области D, т. е. он не позволяет решать задачи нелинейного программирования с ограничениями типа равенств. Кроме того, для использования этого алгоритма необходимо знать начальное приближение х°, в котором все ограничения удовлетворяются как строгие неравенства.

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

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

gi(x) > -cr, i = 1, 2, …, m.

Введем множители Лагранжа следующим образом:

ui = — min [0, gi (х)].

Тогда в точке минимума х* из последнего равенства условий Куна— Таккера можем записать

∇Q(x) + ∑min[0, gi(x)]∇gi(x)/cr = 0.

Полученное выражение означает, что точка хr* является локальным минимумом штрафной функции Ф(х, сr) с квадратичным штрафом R (x, cr)

Ф(x, cr) = Q (x) + 1/crψ(x). (7.92)

Если точка x° находится вне допустимой области D, то движение осуществляется из недопустимой области в допустимую таким образом, чтобы минимизировать значение штрафа за выход точки х из области D. В допустимой области Ф (х, сr) = Q (х), а вне области D значение R (х, cr) очень велико по сравнению с Q (х).



Рис. 7.6. Линии уровня штрафа R(x, cr) (а) и штрафной функции Ф(х, cr) (б) при c1 > c2 > 0 для задачи одномерной оптимизации min {x}

На рис. 7.6 в качестве иллюстрации приведены линии уровня штрафа R(х, сr) = 1/сr{(min [0, (х — 2)])2 + (min [0, (4 — x)])2} и штрафной функции Ф (х, cr) при различных значениях параметра cr(c1 > c2 > 0) для задачи одномерного поиска min {х}.


Оставить комментарий





Статистика

Рейтинг@Mail.ru