Оптимизация и поиск корней (scipy.optimize)

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

Общие функции и объекты, используемые разными решателями:

show_options([solver, method, disp])	Показать документацию по дополнительным параметрам решателей оптимизации.
OptimizeResult	Представляет результат оптимизации.
OptimizeWarning	Общее предупреждение для scipy.optimize.

Оптимизация

Оптимизация скалярных функций

minimize_scalar(fun[, bracket, bounds, ...])

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

The minimize_scalar функция поддерживает следующие методы:

• minimize_scalar(method='brent')
• minimize_scalar(method=’bounded’)
• minimize_scalar(method=’golden’)

Локальная (многомерная) оптимизация

minimize(fun, x0[, args, method, jac, hess, ...])

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

The minimize функция поддерживает следующие методы:

• minimize(method='Nelder-Mead')
• minimize(method='Powell')
• minimize(method=’CG’)
• minimize(method=’BFGS’)
• minimize(method=’Newton-CG’)
• minimize(method=’L-BFGS-B’)
• minimize(method=’TNC’)
• minimize(method='COBYLA')
• minimize(method=’COBYQA’)
• minimize(method='SLSQP')
• minimize(method='trust-constr')
• minimize(method='dogleg')
• minimize(method='trust-ncg')
• minimize(method=’trust-krylov’)
• minimize(method='trust-exact')

Ограничения передаются в minimize функция как единый объект или как список объектов из следующих классов:

NonlinearConstraint(fun, lb, ub[, jac, ...])	Нелинейное ограничение на переменные.
LinearConstraint(A[, lb, ub, keep_feasible])	Линейное ограничение на переменные.

Простые ограничения в виде границ обрабатываются отдельно, и для них есть специальный класс:

Bounds([lb, ub, keep_feasible])

Ограничение на границы переменных.

Стратегии квази-Ньютона, реализующие HessianUpdateStrategy интерфейс может использоваться для аппроксимации гессиана в minimize функция (доступна только для метода 'trust-constr'). Доступные квази-ньютоновские методы, реализующие этот интерфейс:

BFGS([exception_strategy, min_curvature, ...])	Стратегия обновления гессиана Бройдена-Флетчера-Гольдфарба-Шанно (BFGS).
SR1([min_denominator, init_scale])	Стратегия обновления гессиана симметричного ранга 1.

Глобальная оптимизация

basinhopping(func, x0[, niter, T, stepsize, ...])	Найти глобальный минимум функции с помощью алгоритма basin-hopping.
brute(func, ranges[, args, Ns, full_output, ...])	Минимизировать функцию в заданном диапазоне методом грубой силы.
differential_evolution(func, bounds[, args, ...])	Находит глобальный минимум многомерной функции.
shgo(func, bounds[, args, constraints, n, ...])	Находит глобальный минимум функции с использованием оптимизации SHG.
dual_annealing(func, bounds[, args, ...])	Найти глобальный минимум функции с помощью двойного отжига.
direct(func, bounds, *[, args, eps, maxfun, ...])	Находит глобальный минимум функции с использованием алгоритма DIRECT.

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

Нелинейный метод наименьших квадратов

least_squares(fun, x0[, jac, bounds, ...])

Решить задачу нелинейных наименьших квадратов с ограничениями на переменные.

Линейный метод наименьших квадратов

nnls(A, b, *[, maxiter, atol])	Решить argmin_x || Ax - b ||_2 для x>=0.
lsq_linear(A, b[, bounds, method, tol, ...])	Решить задачу линейных наименьших квадратов с ограничениями на переменные.
isotonic_regression(y, *[, weights, increasing])	Непараметрическая изотоническая регрессия.

Аппроксимация кривой

curve_fit(f, xdata, ydata[, p0, sigma, ...])

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

Нахождение корней

Скалярные функции

root_scalar(f[, args, method, bracket, ...])	Найти корень скалярной функции.
brentq(f, a, b[, args, xtol, rtol, maxiter, ...])	Найти корень функции в интервале с использованием метода Брента.
brenth(f, a, b[, args, xtol, rtol, maxiter, ...])	Найти корень функции в интервале с использованием метода Брента с гиперболической экстраполяцией.
ridder(f, a, b[, args, xtol, rtol, maxiter, ...])	Найти корень функции на интервале с использованием метода Риддера.
bisect(f, a, b[, args, xtol, rtol, maxiter, ...])	Найти корень функции на интервале с использованием бисекции.
newton(func, x0[, fprime, args, tol, ...])	Найти корень вещественной или комплексной функции с использованием метода Ньютона-Рафсона (или метода секущих, или метода Халли).
toms748(f, a, b[, args, k, xtol, rtol, ...])	Найти корень с использованием метода TOMS Algorithm 748.
RootResults(корень, итерации, ...)	Представляет результат поиска корней.

