ПОИСК Статьи Рисунки Таблицы Минимизация функций при наличии линейных ограничений из "Оптимизация химико-технологических процессов" В процессе поиска некоторые из ограничений — неравенства (IV,99) — могут стать строгими равенствами. Эти ограничения будем называть активными. Обозначим через т) линейное многообразие, образованное пересечением д гиперплоскостей, из которых т являются гиперплоскостями, описанными уравнениями (IV, 98), а (г/ — т) — гиперплоскостями, соответствующими ( — т) активным ограничениям (IV, 99). Совокупность т ограничений (IV, 98) и всех активных ограничений в данной точке списка будем называть базисом. [c.150] Во время поиска изображающая точка может двигаться в поисковом пространстве внутри некоторого многообразия ( т), может входить на новые гиперплоскости, соответствующие активным ограничениям (увеличение базиса), или наоборот, сходить с некоторой гиперплоскости (уменьшение базиса). В качестве примера на рис. 25 изображена поисковая траектория в трехмерном пространстве при наличии одного ограничения типа неравенства (IV, 99), причем допустимая область находится ниже плоскости 1. Поиск начинается в точке А. Участок траектории АВ лежит в полном пространстве (базис пустой). В точке В поисковая траектория пересекает плоскость 1 и в дальнейшем лежит в этой плоскости. Здесь уже имеется одно активное ограничение (базис состоит из уравнения плоскости 1). В точке С поисковая траектория сходит с плоскости 1 и далее участок траектории СО уже лежит в полном пространстве. Отсюда ясно, что любой алгоритм, осуществляемый в соответствии с формулами (1,39), (1,41), должен содержать следующие основные алгоритмы. [c.150] Направление в данном случае является проекцией градиента функции на пересечение гиперповерхностей (IV, 100) и дает направление наиекорейшего убывания функции в многообразии Lg. [c.151] Формула (IV, 102) лежит в основе метода проектирования градиента [88. с. 134— 135], Ясно, что по скорости сходимости этот метод эквивалентен методам градиента и наиекорейшего спуска для случая отсутствия ограничений. Поэтому методы переменной метрики, дающие большую скорость сходимости, интересно распространить на данный случай. [c.151] Предположим вначале, что матрица А [см. выражение (III, 2)] известна и имеет ранг п. Поставим следующую задачу — пусть координаты точки удовлетворяют уравнениям (IV. 100) необходимо найти точку минимума функции (III, 2) в многообразии Lg. [c.151] Для 1- д это равенство верно в соответствии с условиями (IV, 117), а для г = = д оно легко проверяется. [c.152] Рассмотрим теперь ряд методов минимизации функций многих переменных при наличии линейных ограничений. [c.152] Отсюда, вектор р, 1 = —будет ортогонален векторам Пу, (/= 1, ). Следовательно, все точки полупрямой, начинающейся в точке и проходящей вдоль вектора р +1, будут принадлежать В частности Ьд. Таким образом, все точки XI, (1 = О, 1,. ..) лежат в Ьд. Матрица Я может быть определена с помощью формулы (IV, 116). [c.153] Направления р строятся с помощью формулы (1,41), в которой Я удовлетворяют уравнению (11,32), следовательно, эти направления будут сопряженными. С другой стороны, как мы показали, все векторы р будут лежать в многообразии Ьд размерности п — д. Отсюда (см. с. 82), минимум в многообразии Ьд будет найден за число шагов, не большее, чем п — д. В дальнейшем матрицы Н-, которые обеспечивают движение в Ьд, будем обозначать через Я . Нижний индекс здесь по-прежнему обозначает номер итерации, а верхний — число линейных ограничений, образующих линейное многообразие Ьд. [c.153] Рассмотрим алгоритмы изменения матрицы Н при увеличении и уменьшении числа активных ограничений. [c.154] Отметим, что для преобразования матриц Я может быть использована любая из формул семейства Хуанга (111,95), а не только преобразование ОРР (см. работу Гольдфарба [89]). Остановимся теперь на недостатках метода Гольдфарба. Пусть до точки лг/, (см. рис. 25. точка В) поиск шел во всем пространстве, а начиная с этой точки он должен пойти в многообразии 1 . Матрица Я , полученная в этой точке, удовлетворяет уравнению (11,32). Ясно, что матрица Я . полученная с помощью выражения (IV, 130), не будет решением системы (II, 32), следовательно, информация. [c.154] В данном методе матрицы Н-, пересчитываются отдельно. Матрица Н. [c.155] У этого подхода имеется еще один недостаток. В его основе лежит формула Гринштадта, которая, как показывает опыт решения задач безусловной минимизации, не дает хороших результатов [27]. Интересно обобщить этот подход на более эффективные методы, типа ОРР, ВРОЗ. Для этого так же как и при выводе квазиньютоновских методов безусловной минимизации 1-го рода необходимо заменить критерий (111,64) нормой Фробениуса взвешенной суммы (111,76). В этом случае, применяя подход, использованный при решении задачи (111,68), можно получить выражение для Я/+1. [c.156] У рассмотренных подходов имеется один недостаток — на каждом шаге приходится решать систему линейных уравнений (IV, 135), поэтому может оказаться целесообразным использовать их только в случае, когда число активных ограничений в каждой точке будет мало, а следовательно, будет мала размерность системы линейных уравнений (IV,135). Правда, указанный недостаток имеет и положительную сторону. Действительно, решение системы (IV, 135) на каждом шаге гарантирует ортогональность векторов рх нормалям к гиперплоскостям, входящим в базис, что не дает возможности накапливаться ошибкам округления и приводить к нарушению этой ортогональности, как это может происходить при применении методов Гольдфарба и Муртага — Саджента. [c.156] Вернуться к основной статье