lsqlin

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

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

Синтаксис

x = lsqlin(C,d,A,b)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)
x = lsqlin(problem)
[x,resnorm,residual,exitflag,output,lambda] = lsqlin(___)

Описание

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

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

minx12‖C⋅x−d‖22 таким образом , что {A⋅x≤b,Aeq⋅x=beq,lb≤x≤ub.

Примечание

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

пример

x = lsqlin(C,d,A,b) решает линейную систему   C*x = d в наименьших квадратах распознаются согласно A*x ≤ b.

пример

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub) добавляют линейные ограничения равенства   Aeq*x = beq и границы lb ≤ x ≤ ub. Если вам не нужны определенные ограничения, такие как Aeq и beq, установите их на []. Если x(i) неограниченно ниже, установите lb(i) = -Inf, и если x(i) неограниченно выше, установите ub(i) = Inf.

пример

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options) минимизирует с начальной точкой x0 и опции оптимизации заданы в options. Используйте optimoptions установить эти опции. Если вы не хотите включать начальную точку, установите x0 аргумент к [].

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

пример

[x,resnorm,residual,exitflag,output,lambda] = lsqlin(___), для любых входных параметров, описанных выше, возвращается:

  • Квадратичная норма остаточного  resnorm = ‖C⋅x−d‖22

  • Остаточный   residual = C*x - d

  • Значение exitflag описание выходного условия

  • Структура output содержа информацию о процессе оптимизации

  • Структура lambda содержа множители Лагранжа

    Фактор ½ в определении проблемы влияет на значения в lambda структура.

Примеры

свернуть все

Скрипт Open Live Script

Найдите x это минимизирует норму C*x - d для сверхрешительной проблемы с линейными ограничениями неравенства.

Задайте проблему и ограничения. 