The root_scalar функция поддерживает следующие методы:

• root_scalar(method='brentq')
• root_scalar(method='brenth')
• root_scalar(method='bisect')
• root_scalar(method='ridder')
• root_scalar(method='newton')
• root_scalar(method=’toms748’)
• root_scalar(method=’secant’)
• root_scalar(method='halley')

В таблице ниже перечислены ситуации и подходящие методы, вместе с асимптотический Скорости сходимости за итерацию (и за вычисление функции) для успешной сходимости к простому корню(*). Метод бисекции самый медленный из всех, добавляя один бит точности за каждое вычисление функции, но гарантированно сходится. Другие методы, использующие интервалы, все (в конечном итоге) увеличивают количество точных битов примерно на 50% за каждое вычисление функции. Методы, основанные на производных, все построены на newton, могут сходиться довольно быстро если начальное значение близко к корню. Они также могут быть применены к функциям, определенным на (подмножестве) комплексной плоскости.

Область определения f	Скобка?	Производные?		Решатели	Сходимость
		fprime	fprime2		Гарантировано?	Rate(s)(*)
R	Да	Н/Д	Н/Д	бисекция brentq brenth ridder toms748	Да Да Да Да Да	1 "Линейный" >=1, <= 1.62 >=1, <= 1.62 2.0 (1.41) 2.7 (1.65)
R или C	Нет	Нет	Нет	секанс	Нет	1.62 (1.62)
R или C	Нет	Да	Нет	newton	Нет	2.00 (1.41)
R или C	Нет	Да	Да	halley	Нет	3.00 (1.44)

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

scipy.optimize.cython_optimize – Типизированные версии функций поиска корней на Cython

Поиск неподвижной точки:

fixed_point(func, x0[, args, xtol, maxiter, ...])

Найти неподвижную точку функции.

Многомерный

root(fun, x0[, args, method, jac, tol, ...])

Найти корень векторной функции.

The root функция поддерживает следующие методы:

• root(method='hybr')
• root(method='lm')
• root(method=’broyden1’)
• root(method='broyden2')
• root(method='anderson')
• root(method='linearmixing')
• root(method=’diagbroyden’)
• root(method='excitingmixing')
• root(method=’krylov’)
• root(method='df-sane')

Поэлементная минимизация и поиск корней

• Поэлементная скалярная оптимизация (scipy.optimize.elementwise)
  • Нахождение корней
    • find_root
    • bracket_root
  • Минимизация
    • find_minimum
    • bracket_minimum

Линейное программирование / MILP

milp(c, *[, integrality, bounds, ...])	Смешанно-целочисленное линейное программирование
linprog(c[, A_ub, b_ub, A_eq, b_eq, bounds, ...])	Линейное программирование: минимизация линейной целевой функции при линейных ограничениях равенства и неравенства.

The linprog функция поддерживает следующие методы:

• linprog(method='simplex')
• linprog(method=’interior-point’)
• linprog(method='revised simplex')
• linprog(method=‘highs-ipm’)
• linprog(method='highs-ds')
• linprog(method=’highs’)

Методы симплекс, внутренней точки и модифицированного симплекса поддерживают функции обратного вызова, например:

linprog_verbose_callback(res)

Пример функции обратного вызова, демонстрирующей интерфейс обратного вызова linprog.

Задачи назначения

linear_sum_assignment	Решить задачу линейного назначения с минимальной суммой.
quadratic_assignment(A, B[, method, options])	Приближает решение задачи квадратичного назначения и задачи сопоставления графов.

The quadratic_assignment функция поддерживает следующие методы:

• quadratic_assignment(method='faq')
• quadratic_assignment(method=’2opt’)

Утилиты

Конечно-разностная аппроксимация

approx_fprime(xk, f[, epsilon])	Конечно-разностная аппроксимация производных скалярной или векторнозначной функции.
check_grad(func, grad, x0, *args[, epsilon, ...])	Проверка корректности функции градиента путем сравнения с (прямой) конечно-разностной аппроксимацией градиента.

Поиск по линии

