5.4.2. ПРОЦЕДУРЫ, ОСНОВАННЫЕ НА МЕТОДЕ ГРАДИЕНТНОГО СПУСКА

Метод, используемый для нахождения решения системы линейных неравенств а^уг>0, состоит в определении функции критерия У (а), которая минимизируется при условии, что а является вектором решения. Данный подход сводит рассматриваемую задачу к минимизации скалярной функции, что часто можно осуществить при помощи процедуры градиентного спуска. Принцип процедуры спуска очень прост. Она начинается с выбора некоторого произвольного весового вектора аі и вычисления градиентного вектора Ѵ/(аі). Следующее значение а^ получается при смещении на некоторое расстояние относительно вектора аі в направлении наискорейшего спуска, т. е. вдоль отрицательного градиента. В общем случае а/і+1 получают из а^ по алгоритму

где ph есть положительный скалярный коэффициент, определяющий величину шага. По-видимому, такая последовательность весовых векторов должна сходиться к решению, минимизирующему функцию У (а).

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

где D является матрицей частных производных второго порядка дЧідаідйі, вычисленных при условии а=а^. Тогда, используя а*+і, взятое из соотношений (8) и (9), можно получить следующее выражение:

из чего следует, что функцию /(а^^+і) можно минимизировать, выбрав

Другую процедуру спуска можно получить, если, не используя (8), выбирать а*+х, минимизирующее это разложение второго порядка. Это приводит к алгоритму Ньютона, имеющему вид:

Вообще говоря, один шаг алгоритма Ньютона обычно более эффективен, нежели шаг алгоритма простого градиентного спуска даже при оптимальном значении р^. Однако если матрица D вырожденка, то алгоритм Ньютона неприменим. Более того, даже при условии, что матрица D невырожденна, потери времени, связанные с ее обращением, могут легко свести на нет указанные преимущества. Фактически зачастую небходимость сделать несколько лишних коррекций, если в качестве взято заниженное значение р, приводит к меньшим затратам времени, чем вычисление оптимального р^ на каждом шаге. В дальнейшем еще придется вернуться ко всем этим вопросам.