Методы многомерной оптимизации реферат

Обновлено: 08.07.2024

Аннотация: Данная лекция рассматривает основные методы решения задач многомерной оптимизации, в частности, такие как метод Хука – Дживса, метод Нелдера – Мида, метод полного перебора (метод сеток), метод покоординатного спуска, метод градиентного спуска.

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

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

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

1. Метод Хука – Дживса

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

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной xj, j = 1, 2, . n . В приведенной ниже программе для каждой переменной используется шаг h , однако указанная выше модификация тоже может оказаться полезной.

Б. Вычислить f(x) в базисной точке b1 с целью получения сведений о локальном поведении функции f(x) . Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b1 находится следующим образом:

1. Вычисляется значение функции f(b1) в базисной точке b1 .

2. Каждая переменная по очереди изменяется прибавлением длины шага.

Таким образом, мы вычисляем значение функции f(b1 + h1e1) , где e1 - единичный вектор в направлении оси х1 . Если это приводит к уменьшению значения функции, то b1 заменяется на b1 + h1e1 . В противном случае вычисляется значение функции f(b1 – h1e1) , и если ее значение уменьшилось, то b1 заменяем на b1-h1e1 . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2 , т.е. находится значение функции f(b1 + h2e2) и т.д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2 .

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

b_2 \neq b_1

4. Если , то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

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

P_1 = b_1 + 2 (b_2 - b_1)
 ( 1.1)
P_j = b_j + 2 (b_<j+1>- b_i)
 ( 1.2)

2. Затем исследование следует продолжать вокруг точки P1 ( Pj ).

3. Если наименьшее значение на шаге В,2 меньше значения в базисной точке b2 (в общем случае bj+1 ), то получают новую базисную точку b3 (bj+2) , после чего следует повторить шаг В,1. В противном случае не производить поиск по образцу из точки b2 (bj+1) а продолжить исследования в точке b2 (bj+1) .

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

1. Основные определения.Задачей многомерной оптимизации является минимизация функции U=f(x1,x2. xm) от m переменных (параметров) x1,x2. xm. Если нет ограничений на параметры x1. xm, то говорят о глобальной безусловной минимизации, если есть ограничения на параметры x1. xm, то говорят об условной минимизации.

Для сокращенного обозначения функции многих переменных удобно использовать векторное обозначение , при этом подразумевается, что каждой величине сопоставлен свой единственный набор значений величин x1. xm. В соответствии с этим величину можно рассматривать как точку (элемент) m-мерного линейного пространства независимых переменных x1. xm. Если в этом пространстве ввести единичные векторы , поставленные в соответствие переменным x1. xm, то величину можно рассматривать как вектор: , а операции сложения и вычитания производить по правилу векторов.

а) поверхность уровня. Множество точек , для которых называется поверхностью уровня, для двух переменных это множество называется линей уровня

б) градиент. Вектор называется градиентом функции и обозначается:

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

2. Необходимое и достаточное условия минимума функции многих переменных:

а) необходимое условие. Необходимым условием минимума функции многих переменных является условие равенства нулю ее градиента:

б) достаточное условие. Достаточным условием является условие положительной определенности матриц Гессе:

Для положительной определенности матрица Гесса необходимо, чтобы ее собственные числа l1. lm были положительны. Собственные числа l1. lm являются корнями характеристического уравнения:

где det -определитель квадратной матрицы ранга m, Е - единичная матрица.

Матрица C=G-lE называется характеристической матрицей для матрицы G.

3. Основные методы безусловной многомерной минимизации:

а) покоординатный спуск. В методе покоординатного спуска выбирается начальная точка x0 с координатами . Фиксируются все координаты кроме первой, и решается одномерная задача минимизации относительно переменной x1 (Рис.5). Затем фиксируются все координаты кроме второй, и опять решается задача одномерной минимизации относительно переменной x2 и т.д., т.е. поочередно производится спускание по всем координатам xi, до тех пор, пока не выполнятся все условия:

Если линия уровня имеет изломы, что соответствует “оврагам” на поверхности , то данный метод становится непригодным;

б) простой градиентный метод. В методе простого градиентного спуска выбирается начальная точка и начальное значение шага h. В точке вычисляется градиент и делается шаг в направлении антиградиента (Рис.6):

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

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

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

где a выступает в качестве параметра.

В результате находится значение , соответствующее минимальному значению функции на выбранной прямой (Рис.7). Затем вычислительный процесс повторяется для точки и т.д. Критерием окончания является третье условие (8.5);

г) метод деформирован-ного многогранника. Когда не является гладкой, и имеются множества точек, где она не дифференцируема, используются прямые методы. Наиболее известным из них является метод деформированного многогранника или метод Нелдера-Мида. Задается m+1 точка . При этом все разности должны быть линейно независимыми.

Обычно это делается следующим образом. Задаются координаты точки , а координаты остальных точек определяются с помощью соотношения:

где h-параметр, который определяет стороны многогранника.

Точки являются сторонами равнобедренного многогранника (на плоскости это треугольник).

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

Далее вычисляется пробная точка:

которая является симметричным отражением исключенной точки относительно точки (Рис.8).

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

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


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

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

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

в) значение в пробной точке больше, чем в исключенной точке . Тогда выбирается новая пробная точка внутри многогранника:

и тоже рассматривается новый многогранник с точками , где , а . Многогранник при этом также деформируется.

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

Процесс заканчивается, когда длины всех сторон многогранника, выходящих из точки с минимальным значением, станут меньше некоторого выбранного e или после очередного восстановления параметр h/2 станет меньше e.

Варианты задания №11

Найти точку минимума функции U(x,y) с точностью 0,1 указанным методом: а-покоординатный спуск, б-простой градиентный метод, в-метод наискорейшего спуска, г-метод деформированного многогранника.

Где S — новый одномерный параметр, значения которого отсчитываются в направлении градиента. Получив одномерный оптимум в направлении данного градиента, находят новый градиент и повторяют процесс до тех пор, пока последующие вычисления позволяют улучшать полученный результат. Главное достоинство этого метода состоит в том, что параметр S можно использовать в качестве независимой переменной для… Читать ещё >

Оптимизация. Методы многомерного поиска ( реферат , курсовая , диплом , контрольная )

Математический факультет Кафедра ВМ и П

Выполнили студентки группы М — 51, М — 52

Лаптева Е.Н., Кулай Н.В.

