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 cuadrática

Definición de programación cuadrática

La programación cuadrática es el problema de encontrar un vector que minimiza una función cuadrática, posiblemente sujeta a restricciones lineales:x

minx12xTHx+cTx

tal que A·x ≤ b, Aeq·x = beq, l ≤ x ≤ u.

Algoritmointerior-point-convexquadprog

El algoritmo realiza los siguientes pasos:interior-point-convex

Nota

El algoritmo tiene dos rutas de código. Se necesita uno cuando la matriz de Hessian es una matriz ordinaria (completa) de dobles, y se toma la otra cuando es una matriz dispersa.HH Para obtener información detallada sobre el tipo de datos dispersos, consulte.Matrices dispersas (MATLAB) Por lo general, el algoritmo es más rápido para problemas grandes que tienen relativamente pocos términos distintos de cero cuando se especifica como.Hsparse Del mismo modo, el algoritmo es más rápido para problemas pequeños o relativamente densos cuando se especifica como.Hfull

PRESOLVE/Postsolve

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

  • Compruebe si alguna variable tiene límites superiores e inferiores iguales. Si es así, Compruebe la viabilidad y, a continuación, corrija y quite las variables.

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

  • Compruebe si cualquier restricción de igualdad lineal implica solo una variable. Si es así, Compruebe la viabilidad y, a continuación, corrija y quite la variable.

  • Compruebe si alguna matriz de restricción lineal tiene cero filas. Si es así, Compruebe la 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 rebote, y corrija las variables en sus límites apropiados.

  • Cambie las restricciones de desigualdad lineal a las restricciones de igualdad lineales agregando variables de holgura.

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

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

Si el algoritmo no detecta un problema no factible o ilimitado en el paso de PRESOLVE, continúa, si es necesario, con los otros pasos. Al final, el algoritmo reconstruye el problema original, deshaciendo cualquier transformación PRESOLVE. Este paso final es el paso de postresolución.

Para obtener más información, consulte Gould y Toint.[63]

Generar punto inicial

El punto inicial para el algoritmo es:x0

  1. Inicializar a, donde está el número de filas.x0ones(n,1)nH

  2. Para los componentes que tienen un límite superior y un límite inferior, si un componente de no está estrictamente dentro de los límites, el componente se establece en.ublbx0(ub + lb)/2

  3. Para los componentes que tienen solo un límite, modifique el componente si es necesario para que se encuentran estrictamente dentro del límite.

  4. Tome un paso de predictor (ver), con correcciones menores para la viabilidad, no un paso completo de predictor-corrector.Predictor-corrector Esto coloca el punto inicial más cerca de la sin que conlleva la sobrecarga de un paso de predictor-corrector completo.Ruta central Para más detalles sobre la ruta central, véase Nocedal y Wright, Página 397.[7]

Predictor-corrector

Los algoritmos dispersos y completos de punto interior-convexo difieren principalmente en la fase de predictor-corrector. Los algoritmos son similares, pero difieren en algunos detalles. Para la descripción básica del algoritmo, véase Mehrotra.[47]

Los algoritmos empiezan por convertir las desigualdades lineales AX < = b en desigualdades de la forma Ax > = b multiplicando A y b por-1. Esto no tiene ninguna relación con la solución, pero hace que el problema de la misma forma se encuentra en alguna literatura.

Predictor-corrector disperso.  De forma similar a la, el algoritmo disperso intenta encontrar un punto donde se encuentran las condiciones.fminconalgoritmo de punto interiorinterior-point-convexKarush-Kuhn-Tucker (KKT) Para el problema de programación cuadrática descrito en, estas condiciones son:Definición de programación cuadrática

Hx+cAeqTyA¯Tz=0A¯xb¯s=0Aeqxbeq=0sizi=0, i=1,2,...,ms0z0.

Aquí

  • A¯ es la matriz de desigualdad lineal extendida que incluye límites escritos como desigualdades lineales. b¯ es el vector de desigualdad lineal correspondiente, incluidos los límites.

  • es el vector de los pantalones que convierten las restricciones de desigualdad en ecualidades. tiene longitud, el número de desigualdades lineales y límites.ssm

  • es el vector de los multiplicadores de Lagrange correspondientes.zs

  • es el vector de los multiplicadores de Lagrange asociados con las restricciones de igualdad.y

El algoritmo predice primero un paso de la fórmula de Newton-Raphson y, a continuación, calcula un paso de corrector. El corrector intenta aplicar mejor la restricción no lineal sizi = 0.

Definiciones para el paso de predictor:

  • Rd, el residuo doble:

    rd=Hx+cAeqTyA¯Tz.

  • Req, la restricción de igualdad primordial residual:

    req=Aeqxbeq.

  • Rineq, la restricción de la desigualdad primaria residual, que incluye límites y pantalones:

    rineq=A¯xb¯s.

  • Rsz, la complementariedad residual:

    Rsz = .Sz

    es la matriz diagonal de términos de Slack, es la matriz de columnas de los multiplicadores de Lagrange.Sz

  • Rc, la complementariedad media:

    rc=sTzm.

En un paso de Newton, los cambios en,,, y, son dados por:xsyz

(H0AeqTA¯TAeq000A¯I000Z0S)(ΔxΔsΔyΔz)=(rdreqrineqrsz).(1)

Sin embargo, un paso completo de Newton podría ser inviable, debido a las restricciones de positividad en y.sz Por lo tanto, acorta el paso, si es necesario, para mantener la positividad.quadprog

Además, para mantener una posición "centrada" en el interior, en lugar de tratar de resolver sizi = 0, el algoritmo toma un parámetro positivo e intenta resolverσ

siZi = repetición σrc.

Reemplazaquadprog Rsz en la ecuación de paso de Newton con rsz + ΔsΔz – σrc, donde está el vector de los.11 Además, reordena las ecuaciones de Newton para obtener un sistema simétrico, más estable numéricamente para el cálculo del paso del predictor.quadprog

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

Full predictor-corrector.  El algoritmo completo de predictor-corrector no combina límites en restricciones lineales, por lo que tiene otro conjunto de variables de holgura que corresponden a los límites. El algoritmo desplaza los límites inferiores a cero. Y, si sólo hay un límite en una variable, el algoritmo lo convierte en un límite inferior de cero, negando la desigualdad de un límite superior.

A¯ es la matriz lineal extendida que incluye tanto desigualdades lineales como ecualidades lineales. b¯ es el vector de igualdad lineal correspondiente. A¯ también incluye términos para extender el vector con variables de holgura que convierten las restricciones de desigualdad en restricciones de igualdad:xs

A¯x=(Aeq0AI)(x0s),

Dóndex0 significa el vector original.x

Las condiciones de KKT son

Hx+cA¯Tyv+w=0A¯x=b¯x+t=uvixi=0, i=1,2,...,mwiti=0, i=1,2,...,nx,v,w,t0.(2)

Para encontrar la solución, variables de Slack y variables duales, el algoritmo básicamente considera un paso de Newton-Raphson:xEcuación 2

(HA¯T0IIA¯0000I0I00V00X000W0T)(ΔxΔyΔtΔvΔw)=(Hx+cA¯Tyv+wA¯xb¯uxtVXWT)=(rdrprubrvxrwt),(3)

donde,,, y son matrices diagonales que corresponden a los vectores,,, y respectivamente.XVWTxvwt Los vectores residuales en el lado derecho más lejano de la ecuación son:

  • Rd, el doble residuo

  • Rp, el residuo primigenio

  • Rub, el residuo de límite superior

  • Rvx, el residuo de complementariedad de menor límite

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

El algoritmo resuelve convirtiéndolo primero a la forma de matriz simétricaEcuación 3

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

Dónde

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

Toda la matriz invierte en las definiciones de y son simples de calcular porque las matrices son diagonales.DR

Para derivar de, tenga en cuenta que la segunda fila de es la misma que la segunda fila de matriz de.Ecuación 4Ecuación 3Ecuación 4Ecuación 3 La primera fila viene de resolver las dos últimas filas de Δ y Δ, y luego resolver para Δ.Ecuación 4Ecuación 3vwt

Para resolver, el algoritmo sigue los elementos esenciales de Altman y Gondzio.Ecuación 4[1] El algoritmo resuelve el sistema simétrico por una descomposición de LDL. Como han señalado autores como Vanderbei y Carpenter, esta descomposición es numéricamente estable sin pivotar, por lo que puede ser rápido.[2]

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

El algoritmo completo predictor-corrector es en gran parte el mismo que en el algoritmo, pero incluye términos cuadráticos también.quadproglinprog'interior-point' Ver.Predictor-corrector

Referencias

[1] Altman, Anna and J. Gondzio. Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optimization Methods and Software, 1999. Available for download here.

[2] Vanderbei, R. J. and T. J. Carpenter. Symmetric indefinite systems for interior point methods. Mathematical Programming 58, 1993. pp. 1–32. Available for download here.

Condiciones de detención

El algoritmo de predictor-corrector recorre en iteración hasta que alcanza un punto que es factible (satisface las restricciones dentro de las tolerancias) y donde los tamaños de paso relativo son pequeños. En concreto, defina

ρ=max(1,H,A¯,Aeq,c,b¯,beq)

El algoritmo se detiene cuando se cumplen todas estas condiciones:

rp1+rub1ρTolConrdρTolFunrcTolFun,

Dónde

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

Rc mide esencialmente el tamaño de los residuos de complementariedad y, que son cada uno de los vectores de ceros en una solución.xvtw

Detección de infactibilidad

calcula una en cada iteración.quadprogmerit functionφ La función de mérito es una medida de viabilidad. se detiene si la función de mérito crece demasiado grande.quadprog En este caso, declara que el problema es inviable.quadprog

La función de mérito está relacionada con las condiciones KKT para el problema — ver.Predictor-corrector Utilice las siguientes definiciones:

ρ=max(1,H,A¯,Aeq,c,b¯,beq)req=Aeqxbeqrineq=A¯xb¯srd=Hx+c+AeqTλeq+A¯Tλ¯ineqg=xTHx+fTxb¯Tλ¯ineqbeqTλeq.

La notación A¯ Y b¯ significa los coeficientes de desigualdad lineales, aumentados con términos para representar los límites del algoritmo disperso. La notación λ¯ineq representa de forma similar a los multiplicadores de Lagrange por las restricciones de desigualdad lineales, incluidas las restricciones enlazadas. Esto fue llamado yzPredictor-corrector λeq fue llamado.y

La función de mérito esφ

1ρ(max(req,rineq,rd)+g).

Si esta función de mérito se vuelve demasiado grande, declara que el problema es inviable y se detiene con la bandera de salida.quadprog-2

Algoritmotrust-region-reflectivequadprog

Muchos de los métodos utilizados en los solucionadores se basan en un concepto simple pero potente en la optimización.Optimization Toolbox™trust regions,

Para comprender el enfoque de optimización de la región de confianza, considere el problema de minimización sin restricciones, minimice (), donde la función toma argumentos vectoriales y devuelve escalares.fx Supongamos que está en un punto en el espacio y desea mejorar, es decir, pasar a un punto con un valor de función inferior.xn La idea básica es aproximarse con una función más simple, que refleja razonablemente el comportamiento de la función en un vecindario alrededor del punto.fqfNx Este vecindario es la región de confianza. Un paso de prueba se calcula minimizando (o aproximadamente minimizando) más.sN Este es el subproblema de la región de confianza,

mins{q(s), sN}.(5)

El punto actual se actualiza para ser + sixs f(x + s) < f(x); de lo contrario, el punto actual permanece sin cambios y, la región de confianza, se encogió y se repite el cálculo del paso de prueba.N

Las preguntas clave en la definición de un enfoque específico de la región de confianza para minimizar () son cómo elegir y calcular la aproximación (definida en el punto actual), cómo elegir y modificar la región de confianza y cómo resolver con precisión el subproblema de la región de confianza.fxqxN Esta sección se centra en el problema sin restricciones. Las secciones posteriores discuten complicaciones adicionales debido a la presencia de restricciones en las variables.

En el método de la región de confianza estándar (), la aproximación cuadrática se define por los dos primeros términos de la aproximación de Taylor a en; la vecindad es generalmente esférica o elipsoidal en forma.[48]qFxN Matemáticamente el subproblema de la región de confianza normalmente se indica

min{12sTHs+sTg  such that  DsΔ},(6)

