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 optimización no lineal limitados

Definición de optimización restringida

La minimización restringida es el problema de encontrar un vector x que es un mínimo local a una función escalar f(x) sujeto a restricciones en el xpermisible:

minxf(x)

de tal manera que una o más de las siguientes suspensiones: c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, l ≤ x ≤ u. Hay aún más restricciones utilizadas en la programación semi-infinita; Véase formulación y algoritmo del problema de fseminf.

algoritmo reflexivo de la región de confianza fmincon

Métodos de la confianza-región para la minimización no lineal

Muchos de los métodos utilizados en Optimization Toolbox™ Solvers se basan en regiones de confianza, un concepto simple pero poderoso en la optimización.

Para entender el enfoque de la región de confianza para la optimización, considere el problema de minimización no restringida, minimice f(x), donde la función toma argumentos vectoriales y devuelve escalares. Suponga que está en un punto x en n-Space y desea mejorar, es decir, pasar a un punto con un valor de función inferior. La idea básica es aproximar f con una función más simple q, que refleja razonablemente el comportamiento de la función f en un barrio N alrededor del punto x. Este vecindario es la región de confianza. Un paso de ensayo s se computa reduciendo al mínimo (o aproximadamente reduciendo al mínimo) el excedente N. Este es el subproblema de la región de confianza,

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

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

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

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

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

donde g es el gradiente de f en el punto actual x, H es la matriz del hessian (la matriz simétrica de los segundos derivados), D es una matriz de escalamiento diagonal, Δ es un escalar positivo, y ∥. ∥ es el 2-Norm. Existen buenos algoritmos para resolver Ecuación 2 (ver [48]); Estos algoritmos típicamente implican el cómputo de un eigensystem completo y un proceso de Newton aplicado a la ecuación secular

1Δ1s=0.

Tales algoritmos proporcionan una solución exacta a Ecuación 2. Sin embargo, requieren tiempo proporcional a varios factorizaciones de H. Por lo tanto, para problemas a gran escala es necesario un enfoque diferente. Se han propuesto varias estrategias de aproximación y heurística, basadas en Ecuación 2, en la bibliografía ([42] y [50]). El enfoque de aproximación seguido en Optimization Toolbox Solvers es restringir el subproblema de la región de confianza a un S subespacial de dos dimensiones ([39] y [42]). Una vez que el subespacio S se ha calculado, el trabajo para solucionar Ecuación 2 es trivial incluso si se necesita la información completa del valor propio/vector (puesto que en el subespacio, el problema es solamente de dos dimensiones). El trabajo dominante se ha trasladado ahora a la determinación del subespacio.

El subespacio S de dos dimensiones se determina con la ayuda de un proceso de gradiente conjugado precondicionado descrito a continuación. El solucionador define S como el espacio lineal atravesado por s1 y s2, donde s1 está en la dirección del gradiente g, y s2 es una aproximación Newton Dirección, es decir, una solución para

Hs2=g,(3)

o una dirección de curvatura negativa,

s2THs2<0.(4)

La filosofía detrás de esta opción de S es forzar la convergencia global (vía la dirección más escarpada de la pendiente o la dirección negativa de la curvatura) y alcanzar la convergencia local rápida (vía el paso del neutonio, cuando existe).

Un bosquejo de la minimización no restringida usando ideas de la confianza-región es ahora fácil de dar:

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

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

  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 confianza-región Δ se ajusta según reglas estándares. En particular, se reduce si no se acepta el paso de prueba, es decir, f(x + s) ≥ f(x). Vea [46] y [49] para una discusión de este aspecto.

los solucionadores de Optimization Toolbox tratan algunos casos especiales importantes de f con funciones especializadas: menos cuadrados no lineales, funciones cuadráticas, y mínimos-cuadrados lineares. Sin embargo, las ideas algorítmicas subyacentes son las mismas que para el caso general. Estos casos especiales se discuten en secciones más últimas.

Método de gradiente de conjugado precondicionado

Una manera popular de resolver los sistemas definidos positivos simétricos grandes de ecuaciones lineares Hp = –g es el método de gradientes de conjugado precondicionado (PCG). Este enfoque iterativo requiere la capacidad de calcular los productos vectoriales matriciales de la forma H·v donde v es un vector arbitrario. La matriz definida positiva simétrica M es un precondicionador para H. Es decir M = C2Donde C–1HC–1 es una matriz bien acondicionada o una matriz con valores propios agrupados.

En un contexto de minimización, puede asumir que la matriz de hessian H es simétrica. Sin embargo, H se garantiza para ser positivo definido solamente en el vecindario de un minimizador fuerte. El algoritmo PCG sale cuando se encuentra una dirección de curvatura negativa (o cero), es decir, dTHd ≤ 0. La dirección de la salida de PCG, p, es una dirección de la curvatura negativa o un aproximado (tol controla cómo aproximado) solución al sistema del neutonio Hp = –g. En cualquiera de los casos, p se utiliza para ayudar a definir el subespacio bidimensional utilizado en el enfoque de la región de confianza discutido en Métodos de la confianza-región para la minimización no lineal.

