Классификация задач и методов оптимизации

Для решения задач оптимизации существует огромное количество различных математических методов. Выбор наилучшего среди них является чрезвычайно труднодостижимой задачей при минимизации широкого класса функций. Эффективность того или иного метода определяется постановкой задачи, сложностью вычисления функции и ее производных, поведением функции и т. д. в качестве критерия сравнения методов в рассматриваемом случае целесообразно использовать объем вычислений значений функции качества в процессе решения задачи. Это объясняется тем, что вычисление целевой функции (функции качества) связано с обращением к численной модели и занимает основное время при решении задачи.

Один из способов классификации методов оптимизации состоит в отнесении их оптимизационным задачам, для решения которых они предназначены.

Методы однокритериальной оптимизации направлены на поиск оптимума единственной целевой функции. Методы многокритериальной оптимизации обеспечивают процедуры принятия решения при многих критериях, в частности сводят векторную задачу к последовательности скалярных задач.

Методы локальной оптимизации обеспечивают отыскание одного локального минимума, а методы глобальной оптимизации направлены на установление всех локальных минимумов или наилучшего из них.

Различают также методы непрерывной и дискретной (в том числе комбинаторной) оптимизации, методы линейного и нелинейного программирования, методы условной и безусловной оптимизации, методы одномерной оптимизации и методы оптимизации функций многих переменных, и т.д., и т.п.

По типу информации о производных, требуемой для организации процесса оптимизации, методы подразделяются на методы:

- нулевого порядка (прямые), требующие только вычисления значений функции в точках пространства оптимизации и не требующие аналитического вида производных,

- первого порядка (градиентные), требующие кроме значений функции в точке еще и аналитического вида производных первого порядка для вычисления градиента,

- второго порядка (ньютоновские), для работы, которых требуются еще и производные второго порядка.

известны также несколько алгоритмов третьего порядка, но они не применяются при практической оптимизации.

различают также методы прямого поиска, методы линейной и квад-ратичной аппроксимации целевой функции (называемые также методами спуска). Принято считать эту классификацию эквивалентной предыдущей, но имеются и отличия.

По степени математической обоснованности методы делят на: эвристические и рациональные. Последние ориентированы на некоторую математическую модель оптимизируемой функции (например, предполагают ее непрерывно дифференцируемой) и обычно обладают строгими доказательствами сходимости к стационарной точке (критериями останова таких методов обычно является выполнение необходимых условий существования экстремума в данной точке) и оценками скорости сходимости. Вопрос о том, насколько реальная задача соответствует используемой алгоритмом модели, остается на совести человека, использующего данный метод. Эвристические алгоритмы обычно не используют никакой модели целевой функции, а основывают процесс оптимизации на формализованной человеческой интуиции и других нестрогих, но разумных предположениях. Строгие доказательства сходимости и теоретические оценки скорости сходимости обычно отсутствуют. критериями останова являются обычно такие условия как малое приращение аргумента или значения функции на нескольких последовательных шагах, что характерно для точки минимума, но не только для нее. применение этих методов обосновывается только тем, что их многократное использование в прошлом обычно приводило к успеху. зато такие алгоритмы можно применять к любой функция (хотя и с разной степенью успеха), не заботясь о доказательстве соответствия этой функции некоторой теоретической модели. большинство алгоритмов сочетают в той или иной степени оба эти подхода.

Методы оптимизации подразделяют также на детерминированные и стохастические. Стохастические алгоритмы используют элемент случайности при выборе направления или длины шага в процессе оптимизации. Отметим, что стохастические методы оптимизации применяются к детерминированным задачам, т.е. случайность намеренно вводится в алгоритм для того, чтобы обеспечить достижение цели.