scipy.optimize.

lsq_linear#

scipy.optimize.lsq_linear(A, b, границы=(-inf, inf), метод='trf', tol=1e-10, lsq_solver=None, lsmr_tol=None, max_iter=None, verbose=0, *, lsmr_maxiter=None)[источник]#

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

Дана матрица плана A размером m на n и целевой вектор b с m элементами, lsq_linear решает следующую задачу оптимизации:

minimize 0.5 * ||A x - b||**2
subject to lb <= x <= ub

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

Параметры:
Aarray_like, разреженный массив или LinearOperator, форма (m, n)

Матрица плана. Может быть scipy.sparse.linalg.LinearOperator.

barray_like, shape (m,)

Вектор целевых значений.

границы2-кортеж из array_like или Bounds, опционально

Нижние и верхние границы параметров. По умолчанию границы не заданы. Есть два способа указать границы:

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

  • 2-кортеж из array_like: Каждый элемент кортежа должен быть либо массивом с длиной, равной количеству параметров, либо скаляром (в этом случае граница считается одинаковой для всех параметров). Используйте np.inf с соответствующим знаком для отключения ограничений на все или некоторые параметры.

метод'trf' или 'bvls', опционально

Метод выполнения минимизации.

  • ‘trf’ : Алгоритм Trust Region Reflective, адаптированный для линейной задачи наименьших квадратов. Это метод, подобный внутренней точке, и требуемое количество итераций слабо коррелирует с количеством переменных.

  • ‘bvls’ : Алгоритм наименьших квадратов с ограниченными переменными. Это метод активного множества, требующий количества итераций, сравнимого с количеством переменных. Не может использоваться, когда A является разреженной или LinearOperator.

По умолчанию 'trf'.

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

Параметр допуска. Алгоритм завершается, если относительное изменение функции стоимости меньше tol на последней итерации. Кроме того, рассматривается мера оптимальности первого порядка:

  • method='trf' завершается, если равномерная норма градиента, масштабированная с учетом наличия границ, меньше tol.

  • method='bvls' завершается, если условия Каруша-Куна-Такера выполнены в пределах tol допуск.

lsq_solver{None, 'exact', 'lsmr'}, необязательный

Метод решения неограниченных задач наименьших квадратов на протяжении итераций:

  • ‘exact’ : Использовать подход плотного QR или SVD разложения. Не может использоваться, когда A является разреженной или LinearOperator.

  • ‘lsmr’ : Использовать scipy.sparse.linalg.lsmr итеративная процедура, которая требует только вычислений матрично-векторных произведений. Не может использоваться с method='bvls'.

Если None (по умолчанию), решатель выбирается на основе типа A.

lsmr_tolNone, float или 'auto', опционально

Параметры допуска 'atol' и 'btol' для scipy.sparse.linalg.lsmr Если None (по умолчанию), устанавливается в 1e-2 * tol. Если 'auto', допуск будет автоматически настроен на основе оптимальности текущей итерации, что может ускорить процесс оптимизации, но не всегда надежно.

max_iterNone или int, опционально

Максимальное количество итераций до завершения. Если None (по умолчанию), устанавливается в 100 для method='trf' или к количеству переменных для method='bvls' (не считая итераций для инициализации 'bvls').

verbose{0, 1, 2}, опционально

Уровень детализации алгоритма:

  • 0 : работать без вывода (по умолчанию).

  • 1 : отобразить отчет о завершении.

  • 2 : отображать прогресс во время итераций.

lsmr_maxiterNone или int, опционально

Максимальное количество итераций для решателя наименьших квадратов lsmr, если он используется (путем установки lsq_solver='lsmr'). Если None (по умолчанию), он использует стандартное значение lsmr, равное min(m, n) где m и n являются количеством строк и столбцов A, соответственно. Не оказывает эффекта, если lsq_solver='exact'.

Возвращает:
OptimizeResult со следующими определёнными полями:
xndarray, форма (n,)

Решение найдено.

стоимостьfloat

Значение целевой функции в решении.

funndarray, форма (m,)

Вектор невязок в решении.

оптимальностьfloat

Мера оптимальности первого порядка. Точное значение зависит от метод, см. описание tol параметр.

active_maskndarray из int, форма (n,)

Каждый компонент показывает, активен ли соответствующий ограничение (то есть, находится ли переменная на границе):

  • 0 : ограничение не активно.

  • -1: активна нижняя граница.

  • 1 : верхняя граница активна.

