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 multiobjetivo

Definición de optimización multiobjetivo

Hay dos solucionadores multiobjetivos: y.Optimization Toolbox™fgoalattainfminimax

  • soluciona el problema de reducir un conjunto de funciones no linealesfgoalattain Fi() por debajo de un conjunto de objetivosx Fi. Dado que hay varias funciones Fi(), no siempre está claro lo que significa para resolver este problema, especialmente cuando no se puede lograr todos los objetivos al mismo tiempo.x Por lo tanto, el problema se reformula a uno que esté siempre bien definido.

    El es para minimizar el máximo deproblema de consecución de objetivo no escalado Fi(x) – F*i.

    Hay una generalización útil del problema sin escalar. Dado un conjunto de pesos positivos Wi, los intentos de encontrar para minimizar el máximo deproblema de logro de objetivox

    Fi(x)Fi*wi.(1)

    Esta minimización se supone que debe lograrse al tiempo que satisface todos los tipos de restricciones: c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u.

    Si establece todas las ponderaciones iguales a 1 (o cualquier otra constante positiva), el problema de consecución del objetivo es el mismo que el problema de consecución de objetivo no escalado. Si el Fi son positivas y establece todos los pesos como wi = F*i, el problema de logro de objetivo se convierte en minimizar la diferencia relativa entre las funciones Fi() y los objetivosx Fi.

    En otras palabras, el problema de logro de objetivo es minimizar una variable de holgura, definida como el máximo de las expresiones en.γiEcuación 1 Esto implica la expresión que es la declaración formal del problema de logro del objetivo:

    minx,γγ

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

  • resuelve el problema de minimizar el máximo de un conjunto de funciones no lineales, sujeto a todos los tipos de restricciones:fminimax

    minxmaxiFi(x)

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

    Evidentemente, este problema es un caso especial del problema de consecución de los meta no escalado, con F*i = 0 Y wi = 1.

Algoritmos

Método de consecución de objetivo

En esta sección se describe el método de logro de objetivo de Gembicki.[3] Este método utiliza un conjunto de objetivos de diseño, F*={F1*,F2*,...,Fm*}, asociado a un conjunto de objetivos, F(x) = {F1(x),F2(x),...,Fm(x)}. La formulación del problema permite que los objetivos estén bajo o sobrealcanzados, lo que permite que el diseñador sea relativamente impreciso sobre los objetivos de diseño iniciales. El grado relativo de subtitulación o sobreconsecución de los objetivos se controla mediante un vector de coeficientes de ponderación, w = {w1,w2,...,wm}, y se expresa como un problema de optimización estándar utilizando la formulación

minimizeγ, xΩγ(2)

tal que Fi(x)wiγFi*,  i=1,...,m.

El término WiΓ introduce un elemento en el problema, que de otro modo impone que los objetivos se cumplan rígidamente.slackness El vector de ponderación, permite al diseñador expresar una medida de las compensaciones relativas entre los objetivos.w Por ejemplo, establecer el vector de ponderación igual a los objetivos iniciales indica que se alcanza el mismo porcentaje bajo o sobrerendimiento de los objetivos.wF* Puede incorporar restricciones duras en el diseño estableciendo un factor de ponderación determinado en cero (es decir, wi = 0). El método de consecución de objetivo proporciona una práctica interpretación intuitiva del problema de diseño, que se puede resolver mediante procedimientos de optimización estándar. En Fleming se pueden encontrar ejemplos ilustrativos del uso del método de consecución de los meta en el diseño del sistema de control.[10][11]

El método de consecución de objetivo se representa geométricamente en la figura siguiente en dos dimensiones.

Figura 8-1, Representación geométrica del método de consecución de objetivo

Especificación de los objetivos, {F1*,F2*}, define el punto de objetivo,.P El vector de ponderación define la dirección de la búsqueda desde el espacio de la función factible,P Λ(γ). Durante la optimización es variada, lo que cambia el tamaño de la región factible.γ Los límites de restricción convergen en el punto de solución único F1s, F2s.

Mejoras del algoritmo para el método de consecución de objetivo

El método de consecución de objetivo tiene la ventaja de que puede ser planteado como un problema de programación no lineal. Las características del problema también se pueden explotar en un algoritmo de programación no lineal. En la programación cuadrática secuencial (SQP), la elección de la función de mérito para la búsqueda de línea no es fácil porque, en muchos casos, es difícil "definir" la importancia relativa entre la mejora de la función objetiva y la reducción de las violaciones de restricciones. Esto ha dado lugar a una serie de esquemas diferentes para la construcción de la función de mérito (véase, por ejemplo, Schittkowski).[36] En la programación de logro de objetivo puede haber una función de mérito más adecuada, que se puede lograr haciéndose pasar por el problema MiniMaxEcuación 2

minimizexn maxi{Λi},(3)

Dónde

Λi=Fi(x)Fi*wi,  i=1,...,m.

