Решение задач минимума среднего квадрата с линейными ограничениями
Решатель линейного метода наименьших квадратов с границами или линейными ограничениями.
Решает задачи аппроксимирования кривыми наименьших квадратов формы
Примечание
lsqlin
применяется только к основанному на решателе подходу. Для обсуждения двух подходов оптимизации смотрите, Сначала Выбирают Problem-Based or Solver-Based Approach.
добавляют линейные ограничения равенства 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(problem
)problem
, структура описана в problem
. Создайте problem
структура с помощью записи через точку или struct
функция. Или создайте problem
структура от OptimizationProblem
объект при помощи prob2struct
.
[
, для любых входных параметров, описанных выше, возвращается:x
,resnorm
,residual
,exitflag
,output
,lambda
]
= lsqlin(___)
Квадратичная 2-норма невязки resnorm =
Остаточный residual = C*x - d
Значение exitflag
описание выходного условия
Структура output
содержа информацию о процессе оптимизации
Структура lambda
содержа множители Лагранжа
Фактор ½ в определении проблемы влияет на значения в lambda
структура.
Найдите 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
Найдите 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
В этом примере показано, как использовать опции не по умолчанию для линейного метода наименьших квадратов.
Установите опции использовать '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
Получите и интерпретируйте весь 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
— Матрица множителяМатрица множителя в виде матрицы удваивается. C
представляет множитель решения x
в выражении C*x - d
C
M
- N
, где M
количество уравнений и N
число элементов x
.
Пример: C = [1,4;2,5;7,8]
Типы данных: double
d
— Постоянный векторПостоянный вектор в виде вектора из удваивается. d
представляет термин аддитивной постоянной в выражении C*x - d
D
M
- 1
, где M
количество уравнений.
Пример: d = [5;0;-12]
Типы данных: double
A
— Линейные ограничения неравенстваЛинейные ограничения неравенства в виде действительной матрицы. A
M
- N
матрица, где M
количество неравенств и N
количество переменных (число элементов в x0
). Для больших проблем передайте A
как разреженная матрица.
A
кодирует M
линейные неравенства
A*x <= b
,
где x
вектор-столбец N
переменные x(:)
, и b
вектор-столбец с M
элементы.
Например, чтобы задать
x 1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30,
введите эти ограничения:
A = [1,2;3,4;5,6]; b = [10;20;30];
Пример: Чтобы указать что x сумма компонентов к 1 или меньше, используйте A = ones(1,N)
и b = 1
.
Типы данных: double
b
— Линейные ограничения неравенстваЛинейные ограничения неравенства в виде вектора действительных чисел. b
M
- вектор элемента связан с A
матрица. Если вы передаете b
как вектор-строка, решатели внутренне преобразуют b
к вектор-столбцу b(:)
. Для больших проблем передайте b
как разреженный вектор.
b
кодирует M
линейные неравенства
A*x <= b
,
где x
вектор-столбец N
переменные x(:)
, и A
матрица размера M
- N
.
Например, рассмотрите эти неравенства:
x 1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.
Задайте неравенства путем ввода следующих ограничений.
A = [1,2;3,4;5,6]; b = [10;20;30];
Пример: Чтобы указать что x сумма компонентов к 1 или меньше, используйте A = ones(1,N)
и b = 1
.
Типы данных: double
Aeq
— Линейные ограничения равенстваЛинейные ограничения равенства в виде действительной матрицы. Aeq
Me
- N
матрица, где Me
количество равенств и N
количество переменных (число элементов в x0
). Для больших проблем передайте Aeq
как разреженная матрица.
Aeq
кодирует Me
линейные равенства
Aeq*x = beq
,
где x
вектор-столбец N
переменные x(:)
, и beq
вектор-столбец с Me
элементы.
Например, чтобы задать
x 1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x 3 = 20,
введите эти ограничения:
Aeq = [1,2,3;2,4,1]; beq = [10;20];
Пример: Чтобы указать что x сумма компонентов к 1, используйте Aeq = ones(1,N)
и beq = 1
.
Типы данных: double
beq
— Линейные ограничения равенстваЛинейные ограничения равенства в виде вектора действительных чисел. beq
Me
- вектор элемента связан с Aeq
матрица. Если вы передаете beq
как вектор-строка, решатели внутренне преобразуют beq
к вектор-столбцу beq(:)
. Для больших проблем передайте beq
как разреженный вектор.
beq
кодирует Me
линейные равенства
Aeq*x = beq
,
где x
вектор-столбец N
переменные x(:)
, и Aeq
матрица размера Me
- N
.
Например, рассмотрите эти равенства:
x 1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x 3 = 20.
Задайте равенства путем ввода следующих ограничений.
Aeq = [1,2,3;2,4,1]; beq = [10;20];
Пример: Чтобы указать что x сумма компонентов к 1, используйте Aeq = ones(1,N)
и beq = 1
.
Типы данных: double
lb
— Нижние границы[]
(значение по умолчанию) | вектор действительных чисел или массивНижние границы в виде вектора или массива типа double. lb
представляет нижние границы поэлементно в lb
≤ x
≤ ub
.
Внутренне, lsqlin
преобразует массив lb
к векторному lb(:)
.
Пример: lb = [0;-Inf;4]
средние значения x(1) ≥ 0
, x(3) ≥ 4
.
Типы данных: double
ub
— Верхние границы[]
(значение по умолчанию) | вектор действительных чисел или массивВерхние границы в виде вектора или массива типа double. ub
представляет верхние границы поэлементно в lb
≤ x
≤ ub
.
Внутренне, lsqlin
преобразует массив ub
к векторному ub(:)
.
Пример: ub = [Inf;4;10]
средние значения x(2) ≤ 4
, x(3) ≤ 10
.
Типы данных: double
x0
— Начальная точка[]
(значение по умолчанию) | вектор действительных чисел или массивНачальная точка для процесса решения в виде вектора действительных чисел или массива. 'trust-region-reflective'
и 'active-set'
алгоритмы используют x0
(дополнительный).
Если вы не задаете x0
для 'trust-region-reflective'
или 'active-set'
алгоритм, lsqlin
наборы x0
к нулевому вектору. Если любой компонент этого нулевого векторного x0
нарушает границы, lsqlin
наборы x0
к точке во внутренней части поля, заданного границами.
Пример: x0 = [4;-3]
Типы данных: double
options
— Опции для lsqlin
optimoptions
| структура такой, как создано optimset
Опции для lsqlin
В виде выхода optimoptions
функционируйте или как структуру такой, как создано optimset
.
Некоторые опции отсутствуют в optimoptions
отображение. Эти опции появляются курсивом в следующей таблице. Для получения дополнительной информации, Опции вида на море.
Все алгоритмы
| Выберите алгоритм:
Когда проблема не имеет никаких ограничений, Если у вас есть большое количество линейных ограничений и не большое количество переменных, попробуйте Для получения дополнительной информации о выборе алгоритма смотрите Выбор Algorithm. |
Диагностика | Отобразите диагностическую информацию о функции, которая будет минимизирована или решена. Выбором является |
Display | Level of display возвращен в командную строку.
|
MaxIterations | Максимальное количество позволенных итераций, положительное целое число. Значением по умолчанию является Для |
trust-region-reflective
Опции алгоритма
FunctionTolerance | Допуск завершения на значении функции, положительной скалярной величине. Значением по умолчанию является Для |
JacobianMultiplyFcn | Функция умножения якобиана в виде указателя на функцию. Для крупномасштабных структурированных проблем эта функция должна вычислить якобиевское матричное произведение W = jmfun(Jinfo,Y,flag) где
В каждом случае, Смотрите функцию умножения якобиана с Линейным методом наименьших квадратов для примера. Для |
MaxPCGIter | Максимальное количество PCG (предобусловленный метод сопряженных градиентов) итерации, положительная скалярная величина. Значением по умолчанию является |
OptimalityTolerance | Допуск завершения на оптимальности первого порядка, положительной скалярной величине. Значением по умолчанию является Для |
PrecondBandWidth | Верхняя пропускная способность предварительного формирователя для PCG (предобусловленный метод сопряженных градиентов). По умолчанию диагональное предварительное создание условий используется (верхняя пропускная способность 0). Для некоторых проблем, увеличивая пропускную способность сокращает количество итераций PCG. Установка |
SubproblemAlgorithm | Определяет, как шаг итерации вычисляется. Значение по умолчанию, |
TolPCG | Допуск завершения на PCG (предобусловленный метод сопряженных градиентов) итерация, положительная скалярная величина. Значением по умолчанию является |
TypicalX | Типичный |
interior-point
Опции алгоритма
ConstraintTolerance | Допуск на нарушении ограничений, положительной скалярной величине. Значением по умолчанию является Для |
LinearSolver | Тип внутреннего линейного решателя в алгоритме:
|
OptimalityTolerance | Допуск завершения на оптимальности первого порядка, положительной скалярной величине. Значением по умолчанию является Для |
StepTolerance | Допуск завершения на Для |
'active-set'
Опции алгоритма
ConstraintTolerance | Допуск на нарушении ограничений, положительной скалярной величине. Значением по умолчанию является Для |
ObjectiveLimit | Допуск (останавливающий критерий), который является скаляром. Если значение целевой функции понижается |
OptimalityTolerance | Допуск завершения на оптимальности первого порядка, положительной скалярной величине. Значением по умолчанию является Для |
StepTolerance | Допуск завершения на Для |
problem
— Задача оптимизацииЗадача оптимизации в виде структуры со следующими полями.
| Матричный множитель в термине C*x - d |
| Аддитивная постоянная в термине C*x - d |
| Матрица для линейных ограничений неравенства |
| Вектор для линейных ограничений неравенства |
| Матрица для линейных ограничений равенства |
| Вектор для линейных ограничений равенства |
lb | Вектор из нижних границ |
ub | Вектор из верхних границ |
| Начальная точка для x |
| 'lsqlin' |
| Опции, созданные с optimoptions |
Типы данных: struct
x
РешениеРешение, возвращенное как вектор, который минимизирует норму C*x-d
подвергните всем границам и линейным ограничениям.
resnorm
— Объективное значениеОбъективное значение, возвращенное как скалярное значение norm(C*x-d)^2
.
residual
— Остаточные значения решенияОстаточные значения решения, возвращенные как векторный C*x-d
.
exitflag
— Алгоритм, останавливающий условиеАлгоритм, останавливающий условие, возвращенное как целое число, идентифицирующее причину остановленный алгоритм. Следующие списки значения exitflag
и соответствующие причины lsqlin
остановленный.
3 | Изменение в невязке было меньшим, чем заданный допуск |
2 | Размер шага, меньший, чем |
1 | Функция сходилась к решению |
0 | Количество итераций превысило |
-2 | Проблема неосуществима. Или, для |
-3
| Проблема неограниченна. |
-4 | Плохо создание условий предотвращает дальнейшую оптимизацию. |
-8 | Не мог вычислить направление шага. |
Выходное сообщение для interior-point
алгоритм может предоставить больше подробную информацию на причине lsqlin
остановленный, такие как превышение допуска. Смотрите Выходные Флаги и Выходные сообщения.
output
— Сводные данные процесса решенияСводные данные процесса решения, возвращенные как структура, содержащая информацию о процессе оптимизации.
| Количество итераций решатель взяло. |
| Один из этих алгоритмов:
Для неограниченной проблемы, |
| Нарушение ограничений, которое положительно для нарушенных ограничений (не возвращенный для
|
| Выходное сообщение. |
| Оптимальность первого порядка в решении. Смотрите Меру оптимальности Первого порядка. |
linearsolver | Тип внутреннего линейного решателя, |
| Количество итераций метода сопряженных градиентов решатель выполняется. Непустой только для |
Смотрите структуры output.
lambda
— Множители ЛагранжаМножители Лагранжа, возвращенные как структура со следующими полями.
| Нижние границы |
| Верхние границы |
| Линейные неравенства |
| Линейные равенства |
Смотрите структуры множителя Лагранжа.
Для проблем без ограничений можно использовать mldivide
(матричное левое деление). Когда у вас нет ограничений, lsqlin
возвращает x = C\d
.
Поскольку решенная задача всегда выпукла, lsqlin
находит глобальную переменную, несмотря на то, что не обязательно уникальной, решение.
Если ваша проблема имеет много линейных ограничений и немного переменных, попытайтесь использовать 'active-set'
алгоритм. Смотрите Квадратичное программирование со Многими Линейными Ограничениями.
Лучше числовые результаты вероятны, если вы задаете равенства явным образом, с помощью Aeq
и beq
, вместо неявно, с помощью lb
и ub
.
trust-region-reflective
алгоритм не позволяет равные верхние и нижние границы. Используйте другой алгоритм для этого случая.
Если заданные входные границы для проблемы противоречивы, выход x
x0
и выходные параметры resnorm
и residual
[]
.
Можно решить некоторые большие структурированные задачи, включая тех где C
матрица является слишком большой, чтобы уместиться в памяти, с помощью trust-region-reflective
алгоритм с функцией умножения якобиана. Для получения информации смотрите доверительную область отражающие Опции Алгоритма.
Этот метод является методом доверительной области подпространства на основе внутреннего отражающего метода Ньютона, описанного в [1]. Каждая итерация включает приближенное решение большой линейной системы с помощью метода предобусловленных методов сопряженных градиентов (PCG). Смотрите Доверительную область Отражающие Наименьшие квадраты, и в конкретном Крупномасштабном Линейном методе наименьших квадратов.
'interior-point'
алгоритм на основе quadprog
'interior-point-convex'
алгоритм. Смотрите Линейный метод наименьших квадратов: внутренняя точка или Активный Набор.
'active-set'
алгоритм на основе quadprog
'active-set'
алгоритм. Для получения дополнительной информации смотрите Линейный метод наименьших квадратов: внутренняя точка или Активный Набор и активный набор quadprog Алгоритм.
[1] Коулман, T. F. и И. Ли. “Отражающий Метод Ньютона для Минимизации Квадратичной Функции Согласно Границам на Некоторых Переменных”, SIAM Journal на Оптимизации, Издании 6, Номере 4, стр 1040–1058, 1996.
[2] Жабры, P. E. В. Мюррей и М. Х. Райт. Практическая оптимизация, Academic Press, Лондон, Великобритания, 1981.
Оптимизировать задача Live Editor обеспечивает визуальный интерфейс для lsqlin
.
У вас есть модифицированная версия этого примера. Вы хотите открыть этот пример со своими редактированиями?
1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.
2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.
3. Сохраняйте структуру оригинального текста - например, не разбивайте одно предложение на два.
4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.
5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.