Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

lsqlin

Resuelva los problemas lineales de mínimos cuadrados restringidos

Descripción

Solver lineal de mínimos cuadrados con límites o restricciones lineales.

Resuelve los problemas de ajuste de curva de mínimos cuadrados de la forma

minx12Cxd22 such that {Axb,Aeqx=beq,lbxub.

Nota

lsqlin solo se aplica al enfoque basado en el solucionador. Para ver una explicación de los dos enfoques de optimización, consulte.Elija primero el enfoque basado en problemas o basado en Solver

ejemplo

x = lsqlin(C,d,A,b) resuelve el sistema lineal en el sentido de mínimos cuadrados, sujeto a ≤.C*x = dA*xb

ejemplo

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub) añade restricciones y límites de igualdad lineales ≤ ≤.Aeq*x = beqlbxub Si no necesita ciertas restricciones como y, establecerlas.Aeqbeq[] Si se deslimita a continuación, se establece, y si se encuentra sin delimitar, se establece.x(i)lb(i) = -Infx(i)ub(i) = Inf

ejemplo

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options) minimiza con un punto inicial y las opciones de optimización especificadas en.x0Opciones Se usa para establecer estas opciones.optimoptions Si no desea incluir un punto inicial, establezca el argumento.x0[]

x = lsqlin(problem) encuentra el mínimo para, donde es una estructura.problemproblem Cree la estructura exportando un problema desde la aplicación de optimización, como se describe en.problemExportar su trabajo O cree una estructura a partir de un objeto mediante.problemOptimizationProblemprob2struct

ejemplo

[x,resnorm,residual,exitflag,output,lambda] = lsqlin(___), para los argumentos de entrada descritos anteriormente, devuelve:

  • La 2-norma cuadrada del residuoresnorm = Cxd22

  • El residuoresidual = C*x - d

  • Un valor que describa la condición de salidaexitflag

  • Una estructura que contiene información sobre el proceso de optimizaciónoutput

  • Una estructura que contiene los multiplicadores de Lagrangelambda

    El factor 1/2 en la definición del problema afecta a los valores de la estructura.lambda

Ejemplos

contraer todo

Encuentre lo que minimiza la norma de un problema sobredeterminado con restricciones de desigualdad lineales.xC*x - d

Especifique el problema y las restricciones.

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];

Llame para resolver el problema.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

Encuentra el que minimiza la norma de un problema sobredeterminado con igualdad lineal y restricciones y límites de desigualdad.xC*x - d

Especifique el problema y las restricciones.

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);

Llame para resolver el problema.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

Este ejemplo muestra cómo utilizar las opciones no predeterminadas para los cuadrados mínimos lineales.

Configure las opciones para utilizar el algoritmo y para dar una visualización iterativa.'interior-point'

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

Configure un problema de mínimos cuadrados lineales.

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];

Ejecute el problema.

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

Obtener e interpretar todas las salidas.lsqlin

Defina un problema con límites y restricciones de desigualdad lineales. El problema está sobredeterminado porque hay cuatro columnas en la matriz, pero cinco filas.C Esto significa que el problema tiene cuatro desconocidos y cinco condiciones, incluso antes de incluir las restricciones lineales y los límites.

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);

Configure las opciones para utilizar el algoritmo.'interior-point'

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

El algoritmo no utiliza un punto inicial, por lo que se establece en.'interior-point'x0[]

x0 = [];

Llame con todas las salidas.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]

Examine los campos multiplicadores de Lagrange distintos de cero con más detalle. Primero examine los multiplicadores de Lagrange para la restricción de desigualdad lineal.

lambda.ineqlin
ans = 3×1

    0.0000
    0.2392
    0.0000

Los multiplicadores de Lagrange son distintos de cero exactamente cuando la solución está en el límite de restricción correspondiente. En otras palabras, los multiplicadores de Lagrange son distintos de cero cuando la restricción correspondiente está activa. es distinto de cero.lambda.ineqlin(2) Esto significa que el segundo elemento en debe ser igual al segundo elemento, porque la restricción está activa.A*xb

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

    0.2026    0.2026

Ahora examine los multiplicadores de Lagrange para las restricciones de límite inferior y superior.

lambda.lower
ans = 4×1

    0.0409
    0.2784
    0.0000
    0.0000

lambda.upper
ans = 4×1

     0
     0
     0
     0

Los dos primeros elementos son distintos de cero.lambda.lower Ves eso y estás en sus límites inferiores,.x(1)x(2)-0.1 Todos los elementos de son esencialmente cero, y se ve que todos los componentes de son menores que su límite superior,.lambda.upperx2

Argumentos de entrada

contraer todo

Matriz multiplicadora, especificada como una matriz de dobles. representa el multiplicador de la solución en la expresión. es-por-, donde está el número de ecuaciones, y es el número de elementos de.CxC*x - dCMNMNx