Может быть несколько произвольным для trf метод, так как он генерирует последовательность строго допустимых итераций, а active_mask определяется в пределах порога допуска.

unbounded_solкортеж

Неограниченный кортеж решения методом наименьших квадратов, возвращаемый решателем наименьших квадратов (устанавливается с помощью lsq_solver опция). Если lsq_solver не установлен или установлен в 'exact', кортеж содержит ndarray формы (n,) с неограниченным решением, ndarray с суммой квадратов остатков, int с рангом A, и ndarray с сингулярными значениями для A (см. NumPy linalg.lstsq для дополнительной информации). Если lsq_solver установлено в 'lsmr', кортеж содержит ndarray формы (n,) с неограниченным решением, int с кодом выхода, int с количеством итераций и пять float с различными нормами и числом обусловленности A (см. SciPy's sparse.linalg.lsmr для получения дополнительной информации). Этот вывод может быть полезен для определения сходимости метода наименьших квадратов, особенно итеративного 'lsmr' решатель. Неограниченная задача наименьших квадратов заключается в минимизации 0.5 * ||A x - b||**2.

nitint

Количество итераций. Ноль, если неограниченное решение оптимально.

statusint

Причина завершения алгоритма:

  • -1 : алгоритм не смог продвинуться на последней итерации.

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

  • 1 : мера оптимальности первого порядка меньше, чем tol.

  • 2 : относительное изменение функции стоимости меньше, чем tol.

  • 3 : неограниченное решение является оптимальным.

messagestr

Словесное описание причины завершения.

successbool

True, если выполнено одно из условий сходимости (status > 0).

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

nnls

Линейный метод наименьших квадратов с ограничением неотрицательности.

least_squares

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

Примечания

Алгоритм сначала вычисляет неограниченное решение методом наименьших квадратов с помощью numpy.linalg.lstsq или scipy.sparse.linalg.lsmr в зависимости от lsq_solver. Это решение возвращается как оптимальное, если оно лежит в пределах границ.

Метод 'trf' запускает адаптацию алгоритма, описанного в [STIR] для задачи линейного метода наименьших квадратов. Итерации по сути те же, что и в алгоритме нелинейного метода наименьших квадратов, но поскольку квадратичная модель функции всегда точна, нам не нужно отслеживать или изменять радиус доверительной области. Линейный поиск (backtracking) используется как страховка, когда выбранный шаг не уменьшает целевую функцию. Подробнее читайте описание алгоритма в scipy.optimize.least_squares.

Метод 'bvls' запускает реализацию алгоритма на Python, описанного в [BVLS]. Алгоритм поддерживает активные и свободные наборы переменных, на каждой итерации выбирает новую переменную для перемещения из активного набора в свободный набор, а затем решает задачу неограниченных наименьших квадратов на свободных переменных. Этот алгоритм гарантированно дает точное решение в конечном итоге, но может потребовать до n итераций для задачи с n переменными. Дополнительно реализована специальная процедура инициализации, которая определяет, какие переменные установить свободными или активными изначально. Это занимает некоторое количество итераций до фактического начала BVLS, но может значительно сократить количество последующих итераций.

Ссылки

[STIR]

M. A. Branch, T. F. Coleman, and Y. Li, "A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems," SIAM Journal on Scientific Computing, Vol. 21, Number 1, pp 1-23, 1999.

[BVLS]

П. Б. Старт и Р. Л. Паркер, "Метод наименьших квадратов с ограниченными переменными: алгоритм и приложения", Computational Statistics, 10, 129-141, 1995.

Примеры

В этом примере решается задача с большими разреженными массивами и ограничениями на переменные.

>>> import numpy as np
>>> from scipy.sparse import random_array
>>> from scipy.optimize import lsq_linear
>>> rng = np.random.default_rng()
...
>>> m = 2000
>>> n = 1000
...
>>> A = random_array((m, n), density=1e-4, random_state=rng)
>>> b = rng.standard_normal(m)
...
>>> lb = rng.standard_normal(n)
>>> ub = lb + 1
...
>>> res = lsq_linear(A, b, bounds=(lb, ub), lsmr_tol='auto', verbose=1)
The relative change of the cost function is less than `tol`.
Number of iterations 10, initial cost 1.0070e+03, final cost 9.6602e+02,
first-order optimality 2.21e-09.        # may vary
На этой странице