scipy.optimize.

minimize

scipy.optimize.minimize(fun, x0, args=(), метод=None, jac=None, hess=None, hessp=None, границы=None, ограничения=(), tol=None, callback=None, опции=None)

Минимизация скалярной функции одной или нескольких переменных.

Параметры:

funcallable

Целевая функция для минимизации:

fun(x, *args) -> float

где x является одномерным массивом с формой (n,) и args является кортежем фиксированных параметров, необходимых для полного определения функции.

Предположим, что вызываемый объект имеет сигнатуру f0(x, *my_args, **my_kwargs), где my_args и my_kwargs являются обязательными позиционными и ключевыми аргументами. Вместо передачи f0 в качестве вызываемого объекта, оберните его, чтобы он принимал только x; например, передать fun=lambda x: f0(x, *my_args, **my_kwargs) как вызываемый объект, где my_args (кортеж) и my_kwargs (dict) были собраны перед вызовом этой функции.

x0ndarray, форма (n,)

Начальное приближение. Массив вещественных элементов размера (n,), где n это количество независимых переменных.

argsкортеж, необязательный

Дополнительные аргументы, передаваемые в целевую функцию и её производные (fun, jac и hess функции).

методstr или callable, опционально

Тип решателя. Должен быть одним из

• 'Nelder-Mead' (см. здесь)

• ‘Powell’ (см. здесь)

• ‘CG’ (см. здесь)

• 'BFGS' (см. здесь)

• ‘Newton-CG’ (см. здесь)

• ‘L-BFGS-B’ (см. здесь)

• 'TNC' (см. здесь)

• ‘COBYLA’ (см. здесь)

• ‘COBYQA’ (см. здесь)

• ‘SLSQP’ (см. здесь)

• 'trust-constr'(см. здесь)

• ‘dogleg’ (см. здесь)

• 'trust-ncg' (см. здесь)

• ‘trust-exact’ (см. здесь)

• ‘trust-krylov’ (см. здесь)

• custom — вызываемый объект, см. ниже описание.

Если не указано, выбирается одним из BFGS, L-BFGS-B, SLSQP, в зависимости от того, имеет ли задача ограничения или границы.

jac{callable, ‘2-point’, ‘3-point’, ‘cs’, bool}, optional

Метод вычисления вектора градиента. Только для CG, BFGS, Newton-CG, L-BFGS-B, TNC, SLSQP, dogleg, trust-ncg, trust-krylov, trust-exact и trust-constr. Если это вызываемый объект, он должен быть функцией, возвращающей вектор градиента:

jac(x, *args) -> array_like, shape (n,)

где x является массивом формы (n,) и args является кортежем с фиксированными параметрами. Если jac является логическим значением и равно True, fun предполагается, что возвращает кортеж (f, g) содержащий целевую функцию и градиент. Методы 'Newton-CG', 'trust-ncg', 'dogleg', 'trust-exact' и 'trust-krylov' требуют, чтобы была предоставлена вызываемая функция, или чтобы fun возвращает целевую функцию и градиент. Если None или False, градиент будет оценен с использованием 2-точечной оценки конечных разностей с абсолютным размером шага. В качестве альтернативы, ключевые слова {'2-point', '3-point', 'cs'} могут быть использованы для выбора схемы конечных разностей для численной оценки градиента с относительным размером шага. Эти схемы конечных разностей соблюдают любые указанные границы.

hess{callable, '2-point', '3-point', 'cs', HessianUpdateStrategy}, опционально

Метод вычисления матрицы Гессе. Только для Newton-CG, dogleg, trust-ncg, trust-krylov, trust-exact и trust-constr. Если это вызываемый объект, он должен возвращать матрицу Гессе:

hess(x, *args) -> {LinearOperator, spmatrix, array}, (n, n)

