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

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

5.6.1 Общие соображения

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

ятность унимодальности целевой функции . Кроме того, множество элементов,

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

цией , показатель которой равен размерности пространства. Так, если в случае одномерного пространства для достижения f = 0.1 методом общего поиска требуется вычислить 19 значений целевой функции, то в случае двумерного пространства это число составляет 361, трехмерного — 6859, четырехмерного — 130321, а пятимерного — 2476099! Поскольку при выборе оптимальном проектировании нередко приходится иметь дело с пятью и более переменными, серьезность трудностей, обусловленных многомерностью, становится бесспорной.

5.6.2 Метод покоординатного спуска (подъема)

Наиболее простым прямым методом поиска оптимума считается метод Га-

усса-Зейделя, называемый также методом покоординатного спуска ( подъема ).

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

Пусть значения всех проектных параметров фиксируются, кроме последнего. На рис. 5.11 показана двумерная целевая функция, заданная линиями уровня, где начальная координата

зафиксирована, а вдоль коор-

ищется минимум или макси-

мум (точка M 1 ) одним из методов одно-

мерной оптимизации. Затем, сохраняя новое значение постоянным, ищут оптимум по (точка M 2 ) и т.д. В общем случае, по завершении этой процедуры для всех переменных можно вернуться к

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

ствляется по достижению заданной точности.

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

Метод покоординатного подъема совершенно неприменим, если линии уровня имеют точки излома ( рис . 5.13 ). Поскольку линии уровня такого типа очень часто встречаются в инженерной

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

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

Рисунок 5.12 — Линии уровня целевой функции близки по форме к окружностям или эллипсам, оси которых параллельны осям координат

отнести возможность использования простых алгоритмов одномерного поиска, таких, как метод золотого сечения.

5.6.3 Метод случайного поиска

Рисунок 5.13 — Целевая функция имеет линию излома

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

Читайте также:  Как обновить айос на айпаде

вычислить, чтобы, пользуясь методом общего поиска, получить f = 0.1, и было показано, что это число растет как степенная функция, показатель степени которой

равен размерности пространства. Оригинальный подход, позволяющий обойти эту

трудность, основан на случайном поиске (метод Монте-Карло).

Сущность метода Монте-Карло заключается в том, что на каждом k-цикле с

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

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

ции . Перебирая точки ( рис. 5.14 ), компьютер отбрасывает те из них, кото-

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

Результат, полученный с помощью метода Монте-Карло характеризуется вероятностью P того, что при данном числе случайных проб K, расположение точки оптимума будет определено с точностью f , где f — объем N -мерного куба, выраженный в долях от общего объема поиска.

В этом случае f есть вероятность попадания для каждой пробы в заданную область, имеющую объем f . Если делается K случайных проб, то вероятность того, что одна из этих проб попадет в заданную область, может быть определена по формуле

Рисунок 5.14 — Метод случайного поиска

– вероятность попадания в

заданную область f для одной пробы;

– вероятность того же для K проб.

Для нахождения числа случайных проб K , необходимых для того, чтобы с заданной вероятностью P расположение точки оптимума определялось с точностью f , можно воспользоваться формулой

В табл. 5.1 указано, сколько надо сделать случайных проб K для соответствующих величин P и f . Из таблицы видно, что при 44 случайных пробах вероятность достижения f = 0.1 составит 99%. Вспомним, что для 100%-ного обеспечения целевую функцию в случае пяти переменных пришлось бы вычислить 2 476 099 раз!

Таблица 5.1 – Необходимое число случайных проб K для обеспечения вероятности P получения заданного точности f

Значения K для различных P

Метод случайного поиска имеет два преимущества. Во-первых, он пригоден

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

сматриваемого пространства. Хотя этот метод не позволяет непосредственно

найти оптимальное решение, он создает подходящие предпосылки для примене-

ния в дальнейшем других методов поиска. Поэтому его часто применяют в соче-

тании с одним или несколькими методами других типов.

5.6.4 Градиентные методы

Во многих алгоритмах многомерной оптимизации используется информация

о градиентах. Как известно, градиент ортогонален к гиперповерхности отклика

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

Чтобы наглядно представить идею метода, рассмотрим следующий простой пример. Представим себе, что альпинисту завязали глаза и предложили добраться до вершины «унимодальной» горы. Даже ничего не видя, он может это сделать, если все время будет двигаться вверх. Хотя любая ведущая вверх тропа в конечном счете приведет его к вершине, кратчайшей из них будет самая крутая, если, правда, альпинист не натолкнется на вертикальный обрыв 6 , который придется обходить.

Чтобы лучше понять идею градиентных методов, подробнее остановимся на свойствах градиентов. Рассмотрим систему независимых единичных векторов , направленных вдоль осей координат х 1 , х 2 , х 3 , . x N , являющихся в то же время проектными параметрами. Вектор градиента произвольной целевой

функции F ( х 1 , х 2 , х 3 , . x N ) имеет вид

где частные производные вычисляются в рассматриваемой точке. Этот вектор направлен вверх, в направлении подъема; обратный ему вектор указывает направление спуска. Единичный вектор градиента часто представляют в виде

Читайте также:  Красивые шрифты в инстаграм в описание

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