Siguiendo el argumento de Brayton et al. para la optimización MiniMax utilizando SQP, utilizando la función de mérito de para el problema de logro de objetivo de da[1]Ecuación 30Ecuación 3

ψ(x,γ)=γ+i=1mrimax{0,Fi(x)wiγFi*}.(4)

Cuando la función de mérito de se utiliza como base de un procedimiento de búsqueda de línea, a continuación, aunqueEcuación 4 ψ(x,γ) puede disminuir para un paso en una dirección de búsqueda determinada, la función Λmaxi podría aumentar paradójicamente. Esto está aceptando una degradación en el peor de los casos. Dado que el peor de los casos es responsable del valor de la función objetiva, esto es aceptar un paso que en última instancia incrementa la función objetiva para ser minimizada.γ Inversa ψ(x,γ) podría aumentar cuando Λmaxi disminuye, lo que implica el rechazo de un paso que mejore el peor objetivo del caso.

Siguiendo las líneas de Brayton et al. , una solución es, por lo tanto, establecer[1] ψ(x) igual al peor objetivo del caso, es decir,

ψ(x)=maxiΛi.(5)

Un problema en el método de consecución de objetivo es que es común utilizar un coeficiente de ponderación igual a 0 para incorporar restricciones duras. La función de mérito de entonces se convierte en infinito para las violaciones arbitrarias de las restricciones.Ecuación 5

Para superar este problema sin dejar de retener las características de, la función de mérito se combina con la de, dando lo siguiente:Ecuación 5Ecuación 31

ψ(x)=i=1m{rimax{0,Fi(x)wiγFi*}if wi=0maxiΛi, i=1,...,motherwise.(6)

Otra característica que se puede explotar en SQP es la función objetiva.γ De las ecuaciones KKT se puede demostrar que la aproximación al Hessiano del Lagrangio,, debe tener ceros en las filas y columnas asociadas con la variable.Hγ Sin embargo, esta propiedad no aparece si se inicializa como la matriz de identidad. por lo tanto se inicializa y se mantiene para tener ceros en las filas y columnas asociadas.HHγ

Estos cambios hacen que el Hessiano, indefinido.H Por lo tanto, se establece para tener ceros en las filas y columnas asociadas, excepto para el elemento diagonal, que se establece en un pequeño número positivo (por ejemplo,-10).Hγ1e Esto permite el uso del método de QP definido de forma positiva y rápida convergente que se describe en.Solución de programación cuadrática

Las modificaciones anteriores se han implementado en y se han encontrado para hacer el método más robusto.fgoalattain Sin embargo, debido a la rápida convergencia del método SQP, el requisito de que la función de mérito disminuya estrictamente a veces requiere más evaluaciones de funciones que una implementación de SQP utilizando la función de mérito de.Ecuación 30

Minimizando el objetivo máximo

utiliza un método de consecución de objetivo.fminimax Toma goles de 0, y pesos de 1. Con esta formulación, el problema de logro de objetivo se convierte en

minimaxx(fi(x)goaliweighti)=minimaxxfi(x),

que es el problema del minimax.

Entre paréntesis, podría esperar que la función multiobjetivo se convierta en un único objetivo.fminimax La función

() = máx (fxF1( ),...xFj( ))x

es una función de objetivo único para minimizar. Sin embargo, no es diferenciable y se requiere que los objetivos sean suaves.Optimization Toolbox Por lo tanto, el problema de MiniMax se formula como un problema de logro de objetivo suave.

Referencias

[1] Brayton, R. K., S. W. Director, G. D. Hachtel, and L.Vidigal, “A New Algorithm for Statistical Circuit Design Based on Quasi-Newton Methods and Function Splitting,” IEEE Transactions on Circuits and Systems, Vol. CAS-26, pp 784-794, Sept. 1979.

[2] Fleming, P.J. and A.P. Pashkevich, Computer Aided Control System Design Using a Multi-Objective Optimisation Approach, Control 1985 Conference, Cambridge, UK, pp. 174-179.

[3] Gembicki, F.W., “Vector Optimization for Control with Performance and Parameter Sensitivity Indices,” Ph.D. Dissertation, Case Western Reserve Univ., Cleveland, OH, 1974.

[4] Grace, A.C.W., “Computer-Aided Control System Design Using Optimization Techniques,” Ph.D. Thesis, University of Wales, Bangor, Gwynedd, UK, 1989.

[5] Han, S.P., “A Globally Convergent Method For Nonlinear Programming,” Journal of Optimization Theory and Applications, Vol. 22, p. 297, 1977.

[6] Madsen, K. and H. Schjaer-Jacobsen, “Algorithms for Worst Case Tolerance Optimization,” IEEE Trans. of Circuits and Systems, Vol. CAS-26, Sept. 1979.

[7] Powell, M.J.D., “A Fast Algorithm for Nonlinear Constrained Optimization Calculations,” Numerical Analysis, ed. G.A. Watson, Lecture Notes in Mathematics, Vol. 630, Springer Verlag, 1978.