где x является (n,) ndarray и args является кортежем с фиксированными параметрами. Ключевые слова {‘2-point’, ‘3-point’, ‘cs’} также могут использоваться для выбора схемы конечных разностей для численной оценки гессиана. В качестве альтернативы, объекты, реализующие HessianUpdateStrategy интерфейс может использоваться для аппроксимации гессиана. Доступные квази-ньютоновские методы, реализующие этот интерфейс:

• BFGS

• SR1

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

hesspвызываемый объект, необязательный

Гессиан целевой функции, умноженный на произвольный вектор p. Только для Newton-CG, trust-ncg, trust-krylov, trust-constr. Только один из hessp или hess должен быть задан. Если hess предоставляется, тогда hessp будет проигнорирован. hessp должен вычислять матрицу Гессе, умноженную на произвольный вектор:

hessp(x, p, *args) ->  ndarray shape (n,)

где x — это ndarray размерности (n,), p является произвольным вектором с размерностью (n,) и args является кортежем с фиксированными параметрами.

границыпоследовательность или Bounds, опционально

Границы переменных для методов Nelder-Mead, L-BFGS-B, TNC, SLSQP, Powell, trust-constr, COBYLA и COBYQA. Существует два способа указания границ:

1. Экземпляр Bounds класс.

2. Последовательность (min, max) пары для каждого элемента в x. None используется для указания отсутствия границы.

ограничения{Constraint, dict} или список {Constraint, dict}, необязательно

Определение ограничений. Только для COBYLA, COBYQA, SLSQP и trust-constr.

Ограничения для ‘trust-constr’, ‘cobyqa’ и ‘cobyla’ определяются как единый объект или список объектов, задающих ограничения для задачи оптимизации. Доступные ограничения:

• LinearConstraint

• NonlinearConstraint

Ограничения для COBYLA, SLSQP определены как список словарей. Каждый словарь с полями:

типstr

Тип ограничения: 'eq' для равенства, 'ineq' для неравенства.

funcallable

Функция, определяющая ограничение.

jacвызываемый объект, необязательный

Якобиан fun (только для SLSQP).

argssequence, optional

Дополнительные аргументы для передачи в функцию и якобиан.

Ограничение равенства означает, что результат функции ограничения должен быть нулевым, тогда как неравенство означает, что он должен быть неотрицательным.

tolfloat, опционально

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

опцииdict, optional

Словарь параметров решателя. Все методы, кроме TNC принимают следующие общие опции:

maxiterint

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

Для TNC использовать maxfun вместо maxiter.

dispbool

Установите True для вывода сообщений о сходимости.

Для специфичных для метода опций см. show_options.

callbackвызываемый объект, необязательный

Вызываемый объект, вызываемый после каждой итерации.

Все методы, кроме TNC и SLSQP, поддерживают вызываемый объект с сигнатурой:

callback(intermediate_result: OptimizeResult)

где intermediate_result является ключевым параметром, содержащим OptimizeResult с атрибутами x и fun, текущие значения вектора параметров и целевой функции. Не все атрибуты OptimizeResult может присутствовать. Имя параметра должно быть intermediate_result для передачи обратного вызова OptimizeResult. Эти методы также завершатся, если обратный вызов вызовет StopIteration.

Все методы, кроме trust-constr (также) поддерживают сигнатуру вида:

callback(xk)

где xk является текущим вектором параметров.

Интроспекция используется для определения, какую из вышеуказанных сигнатур вызывать.

Возвращает:

resOptimizeResult

Результат оптимизации, представленный как OptimizeResult объект. Важные атрибуты: x массив решения, success логический флаг, указывающий, успешно ли завершился оптимизатор, и message который описывает причину завершения. См. OptimizeResult для описания других атрибутов.

Смотрите также

minimize_scalar

Интерфейс к алгоритмам минимизации для скалярных функций одной переменной

show_options

Дополнительные параметры, принимаемые решателями

Примечания

Этот раздел описывает доступные решатели, которые можно выбрать с помощью параметра 'method'. Метод по умолчанию — BFGS.

Минимизация без ограничений

