20.2 Минимизаторы ¶

Зачастую полезно найти минимальное значение функции, а не только нули, где она пересекает ось x. fminbnd предназначен для более простого, но очень распространённого случая унивариантной функции, где интервал поиска ограничен. Для неограниченной минимизации функции с потенциально многими переменными используйте fminunc или fminsearch. Эти две функции используют разные внутренние алгоритмы, и требуется некоторое знание целевой функции. Для функций, которые можно дифференцировать, fminunc подходит. Для функций с разрывами или для функций, для которых поиск по градиенту потерпит неудачу, используйте fminsearch. См. Оптимизация для минимизации при наличии функций ограничений. Обратите внимание, что поиск максимумов можно выполнить, просто инвертировав целевую функцию (Fto_max = -Fto_min).

: x = fminbnd (fcn, a, b) ¶

: x = fminbnd (fcn, a, b, options) ¶

: [x, fval, info, output] = fminbnd (…) ¶

Найти точку минимума унивариантной функции.

fcn — это дескриптор функции, встроенная функция или строка, содержащая имя функции для вычисления.

Начальный интервал задается a (левая граница) и b (правая граница). Концы должны быть конечными.

options — это структура, определяющая дополнительные параметры, которые управляют алгоритмом. В настоящее время fminbnd распознает следующие параметры: "Display", "FunValCheck", "MaxFunEvals", "MaxIter", "OutputFcn", "TolX".

"MaxFunEvals" задаёт максимальное количество вычислений функции перед остановкой оптимизации. Значение по умолчанию — 500. Значение должно быть положительным целым числом.

"MaxIter" задаёт максимальное количество итераций алгоритма перед остановкой оптимизации. Значение по умолчанию — 500. Значение должно быть положительным целым числом.

"TolX" задаёт точность завершения для решения x. По умолчанию — 1e-4.

Для описания других параметров см. optimset. Для инициализации структуры параметров со значениями по умолчанию для fminbnd используйте options = optimset ("fminbnd").

При выходе функция возвращает x, приблизительную точку минимума, и fval, значение функции в точке x.

Третий вывод info сообщает, успешно ли завершил алгоритм свою работу, и может принимать одно из следующих значений:

• 1 Алгоритм сошёлся к решению.
• 0 Превышено ограничение по итерациям (либо MaxIter либо MaxFunEvals).
• -1 Алгоритм был остановлен пользователем OutputFcn.

Примечания к применению:

1. Поиск минимума ограничен конечным интервалом, заданным a и b. Если у вас есть только одна начальная точка для начала поиска, вам потребуется использовать алгоритм неограниченной минимизации, такой как fminunc или fminsearch. fminbnd внутренне использует стратегию поиска методом золотого сечения.
2. Используйте Анонимные функции для передачи дополнительных параметров в fcn. Для конкретных примеров, как это сделать для fminbnd и других функций минимизации, см. раздел «Минимизаторы» руководства по GNU Octave.

См. также: fzero, fminunc, fminsearch, optimset.

: x = fminunc (fcn, x0) ¶

: x = fminunc (fcn, x0, options) ¶

: [x, fval] = fminunc (fcn, …) ¶

: [x, fval, info] = fminunc (fcn, …) ¶

: [x, fval, info, output] = fminunc (fcn, …) ¶

: [x, fval, info, output, grad] = fminunc (fcn, …) ¶

: [x, fval, info, output, grad, hess] = fminunc (fcn, …) ¶

Решает задачу безусловной оптимизации, определённую функцией fcn.

fminunc пытается определить вектор x, такой что fcn (x) является локальным минимумом.

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

x0 определяет начальное предположение. Форма x0 сохраняется во всех вызовах fcn, но в противном случае рассматривается как столбец.

options — это структура, определяющая дополнительные параметры, которые управляют алгоритмом. В настоящее время fminunc распознаёт следующие параметры: "AutoScaling", "FinDiffType", "FunValCheck", "GradObj", "MaxFunEvals", "MaxIter", "OutputFcn", "TolFun", "TolX", "TypicalX".

Если "AutoScaling" равно "on", переменные будут автоматически масштабироваться в соответствии с нормой столбцов (оценённой) матрицы Якоби. В результате "TolFun" становится независимой от масштабирования. По умолчанию этот параметр "off", так как он иногда может давать неожиданные (хотя математически правильные) результаты.

Если "GradObj" равно "on", это указывает, что fcn—при вызове с двумя выходными аргументами—также возвращает матрицу Якоби частных производных первого порядка в запрошенной точке.

"MaxFunEvals" предписывает максимальное число вычислений функции перед остановкой оптимизации. Значение по умолчанию равно 100 * number_of_variables, т.е. 100 * length (x0). Значение должно быть положительным целым числом.

"MaxIter" предписывает максимальное число итераций алгоритма перед остановкой оптимизации. Значение по умолчанию равно 400. Значение должно быть положительным целым числом.

"TolX" задаёт толерантность к завершению для неизвестных переменных x, в то время как "TolFun" — толерантность к целевому значению функции fval. По умолчанию равно 1e-6 для обоих параметров.

Описание других параметров см. в optimset.

По возвращении x — это местоположение минимума, а fval содержит значение целевой функции в x.

info может принимать следующие значения:

1

Достигнута точка решения. Относительная ошибка градиента меньше, чем задано в TolFun.

2

Последний относительный размер шага был меньше, чем TolX.

3

Последнее относительное изменение значения функции было меньше, чем TolFun.

0

