 |
 |
 |
 |
|
 |
 |
53
значения скалярных произведений вектора направления s на градиенты функции ограничений:
где I
л
— множество номеров индексов линейных ограничений, I
н
— множество номеров индексов
нелинейных ограничений. Соответственно, I(x
(q)
)?I
л
—номера линейных активных ограничений, а
I(x
(q)
)?I
н
— номера нелинейных активных ограничений. Отличие условий (2.20) от условий (2.21)
заключается в том, что в случае линейного ограничения направление, образующее прямой угол с
градиентом ограничивающей функции (т. е. их скалярное произведение равно нулю), будет заведомо
допустимым, а в случае нелинейного ограничения — возможно, нет.
Все возможные направления в точке x
(q)
образуют так называемый конус допустимых направлений, и
из них для следующего перехода, очевидно, нужно выбрать прогрессивное. Если такового не
существует, то согласно сформулированному выше критерию точка x
(q)
является оптимальной! Для
ускорения максимизации функции желательно, чтобы угол между искомым допустимым
прогрессивным направлением
s
(q)
и градиентом целевой функции ?f(x
(q)
) был как можно меньше или,
что то же самое, как можно большей была бы проекция s на ?f(x
(q)
) (при условиях нормировки вектора
s
(q)
). Иными словами, желательно, чтобы неравенство
s
(q)
?f(x
(q)
)+??0 выполнялось при минимально
возможном
?
?
R. Тогда задачу отыскания наилучшего допустимого прогрессивного направления
s
(q)
можно свести к задаче минимизации параметра
?:
при условиях
где s1² +s2² +...+s
n
2
,
? l
—условие нормировки, обеспечивающее ограниченность решения;
? — некоторое достаточно малое число, характеризующее «строгость» выполнения неравенств.
В отличие от всех остальных, последнее условие в системе (2.23) является нелинейным, что
существенно усложняет процесс решения задачи (2.22)-(2.23). Поэтому на практике для
определения
направления
s
(q)
(возможно, не лучшего) переходят от данной задачи к задаче линейного
программирования путем замены указанных выше условий нормировки на ограничения вида –l
?
s
j
,
?
1:
После того как прогрессивное направление
s
(q)
найдено, шаговый множитель определяется по
методу, описанному в п. 1°.
В заключение отметим, что при практических расчетах алгоритм завершается при достижении такой
точки х*, в которой |?f(x*)|<?, где
?
—достаточно малое число.