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.

Algoritmos de programación lineal

Definición de programación lineal

La programación lineal es el problema de encontrar un vector x que minimiza una función lineal FTx sujeto a restricciones lineales:

minxfTx

tal que uno o más de los siguientes Hold:

A·xb
Aeq·x = beq
xu.l

Algoritmo de linprog de punto interior

El algoritmo linprog 'interior-point' es muy similar al algoritmo de interior-point-convex quadprog. También comparte muchas características con el algoritmo linprog 'interior-point-legacy' . Estos algoritmos tienen el mismo esquema general:

  1. Presolver, significando la simplificación y la conversión del problema a una forma estándar.

  2. Generar un punto inicial. La elección de un punto inicial es especialmente importante para resolver los algoritmos de punto interior de manera eficiente, y este paso puede requerir mucho tiempo.

  3. Predictor-corrector de iteraciones para resolver las ecuaciones KKT. Este paso es generalmente el más desperdiciador de tiempo.

PRESOLVE

El algoritmo comienza intentando simplificar el problema eliminando redundancias y simplificando las restricciones. Las tareas realizadas durante el paso de presolver incluyen:

  • Compruebe si las variables tienen límites superiores e inferiores iguales. Si es así, compruebe si hay viabilidad y, a continuación, fije y elimine las variables.

  • Compruebe si cualquier restricción de desigualdad lineal implica sólo una variable. Si es así, compruebe si hay viabilidad y cambie la restricción lineal a un límite.

  • Compruebe si cualquier restricción de igualdad lineal implica sólo una variable. Si es así, compruebe si hay viabilidad y, a continuación, fije y elimine la variable.

  • Compruebe si cualquier matriz de restricción lineal tiene cero filas. Si es así, compruebe si hay viabilidad y elimine las filas.

  • Compruebe si los límites y las restricciones lineales son coherentes.

  • Compruebe si las variables aparecen sólo como términos lineales en la función objetiva y no aparecen en ninguna restricción lineal. Si es así, Compruebe la viabilidad y el límite, y fije las variables en sus límites apropiados.

  • Cambie las restricciones de desigualdad lineal a las restricciones de igualdad lineal mediante la adición de variables de holgura.

Si el algoritmo detecta un problema inviable o ilimitado, detiene y emite un mensaje de salida apropiado.

El algoritmo podría llegar a un único punto factible, que representa la solución.

Si el algoritmo no detecta un problema inviable o ilimitado en el paso de presolver, continúa, si es necesario, con los demás pasos. Al final, el algoritmo reconstruye el problema original, deshaciendo todas las transformaciones de Presolución. Este paso final es el paso possolve.

Para simplificar, si el problema no se soluciona en el paso de la solución, el algoritmo cambia todos los límites inferiores finitos a cero.

Generar punto inicial

Para establecer el punto inicial, x0, el algoritmo hace lo siguiente.

  1. Inicialice x0 a ones(n,1), donde n es el número de elementos de la función objetiva vector f.

  2. Convertir todos los componentes delimitados para tener un límite inferior de 0. Si el componente i tiene un u(i)límite superior finito, entonces x0(i) = u/2.

  3. Para los componentes que sólo tienen un límite, modifique el componente si es necesario para mentir estrictamente dentro del límite.

  4. Para colocar x0 cerca de la ruta central, tome un paso predictor-corrector y, a continuación, modifique la posición resultante y las variables flojas para que se encuentran bien dentro de los límites. Para detalles de la ruta central, vea Nocedal y Wright [7], Página 397.

Predictor-corrector

Al igual que el fmincon algoritmo de punto interior, el algoritmo interior-point-convex intenta encontrar un punto donde las condiciones Karush-Kuhn-Tucker (KKT) se mantienen. Para describir estas ecuaciones para el problema de programación lineal, considere la forma estándar del problema de programación lineal después del preprocesamiento:

minxfTx subject to {A¯x=b¯x+t=ux,t0.

  • Asumamos por ahora que todas las variables tienen al menos un límite finito. Cambiando y negando componentes, si es necesario, esta suposición significa que todos los componentes x tienen un límite inferior de 0.

  • A¯ es la matriz lineal extendida que incluye las desigualdades lineales y las igualdades lineales. b¯ es el vector de igualdad lineal correspondiente. A¯ también incluye los términos para extender el vector x con las variables flojas s que convierten restricciones de la desigualdad a las restricciones de la igualdad:

    A¯x=(Aeq0AI)(x0s),

    donde x0 significa el vector x original.

  • t es el vector de los pantalones que convierten los límites superiores a las igualdades.

El Lagrange para este sistema implica los vectores siguientes:

  • y, Multiplicadores de Lagrange asociados a las igualdades lineales

  • v, Multiplicadores de Lagrange asociados con el límite inferior (restricción de positividad)

  • w, Multiplicadores de Lagrange asociados con el límite superior

El Lagrange es

L=fTxyT(A¯xb¯)vTxwT(uxt).

Por lo tanto, las condiciones KKT para este sistema son

fA¯Tyv+w=0A¯x=b¯x+t=uvixi=0witi=0(x,v,w,t)0.

El algoritmo primero predice un paso de la fórmula de Newton-Raphson, y luego calcula un paso corrector. El corrector intenta reducir el residuo en las ecuaciones de complementariedad no lineal sizi = 0. El paso de Newton-Raphson es

(0A¯T0IIA¯0000I0I00V00X000W0T)(ΔxΔyΔtΔvΔw)=(fA¯Tyv+wA¯xb¯uxtVXWT)=(rdrprubrvxrwt),(1)

donde X, V, Wy T son matrices diagonales correspondientes a los vectores x, v, wy t respectivamente. Los vectores residuales en el extremo derecho de la ecuación son:

  • Rd, el doble residual

  • Rp, el primario residual

  • Rub, el límite superior residual

  • Rvx, la complementariedad residual de menor límite

  • Rwt, el residuo de complementariedad del límite superior

La pantalla iterativa reporta estas cantidades:

Primal infeasibility=rp1+rub1Dual infeasibility=rd.

Para resolver Ecuación 1, primero convertirlo a la forma de matriz simétrica

(DA¯TA¯0)(ΔxΔy)=(Rrp),(2)

Donde

D=X1V+T1WR=rdX1rvx+T1rwt+T1Wrub.

Todos los inversos de la matriz en las definiciones de D y R son simples de calcular porque las matrices son diagonales.

Para derivar Ecuación 2 de Ecuación 1, observe que la segunda fila de Ecuación 2 es la misma que la segunda fila de matriz de Ecuación 1. La primera fila de Ecuación 2 viene de resolver las dos últimas filas de Ecuación 1 para δv y δw, y entonces resolviendo para δt.

Ecuación 2 es simétrico, pero no es positivo definido debido al término –D . Por lo tanto, no se puede resolver usando una factorización Cholesky. Algunos pasos más conducen a una ecuación diferente que es positiva definida, y por lo tanto puede ser solucionado eficientemente por factorización Cholesky.

El segundo conjunto de filas de Ecuación 2 es

A¯Δx=rp

y el primer conjunto de filas es

DΔx+A¯TΔy=R.

Sustituyendo

Δx=D1A¯TΔy+D1R

Da

A¯D1A¯TΔy=A¯D1Rrp.(3)

Generalmente, la manera más eficiente de encontrar el paso del neutonio es solucionar Ecuación 3 para Δy usando la factorización Cholesky. La factorización Cholesky es posible porque la matriz que multiplica Δy es obviamente simétrica y, en ausencia de degeneraciones, es positiva definida. Después, para encontrar el paso de Newton, sustituto de atrás para encontrar δx, δt, δv, y δw. Sin embargo, cuando A¯ tiene una columna densa, puede ser más eficiente para resolver Ecuación 2 en su lugar. El algoritmo de punto interior de linprog elige el algoritmo de solución basado en la densidad de columnas.

Para obtener más detalles sobre el algoritmo, consulte Mehrotra [6].

Después de calcular el paso corregido del neutonio, el algoritmo realiza más cálculos para conseguir ambos un paso actual más largo, y prepararse para pasos subsecuentes mejores. Estos cálculos de corrección múltiple pueden mejorar tanto el rendimiento como la robustez. Para obtener más información, consulte Gondzio [4].

El algoritmo predictor-corrector es en gran parte el mismo que la versión completa de quadprog 'interior-point-convex' , a excepción de los términos cuadráticos. Véase Predictor completo-corrector.

Condiciones de parada

El algoritmo predictor-corrector itera hasta que alcanza un punto que es factible (satisface las restricciones dentro de las tolerancias) y donde los tamaños de los pasos relativos son pequeños. Específicamente, defina

ρ=max(1,A¯,f,b¯).

El algoritmo se detiene cuando se cumplen todas estas condiciones:

rp1+rub1ρTolConrdρTolFunrcTolFun,

Donde

rc=maxi(min(|xivi|,|xi|,|vi|),min(|tiwi|,|ti|,|wi|)).

Rc esencialmente mide el tamaño de los residuales de complementariedad xv y tw, que son cada vectores de ceros en una solución.

Interior-punto-Legacy programación lineal

Introducción

El método predeterminado interior-punto-legado se basa en LIPSOL ([52]), que es una variante de Algoritmo predictor-corrector de Mehrotra ([47]), un método primal-dual del interior-punto.

Algoritmo principal

El algoritmo comienza aplicando una serie de pasos de preprocesamiento (ver Preprocesamiento). Después del preprocesamiento, el problema tiene la forma

minxfTx such that {Ax=b0xu.(4)

Las restricciones de límites superiores se incluyen implícitamente en la matriz de restricción A. Con la adición de las variables de holgura primarias s, Ecuación 4 se convierte en

minxfTx such that {Ax=bx+s=ux0, s0.(5)

que se conoce como el problema Primordial : x consiste en las variables primarias y s consiste en las variables de holgura primarias. El problema de Doble es

maxbTyuTw  such that  {ATyw+z=fz0, w0,(6)

donde y y w consisten en las variables duales y z consiste en los pantalones dobles. La las condiciones de la optimización para este programa linear, es decir, el Ecuación 5 primario y el Ecuación 6dual, son

F(x,y,z,s,w)=(Axbx+suATyw+zfxizisiwi)=0,                 x0, z0, s0, w0,(7)

Donde xiZi Y siWi denota multiplicación por componentes.

Las ecuaciones cuadráticas xizi = 0 Y siwi = 0 se llaman el Complementariedad condiciones para el programa lineal; las otras ecuaciones (lineales) se denominan condiciones Viabilidad . La cantidad

xTZ + sTW

es el brecha de la dualidad, que mide el residuo de la porción de complementariedad de F cuando (x,z,s,w) ≥ 0.

El algoritmo es un Algoritmo primal-dual, lo que significa que tanto los programas primarios como los duales se resuelven simultáneamente. Se puede considerar un método similar a Newton, aplicado al sistema lineal-cuadrático F(x,y,z,s,w) = 0 en Ecuación 7, mientras que al mismo tiempo manteniendo las iteraciones x, z, w, y s positivo, así el nombre interior-método del punto. (las iteraciones están en la región estrictamente interior representada por las limitaciones de la desigualdad en Ecuación 5.)

El algoritmo es una variante del algoritmo predictor-corrector propuesto por Mehrotra. Considere una iteración v = [x;y;z;s;w]Donde [x;z;s;w] > 0 Primero compute la dirección Predicción supuesta

Δvp=(FT(v))1F(v),

que es la dirección Newton; entonces la llamada dirección corrector

Δvc=(FT(v))1F(v+Δvp)μe^,

Donde μ > 0 se llama el Centrado parámetro y debe ser elegido cuidadosamente. e^ es un vector cero-uno con los que corresponden a las ecuaciones cuadráticas en F(v), es decir, las perturbaciones sólo se aplican a las condiciones de complementariedad, que son todas cuadráticas, pero no a las condiciones de viabilidad, que son todos Lineal. Las dos direcciones se combinan con un parámetro de longitud de paso α > 0 y actualizar v para obtener la nueva iteración v+:

v+=v+α(Δvp+Δvc),

donde se elige el parámetro de longitud de paso α para que

V+ = [x+; y+; z+; s+; w+]

Satisface

[x+; z+; s+; w+] > 0.

En la resolución para las direcciones precedentes del calculador/del corrector, el algoritmo computa una factorización directa (escasa) en una modificación de los factores Cholesky de A·AT. Si A tiene columnas densas, en su lugar utiliza el Fórmula Sherman-Morrison. Si esa solución no es adecuada (el residuo es demasiado grande), realiza una factorización del LDL de una forma del sistema aumentada de las ecuaciones del paso para encontrar una solución. (consulte Ejemplo 4: la estructura de D (MATLAB) en la página de referencia de la función MATLAB® ldl .)

A continuación, el algoritmo se enlaza hasta que convergen las iteraciones. Los principales criterios de parada son los estándares:

max(rbmax(1,b),rfmax(1,f),rumax(1,u),|fTxbTy+uTw|max(1,|fTx|,|bTyuTw|))tol,

Donde

rb=Axbrf=ATyw+zfru={x}+su

son la viabilidad primaria residual, doble residual y de límite superior respectivamente ({x} significa ésos x con los límites superiores finitos), y

fTxbTy+uTw

es la diferencia entre los valores primarios y los objetivos duales, y el tol es una cierta tolerancia. La suma en el los criterios de parada miden los errores relativos totales en las condiciones de la optimalidad en Ecuación 7.

La medida de la inviabilidad primaria es ||rb||, y la medida de la doble inviabilidad es ||rf||, donde la norma es la norma euclidiana.

Preprocesamiento

El algoritmo comienza intentando simplificar el problema eliminando redundancias y simplificando las restricciones. Las tareas realizadas durante el paso de presolver incluyen:

  • Compruebe si las variables tienen límites superiores e inferiores iguales. Si es así, compruebe si hay viabilidad y, a continuación, fije y elimine las variables.

  • Compruebe si cualquier restricción de desigualdad lineal implica sólo una variable. Si es así, compruebe si hay viabilidad y cambie la restricción lineal a un límite.

  • Compruebe si cualquier restricción de igualdad lineal implica sólo una variable. Si es así, compruebe si hay viabilidad y, a continuación, fije y elimine la variable.

  • Compruebe si cualquier matriz de restricción lineal tiene cero filas. Si es así, compruebe si hay viabilidad y elimine las filas.

  • Compruebe si los límites y las restricciones lineales son coherentes.

  • Compruebe si las variables aparecen sólo como términos lineales en la función objetiva y no aparecen en ninguna restricción lineal. Si es así, Compruebe la viabilidad y el límite, y fije las variables en sus límites apropiados.

  • Cambie las restricciones de desigualdad lineal a las restricciones de igualdad lineal mediante la adición de variables de holgura.

Si el algoritmo detecta un problema inviable o ilimitado, detiene y emite un mensaje de salida apropiado.

El algoritmo podría llegar a un único punto factible, que representa la solución.

Si el algoritmo no detecta un problema inviable o ilimitado en el paso de presolver, continúa, si es necesario, con los demás pasos. Al final, el algoritmo reconstruye el problema original, deshaciendo todas las transformaciones de Presolución. Este paso final es el paso possolve.

Para simplificar, el algoritmo desplaza todos los límites inferiores a cero.

Mientras que estos pasos de preprocesamiento pueden hacer mucho para acelerar la parte iterativa del algoritmo, si el Los multiplicadores de Lagrange son requeridos, los pasos de preprocesamiento deben ser deshechos ya que los multiplicadores calculados durante el algoritmo son para el problema transformado, y no el original. Así, si los multiplicadores son No solicitado, esta parte posteriora de la transformación no se computa, y pudo ahorrar una cierta hora de cómputo.

Algoritmo dual-simplex

En un nivel alto, el algoritmo linprog 'dual-simplex' esencialmente realiza un algoritmo simplex en el doble problema.

El algoritmo comienza por preprocesamiento como se describe en Preprocesamiento. Para más detalles, véase Andersen y Andersen [1] y Nocedal y Wright [7], capítulo 13. Este preprocesamiento reduce el problema de programación lineal original a la forma de Ecuación 4:

minxfTx such that {Ax=b0xu.

A y b son versiones transformadas de las matrices de restricción originales. Este es el problema primordial.

La viabilidad primaria se puede definir en términos + Función

x+={xif x>00if x0.

La medida de la inviabilidad primaria es

Primal infeasibility=((lbx)+)2+((xub)+)2+((Axb)+)2+|Aeqxbeq|2.

Como se explica en Ecuación 6, el doble problema es encontrar los vectores y y w, y un z de vectores de holgura variable que resuelven

maxbTyuTw  such that  {ATyw+z=fz0, w0.

La medida de la doble inviabilidad es

Dual infeasibility=ATy+zwf2.

Es bien sabido (por ejemplo, vea [7]) que cualquier solución finita del problema dual da una solución al problema primario, y cualquier solución finita del problema primario da una solución del problema dual. Además, si el problema primario o dual es ilimitado, entonces el otro problema es inviable. Y si el problema primario o dual es inviable, entonces el otro problema es inviable o ilimitado. Por lo tanto, los dos problemas son equivalentes en términos de obtener una solución finita, si existe uno. Debido a que los problemas primarios y duales son matemáticamente equivalentes, pero los pasos computacionales difieren, puede ser mejor resolver el problema primario resolviendo el problema dual.

Para ayudar a aliviar la degeneración (ver Nocedal y Wright [7], página 366), el algoritmo de doble cara comienza por perturbar la función objetiva.

La fase 1 del algoritmo dual simplex es encontrar un punto dual factible. El algoritmo hace esto resolviendo un problema auxiliar de la programación linear.

 Resumen de la fase 1

Durante la fase 2, el solucionador elige repetidamente una variable de entrada y una variable de salida. El algoritmo escoge una variable que se va de acuerdo a una técnica sugerida por Forrest y [3] , llamado precio de borde más escarpado doble. El algoritmo elige una variable que entra usando la variación de la prueba de cociente de Harris sugerida por Koberstein [5]. Para ayudar a aliviar la degeneración, el algoritmo puede introducir perturbaciones adicionales durante la fase 2.

 Contorno de fase 2

El solucionador itera, intentando mantener la viabilidad dual mientras que reduce la inviabilidad primaria, hasta que la solución al problema reducido, perturbado es a la vez factible primario y dual factible. El algoritmo desenrolla las perturbaciones que introdujo. Si la solución (al problema perturbado) es dual inviable para el problema (original) no perturbado, entonces el Solver restaura la viabilidad dual usando los algoritmos primarios simplex o Phase 1. Finalmente, el solucionador desenrolla los pasos de preprocesamiento para devolver la solución al problema original.

Variables básicas y no básicas

En esta sección se definen los términos Base, no basey soluciones básicas factibles para un problema de programación lineal. La definición supone que el problema se da en el siguiente formulario estándar:

minxfTx such that {Ax=b,lbxub.

(Nótese que A y b no son la matriz y vector que definen las desigualdades en el problema original.) Supongamos que A es una matriz de mporn , de rango m < n, cuyas columnas son {a1, a2, ..., Unn}. Suponga que {ai1,ai2,...,aim} es una base para el espacio de columna de A, con índice set B = {i1, i2, ..., mem}, y que N = {1, 2,..., n} \B es el complemento de B. La submatriz AB se llama Base y la submatriz complementaria AN se llama no base. El vector de variables básicas es xB y el vector de variables no básicas es xN. En cada iteración de la fase 2, el algoritmo sustituye una columna de la base actual por una columna de la no base y actualiza las variables xB y xN Por consiguiente.

Si x es una solución para A·x = b y todas las variables no básicas en xN son iguales a sus límites inferiores o superiores, x se llama un solución básica. Si, además, las variables básicas en xB satisfacen sus límites inferiores y superiores, de modo que x sea un punto factible, x se llama un solución básica factible.

Referencias

[1] Andersen, E. D., and K. D. Andersen. Presolving in linear programming. Math. Programming 71, 1995, pp. 221–245.

[2] Applegate, D. L., R. E. Bixby, V. Chvátal and W. J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2007.

[3] Forrest, J. J., and D. Goldfarb. Steepest-edge simplex algorithms for linear programming. Math. Programming 57, 1992, pp. 341–374.

[4] Gondzio, J. “Multiple centrality corrections in a primal dual method for linear programming.” Computational Optimization and Applications, Volume 6, Number 2, 1996, pp. 137–156. Available at http://www.maths.ed.ac.uk/~gondzio/software/correctors.ps.

[5] Koberstein, A. Progress in the dual simplex algorithm for solving large scale LP problems: techniques for a fast and stable implementation. Computational Optim. and Application 41, 2008, pp. 185–204.

[6] Mehrotra, S. “On the Implementation of a Primal-Dual Interior Point Method.” SIAM Journal on Optimization, Vol. 2, 1992, pp 575–601.

[7] Nocedal, J., and S. J. Wright. Numerical Optimization, Second Edition. Springer Series in Operations Research, Springer-Verlag, 2006.