 |
 |
 |
 |
|
 |
 |
51
Направление s называется допустимым (возможным) в точке x
(q)
D, если существует такое
? > 0, что x
(q+1)
= x
(q)
+ ?s
D.
Направление s называется прогрессивным в точке x
(q)
D, если существует такое ? >0, что
f(x
(q)
+ ?s)> > f(x
(q)
) для задачи максимизации и f(x
(q)
+ ?s) < f(x
(q)
) для задачи минимизации.
На основе данных определений достаточно просто сформулировать критерий проверки
оптимальности точки (так называемый критерий оптимальности в терминах допустимых и про-
грессивных направлений):
точка х* является оптимальным планом задачи (2.16), если в ней ни одно допустимое
направление не является прогрессивным.
В алгоритме метода допустимых направлений правила выбора точки
х
(q+1)
, к которой происходит
очередной переход, различаются в зависимости от того, где находится текущая точка х
(q)
.
Принципиально возможны две ситуации.
1°. Точка х
(q)
лежит внутри области D, т. е. для всех i
1: m g
i
(х
(q)
) < 0 (см. рис. 2.4). Очевидно, что
для внутренней точки любое направление будет допустимым (при выборе достаточно малого шага),
поэтому естественным представляется движение в сторону «гарантированного» возрастания значения
функции, а именно в направлении градиента. Значит, для внутренней точки х
(q)
целесообразно выбрать
s
(q)
=
f(х
(q)
).
Шаговый множитель
?
q
выбирается так, чтобы, с одной стороны, новая точка х
(q+1)
принадлежала D, а
с другой — значение целевой функции в ней f(х
(q+1)
) было как можно большим.