На каждой итерации метода строится возможное направление спуска и затем проводится оптимизация вдоль этого направления.

Следующее определение вводит понятие возможного направления спуска.

ОПРЕДЕЛЕНИЕ. Рассмотрим задачу минимизации f(х) при условии, что хÍS, где f: Е_nàЕ₁, а S—непустое мно­жество из Е_n. Ненулевой вектор d называется возможным направлением в точке хÍS, если существует такое d>0, что х+lxÍS для всех lÍ(0,d). Вектор d называется возможным направлением спуска в точке xÍS, если существует такое d>0, что f(х+ld) и х+ldÍS для всех lÍ(0, 6).

Случай линейных ограничений

Вначале рассмотрим случай, когда допустимая область S опре­делена системой линейных ограничений, так что рассматривае­мая задача имеет вид

минимизировать        f(х)

при условиях              Ах£b,

Ех = е.

Здесь А—матрица порядка m ´ n, Е—матрица порядка l ´ n, b есть m-мерный вектор, а е есть l-мерный вектор. В следующей лемме приводятся соответствующие характеристики допустимой области и формулируются достаточные условия для существо­вания возможного направления спуска. В частности, вектор d является возможным направлением спуска, если A₁d£0, Еd=0 и Ñf(х)^Td<0.

ЛЕММА. Рассмотрим задачу минимизации f(х) при условиях Ах£b и Ех=е. Пусть х—допустимая точка, и предположим, что А₁x=b₁ и А₂x<b₂, где   А^T=(А₁^T, А₂^T), а b^T=(b₁^T, b₂^T). Тогда ненулевой вектор и является возможным направлением в точке х в том и только в том случае, если A₁d£0 и Еd=0. Если, кроме того, Ñf(х)^Td<0, то d является возможным направлением спуска.

Геометрическая интерпретация возможного направления спуска

Проиллюстрируем теперь геометрически на примере множество возможных направлений спуска.

ПРИМЕР

Минимизировать при условиях

                                      (x₁-6)²+(x₂-2)²

                                      -x₁+2x₂£4

                                      3x₁+2x₂£12

                                      -x₁£0

Возьмем х=(2, 3)^T и заметим, что первые два ограничении являются активными в этой точке. В частности, матрица А₁ из леммы равна А₁=[^-1₃  ²₂]. Следовательно, вектор d является возможным направлением тогда и только тогда, когда А₁d£0, т.е. в том и только в том случае, если

-d₁+2d₂£0,

 3d₁+2d₂£0.

                                    -x₂£0

На рис. 1, где начало координат перенесено в точку х, изо­бражена совокупность этих направлений, образующая конус возможных направлений. Заметим, что если сдвинуться на не­большое расстояние от точки х вдоль любого вектора d, удов­летворяющего двум приведенным выше неравенствам, то оста­немся в допустимой области.

Если вектор d удовлетворяет неравенству 0>Ñf(х)^Td=-8d₁+2d₂, то он является направлением спуска. Таким образом, совокупность направлений спуска определяется открытым полупространством {(d₁,d₂}: -8d₁+2d₂<0}. Пересече­ние конуса возможных направлений с этим полупространством задает множество всех возможных направлений спуска.

Рис. 1. Возможные направления спуска, 1—конус возможных направле­ний: 2 — конус возможных направлений спуска; 3 — линии уровня целевой функции; 4 — полупространство направлений спуска.