Файл: Методы оптимизации в статистических задачах управления..pdf

где параметр р > О характеризует размер шага. Значение шага выбирается экспериментально. В алгоритме (274) существенное значение имеет выпуклость функций Ft (х), 1 = 0, 1, 2, . . ., т. В общем случае метод может не иметь сходимости. Иногда удается задачу с невыуклыми функциями Ft (х) свести к задаче с выпук­ лыми функциями путем эквивалентной замены исходных огра­ ничений:

выпуклости Fi {х) = ф; (F{ (х)).

Другой вариант градиентного метода был предложен Удзава [115]. В этом методе используется условие оптимальности (271), исходя из которого можно определять оптимальное решение как

х+ = х(А+).

Метод Удзава удобно применять, когда с помощью аналити­ ческих методов нетрудно вычислить минимум значения L (х, А) по X в функции параметра А, т. е. функцию

L (X (А), А) = min L (х, А).

X

Значение А+ определяется как предел решения системы диф­ ференциальных уравнений:

А+ = Нт АО х+ = х (А+).

і-> со

117

Реализация метода по указанной процедуре оказывается слож­ нее, чем по процедуре (274), так как в методе Удзава на каждом шаге необходимо решать задачу максимизации функции L (х, К1) по х. Однако этот метод не требует условия выпуклости функций F{ (х) (і = 0, 1, 2, . . ., т). Аналогичный метод предлагался [84].

Следует обратить внимание, что в работе Удзава [115] доказы­ вается сходимость дискретных методов только при достаточно малом значении параметра^.

Метод Эрроу-Гурвица и метод Удзава являются по существу градиентными методами определения седловой точки для функции Лагранжа L (х, X).

В работе Розена [144] предлагается метод проектирования градиентов, который обобщает градиентный метод на случай минимизации функций при наличии ограничений. При изложении метода мы будем следовать в основном работам [67, 72]. Рассмо­ трим вначале случай ограничения типа равенства. Пусть требуется минимизировать F0 (х):

Зададимся точкой начального приближения х°, причем вполне возможно, что ф (х°) ф 0. Обозначим через 6л; приращение аргу­ мента. Линейная часть приращения функций F0 (х) и <р (х) будет иметь вид:

і = 1, 2 , . . ., т.

Наложим ограничения на квадрат модуля вектора 6х и опреде­ лим вектор 6х из условия минимума линейного приращения функ­ ции F о (х) при ограничении в виде заданной линейной части при­ ращения вектора ф:

118

—УФ (л:0), где 0 < у < 1 . Итак, будем определять вектор бх из условия

Применяя метод множителей Лагранжа, получим решение этой экстремальной задачи в виде

Е — единичная матрица.

Параметр t в выражении (278) определяется из условия фикси­ рованной длины вектора бх:

(бх)* бх = с.

Приращение бхх называется градиентной составляющей при­ ращения, б2х — компенсационной составляющей приращения. Эти названия объясняются тем, что справедливы равенства:

y46jX = 0, Лб2х = бф.

Пользуясь выражениями (279) и (280), легко показать, что составляющие приращения бх взаимно ортогональны:

•

1 Приращение б2х направлено на уменьшение расхождения в выполнении ограничений (276), а бхх смещает точку в сторону уменьшения функции F 0 (х). Наличие составляющей б2х может привести к увеличению значения функции Е 0 при конечных зна­ чениях параметра t, так что в общем случае метод не является монотонным.

В процессе выполнения итерации необходимо задаваться зна­ чениями t и бф. Вначале рекомендуется [72] при t = 0 прибли­ зиться к ограничению ф (х) = 0, не добиваясь точного его выпол-

119

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

Если наряду с ограничениями типа равенства (276) имеются ограничения в виде системы неравенств

то реализация метода проектирования градиентов несколько усложняется. В этом случае, задавшись, как и прежде, точкой начального приближения х°, вычисляем градиентную состав­ ляющую 8^ :

будет стремиться приблизиться или еще более углубиться в область Ф3 (х) < 0. Поэтому на этом шаге итерации ограничение s будем пока игнорировать. Если бFs > 0, то, исключая s-e ограничение из системы (281), необходимо подключить к системе (276) огра­

ничение

Fs (х) = 0.

После того как будут проанализированы все неравенства, необходимо сделать шаг, ориентируясь на новую дополненную систему ограничений (276) без учета оставшихся ограничений типа неравенства.

Аналогичным образом проводятся следующие итерации. Не­ сколько последних итераций нужно осуществлять, ориентируясь только на выполнение всех требуемых ограничений (276) и (281).

8. Метод возможных направлений

Метод проектирования градиентов хорошо приспособлен для ограничений типа равенств, но его реализация усложняется при наличии ограничений в виде неравенств. В 1959 г. Г. Збйтендейком был разработан метод возможных направлений, который^близок

120

по идее к градиентному методу, но лучше приспособлен к случаю наличия ограничений типа равенства [36]. Независимо этот метод был разработан С. И. Зуховицким [37].

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

при наличии системы нелинейных ограничений

Нетрудно показать, что общая задача нелинейного программи­ рования (255), (256) легко может быть сведена к канонической форме (282), (283). Действительно, задача (255), (256) эквива­ лентна задаче

Действительно, предположим противное, т. е. что существует

то точка х+ не есть оптимальная для задачи (284), (285). Это про­

тиворечит исходному предположению об оптимальности х+ для задачи (284), (285). Противоречие доказывает факт оптималь­ ности х+ для задачи (255), (256).

Совершенно аналогичным способом доказывается, что если х+

Но задача (284), (285) является частным случаем задачи в ка­ нонической форме (282), (283). Следовательно, любая задача нелинейного программирования может быть сведена к канониче­ ской форме путем увеличения размерности пространства незави­ симой переменной на единицу.

Основной алгоритм метода возможных направлений состоит в следующем. Задаемся точкой начального приближения х°,

121