Реализация рассмотренных алгоритмов значительно усложняется, если задача сводится к нахождению условного экстремума, т. е. экстремума, находящегося на границе допустимой области. Как показывает проведенный ранее анализ (см. гл. 2), такая ситуация может возникнуть при решении задачи оптимизации параметров теплообменных аппаратов. Например, функция Ψκ (стоимость конденсатора и системы водоснабжения) может принимать минимальные значения при максимально допустимых скоростях воды в трубах Х2 max.
Нахождение условного экстремума намного усложняется, если он находится на нелинейной границе. Такое положение, например, может иметь место при минимизации функции (2.25) при ограничении (2.26) или функции (2.42) при ограничении (2.43). Так как в реальной ситуации необходимо организовать поиск как внутри допустимой области, так и на границе, общий алгоритм поиска целесообразно представлять как совокупность соответствующих двух правил.
В настоящем параграфе рассматриваются правила движения к экстремуму (условному) вдоль границы. Можно выделить три основных подхода к задаче:
- выбор допустимого направления по алгоритму без ограничений и движение к экстремуму вдоль проекции этого вектора на границу;
- коррекция допустимого направления несколько внутрь допустимой области и смещение в другую точку на границе вследствие ее кривизны;
- учет нарушения границы при помощи штрафных функций и организация поиска, способствующего их уменьшению.
В нашем исследовании упор сделан на первых два принципа.
Метод проектируемых градиентов Розена [50, 51].
Метод относится к алгоритмам первого типа. Выполняется задача максимизации, когда имеют место условия (3.1) — (3.3). Рассматриваем момент, когда точка удовлетворяет q соотношениям из (3.3) как равенствам, т. е. лежит на пересечении q ограничений:
Отрицательность в (3.40) означает, что если соответствующее ограничение «несущественно», то градиент направлен от нее в допустимую область. Сходная процедура минимизации на ограничениях приведена в [53].
При описанном поиске на границе выпуклой области, ограниченной нелинейными соотношениями, как правило, будет иметь место нарушение границы при рабочем шаге, что часто нежелательно. В настоящее время разработаны алгоритмы, направленные на уменьшение числа таких нарушений [54]. Имеет место обобщенный подход к задаче программирования, откуда известные алгоритмы оптимизации вытекают как частный случай.
Метод допустимых направлений.
На каждом шаге выбирается подходящее возможное направление. Задача
Как указывалось, использование проективного метода связано с громоздкими вычислениями Pq. При разработке рабочих программ часто прибегают к упрощенным приемам проектирования допустимого вектора на границу. Если позволяют условия задачи, сначала вычисляют шаг вдоль допустимого вектора, а затем полученную точку проектируют на границу вдоль вектора градиента функции ограничения в этой точке. Помимо того, в зависимости от специфики задач рационально вводить упрощения или целесообразные отклонения от основной канвы алгоритма.
Например, для большинства рассмотренных в гл. 2 задач оптимизации параметров теплообменных аппаратов требуется при нахождении минимума критерия качества учитывать нелинейные ограничения на оптимизируемые переменные. Однако предварительные исследования показывают, что часто экстремум функции качества находится вблизи нелинейной границы допустимой области. Например, весьма вероятно, что при параметрах, соответствующих минимуму функции цели Фк, функция ограничений N достигает верхнего предела Nmax, то же можно сказать и о паре функции Ψρ и ΔΡx. В этих случаях при поиске нужно стремиться по возможности быстрее приблизиться к нелинейной границе.
При поиске на ограничениях существенными являются три момента: 1) нарушение границы (т. е. попадание в запретную область); 2) возврат на границу и 3) движение по границе в направлении уменьшения (или увеличения при максимизации) функции качества.
Попадание в запретную область опасно в случае, когда производится оптимизация (управление) реального объекта и нарушение границ может привести, например, к аварии. В рассматриваемом случае наибольший интерес представляет процедура возврата на границу, поскольку возврат по существу может быть и шагом по границе в сторону экстремума.
Предлагается следующий алгоритм [55]. Ставится задача
(3.50)
При поиске в области допустимых значений параметров шаг делается в направлении градиента в данной точке. Величина шага выбирается в зависимости от удаленности точки от границы допустимой области. В частности, на первом шаге, когда нет достаточной информации, пропорциональный множитель вычисляется по выражению
3.2.
Рис. 3.4
Блок-схема поиска при наличии ограничений на оптимизируемые параметры
Таким образом, описанная процедура эквивалентна нахождению корня уравнения d(λ)=Ο модифицированным методом Ньютона, где производные заменены конечными разностями. Движение, согласно (3.58) и (3.61), продолжается до тех пор, пока не станет меньше, чем заданное ε→0.
Получив точку на границе, вновь определяется gradφ(X) и делается первый шаг произвольной длины в этом направлении. Если условие (3.56) выполняется, осуществляется спуск к границе согласно (3.61).
Следует отметить, что если функция ограничений не выпукла, то спуск вдоль градиента может увести от границы. Признаком этого является условие T>0. В этом случае необходим возврат точки на границу. Корректировка шага тогда осуществляется по правилу
(3.62)
При наличии двух точек на границе возможно более эффективное движение к экстремуму. Коррекцию λ в этом случае можно производить с учетом знака скалярного произведения градиентов в этих точках, а также степени приращения градиента и функции качества.
Поиск заканчивается, когда последний рабочий шаг будет меньше заданной величины ε:
(3-63)
Блок-схема программы на ЭЦВМ «М-222» по приведенному выше алгоритму представлена на рис. 3.4.
В АЛГОЛ-программе алгоритма в процедуры выделены вычисления функции качества (fun) и функции ограничений (con), а также вычисления их градиентов (gf и gc соответственно). В одну процедуру (arg) объединено вычисление приращения вектора оптимизируемых параметров. В этой процедуре осуществляется также спуск попавшей в запретную зону точки на линейные границы.
