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.

quadprog

Programación cuadrática

Sintaxis

x = quadprog(H,f)
x = quadprog(H,f,A,b)
x = quadprog(H,f,A,b,Aeq,beq)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
x = quadprog(problem)
[x,fval] = quadprog(H,f,...)
[x,fval,exitflag] = quadprog(H,f,...)
[x,fval,exitflag,output] = quadprog(H,f,...)
[x,fval,exitflag,output,lambda] = quadprog(H,f,...)

Descripción

Encuentra un mínimo para un problema especificado por

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

H, Ay Aeq son matrices, y f, b, beq, lb, uby x son vectores.

f, lby ub se pueden pasar como vectores o matrices; Véase Argumentos de matriz.

x = quadprog(H,f) Devuelve un vector x que minimiza 1/2*x'*H*x + f'*x. H debe ser positivo definido para que el problema tenga un mínimo finito.

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

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 = [].

x = quadprog(H,f,A,b,Aeq,beq,lb,ub) resuelve el problema anterior sujeto a las restricciones adicionales lb  x  ub. 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 incoherentes, el x de salida es x0 y el fval de salida es [].

quadprog restablece los componentes de x0 que violan los límites lb  x  ub al interior de la caja definida 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) soluciona el problema precedente a partir del vector x0. Si no existen límites, establezca lb = [] y ub = []. Algunos algoritmos quadprog ignoran x0, véase Argumentos de entrada.

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

x = quadprog(problem) Devuelve el mínimo para problem, donde problem es una estructura descrita en Argumentos de entrada. Crear problem mediante la exportación de un problema mediante la aplicación de optimización; Véase Exportar su trabajo.

[x,fval] = quadprog(H,f,...) Devuelve el valor de la función objetivo en x:

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

[x,fval,exitflag] = quadprog(H,f,...) exitflag, un escalar que describe la condición de salida de quadprog.

[x,fval,exitflag,output] = quadprog(H,f,...) output, una estructura que contiene información sobre la optimización.

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

Argumentos de entrada

H

Matriz simétrica de dobles. Representa el cuadrático en la expresión 1/2*x'*H*x + f'*x.

El algoritmo 'interior-point-convex' tiene diferentes implementaciones para una matriz de hessian disperso H y para una matriz densa. En general, la aplicación dispersa es más rápida en problemas grandes y dispersos, y la aplicación densa es más rápida en problemas densos o pequeños. Para obtener más información, consulte algoritmo de interior-point-convex quadprog.

f

Vector de dobles. Representa el término linear en la expresión 1/2*x'*H*x + f'*x.

A

Matriz de dobles. Representa los coeficientes lineales en las restricciones A*x  b.

b

Vector de dobles. Representa el vector constante en las restricciones A*x  b.

Aeq

Matriz de dobles. Representa los coeficientes lineales en las restricciones Aeq*x = beq.

beq

Vector de dobles. Representa el vector constante en las restricciones Aeq*x = beq.

lb

Vector de dobles. Representa los límites inferiores elementwise en lb  x  ub.

ub

Vector de dobles. Representa los límites superiores elementwise en lb  x  ub.

x0

Vector de dobles. Opcional. El punto inicial del algoritmo trust-region-reflective cuando sólo hay restricciones enlazadas.

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

options

Opciones creadas con optimoptions o la aplicación de optimización.

Algunas opciones están ausentes de la pantalla optimoptions . Estas opciones se enumeran en cursiva. Para obtener más información, consulte Ver opciones.

Todos los algoritmos

Algorithm

Elija el algoritmo:

  • 'interior-point-convex' (por defecto)

  • 'trust-region-reflective'

El algoritmo 'trust-region-reflective' maneja problemas con sólo límites, o sólo restricciones de igualdad lineal, pero no ambas. El algoritmo de 'interior-point-convex' maneja solamente problemas convexos. Para obtener más información, consulte Elegir el algoritmo.

Diagnostics

Mostrar información de diagnóstico sobre la función a minimizar o resolver. Las opciones son 'on' o 'off' (por defecto).

Display

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

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

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

El algoritmo 'interior-point-convex' permite valores adicionales:

  • 'iter' da la exhibición iterativa.

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

  • 'final-detailed' muestra sólo la salida final, con un mensaje de salida detallado.

MaxIterations

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

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

  • Para todos los demás algoritmos y problemas, el valor predeterminado es 200.

