2701
.pdf
|
|
Рис. 3.4. Штрафные функции |
|
|
|
|||
|
|
|
|
|
значений параметра c , реали- |
|||
|
|
|
|
для различных |
|
Ф( , |
) = ( |
k + ) + |
|
|
|
|
|||||
( + )зующие метод внутренней точки |
|
Полученное выражение называется логарифмической функцией штрафа и обладает теми же "барьерными" свойствами, что и штрафная функция (3.27).
Недостатком штрафных функций (3.27) и (3.30) является то, что они требуют существования "внутреннего множества" допустимой области D, т.е. они не позволяют решать задачи нелинейного программирования с ограничениями типа равенств. Кроме того, для их использования в задачах безусловной оптимизации (3.22) необходимо знать начальное приближение х0, в котором все ограничения (3.2) удовлетворяются как строгие неравенства. Это свойство введенных штрафных функций позволяет говорить об алгоритмах основанных на их последовательной минимизации при уменьшающихся пара-
61
метрах сk или аk, как об алгоритмах, реализующих метод внутренних точек.
Построим штрафную функцию Ф(х, сk), для которой не требуется знать внутреннюю точку В и которая позволяет решать задачи нелинейного программирования как с ограничениями типа неравенств, так и с ограничениями типа равенств.
Предположим, что второе неравенство в условиях Ку- на-Таккера выполняется в ослабленном виде:
gi(x)>-ck, = 1, .
Введем множители Лагранжа следующим образом:
ui = –min(0, gi(x)).
Тогда, подставляя полученные значения ui в последнее соотношение условий Куна-Таккера, получаем:
( )+∑ min 0, ( ) ( )⁄c = 0 (3.31)
Выражение (3.31) соответствует необходимому условию существования минимума многопараметрической функции следующего вида:
Ф( ,c ) = ( )+ ∑ (min (0, ( ))) (3.32)
В области допустимых решений D значение функции Ф(х, сk) = Q(x), а вне области D значение R(х, ck) = (х / сk) очень велико по сравнению с Q(x). Поэтому, если точка находится вне допустимой области D, то траектория поиска идет таким образом, чтобы минимизировать значение штрафа за выход точки х из области допустимых решений D. Алгоритм
, основанный на последовательной минимизации штрафной функции (3.32) при уменьшающихся значениях параметров 1 / ck является реализацией метода внешних точек, 62
На рис. 3.5 приведены функции штрафа (3.32), построенные для значений параметра c1 и с2{с2>с1) для задачи оптимизации min { + }.
Рис. 3.5. Штрафные функции Ф( , ) = ( + ) + {(min(0; − )) ;(min(0; − )) }для различных значе-
ний параметра ck, реализующие метод внешней точки
Недостатком рассмотренных алгоритмов, реализующих метод штрафных функций, является отсутствие формализованных процедур выбора постоянных коэффициентов ck. Кроме этого, для определения оптимального решения х* исходной задачи выпуклого программирования (3.1) - (3.2) требуется, чтобы вспомогательные задачи безусловной оптимизации (3.23) решались с высокой степенью точности. Это требование, как и необходимость многократного применения методов безусловной оптимизации для последовательности коэффициентов {ck}, может привести к большим вычислительным затратам.
63
3.3. Методы проектирования градиента
Будем считать, что в задаче нелинейного программиро-
вания:
min ( ) |
(3.33) |
имеются ограничения только типа равенств:
D = {x | hi(x) = 0, = 1, } |
(3.34) |
Это предположение не ограничивает общности рассмотрения, так как любое ограничение типа неравенства gi(х) > 0 может быть преобразовано в ограничение типа равенства. Особенностью задачи (3.33) - (3.34) является то, что ее оптимальное решение х* находится в (n-m) - мерном подпространстве D, образованном пересечением гиперповерхностей:
|
Hj(x) = {x | hi(x) = 0}, = 1, |
(3.35) |
|
Алгоритм |
|
основанный на этой особенности |
|
задачи, позволяет |
осуществлять поиск ее оптимального реше- |
||
|
|
|
ния с помощью выпуклого программирования (3.33) - (3.34) методом проектирования градиента, который состоит из двух этапов: градиентной фазы и фазы восстановления.
В градиентной фазе предполагается, что точка хk удовлетворяет системе ограничений типа равенств (3.34), а приращение ∆хk вычисляется таким образом, чтобы величина минимизируемой функции уменьшалась. Для этого через точку хk проводятся гиперплоскости, касательные к гиперповерхностям Hj(x) и путем проектирования градиента функции Q(x) на пересечение этих аппроксимирующих ограничений определяется направление Sk наибыстрейшего убывания функции Q(x) в подпространстве D. Вдоль полученного направления Sk
64
осуществляется поиск точки yk+1 с наименьшим значением функции Q(x):
yk+1 = xk + ∆k = xk + kSk |
(3.36) |
Поскольку уравнения (3.34) являются нелинейными, а размер шага может оказаться большим, то точка yk+1 в общем случае не будет принадлежать множеству D. В связи с этим в фазе восстановления для обеспечения сходимости процесса поиска необходимо на каждом шаге осуществлять возращение текущей точки уk+1 на множество D, корректируя ее значение по следующей формуле:
xk+1 = yk+1 + ∆yk+1 |
(3.37) |
Приращение ∆yk+1 определяется таким образом, чтобы ограничения (3.34) в очередной точке испытаний xk+1 удовле-
творялись с заданной точностью : |
|
(hT (xk+1), h(xk+1)) ≤ , |
(3.38) |
где — требуемая точность выполнения ограничений типа равенств.
На рис. 3.6 показаны градиентная фаза и фаза восстановления для первых двух итераций метода проектирования градиента.
Остановимся более подробно на определении аналитических выражений для вычисления приращений ∆xk и ∆yk.
Обозначим матрицу нормалей к каждой касательной гиперплоскости:
( ) + Т( )( − ) = 0, = 1, , (3.39)
проведенной в точке xk гиперповерхности Hj(x) = 0, следующим образом:
65
( |
) = ( , |
,…, |
) = |
⁄ |
,…, |
⁄ |
, |
(3.40) |
⁄ |
,…, |
⁄ |
|
|||||
где |
Т = ( |
) = |
⁄ |
,…, |
⁄ |
|
|
(3.41) |
Рис. 3.6. Траектория движения вдоль ограничения типа равенства с помощью метода проектирования градиента
Предположим, что для любой точки х, принадлежащей
-окрестности множества D, векторы uj линейно-независимы
ине равны нулю. Тоща матрица (UT(x)U(x)) является невырожденной и имеет обратную матрицу:
V(x) = (UT(x)U(x)–1. |
(3.42) |
На каждой k-ой итерации градиентной фазы при выборе направления поиска Sk необходимо обеспечить выполнение следующих требований.
66
Во-первых, направление Sk должно выбираться так, чтобы вдоль него достигалось наибольшее уменьшение функции Q(x). Разлагая функцию Q(x) около точки хk в ряд Тейлора с точностью до членов первого порядка, получаем, что вдоль направления Sk необходимо минимизировать разность:
|
(направление) ( |
) k |
|
Т |
|
(3.43) |
Во-вторых, |
являющееся( ) |
. |
единичным |
|||
− |
S=, |
Q |
|
|
||
вектором |
|
|
|
|
|
|
|
((Sk)T,Sk) = 1, |
|
|
(3.44) |
должно принадлежать пересечению касательных гиперплоскостей (3.39), проходящих через точку хk, т.е. направление Sk должно быть ортогонально к каждой нормали uj,
= 1, :
UТ(xk)Sk = 0 |
(3.45) |
Таким образом, учитывая требования (3.43) - (3.45), для определения направления поиска Sk необходимо решить следующую задачу оптимизации:
min {( Т( ), )} |
(3.46) |
при условии, что
UТ(xk)S = 0; ((S)T, S) = 1.
Построим функцию Лагранжа для задачи оптимизации
(3.46):
( , , ) = ( ( ) , ) + Т Т( ) + (( Т, ) − 1).
67
Значения s, v и а должны удовлетворять системе урав-
нений:
( , , )⁄ = ( ) + Т( ) 1 = 0;
( , , )⁄ |
= Т( ) = 0; |
( , , )⁄ |
= ( Т, ) −1 = 0; |
Откуда получаем, что оптимальным решением задачи оптимизации (3.46) является вектор sk, вычисляемый по формуле:
= − |
( |
) ( |
) = |
|
|
= − − ( ) |
( |
) Т( |
)k |
( ), |
(3.47) |
где Е - единичная матрица; Р(х ) - матрица проектиро-
вания градиента функции Q(x) на пересечении гиперповерх-
Для |
|
= 1, . |
|
|
|
|
|
ностей Нj(х), |
|
|
|
|
вдоль направления Sk |
||
|
определения длины шага |
||||||
решается одномерная задача оптимизации: |
), (3.48) |
||||||
( |
|
) = |
( |
+ |
) = min |
( + |
|
где |
|
= |
( |
+ |
) ≤ , = 1, . |
|
Поиск оптимального решения x* исходной задачи нелинейного программирования (3.33) - (3.34) считается законченным, если выполняется условие:
|| ( ) ( )|| ≤ |
(3.49) |
В том случае, если точка yk+1 принадлежит - окрестности области решений D, то она принимается за новое приближение xk+1, для которой выполняется градиентная фаза. В
68
противном случае, прежде чем перейти к новой (k+1)-й итерации, необходимо выполнить фазу восстановления (3.37)
Аппроксимируя около точки yk+1 ограничения типа равенств разложениями в ряд Тейлора до членов первого порядка, потребуем, чтобы полученные линеаризированные уравнения выполнялись в точке xk+1:
h(xk+1) =h(yk+1 + ∆yk+1) = |
|
=h(yk+1) + UT(xk+1) ∆yk+1) = 0 |
(3.50) |
Для того, чтобы величина функции Q(yk+1), полученная на предыдущей фазе, изменялась в точке xk+1 незначительно, приращение ∆yk+1должно выбираться как можно меньшей величины. Учитывая это требование и имея в виду соотношение (3.50) для определения приращения ∆yk+1, сформулируем следующую задачу оптимизации:
min∆ { |
|
(∆ Т,∆ )} |
(3.51) |
|
при условии, что
h(xk+1) + UT(yk+1) ∆y = 0.
Построим функцию Лангранжа для задачи оптимиза-
ции (3.51):
(∆ , ) = |
1 |
(∆ Т,∆ )+ Т( ( |
) + Т( |
)∆ ). |
Значения |
2∆y и должны удовлетворять системе урав- |
нений:
(∆ , )⁄ ∆ = ∆ Т + Т Т( ) = 0;
69
(∆ , )⁄ = ( ) + Т( )∆ = 0.
Откуда получаем, что оптимальным решением задачи оптимизации (3.51) является вектор ∆yk+1, вычисляемый по формуле:
|
|
∆yk+1 = –UT(yk+1)V(yk+1)h(yk+1) = 0 |
(3.52) |
||
Если в фазе восстановления не обеспечивается требуе- |
|||||
мая точность |
выполнения ограничений типа равенств, то |
||||
она повторяется несколько раз. |
|
|
|
||
Недостатком метода проектирования |
|
являет- |
|||
ся то, что0 |
|
|
|
требуется знать |
|
в качестве начального приближения |
|
|
|||
точку х , в которой ограничения (3.34) выполняются как ра- |
|||||
венства ( |
|
) с требуемой точностью . |
|
|
|
|
повышения скорости сходимости процедуры поис- |
||||
Для |
|
* |
|
|
|
ка точки |
условного минимума х |
задачи нелинейного про- |
граммирования (3.33) - (3.34) на каждой итерации в градиентной фазе при выборе приращения ∆хk будем использовать информацию о величине приращения ∆хk-1, полученного на предыдущей итерации. Тогда выбор приращения ∆хk может быть сформулирован как задача оптимизации:
min∆ { ( ),∆ } |
(3.53) |
при условии, что
UT(xk)∆x = 0;
(∆ − ∆ )Т(∆ − ∆ ) = .
Построим функцию Лагранжа для задачи оптимизации
(3.53):
( , , ) = Т( )∆ + Т Т( )∆ +
70