Метод CG использует нелинейный алгоритм сопряжённых градиентов Полака-Рибьера, вариант метода Флетчера-Ривза, описанный в [5] стр.120-122. Используются только первые производные.

Метод BFGS использует квазиньютоновский метод Бройдена, Флетчера, Голдфарба и Шанно (BFGS) [5] стр. 136. Использует только первые производные. BFGS показал хорошую производительность даже для негладких оптимизаций. Этот метод также возвращает аппроксимацию обратной матрицы Гессе, хранящуюся как hess_inv в объекте OptimizeResult.

Метод Newton-CG использует алгоритм Newton-CG [5] стр. 168 (также известный как усечённый метод Ньютона). Использует метод сопряжённых градиентов для вычисления направления поиска. См. также TNC метод для минимизации с ограничениями в виде прямоугольной области с аналогичным алгоритмом. Подходит для крупномасштабных задач.

Метод dogleg использует алгоритм доверительной области dog-leg [5] для неограниченной минимизации. Этот алгоритм требует градиент и матрицу Гессе; кроме того, матрица Гессе должна быть положительно определённой.

Метод trust-ncg использует алгоритм Ньютона-сопряженных градиентов с доверительной областью [5] для безусловной минимизации. Этот алгоритм требует градиент и либо гессиан, либо функцию, вычисляющую произведение гессиана на заданный вектор. Подходит для крупномасштабных задач.

Метод trust-krylov использует алгоритм доверительной области Newton GLTR [14], [15] для безусловной минимизации. Этот алгоритм требует градиент и либо гессиан, либо функцию, вычисляющую произведение гессиана на заданный вектор. Подходит для крупномасштабных задач. На неопределенных задачах обычно требует меньше итераций, чем trust-ncg метод и рекомендуется для задач среднего и большого масштаба.

Метод trust-exact является методом доверительной области для безусловной минимизации, в котором квадратичные подзадачи решаются почти точно [13]. Этот алгоритм требует градиент и матрицу Гессе (которая не требуется быть положительно определенной). Во многих ситуациях это метод Ньютона для сходимости за меньшее количество итераций и наиболее рекомендуется для задач малого и среднего размера.

Минимизация с ограничениями-границами

Метод Nelder-Mead использует симплекс-алгоритм [1], [2]. Этот алгоритм устойчив во многих приложениях. Однако, если численное вычисление производной можно доверять, другие алгоритмы, использующие информацию о первой и/или второй производных, могут быть предпочтительнее из-за их лучшей производительности в общем случае.

Метод L-BFGS-B использует алгоритм L-BFGS-B [6], [7] для минимизации с ограничениями.

Метод Пауэлл является модификацией метода Пауэлла [3], [4] который является методом сопряжённых направлений. Он выполняет последовательные одномерные минимизации вдоль каждого вектора набора направлений (direc поле в опции и info), который обновляется на каждой итерации основного цикла минимизации. Функция не обязательно должна быть дифференцируемой, и производные не берутся. Если границы не предоставлены, то будет использован неограниченный линейный поиск. Если границы предоставлены и начальное предположение находится в пределах границ, то каждое вычисление функции в процессе минимизации будет в пределах границ. Если границы предоставлены, начальное предположение находится вне границ, и direc имеет полный ранг (по умолчанию имеет полный ранг), то некоторые вычисления функций во время первой итерации могут быть за пределами границ, но каждое вычисление функции после первой итерации будет в пределах границ. Если direc не является полного ранга, тогда некоторые параметры могут не быть оптимизированы, и решение не гарантируется быть в пределах границ.

Метод TNC использует усеченный алгоритм Ньютона [5], [8] для минимизации функции с переменными, ограниченными границами. Этот алгоритм использует информацию о градиенте; также называется методом Ньютона-сопряжённых градиентов. Он отличается от Newton-CG метод, описанный выше, так как он оборачивает C-реализацию и позволяет задавать верхние и нижние границы для каждой переменной.

Ограниченная минимизация

