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), градиент в точке решения x (grad) и приближенную матрицу Гессе в точке решения x (hess).

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

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.