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

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

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

Методы безусловной оптимизации подразделяются на методы 0-го, 1-го и 2-го порядка. Для реализации методов 0-го порядка требуется организовать расчет только самой целевой функции, в методах 1-го порядка кроме расчета целевой функции необходимо еще рассчитывать градиент от целевой функции по поисковым параметрам g (X)=grad_xJ(X)=P_xJ(X) в заданной точке X. В методах 2-го порядка кроме целевой функции и градиента требуется рассчитывать еще и матрицу вторых производных от целевой функции по поисковым параметрам . Методы более высокого порядка на практике не используются в силу большой сложности реализации таких методов и возникновением неоднозначности в выборе направления поиска минимума целевой функции.

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

В основе почти всех методов безусловной оптимизации лежит процедура поиска минимума целевой функции в заданном направлении P_k в n - мерном пространстве поисковых параметров X:

X_k+1 = X_k +a_k P_k (1.1.1)

a_k: min_a J(X_k +a P_k), (1.1.2)

здесь k - номер текущего поиска (итерации), a_k - длина шага вдоль поискового направления P_k до достижения ближайшего минимума целевой функции, X_k+1 - новая текущая поисковая точка.

В разделе 1.2 приведены основные методы одномерной оптимизации, которые позволяют реализовать процедуру (1.1.2).

Для лучшего понимания геометрической интерпретации излагаемых ниже методов, рассмотрим свойства квадратичной целевой функции. Хотя реально большинство целевых функций не квадратично, основные свойства квадратичной функции позволяют понять суть многих методов оптимизации. Квадратичная целевая функция может быть описана следующим образом в виде разложения Тейлора относительно текущей точки X_k+1:

J(X)=J(X_k)+ g ^T(X_k)×(X - X_k)+(X - X_k)^T×G×(X - X_k)/2. (1.1.3)

Квадратичная целевая функция имеет один минимум в точке X^*, если матрица вторых производных G (матрица Гессе) положительно определена. В точке минимума X^* градиент от целевой функции обращается в 0, т.е.

g (X^*)=0. (1.1.4)

Тогда выражение (1.1.3) можно переписать относительно точки X^* -

J(X)=J(X^*)+(X - X^*)^T×G×(X - X^*)/2. (1.1.5)

Градиент от функции J в любой точке X определится как

g (X)=G×(X - X^*). (1.1.6)

Сама матрица Гессе представляет в этом случае матрицу констант. Если представить рельеф целевой функции в двумерном случае в виде набора линий уровня, то он будет иметь вид вложенных друг в друга эллипсов, как это изображено на Рис.1.1.1.

Рис.1.1.1

Линии уровня и собственные вектора квадратичной функции

Собственные вектора Q_i и собственные значения l_i матрицы Гессе удовлетворяют условию:

G× Q_i =l_i×× Q_i, i=1..n. (1.1.6)

Собственные вектора Q_i определяют направления осей квадратичной функции, а собственные значения l_i - значения вторых производных вдоль этих векторов.

Направление градиента g (X) указывает на направление наиболее быстрого возрастания функции и это направление всегда ортогонально линии уровня, проходящей через точку X (точка А на рис.1.1.1). Точка минимума функции вдоль заданного направления P соответствует первой точке касания линии проведенной вдоль направления P с какой-либо линией уровня (точка B на рис.1.1.1).

Дата добавления: 2015-11-14