Превышен предел итераций — либо максимальное количество итераций алгоритма MaxIter, либо максимальное число вычислений функции MaxFunEvals.

-1

Алгоритм завершён OutputFcn.

-3

Радиус области доверия стал чрезмерно малым.

Необязательно, fminunc может вернуть структуру со статистикой сходимости (output), градиентом выхода (grad) в решении x и приближённой матрицей Гессе (hess) в решении x.

Примечания к применению:

1. Если целевая функция — это единственное нелинейное уравнение одной переменной, то использование fminbnd обычно является лучшим выбором.
2. Алгоритм, используемый fminunc, — это поиск по градиенту, который зависит от дифференцируемости целевой функции. Если функция имеет разрывы, может быть лучше использовать алгоритм без производных, такой как fminsearch.
3. Используйте Анонимные функции, чтобы передавать дополнительные параметры в fcn. Примеры использования для fminunc и других функций минимизации см. в разделе «Минимизаторы» руководства GNU Octave.

См. также: fminbnd, fminsearch, optimset.

: x = fminsearch (fcn, x0) ¶

: x = fminsearch (fcn, x0, options) ¶

: x = fminsearch (problem) ¶

: [x, fval, exitflag, output] = fminsearch (…) ¶

Найти значение x, минимизирующее многомерную функцию fcn.

fcn — это указатель на функцию, встроенная функция или строка, содержащая имя функции для вычисления.

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

Параметры поиска задаются в параметре options с помощью функции optimset. В настоящее время fminsearch принимает следующие параметры: "Display", "FunValCheck", "MaxFunEvals", "MaxIter", "OutputFcn", "TolFun", "TolX".

"MaxFunEvals" задаёт максимальное количество вычислений функции перед остановкой оптимизации. Значение по умолчанию — 200 * number_of_variables, т.е. 200 * length (x0). Значение должно быть положительным целым числом.

"MaxIter" задаёт максимальное количество итераций алгоритма перед остановкой оптимизации. Значение по умолчанию — 200 * number_of_variables, т.е. 200 * length (x0). Значение должно быть положительным целым числом.

Описание других параметров см. в optimset. Для инициализации структуры параметров со значениями по умолчанию для fminsearch используйте options = optimset ("fminsearch").

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

objective

Функция цели.

x0

Начальная точка.

solver

Должно быть установлено в "fminsearch".

options

Структура, возвращённая из optimset или пустая матрица, чтобы указать, что следует использовать значения по умолчанию.

Поле options необязательно. Все остальные — обязательны.

При выходе функция возвращает x — точку минимума, и fval — значение функции в точке минимума.

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

1

если алгоритм сошёлся (размер симплекса меньше TolX И изменение значения функции между итерациями меньше TolFun).

0

если превышено максимальное количество итераций или максимальное количество вычислений функции.

-1

если итерация остановлена "OutputFcn".

Четвёртый выходной параметр — структура output, содержащая информацию о выполнении алгоритма. Поля в структуре — funcCount (количество вызовов функции fcn), iterations (количество шагов итерации), algorithm (название алгоритма поиска — всегда "Nelder-Mead simplex direct search" ), и message (сообщение об выходе).

Пример:

fminsearch (@(x) (x(1)-5).^2+(x(2)-8).^4, [0;0])

Примечания по применению:

1. Если вам нужно найти минимум функции одной переменной, лучше использовать fminbnd.
2. Устаревшая, недокументированная синтаксическая конструкция для передачи параметров в fcn путём добавления их в список входных аргументов после options не рекомендуется и будет полностью удалена в Octave 10. Предпочтительный, кроссплатформенный метод передачи параметров в fcn — использование Анонимных функций. Конкретные примеры такого подхода для fminsearch и других функций минимизации смотрите в разделе «Оптимизаторы» руководства GNU Octave.

См. также: fminbnd, fminunc, optimset.

Некоторые операции минимизации требуют передачи дополнительных параметров в функцию, F, которую минимизируют. Например, F = F(x, C). Функции минимизации Octave разработаны для передачи только одной переменной оптимизации в F, но передача параметров может быть реализована с помощью определения Анонимной функции, содержащей необходимые параметры. См. пример ниже:

A = 2; B = 3;
f = @(x) sin (A*x + B);
fminbnd (f, 0, 2)
   ⇒   0.8562

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

B = 4;
fminbnd (f, 0, 2)
   ⇒   0.8562
f = @(x) sin (A*x + B);
fminbnd (f, 0, 2)
   ⇒   0.3562

Функция humps — полезная функция для тестирования функций поиска нулей и экстремумов.

: y = humps (x) ¶

: [x, y] = humps (x) ¶

Вычисляет функцию с несколькими локальными минимумами, максимумами и нулевыми значениями.

Результат y — вычисление рациональной функции:

1200*x^4 - 2880*x^3 + 2036*x^2 - 348*x - 88
 y = - ---------------------------------------------
         200*x^4 - 480*x^3 + 406*x^2 - 138*x + 17

x может быть скаляром, вектором или массивом. Если x опущено, используется диапазон по умолчанию [0:0.05:1].

При вызове с двумя выходными аргументами [x, y], x будет содержать входные значения, а y — результат вычисления humps.

Примечания по программированию: humps имеет два локальных максимума, расположенных примерно при x = 0.300 и 0.893, локальный минимум около x = 0.637 и нули около x = -0.132 и 1.300. humps — полезная функция для тестирования алгоритмов поиска нулей или локальных минимумов и максимумов.

Попробуйте demo humps для отображения графика функции humps.

См. также: fzero, fminbnd, fminunc, fminsearch.