ПОИСК Статьи Рисунки Таблицы Общая формулировка задачи оптимизации и характеристика методов ее решения из "Оптимизация химико-технологических процессов" Методы решения задач минимизации можно разделить (в известной степени условно) на две группы (рис. 2). К первой относятся так называемые прямые методы, базирующиеся на непосредственном сравнении значений функции в соседних точках, ко второй — непрямые методы, при использовании которых положение минимума определяется с помощью соответствующего необходимого условия. В дальнейшем всюду -речь будет идти лишь о прямых методах решения задач минимизации, т. е. о методах спуска . [c.15] Таким образом, выполнение одной ( -той) итерации (или шага) в конкретном алгоритме спуска заключается в определении направления спуска Рг и точки на данном направлении. [c.16] Структуру рассматриваемых далее методов безусловной минимизации можно представить следующей схемой (рис. 4). [c.16] Выбирается некоторая начальная точка Хо и положительно определенная (п X гг)-матрица Яо- Выполняется расчет градиента минимизируемой функции в точке х д (хо). [c.16] В общем случае вектор направления р является некоторой явной функцией точки Х , предыдущих точек х г, , векторов градиентов Яг-ь минимизируемой функции / и матриц О,, Gi l ее вторых производных, вычисленных в точках Х , л г.ь. .., т. е. [c.16] В выражении (I, 42) зависимость р от некоторых групп переменных, например (5 , Ог ,,. .., может отсутствовать. [c.16] В зависимости от максимального порядка производных, входящих в выражение (1,42), алгоритмы минимизации относятся соответственно к методам нулевого, первого и второго порядков. Например, в методах нулевого порядка предусматривается такое построение последовательности р , при котором используется лишь информация о значениях минимизируемой функции в различных точках. [c.17] Существуют алгоритмы минимизации (нулевого порядка), такие как симплекс- и комплекс-методы, в которых отсутствует построение направлений спуска они достаточно хорошо освещены в литературе [8, 9] и здесь не приводятся метод Пауэлла, в котором используется система сопряженных направлений, рассматривается в. работе [10], а также [11, с. 121—125]. [c.17] В методах первого порядка вектор направления обычно определяется из соотношения (1,41). В этом случае последовательность матриц Я определяется характером применяемого метода, причем в формировании Я участвуют производные функции / (х) не выше первого порядка. Методы второго порядка допускают зависимость Я,-в выражении (I, 42) от вторых частных производных минимизируемой функции. Например, классический метод Ньютона соответствует выбору Не = т. е. [c.17] Достаточным условием выполнения этого условия является положительная определенность матриц Я , в этом заключается неотъемлемое свойство целого ряда обсуждаемых ниже алгоритмов. [c.17] Рассчитываются точка Хг+1 = Х + и (в градиентных методах) вектор ЯгЧ1 = Я (- г+т), а затем формируется матрица В зависимости от результата проверки условия остановки работа алгоритма либо прекращается (в этом случае с требуемой точностью является оптимальной точкой), либо осуществляется переход к шагу 1 1 + 1). Условием окончания работы алгоритма обычно является неравенство Яг+1 е, где е 0 — заданное число, или I f (хг+1) — / (х ) е. Используются также и другие условия окончания, например х,+1 — Х ё вместе с 1й +1 е, и т. д. [c.18] Точки X перехода на следующее направление определяются с помощью условия (1,47), т. е. а,- = а. [c.18] Характерная особенность этого метода — простота реализации однако общеизвестны и его недостатки метод является линейным — даже при минимизации квадратичной функции процесс поиска ее минимума теоретически бесконечен для функций с сильно вытянутыми линиями уровня (изолиниями) процесс поиска носит явно выраженный зигзагообразный характер и дает слабое продвижение к минимуму точное определение минимума практически нереально. [c.18] Среди алгоритмов решения задач с ограничениями прежде всего следует отметить методы последовательной безусловной минимизации (см. главу IV). Возросший интерес к этим методам связан, по-видимому, с появлением в последнее десятилетие достаточно эффективных квадратичных методов безусловной минимизации. Суть методов последовательной безусловной минимизации, как известно, заключается в построении на основе минимизируемой функции и функций ограничений некоторого семейства функций, зависящих от параметров. Определяется безусловный минимум (или экстремум) каждой функции этого семейства при фиксированных значениях параметров. Оказывается, что при некоторых условиях последовательность полученных решений задач без ограничений сходится к решению исходной задачи при определенном изменении параметров семейства функций. [c.18] Вследствие большой размерности, трудоемкости задач оптимизации ХТС требуется высокая эффективность перечисленных основных алгоритмов поисковых методов. Рассмотрим их с этой, точки зрения. [c.19] Известно, что расчет критерия оптимизации сводится к расчету статического режима системы [3, с. 13]. Повышение эффективности алгоритмов расчета статических режимов процессов достигается применением эффективных методов решения систем нелинейных уравнений, а также использованием методов структурного анализа [1, 3]. Методы решения систем нелинейных уравнений будут подробно рассмотрены в главе П. [c.19] Важнейшую роль в повышении эффективности поисковых методов играют собственно алгоритмы стратегии поиска (алгоритмы 3, 4, 5). Принципам построения эффективных алгоритмов стратегии поиска уделяется в данной книге основное внимание. Главными критериями оценки эффективности методов минимизации являются необходимая для реализации и работы алгоритма память вычислительной машины, быстродействие алгоритма и надежность определения минимума. [c.19] Память, необходимая для реализации алгоритма, зависит от типа используемой ЭВМ, избранного алгоритмического языка программирования, от искусства программирования. Память, необходимая для работы алгоритма определяется, в основном, длиной используемых массивов, зависящих от п — размерности задачи. [c.19] В заключение следует отметить, что в книге рассматриваются только детерминированные локальные методы поиска. Методам случайного поиска посвящена книга [12 ]. Методы глобального поиска рассматриваются в работе [13, с. 491—525]. Таким образом, в дальнейшем предполагается, что либо множество 5 выпукло и / (х) выпукла на 5, т. е. / (х) имеет в 5 единственный минимум, либо начальное приближение выбрано достаточно близко от минимума. [c.20] Вернуться к основной статье