Методы последовательной безусловной оптимизации

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

, определенного во множестве

евклидова пространства

(1)

где множество допустимых значений

(2)

Основная идея методов последовательной безусловной оптимизации состоит в преобразовании задачи условной оптимизации (1), (2) к последовательности задач безусловной оптимизации

(3)

где

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

и тем быстрее, чем больше значение параметра

. В качестве приближенного решения задачи (1), (2) принимается решение

вспомогательной задачи (3) при достаточно большом

Поясним идею методов последовательной безусловной оптимизации примером.

Пример 1

Пусть

(4)

и имеется одно ограничение типа равенств с ограничивающей функцией

(5)

Положим

(6)

где

— вещественная константа. На рисунках рис. 1, рис. 2, рис. 3 приведены линии уровня функции при

, соответственно.

Рис. 1. К прим. 1. Точка минимума функции Q^α(Х) при α = 0 имеет координаты (3, 2). Решением задачи (3), (4), (5), (6) является точка Х^∗ с координатами (2.5, 1.5).

Рис. 2. К прим. 1. Точка минимума функции Q^α(Х) при α = 1 имеет координаты (2.666…, 1.666…). Решением задачи (3), (4), (5), (6) является точка Х^∗ с координатами (2.5, 1.5).

Рис. 3. К прим. 1. Точка минимума функции Q^α(Х) при α = 2 имеет координаты (2.6, 1.6). Решением задачи (3), (4), (5), (6) является точка Х^∗ с координатами (2.5, 1.5).

Линии уровня на рисунках рис. 1, рис. 2, рис. 3 получены с помощью следующей MATLAB-программы:

x = 0 : 0.01 : 5;
y = x;
[X, Y] = meshgrid(x);
alpha = 2;
Z = (X - 3)^2 + (Y - 2)^2 + alpha * (X + Y - 4)^2;
V = [.02, 2, 1, 2, 5, 10, 20, 40, 80];
[C, h] = contour(X, Y, Z, V);
clabel(C, h);

Рисунки показывают, что при увеличении параметра

минимум функции

приближается к решению задачи (3), (4), (5), (6)

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

В методе штрафных функций функцию

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

функция

мало отличалась от функции

при

и быстро возрастала при удалении точки

от границы области допустимых значений

. В методе штрафных функций точка

в процессе поиска может выходить за границы области

(см. рис. 4). Т.е. метод штрафных функций относится к классу методов внешней точки. Рассмотренный выше прим. 1 также иллюстрирует метод штрафных функций.

Рис. 4. К методу штрафных функций (n = 1) Интервал [a, b] — область допустимых значений D; γ > β > α.

В методе барьерных функций функцию

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

функция

мало отличалась от функции

при

и быстро возрастала при приближении точки

к границе области допустимых значений

. В методе барьерных функций точка

в процессе поиска не может выходить за границы области

(см. рис. 5). Это означает, что метод барьерных функций относится к классу методов внутренней точки.

Рис. 5. К методу барьерных функций (n = 1) Интервал [a, b] — область допустимых значений D; γ > β > α.

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

Штрафная функция в общем случае имеет вид

(7)

где

— двумерный вектор параметров штрафной функции;

— весовые коэффициенты, могущие изменяться в процессе итераций,

— функционалы над функциями

, соответственно.

Функционалы

в формуле (7) должны удовлетворять очевидным требованиям:

при

;

В качестве функционалов

можно взять расстояния в какой-либо метрике от точки

до соответствующей границы множества

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

Так в качестве функционалов

обычно используют функционалы

в качестве функционалов

— функционалы

где

В качестве критерия окончания итераций в методе последовательной безусловной оптимизации можно использовать неравенство

(8)

где

— четное число итераций,

— требуемая точность решения по

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

Схема метода штрафных функций.

Задаем начальную точку и полагаем счетчик числа итераций .
Исходя из точки , одним из методов локальной безусловной оптимизации решаем задачу — находим точку .
Проверяем условие окончания поиска . Если условие окончания поиска выполнено, то полагаем и завершаем итерации. Иначе — по некоторому правилу увеличиваем значения параметров , , полагаем и переходим к п.3

Примечание 1

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