Ejemplo: C = [1,4;2,5;7,8]

Tipos de datos: double

Vector constante, especificado como vector de dobles. representa el término constante aditivo en la expresión. es-por-, donde está el número de ecuaciones.dC*x - ddM1M

Ejemplo: d = [5;0;-12]

Tipos de datos: double

Matriz de restricción de desigualdad lineal, especificada como una matriz de dobles. representa los coeficientes lineales de las restricciones ≤. tiene el tamaño por, donde está el número de restricciones y es el número de elementos de.AA*x  bAMineqNMineqNx Para ahorrar memoria, pase como una matriz dispersa.A

Ejemplo: significa tres desigualdades lineales (tres filas) para dos variables de decisión (dos columnas).A = [4,3;2,0;4,-1];

Tipos de datos: double

Vector de restricción de desigualdad lineal, especificado como vector de dobles. representa el vector constante en las restricciones ≤. tiene longitud, donde está-por-.bA*x  bbMineqAMineqN

Ejemplo: [4,0]

Tipos de datos: double

Matriz de restricción de igualdad lineal, especificada como una matriz de dobles. representa los coeficientes lineales en las restricciones =. tiene el tamaño por, donde está el número de restricciones y es el número de elementos de.AeqAeq*x  beqAeqMeqNMeqNx Para ahorrar memoria, pase como una matriz dispersa.Aeq

Ejemplo: significa tres desigualdades lineales (tres filas) para dos variables de decisión (dos columnas).A = [4,3;2,0;4,-1];

Tipos de datos: double

Vector de restricción de igualdad lineal, especificado como vector de dobles. representa el vector constante en las restricciones =. tiene longitud, donde está-por-.beqAeq*x  beqbeqMeqAeqMeqN

Ejemplo: [4,0]

Tipos de datos: double

Límites inferiores, especificados como vector o array de dobles. representa los límites inferiores elementwise en ≤ ≤.lblb  x  ub

Internamente, convierte una matriz en el vector.lsqlinlblb(:)

Ejemplo: Significa.lb = [0;-Inf;4]x(1) ≥ 0x(3) ≥ 4

Tipos de datos: double

Límites superiores, especificados como un vector o una matriz de dobles. representa los límites superiores elementwise en ≤ ≤.ublb  x  ub

Internamente, convierte una matriz en el vector.lsqlinubub(:)

Ejemplo: Significa.ub = [Inf;4;10]x(2) ≤ 4x(3) ≤ 10

Tipos de datos: double

Punto inicial para el proceso de solución, especificado como vector o array de dobles. sólo es utilizado por el algoritmo.x0'trust-region-reflective' Opcional.

Si no proporciona un para el algoritmo, establece en el vector cero.x0'trust-region-reflective'lsqlinx0 Si algún componente de este vector cero infringe los límites, se establece en un punto en el interior del cuadro definido por los límites.x0lsqlinx0

Ejemplo: x0 = [4;-3]

Tipos de datos: double

Opciones para, especificadas como la salida de la función o la aplicación de optimización.lsqlinoptimoptions

Algunas opciones están ausentes en la pantalla.optimoptions Estas opciones aparecen en cursiva en la tabla siguiente. Para obtener más información, consulte.Ver opciones

Todos los algoritmos

Algorithm

Elija el algoritmo:

  • predeterminado'interior-point'

  • 'trust-region-reflective'

El algoritmo permite límites superiores e inferiores, lo que significa que no hay desigualdades lineales o ecualidades.'trust-region-reflective'only Si especifica tanto las restricciones como las lineales, utiliza el algoritmo.'trust-region-reflective'lsqlin'interior-point'

El algoritmo no permite los límites superior e inferior iguales.'trust-region-reflective'

Para obtener más información sobre cómo elegir el algoritmo, consulte.Elegir el algoritmo

Diagnostics

Mostrar información de diagnóstico sobre la función que se debe minimizar o resolver. Las opciones son o el valor predeterminado.'on''off'

Display

Nivel de visualización devuelto a la línea de comandos.

  • o no muestra ninguna salida.'off''none'

  • muestra sólo la salida final (por defecto).'final'

El algoritmo permite valores adicionales:'interior-point'

  • ofrece una visualización iterativa.'iter'

  • proporciona una visualización iterativa con un mensaje de salida detallado.'iter-detailed'

  • muestra solo la salida final, con un mensaje de salida detallado.'final-detailed'

MaxIterations

Número máximo de iteraciones permitidas, un entero positivo. El valor predeterminado es.200

El nombre es.optimsetMaxIter Ver.Las tablas de nombres de opciones actuales y heredadas

Opciones de algoritmotrust-region-reflective

FunctionTolerance