Содержине

  • Введение
    • 1. Основы теории оптимизации
    • 1.1 Проектные параметры
    • 1.2 Целевая функция
    • 1.3 Поиск минимума и максимума
    • 1.4 Пространство проектирования
    • 1.5 Ограничения — равенства
    • 1.6 Ограничения — неравенства
    • 1.7 Локальный оптимум
    • 1.8 Глобальный оптимум
    • 2. Методы многомерного поиска
    • 3. Метод покоординатного подъема
    • 4. Метод исключения областей
    • 5. Метод случайного поиска
    • 6. Градиентные методы
    • 6.1 Ступенчатый наискорейший подъем
    • Литература

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

    1. Основы теории оптимизации

    Рассматривая некоторую произвольную систему, описываемую т уравнениями с n неизвестными, можно выделить три основных типа задач. Если т=n, задачу называют алгебраической. Такая задача обычно имеет одно решение. Если т>n, то задача переопределена и, как правило, не имеет решения. Наконец, при т min, x R n

    x 0 -начальное приближение (массив [1: n])

    Будем считать, что нам известна функция

    minf (()), которая вычисляется min: (min) =min ()

    r: =f (x 0 ); r1: =r+2*; x: =x 0 ;

    Для i от 1 до n

    4. Метод исключения областей

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

    Одним из методов исключения является метод сеточного поиска, разработанный Мишке и дающий неплохие результаты. В этом случае суженная область неопределенности представляет собой гиперкуб — многомерный аналог квадрата или куба, — размеры которого можно определить заранее. Благодаря этому метод Мишке является одним из немногих методов многомерного поиска, эффективность которого поддается измерению. Чтобы лучше понять сущность этого метода, рассмотрим его для случая пространства проектирования, определяемого двумя переменными. Исходную область неопределенности в зависимости от размерности пространства отобразим на единичный квадрат, куб или гиперкуб. Это позволит вести поиск в нормированной области со стороной, равной единице. В гиперкубе построим сетку, образованную попарно симметричными взаимно ортогональными плоскостями, параллельными координатным направлениям, вдоль которых изменяются проектные параметры. Эти плоскости пересекаются по прямым, которые в свою очередь пересекаются в точках, называемых в дальнейшем узлами. Вычислим значения целевой функции в узлах и в центре куба. В случае М проектных параметров получим 2 значений целевой функции, из которых выберем наибольшее. Примем соответствующий узел за центр гиперкуба меньших размеров и продолжим исследование. Процесс продолжается до тех пор, пока не будет достигнута требуемая степень сужения интервала неопределенности. Если в области допустимых значений обозначить степень сужения вдоль какой-либо оси координат через r, то линейное сужение для b-мерного гиперкуба будет равно f=r, а число вычисленных значений целевой функции N=b (2) +1.

    Мишке рекомендует выбирать r в интервале значений 2/3

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

    Выше в этой главе говорилось о громоздкости вычислений в случае многомерного пространства на примере числа значений целевой функции, которые необходимо вычислить, чтобы, пользуясь методом сеток, получить f==0,1, и было показано, что это число растет как степенная функция, показатель степени которой равен размерности пространства. Оригинальный подход, позволяющий обойти эту трудность, предложен Бруксом и основан на случайном поиске. Пусть пространство проектирования представляет собой куб или гиперкуб со стороной, равной единице, и разделено на кубические ячейки путем деления на 10 равных частей каждой стороны куба, соответствующей одному из проектных параметров. При N=2 число ячеек равно 100, при N=3 оно равно 100, в общем случае при N измерений число ячеек равно 10. Вероятность того, что выбранная наугад ячейка войдет в число 10% наиболее перспективных ячеек, равна 0,1, так как при N=1 нас будет интересовать одна ячейка из 10, при N=2 — одна из десяти лучших при общем количестве ячеек 100 и т. д. Вероятность того, что мы пропустим одну из 10% наиболее перспективных ячеек, составит 0,9. Если случайным образом выбрать две ячейки, то вероятность пропуска будет 0,9, т. е 0,81. Вообще вероятность нахождения по крайней мере одной ячейки из наиболее перспективных, доля которых равна f, после N попыток составит Р=1- (1-f) .

    В таблице 1 указано, сколько ячеек надо выбрать случайным образом, чтобы обеспечить заданную вероятность при заданной доле наиболее перспективных ячеек. Из нее видно, что при случайной выборке 44 ячеек вероятность достижения f=0,1 составит 99%.

    Это очень неплохо, если вспомнить, что для 100% -ного обеспечения целевую функцию в случае пяти переменных пришлось бы вычислить 2 476 099 раз.

    Задача: Распределить Т = 100 ден.ед. по четырем предприятиям с целью получения максимальной суммарной прибыли. Прибыль с предприятий задается таблицей 1.1.

    X g1 g2 g3 g4
    0 0 0 0 0
    20 11 24 12 35
    40 26 22 28 33
    60 31 32 37 36
    80 42 41 47 40
    100 58 59 53 54

    Процесс оптимизации разобьем на n шагов (в нашей задаче n =4). На k-м шаге будем оптимизировать инвестирование не всех предприятий, а только с k-го по n-е. При этом на них расходуются не все средства, а некоторая меньшая сумма Ck≤Т, которая и будет являться переменной состояния системы. Переменной управления на k-м шаге назовем величину xk средств, вкладываемых в k-ое предприятие. В качестве функции Беллмана Fk(Ck) на k-м шаге в этой задаче можно выбрать максимально возможную прибыль, которую можно получить с предприятий с k-го по n-е при условии, что на их инвестирование осталось Ck средств. Очевидно, что при вложении в k-е предприятие xk средств получим прибыль gk(xk), а система в (k+1)-му шагу перейдет в состояние Ck+1 = Ck – xk, т.е. на инвестирование предприятий с (k+1)-ого до n-го останется Ck+1 средств.

    Таким образом, на первом шаге условной оптимизации при k=n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может выделяться количество средств Ck, 0≤Ck≤Т. Очевидно, чтобы получить максимум прибыли с этого последнего последнего предприятия, надо вложить в него все эти средства, т.е. Fn(Cn)=gn(Cn) и xn=Cn.

    На каждом из последующих шагов для вычисления функции Беллмана следует использовать результаты предыдущего шага. Максимально возможная прибыль, которая может быть получена предприятиями с k-го по n-е, равна:


    .

    Максимум этого выражения достигается на некотором значении x*k, которое и является оптимальным управлением на k-м шаге для состояния системы Ck. Аналогично можно отыскать функции Беллмана и оптимальные управления вплоть до шага k=1.

    Функция Беллмана F1(C1) представляет собой максимально возможную прибыль со всех предприятий (с 1-го по n-е), а значение x*k, на котором достигается максимум прибыли, является оптимальным количеством средств, которые необходимо вложить в 1-е предприятие. Далее, для всех последующих шагов вычисляется величина Ck = Ck-1 – Xk и оптимальным управлением на k-м шаге является то значение Xk, которое доставляет максимум прибыли при соответствующем состоянии системы Ck.

    Этап I. Условная оптимизация.

    Шаг 1. k = 4. Предполагаем, что все средства 100 ден.ед. переданы на инвестирование третьего предприятия. В этом случае максимальная прибыль составит F4(C4) = 54, см. таблицу 1.2.

    С4 x4 F4(C4) X*4
    0 20 40 60 80 100
    0 0 – – – – – 0 0
    20 – 35 – – – – 35 20
    40 – – 33 – – – 33 40
    60 – – – 36 – – 36 60
    80 – – – – 40 – 40 80
    100 – – – – – 54 54 100

    Шаг 2. k = 3. Определяем оптимальную стратегию инвестирования во второе и третье предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:


    .

    На его основании рассчитываются данные таблицы 1.3.

    Шаг 3. k = 2. Определяем оптимальную стратегию инвестирования в первое и остальные предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:


    .

    На его основе находятся данные таблицы 1.4.

    Шаг 4. k = 1. Определяем оптимальную стратегию инвестирования в первое и остальные предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:


    .

    На его основе находятся данные таблицы 1.5.

    Этап II. Безусловная оптимизация.

    Шаг 1. По данным таблицы 1.5 максимальный доход при распределении 100 ден.ед. между тремя предприятиями составляет F1= 98. При этом первому предприятию нужно выделить x1 = 20 ден.ед.

    Шаг 2. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий:

    С2 = С1 – x*1 = 100 – 20 = 80.

    По данным таблицы 1.4 находим, что оптимальный вариант распределения денежных средств размером 80 ден.ед. между вторым, третьим и четвертым предприятиями составляет F2 = 96 ден.ед. при выделении второму x2 = 20 ден.ед.

    Шаг 3. Определяем величину оставшихся денежных средств, приходящуюся на долю третьего и четвертого предприятия:

    С3 = С2 – x*2 = 80 – 20 = 60.

    Из таблицы 1.3 находим F3 = 63 и x*3 = 40 ден.ед. При этом получается что x*4 = 20 ден.ед. и F4 = 35.

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

    обеспечивающий максимальный доход

    F(100) = g1(20) + g2(40) + g3(20) + g4(20) = 11 + 24 + 28 + 35 = 98 ден.ед.

    Ответ: Максимальная суммарная прибыль по четырем предприятиям составляет 98 ден.ед.

    Раздел: Экономико-математическое моделирование
    Количество знаков с пробелами: 28886
    Количество таблиц: 51
    Количество изображений: 16

    Читайте также: