Main Content

quadprog

Programación cuadrática

Descripción

Solver para funciones objetivo cuadráticas con restricciones lineales.

quadprog encuentra un mínimo para un problema especificado por

minx12xTHx+fTx such that {Axb,Aeqx=beq,lbxub.

H, A y Aeq son matrices, y f, b, beq, lb, ub y x son vectores.

Puede pasar f, lb y ub como vectores o matrices; consulte Argumentos de matriz.

Nota

quadprog se aplica únicamente al enfoque basado en solvers. Para ver una exposición sobre los dos enfoques de optimización, consulte En primer lugar, elija el enfoque basado en problemas o el enfoque basado en solvers.

x = quadprog(H,f) devuelve un vector x que minimiza 1/2*x'*H*x + f'*x. La entrada H debe ser definida positiva para que el problema tenga un mínimo finito. Si H es definida positiva, la solución es x = H\(-f).

ejemplo

x = quadprog(H,f,A,b) minimiza 1/2*x'*H*x + f'*x sujeto a las restricciones A*x b. La entrada A es una matriz de dobles y b es un vector de dobles.

ejemplo

x = quadprog(H,f,A,b,Aeq,beq) resuelve el problema anterior sujeto a las restricciones adicionales Aeq*x = beq. Aeq es una matriz de dobles y beq es un vector de dobles. Si no existen desigualdades, establezca A = [] y b = [].

ejemplo

x = quadprog(H,f,A,b,Aeq,beq,lb,ub) resuelve el problema anterior sujeto a las restricciones adicionales lb x ub. Las entradas lb y ub son vectores de dobles y las restricciones se mantienen para cada componente x. Si no existen igualdades, establezca Aeq = [] y beq = [].

Nota

Si los límites de entrada especificados para un problema son inconsistentes, la salida x es x0 y la salida fval es [].

quadprog restablece los componentes de x0 que vulneran los límites lb x ub al interior del cuadro definido por los límites. quadprog no cambia los componentes que respetan los límites.

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) resuelve el problema anterior comenzando por el vector x0. Si no existen límites, establezca lb = [] y ub = []. Algunos algoritmos quadprog ignoran x0; consulte x0.

Nota

x0 es un argumento requerido para el algoritmo 'active-set'.

ejemplo

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) resuelve el problema anterior utilizando las opciones de optimización que se especifican en options. Utilice optimoptions para crear options. Si no desea proporcionar un punto inicial, establezca x0 = [].

ejemplo

x = quadprog(problem) devuelve el mínimo para problem, una estructura descrita en problem. Cree la estructura problem utilizando notación de puntos o la función struct. También puede crear una estructura problem a partir de un objeto OptimizationProblem utilizando prob2struct.

ejemplo

[x,fval] = quadprog(___), para cualquier variable de entrada, también devuelve fval, el valor de la función objetivo en x:

fval = 0.5*x'*H*x + f'*x

ejemplo

[x,fval,exitflag,output] = quadprog(___) también devuelve exitflag, un entero que describe la condición de salida de quadprog, y output, una estructura que contiene información sobre el proceso de optimización.

ejemplo

[x,fval,exitflag,output,lambda] = quadprog(___) también devuelve lambda, una estructura cuyos campos contienen los multiplicadores de Lagrange en la solución x.

ejemplo

[wsout,fval,exitflag,output,lambda] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws) inicia quadprog a partir de los datos del objeto ws de arranque en caliente, utilizando las opciones de ws. El argumento wsout devuelto contiene el punto de solución en wsout.X. Utilizando wsout como el objeto inicial de arranque en caliente en una llamada de solver posterior, quadprog puede funcionar más rápidamente.

Ejemplos

contraer todo

Encuentre el mínimo de

f(x)=12x12+x22-x1x2-2x1-6x2

sujeto a las restricciones

x1+x22-x1+2x222x1+x23.

En sintaxis de quadprog, este problema consiste en minimizar

f(x)=12xTHx+fTx,

donde

H=[1-1-12]f=[-2-6],

sujeto a las restricciones lineales.

Para resolver este problema, introduzca primero las matrices de coeficientes.

H = [1 -1; -1 2]; 
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

Llame a quadprog.

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,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.

Examine el punto final, el valor de la función y el indicador de salida.

x,fval,exitflag
x = 2×1

    0.6667
    1.3333

fval = -8.2222
exitflag = 1

Un indicador de salida de 1 indica que el resultado es un mínimo local. Dado que H es una matriz definida positiva, este problema es convexo y el mínimo es un mínimo global.

Confirme que H es definida positiva comprobando sus valores propios.

eig(H)
ans = 2×1

    0.3820
    2.6180

Encuentre el mínimo de

f(x)=12x12+x22-x1x2-2x1-6x2

sujeto a la restricción

x1+x2=0.

En sintaxis de quadprog, este problema consiste en minimizar

f(x)=12xTHx+fTx,

donde

H=[1-1-12]f=[-2-6],

sujeto a la restricción lineal.

Para resolver este problema, introduzca primero las matrices de coeficientes.

H = [1 -1; -1 2]; 
f = [-2; -6];
Aeq = [1 1];
beq = 0;

Llame a quadprog, introduciendo [] para las entradas A y b.

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,[],[],Aeq,beq);
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.

Examine el punto final, el valor de la función y el indicador de salida.

x,fval,exitflag
x = 2×1

   -0.8000
    0.8000

fval = -1.6000
exitflag = 1

Un indicador de salida de 1 indica que el resultado es un mínimo local. Dado que H es una matriz definida positiva, este problema es convexo y el mínimo es un mínimo global.

Confirme que H es definida positiva comprobando sus valores propios.

eig(H)
ans = 2×1

    0.3820
    2.6180

Encuentre la x que minimice la expresión cuadrática

12xTHx+fTx

donde

H=[1-11-12-21-24], f=[2-31],

sujeto a las restricciones

0x1, x=1/2.

Para resolver este problema, introduzca primero los coeficientes.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [2;-3;1];
lb = zeros(3,1);
ub = ones(size(lb));
Aeq = ones(1,3);
beq = 1/2;

Llame a quadprog, introduciendo [] para las entradas A y b.

