Exponenta Banner
exponenta event banner

lsqnonneg

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

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

Синтаксис

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(___)

Описание

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

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

Примечание

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.

пример

[x,resnorm,residual] = lsqnonneg(___), для любого предыдущего синтаксиса, дополнительно возвращает значение квадратичной 2-нормы невязки, 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.

Примеры

свернуть все

Открыть 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

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

Открыть 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.
Открыть 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
Открыть 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

Level of 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

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

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

свернуть все

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

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

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

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

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.

Альтернативная функциональность

Приложение

Задача Optimize Live Editor обеспечивает визуальный интерфейс для lsqnonneg.

Ссылки

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

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

.

См. также

| | |

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

Документация по Optimization Toolbox

Поддержка