Restricciones de igualdad lineal

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

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

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

donde A es una matriz m-por-n (m ≤ n). Algunos Optimization Toolbox solucionadores preprocesan A para eliminar dependencias lineales estrictas utilizando una técnica basada en la factorización LU de UnT [46]. Aquí A se asume para ser de mespeso.

El método utilizado para resolver Ecuación 5 difiere del enfoque sin restricciones en dos formas significativas. Primero, un punto factible inicial x0 se computa, utilizando un paso de mínimos cuadrados dispersos, de modo que Ax0 = b. En segundo lugar, el algoritmo PCG es substituido por gradientes conjugados pre-condicionados reducidos (RPCG), vea [46], para calcular un paso reducido aproximado del neutonio (o una dirección de la curvatura negativa en el espacio nulo de A). El paso de álgebra lineal clave consiste en resolver sistemas de la forma

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

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

Restricciones de caja

El problema de la caja restringida es de la forma

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

donde l es un vector de límites inferiores, y u es un vector de límites superiores. Algunos (o todos) de los componentes de l pueden ser iguales a – ∞ y algunos (o todos) de los componentes de u pueden ser iguales a ∞. El método genera una secuencia de puntos estrictamente factibles. Se utilizan dos técnicas para mantener la viabilidad y lograr un comportamiento de convergencia robusto. En primer lugar, un paso de Newton modificado a escala sustituye el paso de Newton sin restricciones (para definir el subespacio Sde dos dimensiones). Segundo las reflexiones se utilizan para aumentar el tamaño del escalón.

El paso modificado escalado del neutonio se presenta de examinar las condiciones necesarias de Kuhn-Tucker para Ecuación 7,

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

Donde

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

y el vector v(x) se define a continuación, para cada 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 Ecuación 8 no es diferenciable por todas partes. La no diferenciabilidad ocurre cuando vi = 0. Puede evitar estos puntos manteniendo una viabilidad estricta, es decir, restringiendo l < x < u.

El escalón modificado de Newton sk para el sistema no lineal de ecuaciones dadas por Ecuación 8 se define como la solución al sistema lineal

M^DsN=g^(9)

en la iteración kTH, donde

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

Y

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

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 l y u son finitos, Jv = diag(sign(g)). En un punto donde gi = 0, Vi puede que no sea diferenciable. Jiiv=0 se define en un punto. La no diferenciabilidad de este tipo no es motivo de preocupación porque, para dicho componente, no es significativo el valor Vi Toma. Más, |Vi| seguirá siendo discontinua en este punto, pero la función |vigi es continuo.

Segundo las reflexiones se utilizan para aumentar el tamaño del escalón. Un paso de reflexión (Single) se define como sigue. Dado un paso p que intersecta una restricción enlazada, considere la primera restricción enlazada cruzada por p; Supongamos que es la restricción iTH Bound (ya sea el iTH Upper o iTH inferior Bound). A continuación, el paso de reflexión pR = p excepto en el componente iTH, donde pRi = –pi.

algoritmo de conjunto activo fmincon

Introducción

En la optimización restringida, el objetivo general es transformar el problema en un subproblema más fácil que se pueda resolver y utilizar como base de un proceso iterativo. Una característica de una clase grande de métodos tempranos es la traducción del problema restringido a un problema básico sin restricciones utilizando una función de penalización para restricciones que están cerca o más allá del límite de restricción. De esta manera el problema restringido se resuelve usando una secuencia de optimizaciones sin restricciones parametrizado, que en el límite (de la secuencia) convergen al problema restringido. Estos métodos ahora se consideran relativamente ineficientes y han sido sustituidos por métodos que se han centrado en la solución de la Karush-Kuhn-Tucker (KKT) ecuaciones. Las ecuaciones KKT son condiciones necesarias para optimizar el problema de optimización. Si el problema es un llamado problema de programación convexo, esto es, f(x) y Gi(x), i = 1,...,m, son funciones convexas, entonces las ecuaciones de KKT son necesarias y suficientes para un punto global de la solución.

Refiriendo al GP (Ecuación 1), las ecuaciones de Kuhn-Tucker se pueden mencionar como

f(x*)+i=1mλiGi(x*)=0λiGi(x*)=0,  i=1,...,meλi0,  i=me+1,...,m,(12)

Además de las restricciones originales en Ecuación 1.

La primera ecuación describe una cancelación de los gradientes entre la función objetiva y las restricciones activas en el punto de solución. Para cancelar los gradientes, los multiplicadores de Lagrange (Λi, i = 1,...,m) son necesarios para equilibrar las desviaciones en magnitud de la función objetiva y los gradientes de restricción. Dado que sólo se incluyen restricciones activas en esta operación de cancelación, las restricciones que no están activas no deben incluirse en esta operación, por lo que se administran multiplicadores de Lagrange igual a 0. Esto se indica implícitamente en las dos últimas ecuaciones Kuhn-Tucker.

