ПОИСК Статьи Рисунки Таблицы Методы минимизации функций при наличии линейных ограничений из "Моделирование кинетики гетерогенных каталитических процессов" Способ расчета вектора направления специфичен для каждого метода. [c.179] Интегрируя систему дифференциальных уравнений ( 11,10), получим траекторию, касательная к которой в каждой точке обладает заданным свойством. Например, для непрерывного аналога градиентного метода касательная к траектории в каждой точке совпадает с вектором градиента. Если в процессе поиска изменяется способ вычисления вектора я (0), траектория поиска состоит из нескольких участков. [c.179] Следующим признаком классификации является порядок производных, используемых в алгоритме поиска. Обычно применяются методы нулевого, первого и второго порядков. [c.179] Методы различаются скоростью сходимости к минимуму. Так, метод антиградиента имеет линейную сходимость, метод минимизации Ньютона — квадратичную. [c.180] Можно также подразделять методы на детерминированные и случайные, одношаговые и многошаговые и т. д. В многошаговых методах для расчета направления на данной итерации s используется информация, полученная за несколько предыдущих итераций. Один и тот же метод может обладать несколькими из перечисленных классификационных признаков. [c.180] В методах поиска нулевого порядка не требуются вычисления производных и применяются только значения функций. Специально ориелтированы на минимизацию овражных функций метод конфигураций [122, с. 202] и метод вращающихся координат [125, с. 107]. [c.180] Примерами итерационных методов поиска первого порядка с линейной сходимостью является метод антиградиента и его модификация — наискорейший спуск [121, с. 189]. [c.180] Здесь шаг хг выбран так, чтобы достигнуть минимума функции S (0) на направлении s. В полученной точке снова рассчитываются градиент и матррща вторых производных и вычисляется новое приращение Д0 + и т. д. до нахождения минимума функции 5 (0). [c.180] Рассмотрим случай, когда собственное значение положительно п гора ДО меньше Хт, т. е. [c.181] Величина Л получена из Л заменой отрицательных собственных чисел на их абсолютные значения. Прп такой замене матрица (li ) становится положительно-определенной, а направление второго порядка составляет острый угол с вектором антиградиента, что обеспечивает убывание функции на каждой итерации. [c.181] Сравнительные расчеты, проведенные на тестовых функциях, нока. зывают, что метод второго порядка намного успешнее справляется с оврагами , чем методы нулевого порядка и методы первого порядка с линейной сходимостью (см., наиример, [125, с. 112]). [c.181] Недостатком метода второго порядка является не только необходимость вычисления матрицы вторых производных, но и обязательная проверка ртой матрицы на положительную определенность. Поэтому интересны методы, которые обладают сходимостью, близкой к квадратичной, но не требуют вычисления вторых производных. [c.181] Таким образом, замена матрицы вторых производных матрицей МНО состоит в пренебрежении матрицей Q в формуле (VII,21). В отличие от матрицы вторых производных матрица МНО всегда (что очень важно) положительно-полуонределенна [111, с. 31]. [c.181] Здесь Hi — матрица размерностью т X т G — вектор градиента в точке 0 . Если Hi — единичная матрица, то (VII,22) дает направление антиградиента если Hi — матрица, обратная к матрице вторых производных, то (VII,22) определяет направление второго порядка и т. д. [c.181] Свойства данного преобразования таковы, что матрица Hi всегда положительно-определенна и при приближении к минимуму стремится к матрице, обратной к матрице вторых производных функций S. [c.182] Методы ДФП и МНО относятся к итерационным методам первого порядка со сходимостью, близкой к квадратичной. Методы минимизации Ньютона, МНО и ДФП минимизируют функцию Розенброка (VII,2) за 16—20 итераций при применении одинаковой процедуры поиска минимума па направлении. Это подтверждает, что в отношении упомянутой функции три указанных метода одинаково эффективны. Аналогичные результаты получены и для других тестовых функций. В отличие от метода второго порядка и МНО метод ДФП является многошаговым, поскольку при вычислении текущего направления используются сведения о предыдущих. Поэтому в матрице И накапливаются ошибки округления. Чтобы избежать этого и других отклонений от нормальной работы алгоритма ДФП, предложен ряд приемов, например вычисления с двойной точностью, масштабирование переменных, периодический возврат к единичной матрхще п др. [130]. [c.182] Комбинированные алгоритмы. В ряде случаев, когда поиск минимума одним ка1 им-либо методом сильно замедляется вдали от минимума функции, можно применять комбинированные алгоритмы. При этом в каждой точке вычисляются два направления, например метода наискорейшего спуска и метода второго порядка. Затем ищутся минимумы на каждом направлении. За следующую начальную точку выбирается наиболее глубокий минимум по направлению. В работе [131] используется два вида направлений первого порядка с линейной сходимостью и направление МНО. Естественно, что комбинировать проще всего одношаговые методы. [c.182] Эту систему можно интегрировать численными методами на ЭВМ. Существуют методы, в которых зависимость правой части системы (VII,23) от параметров учитывается приближенно. Так, в работе [132] для непрерывного аналога метода антиградиента правая часть разлагается в ряд, и траектория системы (VI 1,23) заменяется участками траектории некоторой аппроксимирующей системы. [c.182] Номер I выбирается так, чтобы на данном этапе Сг была максимальной по модулю компонентной градиента 8 (0). Параметры Сг — это обнуленные компоненты градиента, С/ — параметры, которые предстоит обнулить. Смысл условия (VI 1,24) состоит в том, что /-ая компонента градиента убывала по абсолютной величине. Условие (VII,25) обеспечивает убывание или сохранение абсолютных величин других необнуленных компонент градиента, условие (VII,26) — равенство нулю уже ранее обнуленных компонент. Метод показал хорошие результаты на тестовых функциях, однако вычисления по нему весьма трудоемки. [c.183] Двусторонние ограничения, происхождение которых обсуждено в начале данной главы, записываются в виде пары неравенств (VII,29). Ранее [124, с. 59] был описан ряд методов решения более общей задачи с нелинейными ограничениями типа равенств и неравенств, такие, как метод проектирования градиента, метод исключения зависимых переменных (ИЗП) первого и второго порядков, метод штрафов и др. Все эти результаты легко переносятся на слз чай линейных ограничений. [c.184] Вернуться к основной статье