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

Учреждение  образования

 

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ  И РАДИОЭЛЕКТРОНИКИ

 

Кафедра радиоэлектронных средств

 

 

 

 

 

 

 

 

Реферат по дисциплине «Основы информационных технологий» на тему:

МЕТОДЫ НУЛЕВОГО ПОРЯДКА МИНИМАЗИЦИИ ФУНКИЦИЙ МНОГИХ ПЕРЕМЕННЫХ. ПОСТАНОВКА ЗАДАЧИ. ОПИСАНИЕ МЕТОДОВ. ПРЕИМУЩЕСТВА И НЕДОСТАТКИ.

 

 

 

 

Выполнил: Сыроваткин Максим Игоревич

магистрант  кафедры «Электронные вычислительные средства» группа № 41-з

 

Проверил:

 

 

 

 

 

 

 

 

Минск 2012

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ 3

1 ОБЩЕЕ ОПИСАНИЕ И АРХИТЕКТУРА  БИБЛИОТЕК 4

1.1 Описание и архитектура OpenGL 4

1.2 Описание и архитектураDirectX 6

2 СРАВНЕНИЕ 8

ЗАКЛЮЧЕНИЕ 12

ЛИТЕРАТУРА 13

 

ВВЕДЕНИЕ

 

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

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

 

1 ОБЗОР ОСНОВНЫХ МЕТОДОВ

 

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

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

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

• метод перебора;
• симплекс-метод.

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

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

 

2 МЕТОД ХУКА-ДЖИВСА

 

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

На начальном  этапе задается стартовая точка (обозначим её 1) и шаги h по координатам. Затем замораживаем значения всех координат  кроме 1-й, вычисляем значения функции  в точках x0+h0 и x0-h0 (где x0 — первая координата точки, а h0 — соответственно значение шага по этой координате) и переходим в точку с наименьшим значением функции. В этой точке замораживаем значения всех координат кроме 2-й, вычисляем значения функции в точках x1+h1 и x1-h1, переходим в точку с наименьшим значением функции и т. д. для всех координат. В случае, если для какой-нибудь координаты значение в исходной точке меньше, чем значения для обоих направлений шага, то шаг по этой координате уменьшается. Когда шаги по всем координатам h станут меньше соответствующих значений e, алгоритм завершается и точка 1 признаётся точкой минимума.

Иллюстрация первого этапа для двух координат:

 

Рисунок 1 – Первый этап алгоритма  Хука-Дживса

 

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

На этапе  поиска по образцу откладывается  точка 3 в направлении от 1 к 2 на том  же расстоянии. Её координаты получаются по формуле  , где xi — точка с номером i, λ— параметр алгоритма, обычно выбирающийся равным 2. Затем в новой точке 3 проводится исследующий поиск, как на 1 фазе алгоритма, за исключением того, что шаг на этой фазе не уменьшается. Если на этой фазе, в результате исследующего поиска, удалось получить точку 4, отличную от точки 3, то точку 2 переобозначим на 1, а 4 на 2 и повторим поиск по образцу. В случае если не удаётся найти точку 4, отличную от точки 3, то точку 2 переобозначим на точку 1 и повторим 1-ю фазу алгоритма — исследующий поиск.

Иллюстрация второго этапа для  двух координат:

 

Рисунок 2 – Второй этап алгоритма  Хука-Дживса

 

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

 

3 МЕТОД НЕДЛЕРА-МИДА

 

Метод Нелдера  — Мида, также известный как метод деформируемого многогранника и симплекс-метод — метод безусловной оптимизации функции от нескольких переменных, не использующий производной (точнее — градиентов) функции, а поэтому легко применим к негладким и/или зашумлённым функциям.

Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума. Метод находит локальный экстремум и может «застрять» в одном из них. Если всё же требуется найти глобальный экстремум, можно пробовать выбирать другой начальный симплекс. Более развитый подход к исключению локальных экстремумов предлагается в алгоритмах, основанных на методе Монте-Карло, а также в эволюционных алгоритмах

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

Пусть требуется  найти безусловный минимум функции n переменных:

 

    (1)

 

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

Параметрами метода являются:

• коэффициент отражения α > 0, обычно выбирается равным 1;
• коэффициент сжатия β > 0, обычно выбирается равным 0,5;
• коэффициент растяжения γ > 0, обычно выбирается равным 2.

1. «Подготовка». Вначале выбирается n + 1 точка

 

,   (2)

 

образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции:

 

   (3)

 

2. «Сортировка». Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh, xg со следующим по величине значением fg и xl с наименьшим значением функции fl. Целью дальнейших манипуляций будет уменьшение по крайней мере fh.

3. Найдём центр тяжести всех точек, за исключением xh:

     (4)

Вычислять fc = f(xc) не обязательно.

4. «Отражение». Отразим точку xh относительно xc с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия), получим точку xr и вычислим в ней функцию: fr = f(xr). Координаты новой точки вычисляются по формуле: xr = (1 + α)xc − αxh.

5. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место fr в ряду fh,fg,fl.

Если fr < fl, то направление выбрано удачное  и можно попробовать увеличить  шаг. Производим «растяжение». Новая  точка xe = (1 − γ)xc + γxr и значение функции fe = f(xe).

Если fe < fl, то можно расширить симплекс до этой точки: присваиваем точке xh значение xe и заканчиваем итерацию (на шаг 9).

Если fl < fe, то переместились слишком далеко: присваиваем точке xh значение xr и  заканчиваем итерацию (на шаг 9).

Если fl < fr < fg, то выбор точки неплохой (новая  лучше двух прежних). Присваиваем  точке xh значение xr и переходим на шаг 9.

Если fg < fr < fh, то меняем местами значения xr и xh. Также нужно поменять местами  значения fr и fh. После этого идём на шаг 6.

Если fh < fr, то просто идём на следующий шаг 6.

В результате (возможно, после переобозначения) fl < fg < fh < fr.

6. «Сжатие». Строим точку xs = βxh + (1 − β)xc и вычисляем в ней значение fs = f(xs).

7. Если fs < fh, то присваиваем точке xh значение xs и идём на шаг 9.

8. Если fs > fh, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением xl:

 

,     (5)

 

9. Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.

 

4 МЕТОД СЕТОК

 

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

Рисунок 3 –  Рассматриваемая область

 

Как мы уже  говорили выше, данный метод используется для решения одномерных задач. Иногда он применяется также для решения  двумерных, реже трехмерных задач. Однако для задач большей размерности  он практически непригоден из-за слишком  большого времени, необходимого для  проведения расчетов. Действительно, предположим, что целевая функция зависит  от пяти переменных, а область определения G является пятимерным кубом, каждую сторону  которого при построении сетки мы делим на 40 частей. Тогда общее  число узлов сетки будет равно  . Пусть вычисление значения функции в одной точке требует 1000 арифметических операций (это немного для функции пяти переменных). В таком случае общее число операций составит 1011. Если в нашем распоряжении имеется ЭВМ с быстродействием 1 млн. операций в секунду, то для решения задачи с помощью данного метода потребуется 105 секунд, что превышает сутки непрерывной работы. Добавление еще одной независимой переменной увеличит это время в 40 раз. Проведенная оценка показывает, что для больших задач оптимизации метод сплошного перебора непригоден. Иногда сплошной перебор заменяют случайным поиском. В этом случае точки сетки просматриваются не подряд, а в случайном порядке. В результате поиск наименьшего значения целевой функции существенно ускоряется, но теряет свою надежность.