La solución de las ecuaciones de KKT forma la base a muchos algoritmos de programación no lineales. Estos algoritmos intentan calcular los multiplicadores de Lagrange directamente. Los métodos cuasi-Newton limitados garantizan la convergencia superlineal mediante la acumulación de información de segundo orden con respecto a las ecuaciones KKT usando un procedimiento de actualización cuasi-Newton. Estos métodos se refieren comúnmente como métodos de programación cuadrática secuencial (SQP), puesto que un subproblema del QP se soluciona en cada iteración importante (también conocida como programación cuadrática iterativa, programación cuadrática recursiva, y métrico variable restringido métodos).

El algoritmo 'active-set' no es un algoritmo a gran escala; Véase Algoritmos a gran escala versus a media escala.

Programación cuadrática secuencial (SQP)

Los métodos SQP representan el estado del arte en los métodos de programación no lineales. Schittkowski [36], por ejemplo, ha implementado y probado una versión que supera a cualquier otro método probado en términos de eficiencia, precisión y porcentaje de soluciones exitosas, en un gran número de problemas de prueba.

Basándose en el trabajo de Biggs [1], han [22], y Powell ([32] y [33]), el método le permite imitar de cerca el método de Newton para la optimización restringida, al igual que se hace para la optimización no limitada. En cada iteración importante, se realiza una aproximación del hessian de la función Lagrange utilizando un método de actualización cuasi-Newton. A continuación, se utiliza para generar un subproblema de QP cuya solución se utiliza para formar una dirección de búsqueda para un procedimiento de búsqueda de líneas. Una visión general de SQP se encuentra en Fletcher [13], Gill et al. [19], Powell [35]y Schittkowski [23]. El método general, sin embargo, se indica aquí.

Dada la descripción del problema en GP (Ecuación 1) la idea principal es la formulación de un subproblema de QP basado en una aproximación cuadrática de la función Lagrange.

L(x,λ)=f(x)+i=1mλigi(x).(13)

Aquí se simplifica el Ecuación 1 asumiendo que las restricciones vinculadas se han expresado como restricciones de desigualdad. Se obtiene el subproblema de QP mediante la linealización de las restricciones no lineales.

Subproblema de programación cuadrática (QP)

mindn12dTHkd+f(xk)Tdgi(xk)Td+gi(xk)=0,  i=1,...,megi(xk)Td+gi(xk)0,  i=me+1,...,m.(14)

Este subproblema se puede resolver utilizando cualquier algoritmo QP (véase, por ejemplo, Solución de programación cuadrática). La solución se utiliza para formar una nueva iteración

xk + 1 = xk + αkdk.

El parámetro de longitud de paso αk se determina mediante un procedimiento de búsqueda de línea adecuado para obtener una disminución suficiente de una función de mérito (ver Actualización de la matriz de hessian). The Matrix Hk es una aproximación definida positiva de la matriz del hessian de la función de Lagrange (Ecuación 13). Hk puede ser actualizado por cualquiera de los métodos cuasi-Newton, aunque el método BFGS (ver Actualización de la matriz de hessian) parece ser el más popular.

Un problema no linealmente limitado se puede resolver con frecuencia en menos iteraciones que un problema no restringido mediante SQP. Una de las razones de esto es que, debido a los límites en el área factible, el optimizador puede tomar decisiones informadas con respecto a direcciones de búsqueda y longitud de paso.

Considerar La función de Rosenbrock con una restricción de desigualdad no lineal adicional, g(x),

x12+x221.50.(15)

Esto se resolvió mediante una implementación de SQP en 96 iteraciones en comparación con 140 para el caso no restringido. Figura 6-3, Método SQP en la función de Rosenbrock no linealmente restringida muestra la ruta al punto de solución x = [0.9072,0.8228] a partir de x = [–1.9,2.0].

Figura 6-3, Método SQP en la función de Rosenbrock no linealmente restringida

Implementación de SQP

La puesta en práctica de SQP consiste en tres etapas principales, que se discuten brevemente en las subdivisiones siguientes:

Actualización de la matriz de hessian.  En cada iteración importante una aproximación definida positiva del cuasi-Neutonio del hessian de la función Lagrange, H, se calcula usando el método de BFGS, donde λi, i = 1,...,m, es una estimación de los multiplicadores de Lagrange.

Hk+1=Hk+qkqkTqkTskHkskskTHkTskTHksk,(16)

Donde

sk=xk+1xkqk=(f(xk+1)+i=1mλigi(xk+1))(f(xk)+i=1mλigi(xk)).

