При рассмотрении данного метода будет использоваться следующая теорема [1], [5]:

Теорема 2 (Критерий оптимальности) Пусть U - выпуклое множество, функция , - множество точек минимума J(u) на U. Тогда в любой точке необходимо выполняется неравенство

(35)

при всех , а в случае неравенство (35) превращается в равенство . Если, кроме того, J(u) выпукла на U, то условие (35) является достаточным для того, чтобы .

Пусть - очередное приближение к решению гладкой задачи выпуклого программирования: , - выпуклое замкнутое множество, - выпуклая дифференцируемая функция на . Причем . Тогда в окрестности точки функция представима в виде:

,

и линейная функция является приближением разности с точностью до величины в некоторой окрестности точки .

Поставим вспомогательную задачу минимизации на множестве линейной функции , т.е.

. (36)

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

В силу выпуклости допустимого множества, .

Величина из (37) в различных вариантах метода условного градиента вычисляется по-разному.

Опишем два способа определения :

1) , где найдено из условия наискорейшего спуска по направлению

,

где

.

2) В начале выполнения итерации (37) полагают , после чего проверяют условие:

. (38)

Если оно нарушается, то уменьшают (дробят) в 2 раза и повторно проверяют (38). Дробление производят до выполнения неравенства (38), после чего переходят к следующей итерации (37).

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

Отметим, что вспомогательная задача (36) является, вообще говоря, задачей нелинейного программирования. Укажем случай, когда поиск её решения не представляет затруднений [7], [8].

1. Допустимое множество задано линейными ограничениями и условием неотрицательности переменных. Тогда (9) – это задача линейного программирования, и её решение можно найти с помощью симплекс-метода [16].

2. Допустимое множество

является - мерным параллелепипедом. Тогда

(39)

3. Допустимое множество

является шаром радиуса с центром в точке . Тогда

.

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

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

.

Решение. В качестве начального приближения выберем, например, точку .

Шаг 1. Найдём градиент в точке .

Составим вспомогательную задачу

Это задача линейного программирования, её можно решить симплекс-методом [16]. Однако, допустимое множество – прямоугольник, поэтому проще воспользоваться соотношением (39), записав его для данной задачи:

Откуда следует .

Найдём первым способом. В данном случае

Из условия находим . Поэтому .

Вычислим очередное приближение по формуле (37):

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

Результаты вычислений на следующих шагах метода условного градиента приведены в таблице 5.

Таблица 5.

Окончательно

, .