Будем рассматривать задачу

, (30)

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

Непосредственное применение градиентного метода в случае может привести к затруднениям, так как точка при каком-то может не принадлежать . Однако эту трудность можно преодолеть, если полученную точку при каждом проектировать на множество . В результате мы придем к так называемому методу проекции градиента [7].

А именно, пусть - некоторое начальное приближение. Далее будем строить последовательность по правилу

, (31)

где - положительная величина. Если - выпуклое замкнутое множество и способ выбора в (31) задан, то последовательность будет однозначно определяться условием (31). В частности, при метод (31) превратится в градиентный метод.

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

В зависимости от способа выбора в (31) можно получить различные варианты метода проекции градиента [1], [13]-[15]. Укажем несколько наиболее употребительных на практике способов выбора .

1) Введем функцию одной переменной , , и определим из условий

. (32)

Очевидно, при метод (31), (32) превратится в метод наискорейшего спуска.

2) Иногда приходится довольствоваться нахождением какого-либо , обеспечивающего условие монотонности: Для этого обычно выбирают какую-либо постоянную и в методе (31) на каждой итерации полагают , а затем проверяют условие монотонности и при необходимости дробят величину , добиваясь выполнения условия монотонности.

3) Если функция принадлежит и константа Липшица для градиента известна, то в (31) в качестве можно взять любое число, удовлетворяющее условиям

, (33)

где , - положительные числа, являющиеся параметрами метода.

Заметим, что описанные здесь варианты метода (31) при переходят в соответствующие варианты градиентного метода.

Заметим, что в методе (31) на каждой итерации, кроме выбора параметра , нужно еще проектировать точку на множество . Однако задача отыскания проекции некоторой точки на множество сама, в свою очередь, является задачей минимизации функции или на этом множестве и далеко не всегда просто решается. Поэтому методом проекции градиента обычно пользуются лишь в тех случаях, когда проекция точки на множестве легко определяется. Например, когда множество представляет собой шар в , параллелепипед, гиперплоскость, полупространство или положительный октант, задача проектирования точки решается просто и в явном виде, и реализация каждой итерации метода проекции градиента в этом случае не вызывает особых затруднений. Если же задача проектирования для своего решения в свою очередь требует применения тех или иных итерационных методов, то эффективность метода проекции градиента, вообще говоря, значительно снижается.

Пример 4. Решить следующую задачу нелинейного программирования

,

методом проекции градиента, завершая вычисления при выполнении одного из условий

, .

Решение. В качестве начального приближения возьмём, например, точку . Градиент удовлетворяет условию Липшица: с константой , так как

.

Поэтому в формуле для последующего приближения

, (34)

где , можно положить

.,

(т. е. шаг удовлетворяет неравенству (33)). Например, положим .

Шаг 1. Так как , то по формуле (34) находим

Точка , так как . Поэтому . Требуемая точность не достигнута, так как .

Шаг 2. Как на предыдущем шаге находим , а затем

Точка , так как

.

Множество представляет собой замкнутый шар радиуса с центром в точке в пространстве . По следующей формуле находим проекцию найденной точки на заданное множество:

.

Требуемая точность не достигнута, так как

.

Результаты остальных шагов метода проекции градиента приведены в таблице 4.

Таблица 4.

Из таблицы следует, что , .

Отметим, что точное решение рассматриваемой задачи , .