Нелинейная оптимизация. Метод Нелдера-Мида

Сентябрь 3, 2022

Главная
Алгебра
Нелинейная оптимизация. Метод Нелдера-Мида

Содержание

2. В презентации Минимизация Методы нулевого порядка Метод Нелдера-Мида Алгоритм Области применения Программа на паскале Обзор Сходимость
3. Цель проекта Разработка и внедрение программы минимизации функций Приемы программирования
4. Историческая справка JEFFREY C. LAGARIAS, JAMES A. REEDS, MARGARET H. WRIGHT, AND PAUL E. WRIGHT. NELDER-MEAD
5. Метод впервые был опубликован в работе J. A. Nelder and R. Mead, A simplex method for
6. Историческая справка Метод активно используется при решении прикладных оптимизационных задач в таких областях, как инженерная химия
7. Алгоритм Нелдера-Мида Алгоритм Нелдера-Мида минимизирует скалярную нелинейную функцию n действительных переменных используя лишь вычисление значений функции
8. Алгоритм Нелдера-Мида Обычно метод, базирующийся на итерациях на основе симплекса, начинает с определения самого симплекса и
9. Алгоритм Нелдера-Мида Итак, метод Нелдера-Мида минимизации функции определяется четырьмя скалярными параметрами: коэффициентами отражения ( ), растяжения(
10. Одна итерация метода 1. Упорядочивание. Сортировка n + 1 вершины так, что f(x1) ≤ f(x2) ≤…
11. Одна итерация метода 3. Растяжение. Если , то вычисляем точку растяжения xe, Вычисляем . Если ,
12. 4. Сжатие. Если , то проводим операцию сжатия между и лучшей точкой из и : Внешнее.
13. Одна итерация метода 4. Сжатие. Внутреннее. Если , то проводим внутреннее сжатие: Вычисляем и добавляем точку
14. Одна итерация метода 5. Глобальное сжатие. Вычисляем значения функции f(x) в n точках Упорядочиваем их. Новыми
15. Nelder and Mead’s Method Отражение и растяжение
16. Nelder and Mead’s Method Внешнее, внутреннее и глобальное сжатие
17. Simplex Steps Reflection Expansion Contraction
18. Limitations An interesting open problem concerns whether there exists any function f(x) in R2 for which
19. Applications function Func(X : TeVector) : Extended; begin result := sqr(x[1]-1)+sqr(x[2]-1)+sqr(x[3]-1); end; procedure TForm1.btCalculateClick(Sender: TObject); var
20. function Simplex function Simplex(Func: TFuncNVar; X: TeVector; Lbound, Ubound: Integer; MaxIter: Integer; Tol: Extended; var F_min:
21. Conclusions Our general conclusion about the Nelder{Mead algorithm is that the main mystery to be solved
22. Recommendations Используйте алгоритм Нелдера-Мида в случаях: Необходимо быстро написать программу оптимизации для проверки основных свойств исследуемой
24. Скачать презентацию

Слайд 2

В презентации
Минимизация
Методы нулевого порядка
Метод Нелдера-Мида
Алгоритм
Области применения
Программа на паскале
Обзор
Сходимость

Приложения
Заключение
Рекомендации

Слайд 3

Цель проекта
Разработка и внедрение программы минимизации функций
Приемы программирования

Слайд 4

Историческая справка
JEFFREY C. LAGARIAS, JAMES A. REEDS, MARGARET H. WRIGHT, AND

PAUL E. WRIGHT.
NELDER-MEAD SIMPLEX METHOD IN LOW DIMENSIONS
SIAM J. OPTIM. °c 1998 Society for Industrial and Applied Mathematics
Vol. 9, No. 1, pp. 112-147

Симплекс-метод Нелдера-Мида, впервые опубликованный в 1965 году, неимоверно популярен в качестве метода прямого поиска решения в задачах многомерной оптимизации без ограничений. Однако, несмотря на широкое распространение метода, теоретические результаты о его сходимости практически отсутствуют.
Рассмотрим сходимость этого метода для строго выпуклых функций в пространствах размерности 1 и 2 по материалам статьи авторов, работающих в AT&T Labs-Research, Florham Park, NJ 07932 и Bell Laboratories, Murray Hill, NJ 07974
Докажем сходимость метода к минимуму в пространстве размерности 1 и несколько более слабых результатов о сходимости в пространстве размерности 2. Контрпример МакКиннона (McKinnon) показывает, что существует семейство строго выпуклых функций в пространстве размерности 2 и существуют множества начальных условий, при которых метод Нелдера-Мида не сходится к точке минимума. Поэтому остается открытым вопрос, можно ли доказать сходимость метода для некоторого специального, но достаточно широкого класса выпуклых функций даже в двухмерном пространстве.

Слайд 5

Метод впервые был опубликован в работе
J. A. Nelder and R. Mead,

A simplex method for function minimization, Computer Journal 7 (1965), 308-313.

Историческая справка

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

Слайд 6

Историческая справка
Метод активно используется при решении прикладных оптимизационных задач в таких

областях, как инженерная химия и медицина.
Особую популярность метод приобрел после появления его описания в известной книге Numerical Recipes, где он появился под названием «амеба-алгоритм» и в пакете Matlab.

Слайд 7

Алгоритм Нелдера-Мида
Алгоритм Нелдера-Мида минимизирует скалярную нелинейную функцию n действительных переменных используя

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

Слайд 8

Алгоритм Нелдера-Мида
Обычно метод, базирующийся на итерациях на основе симплекса, начинает с

определения самого симплекса и определения его (n+1)-ой вершины, а также вычисления соответствующих этим вершинам значений функции.
Затем вычисляются одна или несколько пробных вершин и значений функции в них. Переход к новой итерации осуществляется после замены одной из предыдущих вершин новой вершиной.
Итерации прекращаются по достижении заданной точности (определяется как по разности значений функции, так и по объему многогранника – симплекса).

Слайд 9

Алгоритм Нелдера-Мида
Итак, метод Нелдера-Мида минимизации функции
определяется четырьмя скалярными параметрами:
коэффициентами
отражения

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

Слайд 10

Одна итерация метода
1. Упорядочивание. Сортировка n + 1 вершины так, что

f(x1) ≤ f(x2) ≤… ≤ f(xn+1);
2. Отражение. Вычислить точку отражения по формуле
где - центр тяжести n лучших точек. Вычислить .
Если ,, то добавить в набор точку отражения и закончить итерацию.

Слайд 11

Одна итерация метода
3. Растяжение. Если , то вычисляем точку растяжения xe,
Вычисляем

. Если , то добавляем эту
точку в набор и переходим к новой итерации. В противном случае ( ) добавляем в набор точку xr.
Итерация закончена.

Слайд 12

4. Сжатие. Если , то проводим операцию сжатия между и лучшей

точкой из и :
Внешнее. Если , то есть существенно лучше , то проводим внешнее сжатие:
Вычисляем и добавляем в набор, если . Переходим к (п.5)

Одна итерация метода

Слайд 13

Одна итерация метода
4. Сжатие.
Внутреннее. Если , то проводим внутреннее сжатие:
Вычисляем

и добавляем точку в набор, если .Переходим к глобальному сжатию (п.5)

Слайд 14

Одна итерация метода
5. Глобальное сжатие.
Вычисляем значения функции f(x) в n

точках
Упорядочиваем их. Новыми вершинами являются точки

Слайд 15

Nelder and Mead’s Method
Отражение и растяжение

Слайд 16

Nelder and Mead’s Method
Внешнее, внутреннее и глобальное сжатие

Слайд 17

Simplex Steps
Reflection
Expansion
Contraction

Слайд 18

Limitations
An interesting open problem concerns whether there exists any function

f(x) in R2 for which the Nelder-Mead algorithm always converges to a minimizer. The natural candidate is f(x; y) = x2 + y2, which by ane-invariance is equivalent to all strictly convex quadratic functions in two dimensions. A complete analysis of Nelder-Mead for x2 + y2 remains an open problem.

Слайд 19

Applications
function Func(X : TeVector) : Extended;
begin
result := sqr(x[1]-1)+sqr(x[2]-1)+sqr(x[3]-1);
end;
procedure TForm1.btCalculateClick(Sender: TObject);
var

X : TeVector; MaxIter, Iter: integer; F_min : extended;
begin
setlength(x, 4);
MaxIter:= 1500; // максимальное число итераций
x[1] := -0.1; // начальное приближение
x[2] := 1.1;
x[3] := 2.1;
Simplex(Func, X, 1, 3, MaxIter, 1.e-14, F_min, Iter, 0.1, 1.0e-8, nil, 0, '');
Label1.Caption := floattostr(x[1])+'; '+floattostr(x[2])+'; '+floattostr(x[3]);
Label2.Caption := Inttostr(Iter)+'; ';
x := nil;
end;

Слайд 20

function Simplex
function Simplex(Func: TFuncNVar; X: TeVector; Lbound, Ubound: Integer;
MaxIter: Integer;

Tol: Extended;
var F_min: Extended; var Iter: Integer{Iteration count};
Step: Extended; {для задания начального многогранника: скорее процент от текущей координаты}
ZeroCoordinateValue: Extended; {ноль, при котором шаг следует брать специфическим}
SB: TStatusBar; PanelN: Integer; PrefixStr: string): Integer;
{ ----------------------------------------------------------------------
Minimization of a function of several variables by the simplex method
of Nelder and Mead
----------------------------------------------------------------------
Input parameters : Func = objective function
X = initial minimum coordinates
Lbound,
Ubound = indices of first and last variables
MaxIter = maximum number of iterations
Tol = required precision
Step = Step used to construct the initial simplex ~ 1.5
----------------------------------------------------------------------
Output parameters : X = refined minimum coordinates
F_min = function value at minimum
Possible results : OPT_OK
OPT_NON_CONV
---------------------------------------------------------------------- }

Слайд 21

Conclusions
Our general conclusion about the Nelder{Mead algorithm is that the main

mystery to be solved is not whether it ultimately converges to a minimizer|for general (nonconvex) functions, it does not, but rather why it tends to work so well in practice by producing a rapid initial decrease in function values.

Слайд 22

Recommendations
Используйте алгоритм Нелдера-Мида в случаях:
Необходимо быстро написать программу оптимизации для проверки

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

Нелинейная оптимизация. Метод Нелдера-Мида

Содержание

В презентацииМинимизацияМетоды нулевого порядкаМетод Нелдера-МидаАлгоритмОбласти применения Программа на паскале Обзор Сходимость

Цель проекта Разработка и внедрение программы минимизации функцийПриемы программирования

Историческая справкаJEFFREY C. LAGARIAS, JAMES A. REEDS, MARGARET H. WRIGHT, AND

Метод впервые был опубликован в работеJ. A. Nelder and R. Mead,

Историческая справкаМетод активно используется при решении прикладных оптимизационных задач в таких

Алгоритм Нелдера-МидаАлгоритм Нелдера-Мида минимизирует скалярную нелинейную функцию n действительных переменных используя

Алгоритм Нелдера-МидаОбычно метод, базирующийся на итерациях на основе симплекса, начинает с

Алгоритм Нелдера-МидаИтак, метод Нелдера-Мида минимизации функции определяется четырьмя скалярными параметрами: коэффициентамиотражения

Одна итерация метода1. Упорядочивание. Сортировка n + 1 вершины так, что

Одна итерация метода3. Растяжение. Если , то вычисляем точку растяжения xe,Вычисляем

4. Сжатие. Если , то проводим операцию сжатия между и лучшей

Одна итерация метода4. Сжатие. Внутреннее. Если , то проводим внутреннее сжатие:Вычисляем

Одна итерация метода5. Глобальное сжатие. Вычисляем значения функции f(x) в n

Nelder and Mead’s MethodОтражение и растяжение

Nelder and Mead’s MethodВнешнее, внутреннее и глобальное сжатие

Simplex StepsReflectionExpansionContraction

Limitations An interesting open problem concerns whether there exists any function

Applicationsfunction Func(X : TeVector) : Extended;begin result := sqr(x[1]-1)+sqr(x[2]-1)+sqr(x[3]-1);end;procedure TForm1.btCalculateClick(Sender: TObject);var

function Simplexfunction Simplex(Func: TFuncNVar; X: TeVector; Lbound, Ubound: Integer; MaxIter: Integer;

ConclusionsOur general conclusion about the Nelder{Mead algorithm is that the main

RecommendationsИспользуйте алгоритм Нелдера-Мида в случаях:Необходимо быстро написать программу оптимизации для проверки

Похожие презентации