Exponenta Banner

lsqnonneg

Решает неотрицательную линейную задачу методом наименьших квадратов

свернуть все на странице

Решает неотрицательную задачу аппроксимации методом наименьших квадратов вида

minx‖C⋅x−d‖22, где x≥0.

Примечание

lsqnonneg применяется только к основанному на решателе подходу. Для обсуждения двух подходов оптимизации смотрите, Сначала Выбирают Problem-Based or Solver-Based Approach.

Синтаксис

x = lsqnonneg(C,d)
x = lsqnonneg(C,d,options)
x = lsqnonneg(problem)
[x,resnorm,residual] = lsqnonneg(___)
[x,resnorm,residual,exitflag,output] = lsqnonneg(___)
[x,resnorm,residual,exitflag,output,lambda] = lsqnonneg(___)

Описание

пример

x = lsqnonneg(C,d) возвращает векторный x, который минимизирует norm(C*x-d), подвергающийся   x ≥ 0. Аргументы C и d должны быть действительными.

пример

x = lsqnonneg(C,d,options) минимизирует с опциями оптимизации, заданными в структуре options. Используйте optimset, чтобы установить эти опции.

x = lsqnonneg(problem) находит минимум для problem, где problem является структурой. Создайте аргумент problem путем экспорта проблемы из приложения Оптимизации, как описано в Экспорте работы.

пример

[x,resnorm,residual] = lsqnonneg(___), для любого предыдущего синтаксиса, дополнительно возвращает значение квадратичной нормы невязки, norm(C*x-d)^2, и возвращает остаточный d-C*x.

[x,resnorm,residual,exitflag,output] = lsqnonneg(___) дополнительно возвращает значение exitflag, который описывает выходное условие lsqnonneg и структуру output с информацией о процессе оптимизации.

пример

[x,resnorm,residual,exitflag,output,lambda] = lsqnonneg(___) дополнительно возвращает вектор множителей Лагранжа lambda.

Примеры

свернуть все

Скрипт Open Live Script

Найдем неотрицательное решение линейной задачи методом наименьших квадратов и сравним результат с решением задачи без ограничений.

Подготовим матрицу C и вектор d для задачи min||Cx-d||.

C = [0.0372    0.2869
     0.6861    0.7071
     0.6233    0.6245
     0.6344    0.6170];
 
d = [0.8587
     0.1781
     0.0747
     0.8405];

Вычислите ограниченные и неограниченные решения.

x = lsqnonneg(C,d)
x = 2×1

         0
    0.6929


xunc = C\d
xunc = 2×1

   -2.5627
    3.1108

Все записи в x являются неотрицательными, но некоторые записи в xunc отрицательны.

Вычислите нормы невязок для этих двух решений.

constrained_norm = norm(C*x - d)
constrained_norm = 0.9118

unconstrained_norm = norm(C*xunc - d)
unconstrained_norm = 0.6674

Неограниченное решение имеет меньшую норму невязки, потому что ограничения могут только увеличить норму невязки.

Скрипт Open Live Script

Установите опцию Display на 'final' видеть вывод, когда lsqnonneg закончится.

Создайте опции.

options = optimset('Display','final');

Подготовим матрицу C и вектор d для задачи min||Cx-d||.

C = [0.0372    0.2869
     0.6861    0.7071
     0.6233    0.6245
     0.6344    0.6170];

d = [0.8587
     0.1781
     0.0747
     0.8405];

Вызовите lsqnonneg со структурой опций.

x = lsqnonneg(C,d,options);
Optimization terminated.
Скрипт Open Live Script

Вызовите lsqnonneg с выходными параметрами, чтобы получить решение, норму невязки и вектор невязок.

Подготовим матрицу C и вектор d для задачи min||Cx-d||.

C = [0.0372    0.2869
     0.6861    0.7071
     0.6233    0.6245
     0.6344    0.6170];

d = [0.8587
     0.1781
     0.0747
     0.8405];

Получите решение и остаточную информацию.

 [x,resnorm,residual] = lsqnonneg(C,d)
x = 2×1

         0
    0.6929


resnorm = 0.8315

residual = 4×1

    0.6599
   -0.3119
   -0.3580
    0.4130

Проверьте, что возвращенная норма невязки является квадратом нормы возвращенного вектора невязок.

 norm(residual)^2
ans = 0.8315
Скрипт Open Live Script

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

Подготовим матрицу C и вектор d для задачи min||Cx-d||.

C = [0.0372    0.2869
     0.6861    0.7071
     0.6233    0.6245
     0.6344    0.6170];

d = [0.8587
     0.1781
     0.0747
     0.8405];