C = [0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A = [0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b = [0.5251
    0.2026
    0.6721];

Вызовите lsqlin решать задачу. 

x = lsqlin(C,d,A,b)
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

x = 4×1

    0.1299
   -0.5757
    0.4251
    0.2438
Скрипт Open Live Script

Найдите x это минимизирует норму C*x - d для сверхрешительной проблемы с линейным равенством и ограничениями неравенства и границами.

Задайте проблему и ограничения. 

C = [0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A =[0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b =[0.5251
    0.2026
    0.6721];
Aeq = [3 5 7 9];
beq = 4;
lb = -0.1*ones(4,1);
ub = 2*ones(4,1);

Вызовите lsqlin решать задачу. 

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub)
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

x = 4×1

   -0.1000
   -0.1000
    0.1599
    0.4090
Скрипт Open Live Script

В этом примере показано, как использовать опции не по умолчанию в линейном методе наименьших квадратов.

Установите опции использовать 'interior-point' алгоритм и дать итеративное отображение.

options = optimoptions('lsqlin','Algorithm','interior-point','Display','iter');

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

C = [0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A = [0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b = [0.5251
    0.2026
    0.6721];

Запустите проблему.

x = lsqlin(C,d,A,b,[],[],[],[],[],options)
 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0   -7.687420e-02   1.600492e+00   6.150431e-01     1.000000e+00  
    1   -7.687419e-02   8.002458e-04   3.075216e-04     2.430833e-01  
    2   -3.162837e-01   4.001229e-07   1.537608e-07     5.945636e-02  
    3   -3.760545e-01   2.000616e-10   2.036997e-08     1.370933e-02  
    4   -3.912129e-01   1.000866e-13   1.006816e-08     2.548273e-03  
    5   -3.948062e-01   2.220446e-16   2.955102e-09     4.295807e-04  
    6   -3.953277e-01   2.775558e-17   1.237758e-09     3.102850e-05  
    7   -3.953581e-01   2.775558e-17   1.645862e-10     1.138719e-07  
    8   -3.953582e-01   2.775558e-17   2.399608e-13     5.693290e-11  

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

x = 4×1

    0.1299
   -0.5757
    0.4251
    0.2438
Скрипт Open Live Script

Получите и интерпретируйте весь lsqlin выходные параметры .

Опишите задачу с линейными ограничениями неравенства и границами. Проблема сверхопределяется, потому что существует четыре столбца в C матрица, но пять строк. Это означает, что проблема имеет четыре неизвестные и пять условий, даже прежде включая линейные ограничения и границы. 

C = [0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A = [0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b = [0.5251
    0.2026
    0.6721];
lb = -0.1*ones(4,1);
ub = 2*ones(4,1);

Установите опции использовать 'interior-point' алгоритм. 

options = optimoptions('lsqlin','Algorithm','interior-point');

'interior-point' алгоритм не использует начальную точку, таким образом, устанавливает x0 к []. 

x0 = [];

Вызовите lsqlin со всеми выходными параметрами. 

[x,resnorm,residual,exitflag,output,lambda] = ...
    lsqlin(C,d,A,b,[],[],lb,ub,x0,options)
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

x = 4×1

   -0.1000
   -0.1000
    0.2152
    0.3502


resnorm = 0.1672

residual = 5×1

    0.0455
    0.0764
   -0.3562
    0.1620
    0.0784


exitflag = 1

output = struct with fields:
            message: '...'
          algorithm: 'interior-point'
      firstorderopt: 4.3374e-11
    constrviolation: 0
         iterations: 6
       linearsolver: 'dense'
       cgiterations: []


lambda = struct with fields:
    ineqlin: [3x1 double]
      eqlin: [0x1 double]
      lower: [4x1 double]
      upper: [4x1 double]

Исследуйте ненулевые поля множителя Лагранжа более подробно. Сначала исследуйте множители Лагранжа на линейное ограничение неравенства.

lambda.ineqlin
ans = 3×1

    0.0000
    0.2392
    0.0000

Множители Лагранжа являются ненулевыми точно, когда решение находится на соответствующей границе ограничений. Другими словами, множители Лагранжа являются ненулевыми, когда соответствующее ограничение активно. lambda.ineqlin(2) является ненулевым. Это означает что второй элемент в A*x должен равняться второму элементу в b, потому что ограничение активно.

[A(2,:)*x,b(2)]
ans = 1×2

    0.2026    0.2026

Теперь исследуйте множители Лагранжа на ограничения нижней и верхней границы.

lambda.lower
ans = 4×1

    0.0409
    0.2784
    0.0000
    0.0000


lambda.upper
ans = 4×1

     0
     0
     0
     0

Первые два элемента lambda.lower являются ненулевыми. Вы видите тот x(1) и x(2) в их нижних границах, -0.1. Все элементы lambda.upper по существу нуль, и вы видите что все компоненты x меньше их верхней границы, 2.

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

свернуть все

Матрица множителя, заданная как матрица, удваивается. C представляет множитель решения x в выражении C*x - dC M- N, где M количество уравнений и N число элементов x.

Пример: C = [1,4;2,5;7,8]

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

Постоянный вектор, заданный как вектор, удваивается. d представляет термин аддитивной постоянной в выражении C*x - dD M- 1, где M количество уравнений.

Пример: d = [5;0;-12]

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

Линейная матрица ограничения неравенства, заданная как матрица, удваивается. A представляет линейные коэффициенты в ограничениях A*x ≤ bA имеет размер Mineq- N, где Mineq количество ограничений и N число элементов x. Чтобы сохранить память, передайте A как разреженная матрица.

Пример: A = [4,3;2,0;4,-1]; средние значения три линейных неравенства (три строки) для двух переменных решения (два столбца).

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

Линейный вектор ограничения неравенства, заданный как вектор, удваивается. b представляет постоянный вектор в ограничениях A*x ≤ bB имеет длину Mineq, где A Mineq- N.

Пример: [4,0]

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

Линейная матрица ограничения равенства, заданная как матрица, удваивается. Aeq представляет линейные коэффициенты в ограничениях Aeq*x = beq. Aeq имеет размер Meq- N, где Meq количество ограничений и N число элементов x. Чтобы сохранить память, передайте Aeq как разреженная матрица.

Пример: A = [4,3;2,0;4,-1]; средние значения три линейных неравенства (три строки) для двух переменных решения (два столбца).

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

Линейный вектор ограничения равенства, заданный как вектор, удваивается. beq представляет постоянный вектор в ограничениях Aeq*x = beq. beq имеет длину Meq, где Aeq Meq- N.

Пример: [4,0]

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

Нижние границы, заданные как вектор или массив, удваиваются. lb представляет нижние границы поэлементно в lb ≤ x ≤ ub.

Внутренне, lsqlin преобразует массив lb к векторному lb(:).

Пример: lb = [0;-Inf;4] средние значения x(1) ≥ 0, x(3) ≥ 4.

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

Верхние границы, заданные как вектор или массив, удваиваются. ub представляет верхние границы поэлементно в lb ≤ x ≤ ub.

Внутренне, lsqlin преобразует массив ub к векторному ub(:).

Пример: ub = [Inf;4;10] средние значения x(2) ≤ 4, x(3) ≤ 10.

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

Начальная точка для процесса решения, заданного как вектор или массив, удваивается. x0 используется только 'trust-region-reflective' алгоритм. Дополнительный.

Если вы не обеспечиваете x0 для 'trust-region-reflective' алгоритм, lsqlin наборы x0 к нулевому вектору. Если любой компонент этого нулевого векторного x0 нарушает границы, lsqlin наборы x0 к точке во внутренней части поля, заданного границами.

Пример: x0 = [4;-3]

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

Опции для lsqlin, заданный как выход optimoptions функционируйте или приложение Оптимизации.

Некоторые опции отсутствуют в optimoptions отображение. Эти опции появляются курсивом в следующей таблице. Для получения дополнительной информации, Опции вида на море.

Все алгоритмы

Algorithm

Выберите алгоритм:

  • 'interior-point' (значение по умолчанию)

  • 'trust-region-reflective'

'trust-region-reflective' алгоритм позволяет только верхние и нижние границы, не означая линейных неравенств или равенств. Если вы задаете обоих 'trust-region-reflective' и линейные ограничения, lsqlin использует 'interior-point' алгоритм.

'trust-region-reflective' алгоритм не позволяет равные верхние и нижние границы.

Когда проблема не имеет никаких ограничений, внутренне lsqlin вызовы mldivide.

Для получения дополнительной информации о выборе алгоритма смотрите Выбор Algorithm.

Диагностика

Отобразите диагностическую информацию о функции, которая будет минимизирована или решена. Выбором является 'on' или 'off' по умолчанию.

Display

Level of display возвращен в командную строку.

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

  • 'final' отображения только окончательный результат (значение по умолчанию).

'interior-point' алгоритм позволяет дополнительные значения:

  • 'iter' дает итеративное отображение.

  • 'iter-detailed' дает итеративное отображение с подробным выходным сообщением.

  • 'final-detailed' отображения только окончательный результат, с подробным выходным сообщением.

MaxIterations

Максимальное количество позволенных итераций, положительное целое число. Значением по умолчанию является 200.

Для optimset, именем является MaxIter. См. текущие и устаревшие таблицы имени опции.

trust-region-reflective Опции алгоритма

FunctionTolerance

Допуск завершения на значении функции, положительной скалярной величине. Значением по умолчанию является 100*eps, о 2.2204e-14.

Для optimset, именем является TolFun. См. текущие и устаревшие таблицы имени опции.

JacobianMultiplyFcn

Якобиан умножает функцию, определенный функцией указатель. Для крупномасштабных структурированных проблем эта функция должна вычислить якобиевское матричное произведение C*Y, C'*Y, или C'*(C*Y) на самом деле не формируя C. Напишите функцию в форме

W = jmfun(Jinfo,Y,flag)

где Jinfo содержит матрицу, использованную для расчета C*Y (или C'*Y, или C'*(C*Y)).

jmfun должен вычислить один из трех различных продуктов, в зависимости от значения flag тот lsqlin передачи:

  • Если flag == 0 затем   W = C'*(C*Y).

  • Если flag > 0 затем W = C*Y.

  • Если flag < 0 затем W = C'*Y.

В каждом случае, jmfun не должен формировать C явным образом. lsqlin использование Jinfo вычислить предварительный формирователь. Смотрите Передающие Дополнительные Параметры для получения информации о том, как предоставить дополнительные параметры при необходимости.

Смотрите, что якобиан Умножает Функцию с Линейным методом наименьших квадратов для примера.

Для optimset, именем является JacobMult. См. текущие и устаревшие таблицы имени опции.

MaxPCGIter

Максимальное количество PCG (предобусловленный метод сопряженных градиентов) итерации, положительная скалярная величина. Значением по умолчанию является max(1,floor(numberOfVariables/2)). Для получения дополнительной информации смотрите Доверительную область Отражающий Алгоритм.

OptimalityTolerance

Допуск завершения на оптимальности первого порядка, положительной скалярной величине. Значением по умолчанию является 100*eps, о 2.2204e-14. Смотрите, что оптимальность первого порядка измеряется.

Для optimset, именем является TolFun. См. текущие и устаревшие таблицы имени опции.

PrecondBandWidth

Верхняя пропускная способность предварительного формирователя для PCG (предобусловленный метод сопряженных градиентов). По умолчанию диагональное предварительное создание условий используется (верхняя пропускная способность 0). Для некоторых проблем, увеличивая пропускную способность сокращает количество итераций PCG. Установка PrecondBandWidth к Inf использует прямую факторизацию (Холесский), а не методы сопряженных градиентов (CG). Прямая факторизация является в вычислительном отношении более дорогой, чем CG, но производит лучший качественный шаг к решению. Для получения дополнительной информации смотрите Доверительную область Отражающий Алгоритм.

SubproblemAlgorithm

Определяет, как шаг итерации вычисляется. Значение по умолчанию, 'cg', делает более быстрый, но менее точный шаг, чем 'factorization'. Смотрите доверительную область отражающие наименьшие квадраты.

TolPCG

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

TypicalX

Типичный x значения. Число элементов в TypicalX равно количеству переменных. Значением по умолчанию является ones(numberofvariables,1). lsqlin использование TypicalX внутренне для масштабирования. TypicalX оказывает влияние только когда x имеет неограниченные компоненты, и когда TypicalX значение для неограниченного компонента больше, чем 1.

interior-point Опции алгоритма

ConstraintTolerance

Допуск на ограничительном нарушении, положительной скалярной величине. Значением по умолчанию является 1e-8.

Для optimset, именем является TolCon. См. текущие и устаревшие таблицы имени опции.

LinearSolver

Тип внутреннего линейного решателя в алгоритме:

  • 'auto' (значение по умолчанию) — использует 'sparse' если C матрица разреженна, 'dense' в противном случае.

  • 'sparse' — Используйте линейную алгебру для разреженных матриц. Смотрите Разреженные матрицы (MATLAB).

  • 'dense' — Используйте плотную линейную алгебру.

OptimalityTolerance

Допуск завершения на оптимальности первого порядка, положительной скалярной величине. Значением по умолчанию является 1e-8. Смотрите, что оптимальность первого порядка измеряется.

Для optimset, именем является TolFun. См. текущие и устаревшие таблицы имени опции.

StepTolerance

Допуск завершения на x, положительная скалярная величина. Значением по умолчанию является 1e-12.

Для optimset, именем является TolX. См. текущие и устаревшие таблицы имени опции.

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

C

Матричный множитель в термине C*x - d

d

Аддитивная постоянная в термине C*x - d

Aineq

Матрица для линейных ограничений неравенства

bineq

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

Aeq

Матрица для линейных ограничений равенства

beq

Вектор для линейных ограничений равенства
lbВектор нижних границ
ubВектор верхних границ

x0

Начальная точка для x

solver

'lsqlin'

options

Опции создаются с optimoptions

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

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

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

свернуть все

Решение, возвращенное как вектор, который минимизирует норму C*x-d подвергните всем границам и линейным ограничениям.

Объективное значение, возвращенное как скалярное значение norm(C*x-d)^2.

Остаточные значения решения, возвращенные как векторный C*x-d.

Алгоритм, останавливающий условие, возвращенное как целое число, идентифицирующее причину остановленный алгоритм. Следующие списки значения exitflag и соответствующие причины lsqlin остановленный.

3

Изменение в невязке было меньшим, чем заданный допуск options.FunctionTolerance. (trust-region-reflective алгоритм)

2

Размер шага, меньший, чем options.StepTolerance, ограничениям удовлетворяют. (interior-point алгоритм)

1

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

0

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

-2

Проблема неосуществима. Или, для interior-point алгоритм, размер шага, меньший, чем options.StepTolerance, но ограничениям не удовлетворяют.

-3Проблема неограниченна.

-4

Плохо создание условий предотвращает дальнейшую оптимизацию.

-8

Не мог вычислить направление шага.

Выходное сообщение для interior-point алгоритм может предоставить больше подробную информацию на причине lsqlin остановленный, такие как превышение допуска. Смотрите Выходные Флаги и Выходные сообщения.

Сводные данные процесса решения, возвращенные как структура, содержащая информацию о процессе оптимизации.

iterations

Количество итераций решатель взяло.

algorithm

Один из этих алгоритмов:

  • 'interior-point'

  • 'trust-region-reflective'

  • 'mldivide' для неограниченной проблемы

Для неограниченной проблемы, iterations = 0, и остающиеся записи в output структура пуста.

constrviolation

Ограничительное нарушение, которое положительно для нарушенных ограничений (не возвращенный для 'trust-region-reflective' алгоритм).

constrviolation = max([0;norm(Aeq*x-beq, inf);(lb-x);(x-ub);(A*x-b)])

message

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

firstorderopt

Оптимальность первого порядка в решении. Смотрите Меру по Оптимальности Первого порядка.

linearsolver

Тип внутреннего линейного решателя, 'dense' или 'sparse' ('interior-point' только алгоритм)

cgiterations

Количество итераций метода сопряженных градиентов решатель выполняется. Непустой только для 'trust-region-reflective' алгоритм.

Смотрите структуры output.

Множители Лагранжа, возвращенные как структура со следующими полями.

lower

Нижние границы lb

upper

Верхние границы ub

ineqlin

Линейные неравенства

eqlin

Линейные равенства

Смотрите структуры множителя Лагранжа.

Советы

  • Для проблем без ограничений можно использовать mldivide (матричное левое деление). Когда у вас нет ограничений, lsqlin возвращает   x = C\d.

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

  • Лучше числовые результаты вероятны, если вы задаете равенства явным образом, с помощью Aeq и beq, вместо неявно, с помощью lb и ub.

  • trust-region-reflective алгоритм не позволяет равные верхние и нижние границы. Используйте другой алгоритм в этом случае.

  • Если заданные входные границы для проблемы противоречивы, выход x x0 и выходные параметры resnorm и residual [].

  • Можно решить некоторые большие структурированные задачи, включая тех где C матрица является слишком большой, чтобы уместиться в памяти, с помощью trust-region-reflective алгоритм с якобианом умножает функцию. Для получения информации смотрите доверительную область отражающие Опции Алгоритма.

Алгоритмы

свернуть все

Доверительная область отражающий алгоритм

Этот метод является методом доверительной области подпространства на основе внутреннего отражающего метода Ньютона, описанного в [1]. Каждая итерация включает приближенное решение большой линейной системы с помощью метода предобусловленных методов сопряженных градиентов (PCG). Смотрите Доверительную область Отражающие Наименьшие квадраты, и в конкретном Крупномасштабном Линейном методе наименьших квадратов.

Алгоритм внутренней точки

'interior-point' алгоритм основан на quadprog 'interior-point-convex' алгоритм. Смотрите Линейный метод наименьших квадратов Внутренней точки.

Ссылки

[1] Коулман, T. F. и И. Ли. “Отражающий Метод Ньютона для Минимизации Квадратичной Функции Согласно Границам на Некоторых Переменных”, SIAM Journal на Оптимизации, Издании 6, Номере 4, стр 1040–1058, 1996.

[2] Жабры, P. E. В. Мюррей и М. Х. Райт. Практическая оптимизация, Academic Press, Лондон, Великобритания, 1981.

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

| | |

Темы

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

Документация Optimization Toolbox
Поддержка
Для просмотра документации необходимо авторизоваться на сайте