Powell [33] recomienda mantener el hessian positivo definido a pesar de que podría ser positiva indefinida en el punto de solución. Un hessian definido positivo se mantiene proporcionando qkTsk es positivo en cada actualización y que H se inicializa con una matriz positiva definida. Cuando qkTsk no es positivo, Qk se modifica sobre una base elemento por elemento para que qkTsk>0. El objetivo general de esta modificación es distorsionar los elementos de Qk, que contribuyen a una actualización definitiva positiva, lo más poco posible. Por lo tanto, en la fase inicial de la modificación, el elemento más negativo de qk*sk se reduce en dos ocasiones. Este procedimiento se continúa hasta que qkTsk es mayor o igual a una pequeña tolerancia negativa. Si, después de este procedimiento, qkTsk todavía no es positivo, modificar Qk añadiendo un vector v multiplicado por un wescalar constante, es

qk=qk+wv,(17)

Donde

vi=gi(xk+1)gi(xk+1)gi(xk)gi(xk)           if (qk)iw<0 and (qk)i(sk)i<0, i=1,...,mvi=0  otherwise,

y aumentar w sistemáticamente hasta qkTsk se vuelve positivo.

Las funciones fmincon, fminimax, fgoalattainy fseminf utilizan SQP. Si Display se establece en 'iter' en options, se proporciona información diversa, como valores de función y la infracción de restricción máxima. Cuando el hessian tiene que ser modificado usando la primera fase del procedimiento precedente para mantenerlo definido positivo, entonces Hessian modified se muestra. Si el hessian tiene que ser modificado otra vez usando la segunda fase del acercamiento descrito arriba, entonces Hessian modified twice se muestra. Cuando el subproblema de QP es inviable, entonces infeasible se muestra. Estas exhibiciones no suelen ser motivo de preocupación, pero indican que el problema es altamente no lineal y que la convergencia puede tardar más de lo habitual. A veces el mensaje no update se muestra, lo que indica que qkTsk es casi cero. Esto puede ser una indicación de que la configuración del problema es incorrecta o que está tratando de minimizar una función no continua.

Solución de programación cuadrática.  En cada iteración importante de la Método SQP, se resuelve un problema de QP de la siguiente forma, donde Uni se refiere a la fila ide la matriz m-por-n A.

mindnq(d)=12dTHd+cTd,Aid=bi,  i=1,...,meAidbi,  i=me+1,...,m.(18)

El método utilizado en las funciones Optimization Toolbox es una estrategia de conjunto activo (también conocida como método de proyección) similar a la de Gill et al., descrita en [18] y [17]. Se ha modificado para problemas de programación lineal (LP) y de programación cuadrática (QP).

El procedimiento de la solución implica dos fases. La primera fase implica el cálculo de un punto factible (si existe uno). La segunda fase implica la generación de una secuencia iterativa de puntos factibles que convergen a la solución. En este método un conjunto activo, A¯k, se mantiene que es una estimación de las restricciones activas (es decir, las que están en los límites de restricción) en el punto de solución. Prácticamente todos los algoritmos QP son métodos de conjunto activo. Este punto se enfatiza porque existen muchos métodos diferentes que son muy similares en estructura pero que se describen en términos muy diferentes.

A¯k se actualiza en cada iteración k, y esto se utiliza para formar una base para una dirección de búsqueda d^k. Las restricciones de igualdad permanecen siempre en el conjunto activo A¯k. La notación para la variable d^k se utiliza aquí para distinguirlo de Dk en las iteraciones principales del método SQP. La dirección de búsqueda d^k se calcula y minimiza la función objetiva mientras permanece en cualquier límite de restricción activa. El subespacio factible para d^k se forma a partir de una base Zk cuyas columnas son ortogonales a la estimación del conjunto activo A¯k (i.e., A¯kZk=0). Así, una dirección de búsqueda, que se forma a partir de una suma lineal de cualquier combinación de las columnas de Zk, está garantizado a permanecer en los límites de las restricciones activas.

La matriz Zk se forma a partir de la última m – l columnas de la descomposición QR de la matriz A¯kT, donde l es el número de restricciones activas y l < m. Es decir Zk se da por

Zk=Q[:,l+1:m],(19)

Donde

QTA¯kT=[R0].

Vez Zk se encuentra, una nueva dirección de búsqueda d^k se busca que reduzca al mínimo q(d) donde d^k se encuentra en el espacio nulo de las restricciones activas. Es decir d^k es una combinación lineal de las columnas de Zk: d^k=Zkp para algunos vectores p.

Luego, si se ve el cuadrático como una función de p, mediante la sustitución de d^k, tienes

q(p)=12pTZkTHZkp+cTZkp.(20)

Diferenciar esto con respecto a los rendimientos p

q(p)=ZkTHZkp+ZkTc.(21)

q(p) se conoce como el gradiente proyectado de la función cuadrática porque es el gradiente proyectado en el subespacio definido por Zk. El término ZkTHZk se llama el hessian proyectado. Asumiendo que la matriz de hessian H es positiva definida (que es el caso en esta implementación de SQP), entonces el mínimo de la función q(p) en el subespacio definido por Zk ocurre cuando q(p) = 0, que es la solución del sistema de ecuaciones lineales