bracket(func[, xa, xb, args, grow_limit, ...])	Ограничить минимум функции.
line_search(f, myfprime, xk, pk[, gfk, ...])	Найти альфа, удовлетворяющую строгим условиям Вульфа.

Аппроксимация гессиана

LbfgsInvHessProduct(*args, **kwargs)	Линейный оператор для приближенной обратной матрицы Гессе L-BFGS.
HessianUpdateStrategy()	Интерфейс для реализации стратегий обновления матрицы Гессе.

Тестовые задачи

rosen(x)	Функция Розенброка.
rosen_der(x)	Производная (т.е. градиент) функции Розенброка.
rosen_hess(x)	Матрица Гессе функции Розенброка.
rosen_hess_prod(x, p)	Произведение матрицы Гессе функции Розенброка на вектор.

Устаревшие функции

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

Оптимизация

Универсальные многомерные методы:

fmin(func, x0[, args, xtol, ftol, maxiter, ...])	Минимизация функции с использованием алгоритма симплексного спуска.
fmin_powell(func, x0[, args, xtol, ftol, ...])	Минимизировать функцию с использованием модифицированного метода Пауэлла.
fmin_cg(f, x0[, fprime, args, gtol, norm, ...])	Минимизировать функцию с использованием алгоритма нелинейного сопряжённого градиента.
fmin_bfgs(f, x0[, fprime, args, gtol, norm, ...])	Минимизируйте функцию с использованием алгоритма BFGS.
fmin_ncg(f, x0, fprime[, fhess_p, fhess, ...])	Безусловная минимизация функции с использованием метода Ньютона-КГ.

Многомерные методы с ограничениями:

fmin_l_bfgs_b(func, x0[, fprime, args, ...])	Минимизация функции func с использованием алгоритма L-BFGS-B.
fmin_tnc(func, x0[, fprime, args, ...])	Минимизировать функцию с переменными, ограниченными границами, используя информацию о градиенте в усеченном алгоритме Ньютона.
fmin_cobyla(func, x0, cons[, args, ...])	Минимизировать функцию с использованием метода Constrained Optimization By Linear Approximation (COBYLA).
fmin_slsqp(func, x0[, eqcons, f_eqcons, ...])	Минимизация функции с использованием последовательного программирования методом наименьших квадратов

Методы минимизации одномерных (скалярных) функций:

fminbound(func, x1, x2[, args, xtol, ...])	Ограниченная минимизация для скалярных функций.
brent(func[, args, brack, tol, full_output, ...])	Для заданной функции одной переменной и возможного интервала возвращает локальный минимизатор функции, изолированный с дробной точностью tol.
golden(func[, args, brack, tol, ...])	Возвращает минимизатор функции одной переменной с использованием метода золотого сечения.

Метод наименьших квадратов

leastsq(func, x0[, args, Dfun, full_output, ...])

Минимизировать сумму квадратов набора уравнений.

Нахождение корней

Общие нелинейные решатели:

fsolve(func, x0[, args, fprime, ...])	Найти корни функции.
broyden1(F, xin[, iter, alpha, ...])	Найти корень функции, используя первое приближение Якобиана Бройдена.
broyden2(F, xin[, iter, alpha, ...])	Найти корень функции, используя второе приближение Якобиана Бройдена.
NoConvergence	Исключение, возникающее при сбое нелинейного решателя сходиться в пределах указанного maxiter.

Крупномасштабные нелинейные решатели:

newton_krylov(F, xin[, iter, rdiff, method, ...])	Найти корень функции, используя приближение Крылова для обратной матрицы Якоби.
anderson(F, xin[, iter, alpha, w0, M, ...])	Найти корень функции, используя (расширенное) смешивание Андерсона.
BroydenFirst([alpha, reduction_method, max_rank])	Найти корень функции, используя первое приближение Якобиана Бройдена.
InverseJacobian(jacobian)	Простая обертка, которая инвертирует якобиан с использованием решить метод.
KrylovJacobian([rdiff, method, ...])	Найти корень функции, используя приближение Крылова для обратной матрицы Якоби.

Простые итерационные решатели:

excitingmixing(F, xin[, iter, alpha, ...])	Найти корень функции, используя настроенную диагональную аппроксимацию Якобиана.
linearmixing(F, xin[, iter, alpha, verbose, ...])	Найти корень функции, используя скалярную аппроксимацию Якобиана.
diagbroyden(F, xin[, iter, alpha, verbose, ...])	Найти корень функции, используя диагональную аппроксимацию Якобиана Бройдена.