donde está el gradiente de en el punto actual, es la matriz de hessian (la matriz simétrica de segundo derivados), es una matriz de escalado diagonal, Δ es un escalar positivo, y ∥. ∥ es la norma 2.gfxHD Existen buenos algoritmos para resolver (ver); Estos algoritmos suelen implicar el cálculo de todos los valores propios y un proceso de Newton aplicado a laEcuación 6[48]H ecuación secular

1Δ1s=0.

Estos algoritmos proporcionan una solución precisa.Ecuación 6 Sin embargo, requieren tiempo proporcional a varias factorizaciones de.H Por lo tanto, para problemas a gran escala es necesario un enfoque diferente. Varias estrategias de aproximación y heurística, basadas en, se han propuesto en la literatura (y).Ecuación 6[42][50] El enfoque de aproximación seguido en los solucionadores es restringir el subproblema de la región de confianza a un subespacio bidimensional (y).Optimization ToolboxS[39][42] Una vez que se ha calculado el subespacio, el trabajo a resolver es trivial incluso si se necesita información completa de eigenvalue/Eigenvector (ya que en el subespacio, el problema es sólo bidimensional).SEcuación 6 La obra dominante se ha desplazado ahora a la determinación del subespacio.

El subespacio bidimensional se determina con la ayuda de unS proceso de gradiente conjugada precondicionado descrito a continuación. El solucionador define como el espacio lineal extendido porSs1 Ys2Dóndes1 está en la dirección del degradado ygs2 es un aproximado Newton Dirección, es decir, una solución para

Hs2=g,(7)

o una dirección de curvatura negativa,

s2THs2<0.(8)

La filosofía detrás de esta elección es forzar la convergencia global (a través de la dirección de descenso más pronunciada o dirección de curvatura negativa) y lograr una rápida convergencia local (a través del paso de Newton, cuando existe).S

Un boceto de minimización sin restricciones utilizando ideas de la región de confianza es ahora fácil de dar:

  1. Formule el subproblema de la región de confianza bidimensional.

  2. Resuelva para determinar el paso de prueba.Ecuación 6s

  3. Si f(x + s) < f(x)Entonces x = x + s.

  4. Ajuste Δ.

Estos cuatro pasos se repiten hasta la convergencia. La dimensión de la región de confianza Δ se ajusta según las reglas estándar. En particular, se disminuye si no se acepta el paso de prueba, es decir, f(x + s) ≥ f(x). Ver y para una discusión de este aspecto.[46][49]

solucionadores tratan algunos casos especiales importantes de funciones especializadas: mínimos cuadrados no lineales, funciones cuadráticas y mínimos cuadrados lineales.Optimization Toolboxf Sin embargo, las ideas algorítmicas subyacentes son las mismas que para el caso general. Estos casos especiales se discuten en secciones posteriores.

El método de la región de confianza de subespacio se utiliza para determinar una dirección de búsqueda. Sin embargo, en lugar de restringir el paso a (posiblemente) un paso de reflexión, como en el caso de minimización no lineal, un búsqueda de línea reflectante se lleva a cabo en cada iteración. Consulte para obtener más información sobre la búsqueda de líneas.[45]

Método de gradiente conjugada precondicionado

Una forma popular de resolver los grandes sistemas de ecuaciones lineales definidas de manera simétrica y positiva Hp = –g es el método de los degradados de conjugación preacondicionados (PCG). Este enfoque iterativo requiere la capacidad de calcular los productos de vector de matriz de la forma, donde es un vector arbitrario.H·vv La matriz definida simétrica positiva es unaM preacondicionador Para.H Es decir M = C2Dónde C–1HC–1 es una matriz bien acondicionadas o una matriz con valores eigenados agrupados.

En un contexto de minimización, puede suponer que la matriz de Hessian es simétrica.H Sin embargo, está garantizado para ser positivo definitivo sólo en el vecindario de un fuerte minimizador.H El algoritmo PCG sale cuando se encuentra una dirección de curvatura negativa (o cero), es decir, dTHd ≤ 0. La dirección de salida PCG,, o bien una dirección de curvatura negativa o una solución aproximada (controla la aproximación) al sistema Newtonptol Hp = –g. En ambos casos se utiliza para ayudar a definir el subespacio bidimensional utilizado en el enfoque de la región de confianza discutido en.pMétodos de la región de confianza para la minimización no lineal

Restricciones de igualdad lineales

