Лекция: Задачи локальной и глобальной оптимизации

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

Целевая функция описывает качество решения задачи. Обычно рассматривается задача минимизации F(X), хотя это не принципиально, поскольку задача поиска максимума F(X) равносильна задаче поиска минимума -F(X).

Например, если рассматривается задача оптимизации параметров регулятора, то X – набор параметров регулятора, а целевую функцию можно представить в виде:

где y*(t) – желаемый переходный процесс, y(t) – реальный переходный процесс при параметрах регулятора X.

Сложность поиска оптимального решения зависит от вида целевой функции. Если F(X) имеет один экстремум (унимодальная), то задача оптимизации относительно проста. Для такой локальной оптимизации предложено большое количество методов, в частности – методы спуска по градиенту целевой функции(см. [20, 21] и другие).

Если F(X) имеет много экстремумов (мультимодальная), то такая задача глобальной оптимизации значительно усложняется.

На рис. 1.2 показаны примеры графиков одномерной унимодальной (1.2, а) и мультимодальной (1.2, б) целевой функции.

Рис. 1.2.Виды целевой функции

Задачу глобальной минимизации описывается следующим образом:

где D – допустимое множество решений задачи, Rn – n–мерное эвклидово пространство.

Можно рассматривать множество оптимальных решений задачи

,

и множество локально-оптимальных решений задачи

,

где

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

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

Существует множество методов глобальной оптимизации [21 — 26], однако все они имеют общие черты:

— Для поиска глобального оптимума следует анализировать различные области множества решений X.

— В каждой области происходит поиск оптимума с помощью алгоритма локальной оптимизации (спуск по градиенту).

— Необходим критерий остановки алгоритма на основании качества полученного решения, поскольку область поиска может быть бесконечно большой.

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

где ε – малая величина (с учетом специфики решаемой задачи).