Многомерная безусловная оптимизация
Задачи многомерной безусловной оптимизации формулируются аналогично общей задаче оптимизации при отсутствии ограничений (28.2)-(28.4). Необходимым условием существования экстремума целевой функции в точке n - мерного пространства проектных параметров является обращение в нуль компонент вектора-градиента функции в этой точке:
(30.1)
В общем случае условие стационарности (30.1) точки, пространства Rn обозначаемой определяется путем решения нелинейной системы уравнений:
; (30.2)
что представляется весьма трудоемкой задачей.
Достаточное условие существования экстремума целевой функции в точке задается результатами исследования матрицы Гессе:
(30.3)
Для максимума целевой функции достаточным условием является то, что матрица Гессе (30.3) в стационарной точке , при любом векторе будет отрицательно определенной, т.е. скалярное произведение и – отрицательно, а для минимума – положительно определенной т.е. произведение и – положительно. В противном случае экстремум в не достигается, а сама стационарная точка – седловая.
Нахождение точек оптимума F(X) путем анализа выше условия (30.2) и исследование матрицы (30.3) даже в двумерном случае вызывает существенные затруднения. Поэтому разработаны математические методы и алгоритмы, позволяющие достаточно простыми способами приближаться к оптимуму.
Один из наиболее наглядных, широко применяемый на практике метод безусловной оптимизации – симплексный поиск.
Регулярным симплексом в пространстве Rn называют правильный многогранник, образованный п+1 равноотстоящими друг от друга вершинами. Так, например, на координатной плоскости, в пространстве (R2) симплекс – правильный треугольник, в трехмерном пространстве (R3) – тетраэдр.
Координаты (п штук) вершин (п+1 штука) регулярного симплекса задаются матрицей размером (п+1)´п
где X0 – так называемая базовая вершина симплекса, выбор которой осуществляют на основании априорной информации о поведении целевой функции. Постоянные Рn и qn находят по следующим формулам:
.
Масштабный множитель α равный длине стороны симплекса также выбирается исходя из предварительной информации о поведении целевой функции.
После построения начального симплекса – определения координат его вершин (рис.30.1,а), находят такую вершину (x1,x2,…,xn), в которой целевая функция имеет наибольшее значение (при отыскании минимума), и отображают ее симметрично центру тяжести остальных вершин симплекса.
Координаты центра тяжести Хц твершин симплекса вычисляют по формуле
где j – номер отображаемой вершины; k=1,2,…,n.
Координаты новой вершины симплекса определяют по формуле
Затем вычисляют значение целевой функции во вновь полученной вершине и сопоставляют со значениями в остальных вершинах симплекса за исключением отраженной вершины. Вновь разыскивается худшая вершина, отображается относительно центра тяжести остальных и т. д. (рис.30.1, б).
Если после очередного отражения вершины не достигается приближение к экстремуму целевой функции при достаточно малой длине ребра симплекса, то поиск можно прекратить. За искомое экстремальное значение в этом случае принимают наименьшее (в случае поиска максимума-наибольшее) значение целевой функции в вершинах последнего из построенных симплексов. Если заданная точность шага длина ребра не удовлетворяет, то выбрав нужную вершину в качестве базовой, уменьшают в требуемой степени масштабный коэффициент α и продолжают симплексный поиск.
Известна модификация симплексного поиска, позволяющая последовательно растягивать и сжимать длину ребра симплекса именуемая процедурой Нелдера-Мида.
Симплексный поиск может быть использован и как метод планирования эксперимента. В этом случае информацию о значениях целевой функции находят экспериментально при величинах проектных параметров, соответствующих координатам вершин симплекса.
К числу достоинств симплексного поиска следует отнести простоту алгоритма и расчетных формул, отсутствие сильной чувствительности к характеру изменения целевой функции.
В то же время метод оптимизации на симплексе имеет ряд недостатков. Алгоритм работает относительно медленно, так как количественная информация о значениях целевой функции в вершинах симплекса не используется. При необходимости изменить длину ребра симплекса требуется заново рассчитать значения целевой функции во всех вершинах вновь построенного симплекса с новой длиной ребра.
От первого из указанных недостатков свободны градиентные методы поиска. В отличие от симплексного поиска при использовании этой группы методов требуется предварительная информация о дифференцируемости целевой функции. Для нахождения точки оптимума в пространстве проектных параметров Rn используют итеративную процедуру:
где –вычисленное на данном шаге приближение к оптимуму вектора проектных параметров; –текущее значение вектора проектных параметров; α(k) – текущее значение параметра, характеризующего длину шага; –направление поиска на текущем шаге.
Выбор векторов осуществляют на основании информации о частных производных целевой функции по проектным параметрам. Выбор числового параметра α(k) на каждом шаге ведут обычно, решая задачу оптимизации целевой функции в направлении .
Из всего многообразия методов многомерной оптимизации рассмотрим относительно простые методы поиска минимума целевой функции .
Метод координатного спуска заключается в поочередном поиске минимума по координате x1, затем x2 и т.д. поиск ведется с одинаковым шагом, который уменьшается после нахождения всех значений x1m, x2m, …, xnm.
Метод координатного спуска с квадратичной интерполяцией – экстраполяцией основан на последовательном поиске минимума каждой переменной с применением для этого метода квадратичной интерполяции – экстраполяции.
Метод спирального координатного спуска отличается тем, что шаг меняется каждый раз при переходе от поиска минимума по одной переменной к поиску по другой. Обычно это дает некоторое сокращение времени поиска и в трехмерном пространстве напоминает спуск во впадину по спирали.
Лекция №31
Дата добавления: 2015-11-06; просмотров: 2455;