Метод COBYLA использует реализацию PRIMA [19] метода ограниченной оптимизации с линейной аппроксимацией (COBYLA) [9], [10], [11]. Алгоритм основан на линейных аппроксимациях целевой функции и каждого ограничения.

Метод COBYQA использует метод Constrained Optimization BY Quadratic Approximations (COBYQA) [18]. Алгоритм является методом доверительной области SQP без производных, основанным на квадратичных аппроксимациях целевой функции и каждого нелинейного ограничения. Границы обрабатываются как нерелаксируемые ограничения, в том смысле, что алгоритм всегда соблюдает их на протяжении всего процесса оптимизации.

Метод SLSQP использует Sequential Least SQuares Programming для минимизации функции нескольких переменных с любыми комбинациями границ, равенств и неравенств ограничений. Метод оборачивает подпрограмму оптимизации SLSQP, изначально реализованную Dieter Kraft [12]. Обратите внимание, что обертка обрабатывает бесконечные значения в границах, преобразуя их в большие значения с плавающей точкой.

Метод trust-constr является алгоритмом доверительной области для ограниченной оптимизации. Он переключается между двумя реализациями в зависимости от определения задачи. Это самый универсальный алгоритм ограниченной минимизации, реализованный в SciPy, и наиболее подходящий для крупномасштабных задач. Для задач с ограничениями равенства это реализация метода доверительной области Byrd-Omojokun SQP, описанного в [17] и в [5], стр. 549. Когда также накладываются ограничения-неравенства, она переключается на метод внутренней точки доверительной области, описанный в [16]. Этот алгоритм внутренней точки, в свою очередь, решает ограничения-неравенства, вводя дополнительные переменные и решая последовательность задач с барьерными функциями и ограничениями-равенствами для постепенно уменьшающихся значений барьерного параметра. Описанный ранее метод SQP с ограничениями-равенствами используется для решения подзадач с возрастающей точностью по мере приближения итерации к решению.

Опции конечных разностей

Для метода trust-constr градиент и гессиан могут быть аппроксимированы с использованием трёх схем конечных разностей: {‘2-point’, ‘3-point’, ‘cs’}. Схема ‘cs’ потенциально наиболее точна, но требует, чтобы функция корректно обрабатывала комплексные входные данные и была дифференцируема в комплексной плоскости. Схема ‘3-point’ более точна, чем ‘2-point’, но требует вдвое больше операций. Если градиент оценивается через конечные разности, гессиан должен быть оценён с использованием одной из квазиньютоновских стратегий.

Специфичные для метода опции для hess ключевое слово

метод/Гессиан	None	callable	'2-point'/'3-point'/'cs'	HUS
Newton-CG	x	(n, n) LO	x	x
dogleg		(n, n)
trust-ncg		(n, n)	x	x
trust-krylov		(n, n)	x	x
trust-exact		(n, n)
trust-constr	x	(n, n) LO sp	x	x

где LO=LinearOperator, sp=Разреженная матрица, HUS=HessianUpdateStrategy

Пользовательские минимизаторы

Может быть полезно передать пользовательский метод минимизации, например, при использовании внешнего интерфейса для этого метода, такого как scipy.optimize.basinhopping или другой библиотекой. Вы можете просто передать вызываемый объект в качестве method параметр.

Вызываемый объект вызывается как method(fun, x0, args, **kwargs, **options) где kwargs соответствует любым другим параметрам, переданным в minimize (такие как callback, hess, и т.д.), за исключением опции dict, который имеет свое содержимое, также передаваемое как метод параметры попарно. Также, если jac был передан как тип bool, jac и fun искажаются таким образом, что fun возвращает только значения функции и jac преобразуется в функцию, возвращающую матрицу Якоби. Метод должен возвращать OptimizeResult объект.

Предоставленный метод вызываемый объект должен уметь принимать (и, возможно, игнорировать) произвольные параметры; набор параметров, принимаемых minimize может расширяться в будущих версиях, и тогда эти параметры будут переданы методу. Пример можно найти в учебнике по scipy.optimize.

