17-9. Метод допустимых направлений Зойтендейка

Предполагается, что задана вогнутая функция цели Q, необязательно квадратичная, с непрерывным градиентом

и требуется определить максимум этой функции при ограничивающих условиях

Необходимо так определить направление перехода из точки х^k в точку х^k+1 = x^k + γs^k, чтобы новая точка при достаточно малом γ > 0 принадлежала области допустимых значений G, определяемой соотношениями (17-65). Необходимым и достаточным условием соблюдения этого требования является следующее:

где S - множество всех индексов i, для которых

т. е. это означает, что множество S соответствует границе допустимой области, достигнутой на предыдущем шаге, а условие (17-66) означает, что последующий шаг направлен внутрь и по границе области допустимых значений.

Направления, удовлетворяющие условиям (17-66) и (17-67), называются допустимыми.

Второе требование к выбору направления очередного шага заключается в том, чтобы функция цели увеличивалась вдоль выбранного направления хотя бы для малых γ, что обеспечивается неравенством

Направления, удовлетворяющие условию (17-68), называются подходящими. Из допустимых и подходящих направлений выбирается некоторое частное направление с помощью условий нормализации, которыми и отличаются различные градиентные методы.

Процедура определения длины очередного шага γ^k при определенном s^k во всех методах одинакова, а именно, определяется такое значение параметра γ', при котором луч "протыкает" область допустимых значений G, определяемую соотношением (17-65), или такое значение γ", при котором Q достигает максимума, т. е.

причем γ' и γ" могут быть бесконечно большими. После этого длина очередного шага определяется из соотношения

При бесконечно большом значении γ^k функция цели неограниченна. Если γ^k конечна, очередная точка вычисляется по формуле

Метод Зойтендейка решает на каждом шаге частные небольшие линейные и нелинейные вспомогательные программы, в которых может с успехом применяться симплекс-метод. Метод применим не только к квадратичным функциям цели и линейным ограничениям. Он не дает сходимости за конечное число шагов, однако если добавить условия сопряженности, то такая сходимость обеспечивается. Сформулируем вспомогательные программы Зойтендейка. Их идея заключается в том, что новое направление s^k ищется оптимальным в том смысле, чтобы функция цели не просто увеличивалась, что обеспечивается соотношением (17-68), а увеличивалась за каждый шаг максимальным образом при определенных условиях, т. е. требуется найти s^k, такое, что

при ограничениях

и одном из пяти дополнительных нормирующих условий:

Следует заметить, что условие (17-71),справедливое для подмножества индексов i ∈ S, содержится в соотношении (17-71).

Условия нормализации необходимы для ограничения величины s^k, так как иначе величину gs можно сделать сколь угодно большой при условии существования допустимого направления, для которого gs > 0. Если некоторые из ограничений исходной программы (17-73) имеют знак строгого равенства, то в соответствующих соотношениях (17-66) также должен стоять знак равенства, т. е. a_is = 0. Можно ввести другие условия нормализации, и тогда получится новый градиентный метод.

Рис. 17-15. Пояснение к методу Зойтендейка

Условие (17-72) ограничивает квадрат модуля вектора s. Условно это ограничение представлено на рис. 17-15,а в виде окружности. Ограничения (17-73) определяют куб допустимых значений вектора направления k-го шага s^k, который может быть направлен в одну из вершин куба (рис. 17-15,6). Условие (17-74) для случая g_i > 0 представлено на рис. 17-15,в. Допустимая область векторов s^k на этом рисунке ограничена двумя лучами, пересекающимися под прямым углом. В случае нормирующего условия (17-75) область допустимых значений векторов s^k лежит по одну сторону от прямой gs = 1 и не ограничена. Эти условия носят несколько более сложный характер, но очевидно, что вся допустимая область х является приемлемой с точки зрения выбора очередного шага, т. е. конец вектора s^k может лежать в любой точке этой области (рис. 17-15, г), так как вектор s^k складывается с вектором x^k, и их сумма не должна выходить за пределы допустимой области значений х. Соотношения (17-76) допускают выбор сколь угодно больших отрицательных значений s_i т. е. область допустимых значений s не ограничена. Оказывается, что ограничения (17-72) приводят к нелинейным, а ограничения (17-73) и (17-74) - к линейным программам.

Пример 17-2. Рассмотрим случай с нормирующими условиями (17-76) при квадратичной функции цели Q = рх - хСх (С положительно полуопределена),

Длину очередного шага определим из соотношения

где

Формулу (17-78) получим из (17-69), учитывая (17-77),