ZkTHZkp=ZkTc.(22)

Se toma un paso de la forma

xk+1=xk+αd^k,  where d^k=Zkp.(23)

En cada iteración, debido a la naturaleza cuadrática de la función objetiva, hay sólo dos opciones de αde longitud de paso. Un paso de unidad a lo largo d^k es el paso exacto al mínimo de la función restringida al espacio nulo de A¯k. Si tal paso se puede tomar, sin la violación de las restricciones, entonces ésta es la solución a QP (Ecuación 18). De lo contrario, el paso adelante d^k a la restricción más cercana es menor que la unidad y se incluye una restricción nueva en el conjunto activo en la siguiente iteración. La distancia a los límites de restricción en cualquier dirección d^k se da por

α=mini{1,...,m}{(Aixkbi)Aid^k},(24)

que se define para las restricciones no en el conjunto activo, y donde la dirección d^k es hacia el límite de restricción, es decir, Aid^k>0, i=1,...,m.

Cuando n restricciones independientes se incluyen en el conjunto activo, sin la ubicación del mínimo, los multiplicadores de Lagrange, Λk, se calculan que satisfacen el conjunto no singular de ecuaciones lineales

A¯kTλk=c.(25)

Si todos los elementos de Λk son positivas, xk es la solución óptima de QP (Ecuación 18). Sin embargo, si algún componente de Λk es negativo, y el componente no corresponde a una restricción de igualdad, el elemento correspondiente se elimina del conjunto activo y se busca una nueva iteración.

Inicialización.  El algoritmo requiere un punto factible para comenzar. Si el punto actual del método SQP no es factible, entonces usted puede encontrar un punto resolviendo el problema de programación lineal

minγ, xnγ  such thatAix=bi,      i=1,...,meAixγbi,  i=me+1,...,m.(26)

La notación Uni indica la iª fila de la matriz A. Puede encontrar un punto factible (si existe) para Ecuación 26 estableciendo x en un valor que satisfaga las restricciones de igualdad. Puede determinar este valor resolviendo un conjunto sub o sobredeterminado de ecuaciones lineales formadas a partir del conjunto de restricciones de igualdad. Si hay una solución a este problema, entonces la variable de holgura γ se establece en la restricción de desigualdad máxima en este punto.

Puede modificar el algoritmo QP anterior para problemas de LP estableciendo la dirección de búsqueda en la dirección de descenso más empinada en cada iteración, donde Gk es el gradiente de la función objetiva (igual a los coeficientes de la función objetiva lineal).

d^k=ZkZkTgk.(27)

Si se encuentra un punto factible utilizando el método LP anterior, se introduce la fase principal de QP. La dirección de búsqueda d^k se inicializa con una dirección de búsqueda d^1 encontrado de resolver el conjunto de ecuaciones lineales

Hd^1=gk,(28)

Donde Gk es el gradiente de la función objetiva en la iteración actual xk (i.e., Hxk + c).

Si no se encuentra una solución factible para el problema de QP, la dirección de búsqueda de la rutina SQP principal se toma como uno que minimiza γ.

Búsqueda de línea y función de mérito.  La solución al subproblema de QP produce un vector Dk, que se utiliza para formar una nueva iteración

xk+1=xk+αdk.(29)

El parámetro de longitud de paso Αk se determina con el fin de producir una disminución suficiente en un función de mérito. En esta implementación se utiliza la función Merit utilizada por han [22] y Powell [33] de la siguiente forma.

Ψ(x)=f(x)+i=1merigi(x)+i=me+1mrimax[0,gi(x)].(30)

Powell recomienda establecer el parámetro de penalización

ri=(rk+1)i=maxi{λi,(rk)i+λi2},  i=1,...,m.(31)

Esto permite una contribución positiva de las restricciones que están inactivas en la solución QP pero que han sido activas recientemente. En esta implementación, el parámetro de penalización Ri se establece inicialmente en

ri=f(x)gi(x),(32)

Donde   representa la norma euclidiana.

Esto asegura contribuciones más grandes al parámetro de la pena de restricciones con gradientes más pequeños, que serían el caso para las restricciones activas en el punto de la solución.

algoritmo de fmincon SQP

El algoritmo de sqp (y el algoritmo casi idéntico de sqp-legacy ) es similar al algoritmo de active-set (para una descripción, vea algoritmo de conjunto activo fmincon). El algoritmo sqp básico se describe en el capítulo 18 de Nocedal y Wright [31].

El algoritmo sqp es esencialmente el mismo que el algoritmo sqp-legacy , pero tiene una implementación diferente. Por lo general, sqp tiene un tiempo de ejecución más rápido y menos uso de memoria que sqp-legacy.

Las diferencias más importantes entre los algoritmos sqp y active-set son:

Estricta viabilidad con respecto a los límites

El algoritmo sqp toma todos los pasos iterativos de la región limitados por los límites. Además, los pasos finitos de la diferencia también respetan límites. Los límites no son estrictos; un paso puede estar exactamente en un límite. Esta viabilidad estricta puede ser beneficiosa cuando la función objetiva o las funciones de restricción no lineales no están definidas o son complejas fuera de la región restringidas por límites.

Robustez a los resultados no dobles

Durante sus iteraciones, el algoritmo sqp puede intentar dar un paso que falle. Esto significa que una función objetiva o una función de restricción no lineal que suministre devuelve un valor de Inf, NaNo un valor complejo. En este caso, el algoritmo intenta dar un paso más pequeño.

Rutinas de álgebra lineal refactorizadas

El algoritmo sqp utiliza un conjunto diferente de rutinas de álgebra lineal para resolver el subproblema de programación cuadrática, Ecuación 14. Estas rutinas son más eficientes tanto en el uso de la memoria como en la velocidad que las rutinas active-set .

Rutinas de viabilidad reformuladas

El algoritmo sqp tiene dos nuevos enfoques para la solución de Ecuación 14 cuando no se satisfacen las restricciones.

  • El algoritmo sqp combina las funciones objetivo y restricción en una función Merit. El algoritmo intenta minimizar la función de mérito sujeto a restricciones relajadas. Este problema modificado puede llevar a una solución factible. Sin embargo, este enfoque tiene más variables que el problema original, por lo que el tamaño del problema en Ecuación 14 aumenta. El aumento del tamaño puede ralentizar la solución del subproblema. Estas rutinas se basan en los artículos de Spellucci [60] y Tone [61]. El algoritmo de sqp fija el parámetro de la pena para la función del mérito Ecuación 30 según la sugerencia en [41].

  • Suponga que no se cumplen las restricciones no lineales y un intento de paso hace que la infracción de restricción crezca. El algoritmo sqp intenta obtener viabilidad utilizando una aproximación de segundo orden a las restricciones. La técnica de segundo orden puede llevar a una solución factible. Sin embargo, esta técnica puede ralentizar la solución al requerir más evaluaciones de las funciones de restricción no lineales.

algoritmo del punto interior de fmincon

Función de barrera

El enfoque de punto interior a la minimización limitada es resolver una secuencia de problemas de minimización aproximados. El problema original es

minxf(x), subject to h(x)=0 and g(x)0.(33)
Para cada μ > 0, el problema aproximado es
minx,sfμ(x,s)=minx,sf(x)μiln(si), subject to h(x)=0 and g(x)+s=0.(34)
Hay tantas variables de holgura si como hay limitaciones de desigualdad g. La si se limitan a ser positivos para mantener ln(si) Limitada. Como μ disminuye a cero, el mínimo de Fμ debe aproximarse al mínimo de f. El término logarítmico agregado se llama un función de barrera. Este método se describe en [40], [41]y [51].

El problema aproximado de Ecuación 34 es una secuencia de problemas limitados de igualdad. Éstos son más fáciles de resolver que el problema Ecuación 33original de la desigualdad-limitado.

Para resolver el problema aproximado, el algoritmo utiliza uno de los dos tipos principales de pasos en cada iteración:

  • Un paso Directa en (x, s). Este paso intenta resolver las ecuaciones KKT, Ecuación 2 y Ecuación 3, para el problema aproximado a través de una aproximación lineal. Esto también se llama un Paso de Newton.

  • Un paso Cg (gradiente conjugado), utilizando una región Fiduciaria.

Por defecto, el algoritmo primero intenta dar un paso directo. Si no puede, intenta un paso CG. Un caso donde no toma un paso directo es cuando el problema aproximado no es localmente convexo cerca de la iteración actual.

En cada iteración el algoritmo disminuye un función del mérito, como

fμ(x,s)+ν(h(x),g(x)+s).

El parámetro ν puede aumentar con el número de iteración para forzar la solución hacia la viabilidad. Si un intento de paso no disminuye la función Merit, el algoritmo rechaza el intento de paso e intenta un nuevo paso.

Si la función objetiva o una restricción no lineal devuelve un valor complejo, Nan, INF o un error en una iteración xj, el algoritmo rechaza xj. El rechazo tiene el mismo efecto que si la función del mérito no disminuyera suficientemente: el algoritmo entonces intenta un paso diferente, más corto. Envuelva cualquier código que pueda error en try-catch:

function val = userFcn(x) try     val = ... % code that can error catch     val = NaN; end

El objetivo y las limitaciones deben producir valores apropiados (double) en el punto inicial.

Paso directo

En la definición del paso directo se utilizan las siguientes variables:

  • H denota el hessian del Lagrange de Fμ:

    H=2f(x)+iλi2gi(x)+jλj2hj(x).(35)

  • Jg denota el jacobiano de la función de restricción g.

  • Jh denota el jacobiano de la función de restricción h.

  • S = diag(s).

  • λ denota el vector multiplicador de Lagrange asociado con las restricciones g

  • Λ = diag(λ).

  • y denota el vector multiplicador de Lagrange asociado con h.

  • e denota el vector de unos del mismo tamaño que g.

