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

$\min_{x} \frac{1}{2} x^{T} H x + f^{T} x such that {\begin{matrix} A \cdot x \leq b, \\ A e q \cdot x = b e q, \\ l b \leq x \leq u b . \end{matrix}$

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*eps`y 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 `HY` 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 `HY`. 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 `MaxPCGIter`y 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/2x'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`
`lb`	Vector de límites inferiores
`ub`	Vector 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) = \frac{1}{2} x_{1}^{2} + x_{2}^{2} - x_{1} x_{2} - 2 x_{1} - 6 x_{2},$

sujeto a

x₁ + x₂ ≤ 2
–x₁ + 2x₂ ≤ 2
2x₁ + x₂ ≤ 3
0 ≤ x₁, 0 ≤ x₂.

En la notación matricial es

$f (x) = \frac{1}{2} x^{T} H x + f^{T} x,$

Donde

$H = [\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix}], f = [\begin{matrix} - 2 \\ - 6 \end{matrix}], x = [\begin{matrix} x_{1} \\ x_{2} \end{matrix}] .$

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

Defina las opciones para utilizar el algoritmo 'interior-point-convex' sin mostrar:

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

Llame a quadprog:

[x,fval,exitflag,output,lambda] = ...    quadprog(H,f,A,b,[],[],lb,[],[],options);

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

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.

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);
```
Incluya el término lineal para el problema:
```
f = -4: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;
```
Defina las opciones para utilizar el algoritmo 'interior-point-convex' y la visualización iterativa:
```
opts = optimoptions('quadprog',...     'Algorithm','interior-point-convex','Display','iter');
```

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.

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.