Ссылки

[1]

Нелдер, Дж. А., и Р. Мид. 1965. Симплексный метод минимизации функции. The Computer Journal 7: 308-13.

[2]

Wright M H. 1996. Direct search methods: Once scorned, now respectable, in Numerical Analysis 1995: Proceedings of the 1995 Dundee Biennial Conference in Numerical Analysis (Eds. D F Griffiths and G A Watson). Addison Wesley Longman, Harlow, UK. 191-208.

[3]

Пауэлл, М. Дж. Д. 1964. Эффективный метод нахождения минимума функции нескольких переменных без вычисления производных. The Computer Journal 7: 155-162.

[4]

Press W, S A Teukolsky, W T Vetterling и B P Flannery. Numerical Recipes (любое издание), Cambridge University Press.

[5] (1,2,3,4,5,6,7,8)

Носедал, Дж., и С. Дж. Райт. 2006. Численная оптимизация. Springer New York.

[6]

Byrd, R H и P Lu и J. Nocedal. 1995. Алгоритм ограниченной памяти для оптимизации с ограничениями. SIAM Journal on Scientific and Statistical Computing 16 (5): 1190-1208.

[7]

Чжу, С. и Р. Х. Бёрд и Дж. Ноцедал. 1997. L-BFGS-B: Алгоритм 778: L-BFGS-B, подпрограммы FORTRAN для крупномасштабной оптимизации с ограничениями. ACM Transactions on Mathematical Software 23 (4): 550-560.

[8]

Нэш, С. Г. Минимизация ньютоновского типа через метод Ланцоша. 1984. SIAM Journal of Numerical Analysis 21: 770-778.

[9]

Пауэлл, М. Дж. Д. Метод прямой оптимизации, который моделирует целевую функцию и функции ограничений с помощью линейной интерполяции. 1994. Advances in Optimization and Numerical Analysis, ред. С. Гомес и Ж.-П. Хеннарт, Kluwer Academic (Дордрехт), 51-67.

[10]

Powell M J D. Direct search algorithms for optimization calculations. 1998. Acta Numerica 7: 287-336.

[11]

Powell M J D. A view of algorithms for optimization without derivatives. 2007.Cambridge University Technical Report DAMTP 2007/NA03

[12]

Kraft, D. Программный пакет для последовательного квадратичного программирования. 1988. Тех. отчёт DFVLR-FB 88-28, Немецкий аэрокосмический центр DLR – Институт механики полёта, Кёльн, Германия.

[13]

Conn, A. R., Gould, N. I., and Toint, P. L. Методы доверительной области. 2000. Siam. стр. 169-200.

[14]

F. Lenders, C. Kirches, A. Potschka: "trlib: векторная реализация метода GLTR для итерационного решения задачи доверительной области", arXiv:1611.04718

[15]

N. Gould, S. Lucidi, M. Roma, P. Toint: «Решение подзадачи доверительной области с использованием метода Ланцоша», SIAM J. Optim., 9(2), 504–525, (1999).

[16]

Бёрд, Ричард Х., Мэри Э. Хрибар и Хорхе Носедал. 1999. Алгоритм внутренней точки для нелинейного программирования большого масштаба. SIAM Journal on Optimization 9.4: 877-900.

[17]

Lalee, Marucha, Jorge Nocedal, и Todd Plantenga. 1998. О реализации алгоритма для крупномасштабной оптимизации с ограничениями-равенствами. SIAM Journal on Optimization 8.3: 682-706.

[18]

Ragonneau, T. M. Методы и программное обеспечение для оптимизации без производных на основе моделей. Диссертация PhD, факультет прикладной математики, Гонконгский политехнический университет, Гонконг, Китай, 2022. URL: https://theses.lib.polyu.edu.hk/handle/200/12294.

[19]