Здесь ∆ — небольшое смещение в направлении x i . Эту формулу часто называют «приближением секущей».

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

Пошаговые градиентные методы при отсутствии ограничений сводятся к следующему.

Этап 1. Пусть нам известны начальные значения проектных параметров

.

Этап 2. Определяется направление наискорейшего изменения целевой

функции F ( х 1 , х 2 , х 3 , . x N ), т.е. ее градиента

Задачи многомерной безусловной оптимизации формули­руются аналогично общей задаче оптимизации при отсутствии ограничений (28.2)-(28.4). Необходимым условием существования экстремума целевой функции в точке n — мерного пространства проектных параметров является обращение в нуль компонент вектора-градиента функции в этой точке:

(30.1)

В общем случае условие стационарности (30.1) точки, про­странства R n обозначаемой определяется путем решения не­линейной системы уравнений:

; (30.2)

что представляется весьма трудоемкой задачей.

Достаточное условие существования экстремума целевой функции в точке задается результатами исследования матрицы Гессе:

(30.3)

Для максимума целевой функции достаточным условием является то, что матрица Гессе (30.3) в стационарной точке , при любом векторе будет отрицательно определенной, т.е. скалярное произведение и – отрицательно, а для минимума – положительно определенной т.е. произведение и – положительно. В противном случае экстремум в не достигается, а сама стационарная точка – седловая.

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

Один из наиболее наглядных, широко применяемый на практике метод безусловной оптимизации – симплексный поиск.

Регулярным симплексом в пространстве R n называют пра­вильный многогранник, образованный п+1 равноотстоящими друг от друга вершинами. Так, например, на координатной плоскости, в пространстве (R 2 ) симплекс – правильный тре­угольник, в трехмерном пространстве (R 3 ) – тетраэдр.

Координаты (п штук) вершин (п+1 штука) регулярного симплекса задаются матрицей размером (п+1)´п

где X 0 – так называемая базовая вершина симплекса, выбор которой осуществляют на основании априорной информации о поведении целевой функции. Постоянные Рn и qn находят по следующим формулам:

.

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

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

Коорди­наты центра тяжести Х ц т вершин симплекса вычисляют по формуле

где j – номер отображаемой вершины; k=1,2,…,n.

Координаты новой вершины симплекса определяют по формуле

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

Читайте также:  Как сделать живые обои на рабочий стол

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

Известна модификация симплексного поиска, позволяю­щая последовательно растягивать и сжимать длину ребра симплекса именуемая процедурой Нелдера-Мида.

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

К числу достоинств симплексного поиска следует отнести простоту алгоритма и расчетных формул, отсутст­вие сильной чувствительности к характеру изменения целе­вой функции.

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

От первого из указанных недостатков свободны градиент­ные методы поиска. В отличие от симплексного поиска при использовании этой группы методов требуется предваритель­ная информация о дифференцируемости целевой функции. Для нахождения точки оптимума в пространстве проектных параметров R n используют итеративную процедуру:

где –вычисленное на данном шаге приближение к оптимуму вектора проектных параметров; –текущее значение вектора проектных па­раметров; α ( k ) – текущее значение параметра, характеризую­щего длину шага; –направление поиска на текущем шаге.

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

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

Метод координатного спуска заключается в поочередном поиске минимума по координате x1, затем x2 и т.д. поиск ведется с одинаковым шагом, который уменьшается после нахождения всех значений x1m, x2m, …, xnm.

Метод координатного спуска с квадратичной интерполяцией – экстраполяцией основан на последовательном поиске минимума каждой переменной с применением для этого метода квадратичной интерполяции – экстраполяции.

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

Метод градиента

Требуется найти минимум функции.

Параметры поиска: коэффициент шага h = 0,1, пробный g = 0,02, погрешность Е = 0,01.

Алгоритм метода: алгоритм 1 (х i+1 =х i — hgrad R(x i )) (3).

Алгоритм коррекции шага: без коррекции коэффициента пропорциональности шага (h = const).

Способ вычисления производной: вычисление gradR с парными пробами.

h:= 0.1; g:= 0.02; E:=0.01

В начальной точке вычисляем градиент функции:

Делаем рабочий шаг №1 , получаем

В новой точке опять вычисляем производные:

Делаем рабочий шаг №2, получаем

Далее вновь вычисляем производные и продолжаем расчет путем повторения шагов. В общем выполняем n кол-во шагов для нахождения оптимального значения.

Ссылка на основную публикацию
Купоны на скидку ив роше
Онлайн-маркет yves-rocher.ru предлагает широкий выбор косметики для ухода за собой. В каталоге вы найдете кремы и маски для лица, средства...
Классное оформление рабочего стола
Установив очередную версию операционной системы, всякий раз ловишь себя на мысли, что разработчики не могут угодить всем и вся. Вот...
Клеан мастер для андроид отзывы
5 - 0 4 - 0 3 - 0 2 - 0 1 - 0 Отличный чистильщик для смартфона, или...
Купоны санлайт как использовать
Сегодня: 3 промокода , 5 акций Промокод активен до 08.05.2020 Дополнительная скидка предоставляется по промокоду и действует при оплате онлайн....
Adblock detector