Решите проблему, запросив все выходные аргументы.

[x,resnorm,residual,exitflag,output,lambda] = lsqnonneg(C,d)
x = 2×1

         0
    0.6929


resnorm = 0.8315

residual = 4×1

    0.6599
   -0.3119
   -0.3580
    0.4130


exitflag = 1

output = struct with fields:
    iterations: 1
     algorithm: 'active-set'
       message: 'Optimization terminated.'


lambda = 2×1

   -0.1506
   -0.0000

exitflag является 1, указывая на правильное решение.

x(1) = 0 и соответствующий lambda(1) ≠ 0, правильно указывая на двойственность. Точно так же x(2) > 0 и соответствующий lambda(2) = 0.

Входные параметры

свернуть все

Линейный множитель, заданный как действительная матрица. Представляет переменную C в задаче

minx‖Cx−d‖22.

Для совместимости количество строк C должно равняться длине d.

Пример: C = [1,2;3,-1;-4,4]

Типы данных: double

Вектор свободных членов, заданный как вектор действительных чисел. Представляет переменную d в задаче

minx‖Cx−d‖22.

Для совместимости длина d должна равняться количеству строк C.

Пример: d = [1;-6;5]

Типы данных: double

Опции оптимизации, заданные как структура, такие как optimset, возвращаются. Можно использовать optimset, чтобы установить или изменить значения этих полей в структуре опций. Дополнительную информацию см. в Ссылке Опций Оптимизации.

Display

Уровень отображения:

  • 'notify' (значение по умолчанию) отображает вывод, только если функция не сходится.

  • 'off' или 'none' не отображают вывода.

  • 'final' отображает только окончательный вывод.

TolX

Допуск завершения на x, положительной скалярной величине. Значением по умолчанию является 10*eps*norm(C,1)*length(C). Смотрите Допуски и Критерий остановки.

Пример: options = optimset('Display','final')

Типы данных: struct

Структура задачи, заданная как структура со следующими полями.

Имя поляЗапись

C

Действительная матрица

d

Вектор действительных чисел

solver

'lsqnonneg'

options

Структура опций такой, как возвращено optimset

Самым простым способом получить структуру problem является экспорт задачи из Optimization app.

Типы данных: struct

Выходные аргументы

свернуть все

Решение, возвращенное как вектор действительных чисел. Длина x совпадает с длиной d.

Квадрат нормы невязки, возвращенный как неотрицательный скаляр. Равный norm(C*x-d)^2.

Невязка, возвращенная как вектор действительных чисел. Невязкой является   d - C*x.

Причина остановки lsqnonneg, возвращается как целое число.

1

Функция сходилась к решению x.

0

Количество итераций превысило options.MaxIter.

Информация о процессе оптимизации, возвращенном как структура с полями:

iterations

Количество проделанных итераций

algorithm

'active-set'

message

Выходное сообщение

Множители Лагранжа, возвращенные как вектор действительных чисел. Записи удовлетворяют условие взаимозависимости x'*lambda = 0. Это означает lambda(i) < 0, когда x(i) является приблизительно 0, и lambda(i) является приблизительно 0 когда x(i) > 0.

Советы

  • Для проблем, где d имеет длину более чем 20, lsqlin может быть быстрее, чем lsqnonneg. Когда d имеет длину под 20, lsqnonneg обычно более эффективен.

    Преобразовывать между решателями, когда C имеет больше строк, чем столбцы (значение системы сверхопределяется),

    [x,resnorm,residual,exitflag,output,lambda] = lsqnonneg(C,d)

    эквивалентно

    [m,n] = size(C);
[x,resnorm,residual,exitflag,output,lambda_lsqlin] = ...
   lsqlin(C,d,-eye(n,n),zeros(n,1));

    Единственная разница - то, что соответствующие множители Лагранжа имеют противоположные знаки: lambda = -lambda_lsqlin.ineqlin.

Алгоритмы

lsqnonneg использует алгоритм, описанный в [1]. Алгоритм запускается с набора возможных базисных векторов и вычисляет связанный двойной векторный lambda. Это затем выбирает базисный вектор, соответствующий максимальному значению в lambda, чтобы заменить его в базисе на другой возможный кандидат. Это продолжается до   lambda ≤ 0.

Ссылки

[1] Лоусон, C. L. и Р. Дж. Хэнсон. Решение задач наименьших квадратов. Верхний Сэддл-Ривер, NJ: Prentice Hall. 1974. Глава 23, p. 161.

Расширенные возможности

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

| | |

Представлено до R2006a

Документация Optimization Toolbox
Поддержка