Проблема глобальной оптимизации

В настоящее время не существует строгих методов поиска глобальной оптимизации, т.е. методов поиска минимального минимума из всех возможных минимумов заданной целевой функции. Обычно такая задача решается многократным использованием метода локальной оптимизации с различных начальных поисковых точек и определением оптимальной точки, где достигается минимальное из всех найденных минимальных значений целевой функции. Начальные поисковые точки можно выбирать или из каких-то физических соображений или случайным образом.

Можно, однако, использовать свойство методов оптимизации с переменной метрикой состоящее в том, что вблизи оптимальной точки целевую функцию можно представить в виде квадратичной аппроксимации вида (1.5.19). Тогда можно искать другой ближайший минимум целевой функции вдоль основных осей квадратичной аппроксимации, а начинать надо с оси с наибольшим значением второй производной, т.е. оси с наибольшим собственным значением l_i собственного вектора Q _i матрицы H_k^-1 (см.(1.1.6)). Это ось или вектор Q _i указывает направление наиболее быстрого возрастания целевой функции. Если пройти вдоль этого направления, то можно с достаточно большой вероятностью и наиболее быстро пройти перевал и оказаться в области притяжения ближайшего, но уже другого, локального минимума. Начальный шаг вдоль этого направления можно приближенно оценить исходя из квадратичной аппроксимации по формуле:

(1.7.1)

С точки притяжения к новому минимуму осуществляем поиск локального минимума одним из методов с переменной метрикой и т.д.. В конце каждого m-ного локального поиска следует запоминать найденные оптимальные значения вектора поисковых параметров X _m^* и найденное приближение матрице Гессе H_m^-1*. В процессе поиска следует проверять текущее значение вектора поисковых параметров X _k на его принадлежность к области притяжения найденных ранее локальных минимумов, чтобы исключить зацикливание алгоритма. Под областью притяжения можно принимать те значения вектора X _k, которые удовлетворяют следующему неравенству:

J(X _m⁰)-J(X _m^*)> (X _k- X _m^*)^T×H_m^-1*×(X _k- X _m^*)/2. (1.7.2)

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

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