Las restricciones lineales complican la situación descrita para la minimización sin restricciones. Sin embargo, las ideas subyacentes descritas anteriormente pueden llevarse a cabo de una manera limpia y eficiente. Los métodos de la región de confianza en los solucionadores generan iterados estrictamente factibles.Optimization Toolbox

El problema general de minimización limitada de la igualdad lineal se puede escribir

min{f(x)  such that  Ax=b},(9)

donde es una-por-matriz (Amnm ≤ n). Algunos solucionadores preprocesan para eliminar las dependencias lineales estrictas mediante una técnica basada en la factorización de LU deOptimization ToolboxA UnT .[46] Aquí se supone que es de rango.Am

El método utilizado para resolver difiere del enfoque sin restricciones de dos maneras significativas.Ecuación 9 En primer lugar, un punto factible inicialx0 se calcula, utilizando un paso de mínimos cuadrados dispersos, para que Ax0 = b. En segundo lugar, el algoritmo PCG se sustituye por degradados de conjugados preacondicionados reducidos (RPCG), ver, para calcular un paso de Newton reducido aproximado (o una dirección de curvatura negativa en el espacio nulo de).[46]A El paso de álgebra lineal clave implica la resolución de sistemas de la forma

[CA˜TA˜0][st]=[r0],(10)

Dónde A˜ aproximados (los pequeños ceros de se fijan a cero rango proporcionado no se pierde) y es una aproximación simétrica positiva-definida escasa a, es decir,AACH C = H. Vea para más detalles.[46]

Restricciones de cuadro

El problema de la caja restringida es de la forma

min{f(x)  such that  lxu},(11)

donde es un vector de límites inferiores, y es un vector de los límites superiores.lu Algunos (o todos) de los componentes de puede ser igual a – ∞ y algunos (o todos) de los componentes de puede ser igual a ∞.lu El método genera una secuencia de puntos estrictamente factibles. Se utilizan dos técnicas para mantener la viabilidad mientras se logra un comportamiento de convergencia robusto. En primer lugar, un paso de Newton modificado a escala reemplaza el paso sin restricciones de Newton (para definir el subespacio bidimensional).S Segundo reflexiones se utilizan para aumentar el tamaño del paso.

El paso de Newton modificado a escala surge de examinar las condiciones necesarias de Kuhn-Tucker para,Ecuación 11

(D(x))2g=0,(12)

Dónde

D(x)=diag(|vk|1/2),

y el vector () se define a continuación, para cadavx 1 ≤ i ≤ n:

  • Si gi < 0 Y ui < ∞ Entonces vi = xi – ui

  • Si gi ≥ 0 Y li > –∞ Entonces vi = xi – li

  • Si gi < 0 Y ui = ∞ Entonces vi = –1

  • Si gi ≥ 0 Y li = –∞ Entonces vi = 1

El sistema no lineal no es diferenciable en todas partes.Ecuación 12 La no diferenciabilidad se produce cuando vi = 0. Puede evitar estos puntos manteniendo una viabilidad estricta, es decir, restringiendo l < x < u.

El paso modificado de Newton escalado sk para el sistema no lineal de ecuaciones dado por se define como la solución al sistema linealEcuación 12

M^DsN=g^(13)

en la iteración TH, dondek

g^=D1g=diag(|v|1/2)g,(14)

Y

M^=D1HD1+diag(g)Jv.(15)

Aquí Jv desempeña el papel del jacobiano de | |.v Cada componente diagonal de la matriz diagonal Jv es igual a 0, – 1 o 1. Si todos los componentes de y son finitos,lu Jv = diag(sign(g)). En un punto donde gi = 0, Vi podría no ser diferenciable. Jiiv=0 se define en ese punto. La no diferenciabilidad de este tipo no es motivo de preocupación porque, para tal componente, no es significativo qué valor Vi Toma. Además, |Vi| seguirá siendo discontinua en este punto, pero la función |vigi es continua.

Segundo reflexiones se utilizan para aumentar el tamaño del paso. Un paso de reflexión (único) se define de la siguiente manera. Dado un paso que intersecta una restricción enlazada, considere la primera restricción enlazada cruzada por; suponer que es la restricción de límite de TH (ya sea el límite superior o inferior de la TH).ppiii A continuación, el paso de reflexión pR = p excepto en el componente TH, dondei pRi = –pi.