Para optimset, el nombre es MaxIter. Véase Tablas de nombres de opciones actuales y heredadas.

OptimalityTolerance

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

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

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

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

Véase Tolerancias y criterios de parada.

Para optimset, el nombre es TolFun. Véase Tablas de nombres de opciones actuales y heredadas.

StepTolerance

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

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

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

Para optimset, el nombre es TolX. Véase Tablas de nombres de opciones actuales y heredadas.

sólo algoritmo de confianza-región-reflexivo

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 restringidos enlazados utilizan 100*epsy los problemas de igualdad lineal utilizan 1e-6. Véase Tolerancias y criterios de parada.

Para optimset, el nombre es TolFun. Véase Tablas de nombres de opciones actuales y heredadas.

HessianMultiplyFcn

El hessian multiplica la función, especificada como manija de la función. Para los problemas estructurados en grande, esta función computa el producto de la matriz del hessian H*Y sin realmente formar H. La función tiene la forma

W = hmfun(Hinfo,Y)

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

Consulte Minimización cuadrática con hessian denso y estructurado para ver un ejemplo que utiliza esta opción.

Para optimset, el nombre es HessMult. Véase Tablas de nombres de opciones actuales y heredadas.

MaxPCGIter

Número máximo de iteraciones de PCG (gradiente conjugado precondicionado), un escalar positivo. El valor predeterminado es max(1,floor(numberOfVariables/2)) para los problemas con restricciones limitadas. Para problemas con restricciones de igualdad, quadprog omite MaxPCGItery utiliza MaxIterations para limitar el número de iteraciones de PCG. Para obtener más información, consulte Método de gradiente de conjugado precondicionado.

PrecondBandWidth

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

SubproblemAlgorithm

Determina cómo se calcula el paso de iteración. El valor predeterminado, 'cg', toma un paso más rápido pero menos preciso que 'factorization'. Véase algoritmo de trust-region-reflective quadprog.

TolPCG

Tolerancia de terminación en la iteración PCG, un escalar positivo. El valor predeterminado es 0.1.

TypicalX

Valores típicos de x . El número de elementos en TypicalX equivale al número de elementos en x0, el punto de partida. El valor predeterminado es ones(numberofvariables,1). quadprog utiliza TypicalX internamente para escalar. TypicalX sólo tiene un efecto cuando x tiene componentes sin límite, y cuando un valor TypicalX para un componente ilimitado excede 1.

algoritmo interior-punto-convexo solamente

ConstraintTolerance

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

Para optimset, el nombre es TolCon. Véase Tablas de nombres de opciones actuales y heredadas.

problem

Estructura encapsulando las entradas y opciones de quadprog :

H

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

f

Vector en el término linear f'*x

Aineq

Matriz en las restricciones de desigualdad lineal Aineq*x  bineq

bineq

Vector en las limitaciones de la desigualdad lineal Aineq*x  bineq

Aeq

Matriz en restricciones de igualdad lineal Aeq*x = beq

beq

Vector en las restricciones de igualdad lineal 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 o la aplicación de optimización

Argumentos de salida

x

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 los problemas convexos, x es un mínimo global. Para obtener más información, consulte Local vs global optima.

fval

Valor de 1/2*x'*H*x + f'*x en la solución x, un doble.

exitflag

Entero que identifica la razón por la que el algoritmo terminó. A continuación se enumeran los valores de exitflag y las razones correspondientes que el algoritmo terminó:

Todos los algoritmos

1

La función convergió a la solución x.

0

Número de iteraciones excedidas options.MaxIterations.

-2

El problema es inviable. O, para interior-point-convex, tamaño del paso más pequeño que options.StepTolerance, pero las restricciones no se satisfacen.

-3

El problema es ilimitado.

algoritmo interior-point-convex

2

Tamaño del paso más pequeño que options.StepTolerance, restricciones satisfechas.

-6

Problema no convexo detectado.

-8

No se puede calcular una dirección de paso.

algoritmo trust-region-reflective

3

El cambio en el valor de la función objetiva era menor que options.FunctionTolerance.

-4

La dirección actual de la búsqueda no era una dirección del descenso. No se podrían hacer más progresos.

output

Estructura que contiene información sobre la optimización. Los campos son:

iterations

Número de iteraciones tomadas

algorithm

Algoritmo de optimización utilizado

cgiterations

Número total de iteraciones de PCG (sólo algoritmo de confianza-región-reflexivo)