Tolerancia de terminación en el valor de la función, un escalar positivo. El valor predeterminado es, about.100*eps2.2204e-14

El nombre es.optimsetTolFun Ver.Las tablas de nombres de opciones actuales y heredadas

JacobianMultiplyFcn

Función de multiplicación jacobiana, especificada como un manejador de funciones. Para problemas estructurados a gran escala, esta función debe calcular el producto de matriz jacobiana, o sin formar realmente.C*YC'*YC'*(C*Y)C Escriba la función en el formulario

W = jmfun(Jinfo,Y,flag)

donde contiene una matriz utilizada para computar (o, o).JinfoC*YC'*YC'*(C*Y)

debe calcular uno de los tres productos diferentes, dependiendo del valor de los pases:jmfunflaglsqlin

  • Si entonces.flag == 0W = C'*(C*Y)

  • Si entonces.flag > 0W = C*Y

  • Si entonces.flag < 0W = C'*Y

En cada caso, no es necesario formar explícitamente. utiliza para calcular el preacondicionador.jmfunClsqlinJinfo Consulte para obtener información sobre cómo suministrar parámetros adicionales si es necesario.Pasar parámetros adicionales

Vea por un ejemplo.Función de multiplicación jacobiana con mínimos cuadrados lineales

El nombre es.optimsetJacobMult Ver.Las tablas de nombres de opciones actuales y heredadas

MaxPCGIter

Número máximo de iteraciones PCG (degradado conjugada precondicionada), un escalar positivo. El valor predeterminado es.max(1,floor(numberOfVariables/2)) Para obtener más información, consulte.Confianza-región-algoritmo reflexivo

OptimalityTolerance

Tolerancia de terminación en la optimalidad de primer orden, un escalar positivo. El valor predeterminado es, about.100*eps2.2204e-14 Ver.Medida de optimalidad de primer orden

El nombre es.optimsetTolFun Ver.Las tablas de nombres de opciones actuales y heredadas

PrecondBandWidth

Ancho de banda superior del preacondicionador para PCG (gradiente conjugada precondicionado). De forma predeterminada, se utiliza el preacondicionamiento diagonal (ancho de banda superior de 0). Para algunos problemas, el aumento del ancho de banda reduce el número de iteraciones PCG. Ajuste a utiliza una factorización directa (Cholesky) en lugar de los degradados conjugados (CG).PrecondBandWidthInf La factorización directa es computacionalmente más costosa que CG, pero produce un mejor paso de calidad hacia la solución. Para obtener más información, consulte.Confianza-región-algoritmo reflexivo

SubproblemAlgorithm

Determina cómo se calcula el paso de iteración. El valor predeterminado, toma un paso más rápido pero menos preciso que.'cg''factorization' Ver.Trust-region-reflectivos mínimos cuadrados

TolPCG

Tolerancia de terminación en la iteración PCG (degradado conjugada precondicionada), un escalar positivo. El valor predeterminado es.0.1

TypicalX

Valores típicos.x El número de elementos en es igual al número de variables.TypicalX El valor predeterminado es. utiliza internamente para escalar. tiene un efecto solo cuando tiene componentes sin enlazar y cuando un valor para un componente sin enlazar es mayor que.ones(numberofvariables,1)lsqlinTypicalXTypicalXxTypicalX1

Opciones de algoritmointerior-point

ConstraintTolerance

Tolerancia en la infracción de restricción, un escalar positivo. El valor predeterminado es.1e-8

El nombre es.optimsetTolCon Ver.Las tablas de nombres de opciones actuales y heredadas

LinearSolver

Tipo de solucionador lineal interno en el algoritmo:

  • (valor predeterminado): se usa si la matriz es dispersa, de lo contrario.'auto''sparse'C'dense'

  • — Utilizar álgebra lineal dispersa.'sparse' Ver.Matrices dispersas (MATLAB)

  • — Utilizar álgebra lineal densa.'dense'

OptimalityTolerance

Tolerancia de terminación en la optimalidad de primer orden, un escalar positivo. El valor predeterminado es.1e-8 Ver.Medida de optimalidad de primer orden

El nombre es.optimsetTolFun Ver.Las tablas de nombres de opciones actuales y heredadas

StepTolerance

Tolerancia de terminación activada, un escalar positivo.x El valor predeterminado es.1e-12

El nombre es.optimsetTolX Ver.Las tablas de nombres de opciones actuales y heredadas

Problema de optimización, especificado como una estructura con los siguientes campos.

C

Multiplicador de matriz en el términoC*x - d

d

Constante aditiva en el términoC*x - d

Aineq

Matriz para las restricciones de desigualdad lineal

bineq

Vector para las restricciones de desigualdad lineal

Aeq

Matriz para las restricciones de igualdad lineal

beq

Vector para las restricciones de igualdad lineales
lbVector de los límites inferiores
ubVector de los límites superiores

x0

Punto inicial parax

solver

'lsqlin'

Opciones

Las opciones creadas conoptimoptions

Cree la estructura exportando un problema desde la aplicación de optimización, tal como se describe en.problemExportar su trabajo

Tipos de datos: struct

Argumentos de salida

contraer todo

Solución, devuelta como un vector que minimiza la norma de sujeto a todos los límites y restricciones lineales.C*x-d

Valor objetivo, devuelto como valor escalar.norm(C*x-d)^2

Los residuales de la solución, devueltos como el vector.C*x-d

Condición de detención del algoritmo, devuelta como un entero que identifica la razón por la que el algoritmo se detuvo. A continuación se enumeran los valores y los motivos correspondientes detenidos.exitflaglsqlin

3

El cambio en el residuo fue menor que la tolerancia especificada. algoritmooptions.FunctionTolerancetrust-region-reflective

2

Tamaño de paso menor que, restricciones satisfechas. algoritmooptions.StepToleranceinterior-point

1

Función convergida a una solución.x

0

Número de iteraciones superada.options.MaxIterations

-2

El problema es inviable. O, para el algoritmo, el tamaño del paso es menor que, pero las restricciones no se satisfacen.interior-pointoptions.StepTolerance

-3El problema es ilimitado.

-4

El mal acondicionamiento evita una mayor optimización.

-8

No se puede calcular una dirección de paso.

El mensaje de salida para el algoritmo puede dar más detalles sobre la razón detenida, tal como exceder una tolerancia.interior-pointlsqlin Ver.Salir de banderas y salir de mensajes

Resumen del proceso de solución, devuelto como una estructura que contiene información sobre el proceso de optimización.

iterations

Número de iteraciones que tomó el solucionador.

algorithm

Uno de estos algoritmos:

  • 'interior-point'

  • 'trust-region-reflective'

constrviolation

Infracción de restricción que es positiva para las restricciones infringidas (no devueltas para el algoritmo).'trust-region-reflective'

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

message

Mensaje de salida.

firstorderopt

Optimalidad de primer orden en la solución. Ver.Medida de optimalidad de primer orden

linearsolver

Tipo de solucionador lineal interno o (solo algoritmo)'dense''sparse''interior-point'

cgiterations

Número de iteraciones de degradado conjugada que realizó el solucionador. No está vacío sólo para el algoritmo.'trust-region-reflective'

Ver.Estructuras de salida

Multiplicadores de Lagrange, devueltos como una estructura con los siguientes campos.

lower

Los límites inferioreslb

upper

Los límites superioresub

ineqlin

Las desigualdades lineales

eqlin

Las equalidades lineales

Ver.Las estructuras multiplicador de Lagrange

Sugerencias

  • Para problemas sin restricciones, puede usar (División de matriz izquierda).mldivide Cuando no tiene restricciones, devuelve.lsqlinx = C\d

  • Debido a que el problema que se resuelve siempre es convexo, encuentra una solución global, aunque no necesariamente única.lsqlin

  • Es probable que los resultados numéricos sean mejores si especifica ecualidades explícitamente, utilizando y, en lugar de implícitamente, utilizando y.Aeqbeqlbub

  • El algoritmo no permite los límites superior e inferior iguales.trust-region-reflective Utilice otro algoritmo para este caso.

  • Si los límites de entrada especificados para un problema son incoherentes, la salida es y las salidas y son.xx0resnormresidual[]

  • Puede resolver algunos problemas estructurados grandes, incluyendo aquellos donde la matriz es demasiado grande para caber en la memoria, utilizando el algoritmo con una función de multiplicación jacobiana.Ctrust-region-reflective Para obtener información, consulte.Opciones de algoritmotrust-region-reflective

Algoritmos

contraer todo

Confianza-región-algoritmo reflexivo

Este método es un método de región de confianza subespacial basado en el método de Newton interior-reflectante descrito en.[1] Cada iteración implica la solución aproximada de un gran sistema lineal utilizando el método de gradientes conjugados preacondicionados (PCG). Ver, y en particular.Trust-region-reflectivos mínimos cuadradosLos cuadrados mínimos lineales de gran escala

Algoritmo de punto interior

El algoritmo se basa en el algoritmo.'interior-point'quadprog'interior-point-convex' Ver.Los cuadrados mínimos lineales de punto interior

Referencias

[1] Coleman, T. F. and Y. Li. “A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on Some of the Variables,” SIAM Journal on Optimization, Vol. 6, Number 4, pp. 1040–1058, 1996.

[2] Gill, P. E., W. Murray, and M. H. Wright. Practical Optimization, Academic Press, London, UK, 1981.

Introducido antes de R2006a