Физически это означает, что очередной шаг выбирается таким образом, чтобы сразу попасть в точку экстремума. В случае (17-76) величина, обеспечивающая "протыкание" лучом области допустимых значений, всегда равна единице, так как в соответствии с формулой (17-76) сам вектор s^k выбирается так, чтобы "проткнуть" эту область.

Рассмотрим задачу, решенную в примере 17-1. Максимизируем квадратичную форму Q = 6x₁ - 2х²₁ + 2х₁х2 - 2х²₂ = max при ограничениях х₁ + х₂ ≤ 2, х₁ ≥ 0, х₂ ≥ 0.

Здесь

В качестве исходной точки возьмем х⁰ = || 0,0 ||. Вопрос о выборе этой точки требует специального обсуждения, на котором здесь мы не останавливаемся. Начальное значение градиента

1. Первая вспомогательная программа в соответствии с нормализацией (17-76) заключается в том, чтобы максимизировать выражение g⁰s = 6s₁ = max при ограничениях
   s₁ + s₂ ≤ 2; s₁ ≥ 0, s₂≥0 (17-79)
   Это - задача линейного программирования. Для ее решения введем вспомогательную переменную ух и составим симплекс-таблицу (табл. 17-8). Уже на следующем шаге с помощью оптимальной симплекс-таблицы (табл. 17-9) придем к оптимальному решению.
   
   Таблица 17-8
   
   
   
   Таблица 17-9
   
   
   Чтобы из табл. 17-9 получить оптимальное решение, необходимо значения координат, соответствующих не базисным переменным, приравнять нулю (sx = 0), а остальные переменные (sx = 2) взять из таблицы: s⁰ = || 2, 0 ||. Далее, g⁰s⁰ = 12, s⁰Cs⁰ - 6, γ" = 12/2-6 - 1, Так как при условиях (17-76) γ' - 1, то γ⁰ - min (γ', γ") = 1. После первого шага координаты следующей точки определятся как
   х¹ =x⁰+γ⁰s⁰ = || 2, 01|;
   g¹ = р - 2Cx¹ = ||- 2, 4||.
   Поскольку γ⁰ = γ", используем условие сопряженности s⁰Cs = 0, а именно,
   4s₁-2s₂ = 0, (17-80)
   т. е. добавим условие (17-80) к ограничениям (17-79). Можно показать [Л. 96], что при вычислениях удобно пользоваться заменой s → t в соответствии с формулой t = x^k + s. Это в ряде случаев позволяет применить сокращенный метод таблиц. Подставим t¹ = х¹ + s. Тогда дополнительное условие (17-80) запишется в виде 4t₁ - 2t₂ = 8.
2. Во второй вспомогательной программе требуется найти максимум g¹x¹ = -2t₁ + 4t₂ при условиях
   t₁t₂y₁=2, y₁≥0
   4t₁-2t₂+y₂=8, y₂=0
   t₁≥0, t₂≥0
   Составим первую и вторую симплекс-таблицы второго шага (табл. 17-10, 17-11).
   
   Таблица 17-10
   
   
   
   Таблица 17-11
   
   
   После второго шага имеем:
   
   
   Поскольку γ₀ = γ"; γ¹ = γ", для третьего шага к ограничениям (17-79) необходимо добавить уже два дополнительных условия, соответствующих s₀Cs = 0 и s₁Cs = 0, а именно, 4s₁ - 2s₂ = 0; -6s₁ + 6s₂ = 0. Теперь подставим t₂ = х₂ + s и получим задачу третьего шага.
3. В третьей вспомогательной программе требуется найти максимум g²t² = -5t₁ + 7t₂ при условиях
   t₁t₂y₁=2, y₁≥0, t₁₂≥0
   4t₁-2t₂+y₂=9, y₂=0
   6t₁-6t₂+y=12, y₃=0
   Решение находим аналогично предыдущему:
   
   
   Выбираем γ² = γ" = 2/5. После третьего шага х³ = || 3/2, 1/2 ||. Поскольку g³ = || 1, 1 ||, к ограничениям (17-79) следует добавить уже три дополнительных условия
   
   
   соответствующие условиям сопряженности
   s⁰Cs = 0;
   s¹Cs = 0;
   s²Cs = 0.
   Подставим t³ = x³ + s и получим задачу четвертого шага.
4. На четвертом шаге необходимо найти максимум g³t³ = t₁ + t₂ = max при условиях:
   
   
   Решение четвертой вспомогательной программы запишется как
   
   
   откуда решение искомой квадратичной программы найдется в виде х³ = || 3/2, 1/2 || и