Zhang, Z. «PRIMA: Reference Implementation for Powell’s Methods with Modernization and Amelioration», https://www.libprima.net, DOI:10.5281/zenodo.8052654

[20]

Условия Каруша-Куна-Таккера, https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions

Примеры

Попробуйте в вашем браузере!

Рассмотрим задачу минимизации функции Розенброка. Эта функция (и её соответствующие производные) реализована в rosen (соответственно. rosen_der, rosen_hess) в scipy.optimize.

>>> from scipy.optimize import minimize, rosen, rosen_der

Простое применение Nelder-Mead метод:

>>> x0 = [1.3, 0.7, 0.8, 1.9, 1.2]
>>> res = minimize(rosen, x0, method='Nelder-Mead', tol=1e-6)
>>> res.x
array([ 1.,  1.,  1.,  1.,  1.])

Теперь используя BFGS алгоритм, использующий первую производную и несколько опций:

>>> res = minimize(rosen, x0, method='BFGS', jac=rosen_der,
...                options={'gtol': 1e-6, 'disp': True})
Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 26
         Function evaluations: 31
         Gradient evaluations: 31
>>> res.x
array([ 1.,  1.,  1.,  1.,  1.])
>>> print(res.message)
Optimization terminated successfully.
>>> res.hess_inv
array([
    [ 0.00749589,  0.01255155,  0.02396251,  0.04750988,  0.09495377],  # may vary
    [ 0.01255155,  0.02510441,  0.04794055,  0.09502834,  0.18996269],
    [ 0.02396251,  0.04794055,  0.09631614,  0.19092151,  0.38165151],
    [ 0.04750988,  0.09502834,  0.19092151,  0.38341252,  0.7664427 ],
    [ 0.09495377,  0.18996269,  0.38165151,  0.7664427,   1.53713523]
])

Далее, рассмотрим задачу минимизации с несколькими ограничениями (а именно Пример 16.4 из [5]). Целевая функция:

>>> fun = lambda x: (x[0] - 1)**2 + (x[1] - 2.5)**2

Определены три ограничения:

>>> cons = ({'type': 'ineq', 'fun': lambda x:  x[0] - 2 * x[1] + 2},
...         {'type': 'ineq', 'fun': lambda x: -x[0] - 2 * x[1] + 6},
...         {'type': 'ineq', 'fun': lambda x: -x[0] + 2 * x[1] + 2})

И переменные должны быть положительными, отсюда следующие ограничения:

>>> bnds = ((0, None), (0, None))

Задача оптимизации решается методом SLSQP следующим образом:

>>> res = minimize(fun, (2, 0), method='SLSQP', bounds=bnds, constraints=cons)

Должно сходиться к теоретическому решению [1.4 ,1.7]. SLSQP также возвращает множители, используемые при решении задачи. Эти множители, когда ограничения задачи линейны, можно рассматривать как множители Каруша-Куна-Таккера (KKT), которые являются обобщением множителей Лагранжа для задач оптимизации с ограничениями-неравенствами ([20]).

Заметим, что в решении первое ограничение активно. Вычислим функцию в решении:

>>> cons[0]['fun'](res.x)
np.float64(1.4901224698604665e-09)

Также обратите внимание, что в оптимальности существует ненулевой множитель:

>>> res.multipliers
array([0.8, 0. , 0. ])

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

>>> eps = 0.01
>>> cons[0]['fun'] = lambda x: x[0] - 2 * x[1] + 2 - eps

мы ожидаем, что оптимальное значение целевой функции увеличится на приблизительно eps * res.multipliers[0]:

>>> eps * res.multipliers[0]  # Expected change in f0
np.float64(0.008000000027153205)
>>> f0 = res.fun  # Keep track of the previous optimal value
>>> res = minimize(fun, (2, 0), method='SLSQP', bounds=bnds, constraints=cons)
>>> f1 = res.fun  # New optimal value
>>> f1 - f0
np.float64(0.008019998807885509)

НазадОткрыть во вкладке