constrviolation

Máximo de funciones de restricción

firstorderopt

Medida de la optimalidad de primer orden

message

Mensaje de salida

lambda

Estructura que contiene los multiplicadores de Lagrange en la solución x (separada por tipo de restricción). Los campos son:

lower

Límites inferiores lb

upper

Límites superiores ub

ineqlin

Desigualdades lineales

eqlin

Igualdades lineales

Para obtener más información, consulte Estructuras multiplicadoras de Lagrange.

Ejemplos

Resuelve un simple problema de programación cuadrática: encuentra los valores de x que minimizan

f(x)=12x12+x22x1x22x16x2,

sujeto a

x1 + x2 ≤ 2
x1 + 2x2 ≤ 2
2x1 + x2 ≤ 3
0 ≤ x1, 0 ≤ x2.

En la notación matricial es

f(x)=12xTHx+fTx,

Donde

H=[1112],  f=[26],  x=[x1x2].

  1. Introduzca las matrices de coeficientes:

    H = [1 -1; -1 2];  f = [-2; -6]; A = [1 1; -1 2; 2 1]; b = [2; 2; 3]; lb = zeros(2,1);
  2. Defina las opciones para utilizar el algoritmo 'interior-point-convex' sin mostrar:

    options = optimoptions('quadprog',...     'Algorithm','interior-point-convex','Display','off');
  3. Llame a quadprog:

    [x,fval,exitflag,output,lambda] = ...    quadprog(H,f,A,b,[],[],lb,[],[],options);
  4. Examine el punto final, el valor de la función y el indicador de salida:

     x,fval,exitflag
    x =     0.6667     1.3333  fval =    -8.2222  exitflag =      1
  5. Una bandera de salida de 1 significa que el resultado es un mínimo local. Debido a que H es una matriz positiva definida, este problema es convexo, por lo que el mínimo es un mínimo global. Usted puede ver H es positivo definido por notar todos sus valores propios son positivos:

    eig(H)
    ans =     0.3820     2.6180

Utilice el algoritmo 'interior-point-convex' para resolver un programa cuadrático escaso.

  1. Generar una matriz simétrica dispersa para la forma cuadrática:

    v = sparse([1,-.25,0,0,0,0,0,-.25]); H = gallery('circul',v);
  2. Incluya el término lineal para el problema:

    f = -4:3;
  3. Incluya la restricción de que la suma de los términos de la solución x debe ser menor que -2:

    A = ones(1,8);b = -2;
  4. Defina las opciones para utilizar el algoritmo 'interior-point-convex' y la visualización iterativa:

    opts = optimoptions('quadprog',...     'Algorithm','interior-point-convex','Display','iter');
  5. Ejecute el solucionador de quadprog y observe las iteraciones:

    [x fval eflag output lambda] = quadprog(H,f,A,b,[],[],[],[],[],opts);
    
                                        First-order	 Total relative
     Iter         f(x)     Feasibility   optimality	     error
        0  -2.000000e+000   1.000e+001   4.500e+000   1.200e+001   
        1  -2.630486e+001   0.000e+000   9.465e-002   9.465e-002   
        2  -2.639877e+001   0.000e+000   3.914e-005   3.914e-005   
        3  -2.639881e+001   0.000e+000   3.069e-015   6.883e-015   
    
    Minimum found that satisfies the constraints.
    
    Optimization completed because the objective function is
    non-decreasing in feasible directions, to within the default value 
    of the function tolerance, and constraints are satisfied to within 
    the default value of the constraint tolerance.
  6. Examine la solución:

    fval,eflag
    fval =   -26.3988  eflag =      1

    Para el algoritmo 'interior-point-convex' , una bandera de salida de 1 significa que el resultado es un mínimo global.

Algoritmos

contraer todo

interior-punto-convexo

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

El algoritmo tiene diversas implementaciones para una matriz escasa del hessian H y para una matriz densa. En general, la aplicación dispersa es más rápida en problemas grandes y dispersos, y la aplicación densa es más rápida en problemas densos o pequeños. Para obtener más información, consulte algoritmo de interior-point-convex quadprog.

confianza-región-reflexivo

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

Alternativas

Puede utilizar la aplicación de optimización para la programación cuadrática. Introduzca optimtool en la línea de comandos MATLAB® y elija el quadprog - Quadratic programming Solver. Para obtener más información, consulte App de optimización.

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.

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

Introducido antes de R2006a