Ecuación 36 define el paso directo x, Δs):

[H0JhTJgT0SΛ0SJh0I0JgS0I][ΔxΔsΔyΔλ]=[fJhTyJgTλSλμehg+s].(36)
Esta ecuación viene directamente de intentar resolver Ecuación 2 y Ecuación 3 usando un Lagrange linearizó.

Con el fin de resolver esta ecuación para x, Δs), el algoritmo hace una factorización de LDL de la matriz. (consulte Ejemplo 3: la estructura de D (MATLAB) en la página de referencia de la función MATLAB® ldl .) Este es el paso más costoso de cómputo. Un resultado de esta factorización es una determinación de si el hessian proyectado es positivo definido o no; Si no es así, el algoritmo utiliza un paso de gradiente conjugado, descrito en la siguiente sección.

Paso del gradiente conjugado

El enfoque de gradiente conjugado para resolver el problema aproximado de Ecuación 34 es similar a otros cálculos de gradiente conjugado. En este caso, el algoritmo ajusta tanto x como s, manteniendo las holguras s positivas. El enfoque consiste en minimizar una aproximación cuadrática al problema aproximado en una región de confianza, sujeto a restricciones lineales.

En concreto, deje que R denota el radio de la región de confianza y deje que otras variables se defina como en Paso directo. El algoritmo obtiene multiplicadores de Lagrange aproximadamente resolviendo las ecuaciones de KKT

xL=xf(x)+iλigi(x)+jyjhj(x)=0,

en el sentido de mínimos cuadrados, sujeto a que λ sea positivo. Entonces toma un paso x, Δs) para solucionar aproximadamente

minΔx,ΔsfTΔx+12ΔxTxx2LΔx+μeTS1Δs+12ΔsTS1ΛΔs,(37)
sujeto a las restricciones de linealización
g(x)+JgΔx+Δs=0,  h(x)+JhΔx=0.(38)
Para resolver Ecuación 38, el algoritmo intenta minimizar una norma de las restricciones de linealización dentro de una región con radio escalada por R. A continuación, Ecuación 37 se resuelve con las limitaciones de ser para que coincida con el residuo de la solución de Ecuación 38, permaneciendo en la región de confianza de RADIUS R, y manteniendo s estrictamente positivo. Para los detalles del algoritmo y de la derivación, vea [40], [41], y [51]. Para obtener otra descripción de los gradientes conjugados, consulte Método de gradiente de conjugado precondicionado.

Opciones de algoritmo de punto interior

Aquí están los significados y los efectos de varias opciones en el algoritmo de punto interior.

  • HonorBounds : Cuando se establece en true, cada iteración satisface las restricciones enlazadas que ha establecido. Cuando se establece en false, el algoritmo puede violar los límites durante iteraciones intermedias.

  • HessianApproximation — Cuando se establece en:

    • 'bfgs', fmincon calcula el hessian por una aproximación densa del cuasi-neutonio.

    • 'lbfgs', fmincon calcula el hessian por una limitado-memoria, aproximación en grande del cuasi-neutonio.

    • 'fin-diff-grads', fmincon calcula un producto del hessian-tiempo-vector por diferencias finitas del gradiente (s); otras opciones deben ser ajustadas apropiadamente.

  • HessianFcnfmincon utiliza el identificador de función que especifique en HessianFcn para calcular el hessian. Véase Incluyendo los hessianos.

  • HessianMultiplyFcn — Da una función separada para la evaluación del hessian-tiempo-vector. Para obtener más información, consulte Incluyendo los hessianos y Hessian multiplique la función.

  • SubproblemAlgorithm — Determina si se intenta o no el paso directo de Newton. La configuración predeterminada 'factorization' permite intentar este tipo de paso. La configuración 'cg' sólo permite pasos de gradiente conjugado.

Para obtener una lista completa de las opciones, vea Algoritmo de punto interior en fmincon options.

algoritmo fminbnd

fminbnd es un solucionador disponible en cualquier instalación de MATLAB . Resuelve para un mínimo local en una dimensión dentro de un intervalo delimitado. No se basa en derivados. En su lugar, utiliza la búsqueda de sección dorada y la interpolación parabólica.

formulación y algoritmo del problema de fseminf

formulación del problema de fseminf

fseminf aborda problemas de optimización con tipos adicionales de restricciones en comparación con los tratados por fmincon. La formulación de fmincon es

minxf(x)

tal que c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u.

fseminf añade el siguiente conjunto de restricciones semi-infinitas a los ya dados. Para Wj en un intervalo o rectángulo acotado de uno o dos dimensiones Mej, para un vector de funciones continuas K(x, w), las limitaciones son

Kj(x, Wj) ≤ 0 para todos WjMej.

El término "dimensión" de un problema fseminf significa la dimensión máxima del conjunto de restricciones I: 1 si todos Mej son intervalos, y 2 si al menos un Mej es un rectángulo. El tamaño del vector de K no entra en este concepto de dimensión.

La razón de esto se llama programación semi-infinita es que hay un número finito de variables (x y Wj), pero un número infinito de restricciones. Esto se debe a que las restricciones en x están sobre un conjunto de intervalos continuos o rectángulos Mej, que contiene un número infinito de puntos, por lo que hay un número infinito de restricciones: Kj(x, wj) ≤ 0 para un número infinito de puntos Wj.

Usted podría pensar que un problema con un número infinito de restricciones es imposible de resolver. fseminf aborda esto reformulando el problema a uno equivalente que tiene dos etapas: una maximización y una minimización. Las restricciones semi-infinitas se reformulan como

maxwjIjKj(x,wj)0 for all j=1,...,|K|,(39)

donde | K| es el número de componentes del vector K; es decir, el número de funciones de restricción semi-infinitas. Para xfijos, se trata de una maximización ordinaria sobre intervalos delimitados o rectángulos.

fseminf simplifica aún más el problema haciendo tramos aproximaciones cuadráticas o cúbicas κj(x, wj) a las funciones Kj(xwj), por cada x que el Solver visita. fseminf considera sólo los máximos de la función de interpolación κj(x, wj)En lugar de Kj(xwj), en Ecuación 39. Esto reduce el problema original, minimizando una función semi-infinitamente limitada, a un problema con un número finito de restricciones.

Puntos de muestreo.  Su función de restricción semi-infinita debe proporcionar un conjunto de puntos de muestreo, puntos utilizados en la realización de las aproximaciones cuadráticas o cúbicas. Para lograrlo, debe contener:

  • El espaciado inicial s entre los puntos de muestreo w

  • Una forma de generar el conjunto de puntos de muestreo w de s

El espaciado inicial s es un | K|-por-2 Matrix. La fila jTH de s representa el espaciado de los puntos de muestreo vecinos para la función de restricción Kj. Si Kj depende de una sola dimensión Wj, fije s(j,2) = 0. fseminf actualiza la matriz s en iteraciones subsecuentes.

fseminf utiliza la matriz s para generar los puntos de muestreo w, que luego utiliza para crear la aproximación κj(x, wj). Su procedimiento para generar w de s debe mantener los mismos intervalos o rectángulos Mej durante la optimización.

Ejemplo de creación de puntos de muestreo.  Considere un problema con dos restricciones semi-infinitas, K1 y K2. K1 tiene un w unidimensional1, y K2 tiene w de dos dimensiones2. El código siguiente genera un conjunto de muestreo de w1 = 2 a 12:

% Initial sampling interval if isnan(s(1,1))     s(1,1) = .2;     s(1,2) = 0; end  % Sampling set w1 = 2:s(1,1):12;

fseminf especifica s como NaN cuando llama por primera vez a la función de restricción. La comprobación de esto le permite establecer el intervalo de muestreo inicial.

El código siguiente genera un conjunto de muestreo de w2 en un cuadrado, con cada componente que va de 1 a 100, muestreado inicialmente más a menudo en el primer componente que el segundo:

% Initial sampling interval if isnan(s(1,1))    s(2,1) = 0.2;    s(2,2) = 0.5; end   % Sampling set w2x = 1:s(2,1):100; w2y = 1:s(2,2):100; [wx,wy] = meshgrid(w2x,w2y);

Los fragmentos de código anteriores se pueden simplificar de la siguiente manera:

% Initial sampling interval if isnan(s(1,1))     s = [0.2 0;0.2 0.5]; end  % Sampling set w1 = 2:s(1,1):12; w2x = 1:s(2,1):100; w2y = 1:s(2,2):100; [wx,wy] = meshgrid(w2x,w2y);

algoritmo fseminf

fseminf esencialmente reduce el problema de la programación semi-infinita a un problema abordado por fmincon. fseminf toma los siguientes pasos para resolver problemas de programación semi-infinitos:

  1. En el valor actual de x, fseminf identifica todos los Wj,i de tal manera que la interpolación κj(x, wj,i) es un máximo local. (el máximo se refiere a la variación de w para xfijos.)

  2. fseminf toma un paso de iteración en la solución del problema de fmincon :

    minxf(x)

    tal que c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u, donde c(x) se aumenta con todos los máximos de κj(xwj) asumido sobre todos wjIj, que es igual a los máximos sobre j y i de κj(xwj,i).

  3. fseminf comprueba si se cumple cualquier criterio de detención en el nuevo punto x (para detener las iteraciones); Si no, sigue el paso 4.

  4. fseminf comprueba si es necesario actualizar la discreción de las restricciones semi-infinitas y actualiza los puntos de muestreo de forma adecuada. Esto proporciona una aproximación actualizada κj(x, wj). Luego continúa en el paso 1.