Введение в методы оптимизации

НИИ однотипных математических операций, называемых ите­ рациями, и обычно позволяют получать лишь приблилсенные решения. Многие методы используют аппарат частных производ­ ных оптимизируемой функции, а некоторые из них - и функ­ ций, с помощью которых задается множество ограничений. Такие методы называют методами первого порядка. К их числу относятся метод множителей Лагранжа, градиентный метод, метод проекции градиента, метод условного градиен­ та, метод возможных направлений и многие другие. Некоторые методы используют аппарат вторых частных производных оптимизируемой функции. Такие методы назы­ вают методами второго порядка. Использование вторых част­ ных производных в ряде случаев позволяет повысить эффек­ тивность вьгаислений. К числу наиболее распространенных методов второго порядка относится метод Ньютона [1]. Во многих задачах частные производные оптимизируе­ мой функции либо не существуют, либо их вычисление очень трудоемко. Для таких задач применяются методы, не исполь­ зующие аппарат частных производных. Эти методы называют методами нулевого порядка. К числу наиболее распростра­ ненных методов нулевого порядка относятся метод деформи­ руемого многогранника [3], метод покоординатного спуска и метод случайного поиска. Иногда задачу оптимизации с ограничениями целесооб­ разно свести к последовательности задач оптимизации на всем пространстве. Для таких случаев разработан метод штрафных функций, один из вариантов которого будет рас­ смотрен в настоящей главе. 58