x = quadprog(H,f,[],[],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 = 3×1

    0.0000
    0.5000
    0.0000

Establezca opciones para monitorizar el progreso de quadprog.

options = optimoptions('quadprog','Display','iter');

Defina un problema con un objetivo cuadrático y restricciones de desigualdad lineales.

H = [1 -1; -1 2]; 
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

Para ayudar a escribir la llamada de función quadprog, establezca todas las entradas innecesarias en [].

Aeq = [];
beq = [];
lb = [];
ub = [];
x0 = [];

Llame a quadprog para resolver el problema.

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0   -8.884885e+00   3.214286e+00   1.071429e-01     1.000000e+00  
    1   -8.331868e+00   1.321041e-01   4.403472e-03     1.910489e-01  
    2   -8.212804e+00   1.676295e-03   5.587652e-05     1.009601e-02  
    3   -8.222204e+00   8.381476e-07   2.793826e-08     1.809485e-05  
    4   -8.222222e+00   3.019807e-14   1.352696e-12     7.525735e-13  

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 = 2×1

    0.6667
    1.3333

Cree una estructura problem con un Flujo de trabajo de optimización basada en problemas. Cree un problema de optimización equivalente a Programa cuadrático con restricciones lineales.

x = optimvar('x',2);
objec = x(1)^2/2 + x(2)^2 - x(1)*x(2) - 2*x(1) - 6*x(2);
prob = optimproblem('Objective',objec);
prob.Constraints.cons1 = sum(x) <= 2;
prob.Constraints.cons2 = -x(1) + 2*x(2) <= 2;
prob.Constraints.cons3 = 2*x(1) + x(2) <= 3;

Convierta prob a una estructura problem.

problem = prob2struct(prob);

Resuelva el problema con quadprog.

[x,fval] = quadprog(problem)
Warning: Your Hessian is not symmetric. Resetting H=(H+H')/2.
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 = 2×1

    0.6667
    1.3333

fval = -8.2222

Resuelva un programa cuadrático y devuelva la solución y el valor de la función objetivo.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
[x,fval] = quadprog(H,f,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 = 3×1

   -3.5714
    2.9286
    3.6429

fval = -47.1786

Compruebe que el valor devuelto de la función objetivo coincida con el valor calculado de la definición de la función objetivo quadprog.

fval2 = 1/2*x'*H*x + f'*x
fval2 = -47.1786

Para consultar el proceso de optimización para quadprog, establezca las opciones para una visualización iterativa y devuelva cuatro salidas. El problema consiste en minimizar

12xTHx+fTx

sujeto a

0x1,

donde

H=[21-11312-1125], f=[4-712].

Introduzca los coeficientes del problema.

H = [2 1 -1
    1 3 1/2
    -1 1/2 5];
f = [4;-7;12];
lb = zeros(3,1);
ub = ones(3,1);

Establezca las opciones para mostrar el progreso iterativo del solver.

options = optimoptions('quadprog','Display','iter');

Llame a quadprog con cuatro salidas.

[x fval,exitflag,output] = quadprog(H,f,[],[],[],[],lb,ub,[],options)
 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0    2.691769e+01   1.582123e+00   1.712849e+01     1.680447e+00  
    1   -3.889430e+00   0.000000e+00   8.564246e-03     9.971731e-01  
    2   -5.451769e+00   0.000000e+00   4.282123e-06     2.710131e-02  
    3   -5.499997e+00   0.000000e+00   1.221903e-10     6.939689e-07  
    4   -5.500000e+00   0.000000e+00   5.842173e-14     3.469847e-10  

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 = 3×1

    0.0000
    1.0000
    0.0000

fval = -5.5000
exitflag = 1
output = struct with fields:
            message: 'Minimum found that satisfies the constraints....'
          algorithm: 'interior-point-convex'
      firstorderopt: 1.5921e-09
    constrviolation: 0
         iterations: 4
       linearsolver: 'dense'
       cgiterations: []

Resuelva un problema de programación cuadrática y devuelva los multiplicadores de Lagrange.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
lb = zeros(3,1);
[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb);
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.

Examine la estructura de multiplicador de Lagrange lambda.

disp(lambda)
    ineqlin: 12.0000
      eqlin: [0x1 double]
      lower: [3x1 double]
      upper: [3x1 double]

La restricción de desigualdad lineal tiene un multiplicador de Lagrange asociado de 12.

Muestre los multiplicadores asociados al límite inferior.

disp(lambda.lower)
    5.0000
    0.0000
    0.0000

Solo el primer componente de lambda.lower tiene un multiplicador distinto de cero. Por lo general, esto significa que solo el primer componente de x está en el límite inferior de cero. Confírmelo mostrando los componentes de x.

disp(x)
    0.0000
    1.5000
    1.5000

Para acelerar llamadas a quadprog posteriores, cree un objeto de arranque en caliente.

options = optimoptions('quadprog','Algorithm','active-set');
x0 = [1 2 3];
ws = optimwarmstart(x0,options);

Resuelva un programa cuadrático utilizando ws.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
lb = zeros(3,1);
tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);
toc
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.
Elapsed time is 0.021717 seconds.

Cambie la función objetivo y resuelva de nuevo el problema.

f = [-10;-15;-20];

tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);
toc
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.
Elapsed time is 0.018485 seconds.

Argumentos de entrada

contraer todo

Término objetivo cuadrático, especificado como matriz real simétrica. H representa el cuadrático en la expresión 1/2*x'*H*x + f'*x. Si H no es simétrica, quadprog emite una advertencia y utiliza en su lugar la versión simetrizada (H + H')/2.

Si la matriz cuadrática H es dispersa, de forma predeterminada el algoritmo 'interior-point-convex' utiliza un algoritmo ligeramente diferente a cuando H es densa. Por lo general, el algoritmo disperso es más rápido para problemas grandes y dispersos, y el denso es más rápido para problemas densos o pequeños. Para obtener más información, consulte la descripción de la opción LinearSolver y interior-point-convex quadprog Algorithm.

Ejemplo: [2,1;1,3]

Tipos de datos: double

Término objetivo lineal, especificado como vector real. f representa el término lineal en la expresión 1/2*x'*H*x + f'*x.

Ejemplo: [1;3;2]

Tipos de datos: double

Restricciones de desigualdad lineales, especificadas como una matriz real. A es una matriz de M por N, donde M es el número de desigualdades y N es el número de variables (número de elementos de x0). Para problemas grandes, pase A como una matriz dispersa.

A codifica las M desigualdades lineales

A*x <= b,

donde x es el vector columna de N variables x(:) y b es un vector columna con M elementos.

Por ejemplo, considere estas desigualdades:

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30,

Especifique las desigualdades introduciendo las siguientes restricciones.

A = [1,2;3,4;5,6];
b = [10;20;30];

Ejemplo: Para especificar que los componentes de x suman 1 o menos, utilice A = ones(1,N) y b = 1.

Tipos de datos: double

Restricciones de desigualdad lineales, especificadas como un vector real. b es un vector de M elementos relacionado con la matriz A. Si pasa b como un vector fila, los solvers convierten internamente b en el vector columna b(:). Para problemas grandes, pase b como un vector disperso.

b codifica las M desigualdades lineales

A*x <= b,

donde x es el vector columna de N variables x(:) y A es una matriz de tamaño M por N.

Por ejemplo, considere estas desigualdades:

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.

Especifique las desigualdades introduciendo las siguientes restricciones.

A = [1,2;3,4;5,6];
b = [10;20;30];

Ejemplo: Para especificar que los componentes de x suman 1 o menos, utilice A = ones(1,N) y b = 1.

Tipos de datos: double

Restricciones de igualdad lineales, especificadas como una matriz real. Aeq es una matriz de Me por N, donde Me es el número de igualdades y N es el número de variables (número de elementos de x0). Para problemas grandes, pase Aeq como una matriz dispersa.

Aeq codifica las Me igualdades lineales

Aeq*x = beq,

donde x es el vector columna de N variables x(:) y beq es un vector columna con Me elementos.

Por ejemplo, considere estas desigualdades:

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20,

Especifique las desigualdades introduciendo las siguientes restricciones.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Ejemplo: Para especificar que los componentes de x suman 1, utilice Aeq = ones(1,N) y beq = 1.

Tipos de datos: double

Restricciones de igualdad lineales, especificadas como un vector real. beq es un vector de Me elementos relacionado con la matriz Aeq. Si pasa beq como un vector fila, los solvers convierten internamente beq en el vector columna beq(:). Para problemas grandes, pase beq como un vector disperso.

beq codifica las Me igualdades lineales

Aeq*x = beq,

donde x es el vector columna de N variables x(:) y Aeq es una matriz de tamaño Me por N.

Por ejemplo, considere estas igualdades:

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20.

Especifique las igualdades introduciendo las siguientes restricciones.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Ejemplo: Para especificar que los componentes de x suman 1, utilice Aeq = ones(1,N) y beq = 1.

Tipos de datos: double

Límites inferiores, especificados como un vector real o un arreglo real. Si el número de elementos en x0 es igual al número de elementos en lb, entonces lb especifica que

x(i) >= lb(i) para todo i.

Si numel(lb) < numel(x0), entonces lb especifica que

x(i) >= lb(i) para 1 <= i <= numel(lb).

Si lb tiene menos elementos que x0, los solvers emiten una advertencia.

Ejemplo: Para especificar que todos los componentes de x son positivos, utilice lb = zeros(size(x0)).

Tipos de datos: double

Límites superiores, especificados como un vector real o un arreglo real. Si el número de elementos en x0 es igual al número de elementos en ub, entonces ub especifica que

x(i) <= ub(i) para todo i.

Si numel(ub) < numel(x0), entonces ub especifica que

x(i) <= ub(i) para 1 <= i <= numel(ub).

Si ub tiene menos elementos que x0, los solvers emiten una advertencia.

Ejemplo: Para especificar que todos los componentes de x son menores que 1, utilice ub = ones(size(x0)).

Tipos de datos: double

Punto inicial, especificado como vector real. La longitud de x0 es el número de filas o columnas de H.

x0 se aplica al algoritmo 'trust-region-reflective' cuando el problema solo tiene límites de restricción. x0 también se aplica al algoritmo 'active-set'.

Nota

x0 es un argumento requerido para el algoritmo 'active-set'.

Si no especifica x0, quadprog establece todos los componentes de x0 en un punto en el interior del cuadro definido por los límites. quadprog ignora x0 para el algoritmo 'interior-point-convex' y para el algoritmo 'trust-region-reflective' con restricciones de igualdad.

Ejemplo: [1;2;1]

Tipos de datos: double

Opciones de optimización, especificadas como la salida de optimoptions o una estructura como la que devuelve optimset.

Algunas opciones no aparecen en la visualización optimoptions. Estas opciones se muestran en cursiva en la siguiente tabla. Para obtener más detalles, consulte Consultar las opciones de optimización.

Todos los algoritmos

Algorithm

Escoja el algoritmo:

  • 'interior-point-convex' (valor predeterminado)

  • 'trust-region-reflective'

  • 'active-set'

El algoritmo 'interior-point-convex' gestiona únicamente problemas convexos. El algoritmo 'trust-region-reflective' gestiona problemas que tienen solo límites o solo restricciones de igualdad lineales, pero no ambos. El algoritmo 'active-set' gestiona problemas indefinidos siempre que la proyección de H en el espacio nulo de Aeq sea semidefinida positiva. Para obtener más detalles, consulte Seleccionar el algoritmo.

Diagnóstico

Muestre información de diagnóstico sobre la función que se desea minimizar o resolver. Las opciones son 'on' u 'off' (valor predeterminado).

Display

Nivel de visualización (consulte Visualización iterativa):

  • 'off' o 'none' no muestran salida alguna.

  • 'final' solo muestra la salida final (valor predeterminado).

Los algoritmos 'interior-point-convex' y 'active-set' admiten valores adicionales:

  • 'iter' especifica una visualización iterativa.

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

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

MaxIterations

Número máximo de iteraciones permitidas; un entero positivo.

  • Para un problema con restricciones de igualdad 'trust-region-reflective', el valor predeterminado es 2*(numberOfVariables – numberOfEqualities).

  • 'active-set' tiene un valor predeterminado de 10*(numberOfVariables + numberOfConstraints).

  • Para el resto de algoritmos y problemas, el valor predeterminado es 200.

Para optimset, el nombre de opción es MaxIter. Consulte Nombres de opciones actuales y antiguos.

OptimalityTolerance

Tolerancia de terminación en la optimalidad de primer orden; un escalar positivo.

  • Para un problema con restricciones de igualdad 'trust-region-reflective', el valor predeterminado es 1e-6.

  • Para un problema con límites de restricción 'trust-region-reflective', el valor predeterminado es 100*eps, aproximadamente 2.2204e-14.

  • Para los algoritmos 'interior-point-convex' y 'active-set', el valor predeterminado es 1e-8.

Consulte Tolerancias y criterios de detención.

Para optimset, el nombre de opción es TolFun. Consulte Nombres de opciones actuales y antiguos.

StepTolerance

Tolerancia de terminación en x; un escalar positivo.

  • Para 'trust-region-reflective', el valor predeterminado es 100*eps, aproximadamente 2.2204e-14.

  • Para 'interior-point-convex', el valor predeterminado es 1e-12.

  • Para 'active-set', el valor predeterminado es 1e-8.

Para optimset, el nombre de opción es TolX. Consulte Nombres de opciones actuales y antiguos.

Solo el algoritmo 'trust-region-reflective'

FunctionTolerance

Tolerancia de terminación en el valor de la función; un escalar positivo. El valor predeterminado depende del tipo de problema: los problemas con límites de restricción utilizan 100*eps y los problemas con restricciones de igualdad utilizan 1e-6. Consulte Tolerancias y criterios de detención.

Para optimset, el nombre de opción es TolFun. Consulte Nombres de opciones actuales y antiguos.

HessianMultiplyFcn

Función de multiplicación de matriz hessiana, especificada como un identificador de función. Para problemas estructurados a gran escala, esta función calcula el producto de la matriz hessiana H*Y sin formar H. La función tiene el formato

W = hmfun(Hinfo,Y)

donde Hinfo (y posiblemente algunos parámetros adicionales) contiene las matrices utilizadas para calcular H*Y.

Consulte Quadratic Minimization with Dense, Structured Hessian para ver un ejemplo que utiliza esta opción.

Para optimset, el nombre de opción es HessMult. Consulte Nombres de opciones actuales y antiguos.

MaxPCGIter

Número máximo de iteraciones PCG (gradiente conjugado precondicionado); un escalar positivo. El valor predeterminado es max(1,floor(numberOfVariables/2)) para los problemas con límites de restricción. Para los problemas con restricciones de igualdad, quadprog ignora MaxPCGIter y utiliza MaxIterations para limitar el número de iteraciones PCG. Para obtener más información, consulte Preconditioned Conjugate Gradient Method.

PrecondBandWidth

Ancho de banda superior del precondicionador para PCG; un entero no negativo. De forma predeterminada, quadprog utiliza precondicionamiento diagonal (ancho de banda superior de 0). Para algunos problemas, aumentar el ancho de banda reduce el número de iteraciones PCG. Estableciendo PrecondBandWidth en Inf se utiliza una factorización directa (Cholesky) en lugar de los gradientes conjugados (CG). La factorización directa es más costosa computacionalmente que CG, pero produce un paso de mejor calidad hacia la solución.

SubproblemAlgorithm

Determina cómo se calcula el paso de iteración. La opción predeterminada, 'cg', realiza un paso más rápido, pero menos preciso que 'factorization'. Consulte trust-region-reflective quadprog Algorithm.

TolPCG

Tolerancia de terminación en la iteración PCG; un escalar positivo. La opción predeterminada es 0.1.

TypicalX

Valores x típicos. El número de elementos en TypicalX es igual al número de elementos en x0, el punto de inicio. El valor predeterminado es ones(numberOfVariables,1). quadprog utiliza TypicalX internamente para el escalado. TypicalX solo tiene efecto cuando x tiene componentes desacotados y cuando un valor TypicalX para un componente desacotado sobrepasa 1.

Solo el algoritmo 'interior-point-convex'

ConstraintTolerance

Tolerancia en la vulneración de restricciones; un escalar positivo. La opción predeterminada es 1e-8.

Para optimset, el nombre de opción es TolCon. Consulte Nombres de opciones actuales y antiguos.

LinearSolver

Tipo de solver lineal interno en el algoritmo:

  • 'auto' (valor predeterminado): utilice 'sparse' si la matriz H es dispersa y 'dense' si no lo es.

  • 'sparse': utiliza álgebra lineal dispersa. Consulte Matrices dispersas.

  • 'dense': utiliza álgebra lineal densa.

Solo el algoritmo 'active-set'

ConstraintTolerance

Tolerancia en la vulneración de restricciones; un escalar positivo. El valor predeterminado es 1e-8.

Para optimset, el nombre de opción es TolCon. Consulte Nombres de opciones actuales y antiguos.

ObjectiveLimit

Una tolerancia (criterio de detención) que es un escalar. Si el valor de la función objetivo es inferior a ObjectiveLimit y el punto actual es factible, las iteraciones se detienen porque se supone que el problema está desacotado. El valor predeterminado es -1e20.

Estructura de problema, especificada como estructura con estos campos:

H

Matriz simétrica en 1/2*x'*H*x

f

Vector en término lineal f'*x

Aineq

Matriz en restricciones de desigualdad lineales Aineq*x bineq

bineq

Vector en restricciones de desigualdad lineales Aineq*x bineq

Aeq

Matriz en restricciones de igualdad lineales Aeq*x = beq

beq

Vector en restricciones de igualdad lineales Aeq*x = beq
lbVector de límites inferiores
ubVector de límites superiores

x0

Punto inicial para x

solver

'quadprog'

options

Opciones creadas con optimoptions u optimset

Los campos requeridos son H, f, solver y options. Durante la resolución, quadprog ignora cualquier campo de problem excepto los enumerados.

Nota

No puede utilizar el arranque en caliente con el argumento problem.

Tipos de datos: struct

Objeto de arranque en caliente, especificado como objeto creado utilizando optimwarmstart. El objeto de arranque en caliente contiene el punto de inicio y opciones, además de datos opcionales para el tamaño de memoria en la generación de código. Consulte Warm Start Best Practices.

Ejemplo: ws = optimwarmstart(x0,options)

Argumentos de salida

contraer todo

Solución, devuelta como un vector real. x es el vector que minimiza 1/2*x'*H*x + f'*x sujeto a todos los límites y restricciones lineales. x puede ser un mínimo local para problemas no convexos. Para problemas convexos, x es un mínimo global. Para obtener más información, consulte Óptimos locales frente a globales.

Solución de objeto de arranque en caliente, devuelta como objeto QuadprogWarmStart. El punto de solución es wsout.X.

Puede utilizar wsout como el objeto de entrada de arranque en caliente en una llamada quadprog posterior.

Valor de la función objetivo en la solución, devuelto como un escalar real. fval es el valor de 1/2*x'*H*x + f'*x en la solución x.

Razón por la que quadprog se ha detenido, devuelta como un entero descrito en esta tabla.

Todos los algoritmos

1

La función ha convergido a la solución x.

0

El número de iteraciones ha sobrepasado options.MaxIterations.

-2

El problema no es factible. O, para 'interior-point-convex', el tamaño de paso ha sido menor que options.StepTolerance, pero no se han cumplido las restricciones.

-3

El problema está desacotado.

Algoritmo 'interior-point-convex'

2

El tamaño de paso ha sido menor que options.StepTolerance y se han cumplido las restricciones.

-6

Problema no convexo detectado.

-8

No se ha podido calcular una dirección de paso.

Algoritmo 'trust-region-reflective'

4

Mínimo local encontrado; el mínimo no es único.

3

El cambio en el valor de la función objetivo ha sido menor que options.FunctionTolerance.

-4

La dirección de búsqueda actual no era una dirección de descenso. No se puede seguir progresando.

Algoritmo 'active-set'

-6

Problema no convexo detectado; la proyección de H en el espacio nulo de Aeq no es semidefinida positiva.

Nota

Ocasionalmente, el algoritmo 'active-set' se detiene con el indicador de salida 0 cuando el problema está efectivamente desacotado. Si se establece un límite de iteración mayor, también se obtiene el indicador de salida 0.

Información sobre el proceso de optimización, devuelta como estructura con estos campos:

iterations

Número de iteraciones realizadas

algorithm

Algoritmo de optimización utilizado

cgiterations

Número total de iteraciones PCG (solo algoritmo 'trust-region-reflective')

constrviolation

Máximo de funciones de restricción

firstorderopt

Medida de optimalidad de primer orden

linearsolver

Tipo de solver lineal interno, 'dense' o 'sparse' (solo algoritmo 'interior-point-convex')

message

Mensaje de salida

Multiplicadores de Lagrange en la solución, devueltos como estructura con estos campos:

lower

Límites inferiores lb

upper

Límites superiores ub

ineqlin

Desigualdades lineales

eqlin

Igualdades lineales

Para obtener más detalles, consulte Estructuras de multiplicadores de Lagrange.

Algoritmos

contraer todo

'interior-point-convex'

El algoritmo 'interior-point-convex' intenta seguir una ruta estrictamente dentro de las restricciones. Utiliza un módulo de prerresolución para eliminar las redundancias y simplificar el problema resolviendo componentes que son sencillos.

El algoritmo tiene diferentes implementaciones para un matriz hessiana dispersa H y para una matriz densa. Por lo general, la implementación dispersa es más rápida para problemas grandes y dispersos, y la densa es más rápida para problemas densos o pequeños. Para obtener más información, consulte interior-point-convex quadprog Algorithm.

'trust-region-reflective'

El algoritmo 'trust-region-reflective' es un método de región de confianza de subespacio basado en el método de Newton de reflejo de punto interior descrito en [1]. Cada iteración implica la solución aproximada de un sistema lineal amplio utilizando el método de gradientes conjugados precondicionados (PCG). Para obtener más información, consulte trust-region-reflective quadprog Algorithm.

'active-set'

El algoritmo 'active-set' es un método de proyección, similar al descrito en [2]. No es un algoritmo a gran escala; consulte Algoritmos a gran escala frente a algoritmos a media escala. Para obtener más información, consulte active-set quadprog Algorithm.

Arranque en caliente

Un objeto de arranque en caliente mantiene una lista de restricciones activas del problema resuelto previamente. El solver guarda tanta información activa de la restricción como sea posible para resolver el problema actual. Si el problema previo es demasiado diferente al actual, no se utiliza ningún conjunto de información activo. En este caso, en la práctica, el solver ejecuta un arranque en frío para restaurar la lista de restricciones activas.

Funcionalidad alternativa

App

La tarea Optimize de Live Editor proporciona una interfaz visual para quadprog.

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, 1996, pp. 1040–1058.

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

[3] Gould, N., and P. L. Toint. “Preprocessing for quadratic programming.” Mathematical Programming. Series B, Vol. 100, 2004, pp. 95–132.

Capacidades ampliadas

Historial de versiones

Introducido antes de R2006a