Optimizacion no lineal

Métodos de Programación no lineal con restricciones

Los problemas con restricciones son más difíciles de resolver debido a los requerimientos adicionales que la solución debe satisfacer.

La mayoría de los métodos propuestos para resolver este tipo de problemas están basados en uno de los siguientes conceptos:

1. Extensión de la metodología lineal a través de repetidasaproximaciones lineales

2. Transformación de un problema con restricciones en una secuencia de problemas sin restricciones mediante el uso de funciones de penalización

r

3. Uso de tolerancias flexibles para acomodar vectores x

de regiones posibles y no posibles


En este curso estudiaremos los últimos dos conceptos.

2.1. Métodos de función de penalización
Enesencia:


Problema de Programación No Lineal con restricciones


se transforma

Problema sin restricciones
ó
Secuencia de problemas sin restricciones


Por ejemplo, supóngase que se quiere encontrar el mínimo de


f x x1

3 2 x 2 2



sujeto a

h x x1 x2 4 0


Se puede deducir una nueva función objetivo sin restricciones,


P x x1 3

x2 2

x1 x2 4al sumarle el cuadrado de la restricción a f(x) como una penalización. Durante la minimización de P(x)
el vector x es forzado por la penalización a satisfacer la restricción.

Los métodos de función de penalización se pueden dividir en dos clases:

Métodos Paramétricos: son caracterizados por uno o más parámetros ajustables que ponderan la función de penalización formada por lasrestricciones. Estos a su vez se pueden dividir en:

o Métodos de punto interior: Mantener lejos de los bordes de la región factible mediante la suma de la función de penalización.

o Métodos de punto exterior: generar una secuencia de puntos no factibles que en el límite llegan a una solución factible. La función de penalización previene de irse muy lejos de la región factible.

o Métodos mixtos:requeridos especialmente con restricciones de igualdad. Algunas restricciones son satisfechas y otras no, pero todas son satisfechas dentro de una tolerancia cuando se alcanza una solución.

Métodos No paramétricos: tratan a la función objetivo como una restricción adicional la cual es sucesivamente apegada a partir de la información desarrollada en la solución del problema.

En resumen:
Elenfoque de funciones de penalización es transformar el problema no lineal con restricciones en una secuencia de problemas sin restricciones sumando una ó más funciones de restricción a la función objetivo y eliminando así tales restricciones.

Formalmente la transformación del problema es como sigue:

Minimizar f r r n
Sujeto a m restricciones de igualdad
r

h j x

0 j = 1,…, my (p-m) restricciones de desigualdad
r

g j x

0 j = m+1,…, p




Minimizar

P x k , r k


f x k

m
r k H h x k

p
r k G g x k

i 1 i m 1


Donde
P x k , r k


: función aumentada generalizada, o función de penalización


i 0
H hi x


: factores de ponderación
: funcional de h x k



G g i x

: funcional de

g i xk : pasos de la búsqueda numérica

Selecciones típicas para funciones de restricciones de desigualdad G g i x


1. G1 gi x

à + si g i x

à 0+ è x siempre es un punto interior.



2. G2 g i x

à 0 si

g i x

à 0- è sólo son aceptados puntos exteriores.



3. G3 g i x

> 0 para g i x

< 0 y

G4 g i x

= 0 para g i x

≥ 0.Esta opción no

contempla la satisfacción de la restricción excepto en la solución.

Para restricción de igualdad una selección funcional típica es:


H hi x

à 0 si hi x à 0


Una forma típica para las restricciones de igualdad es H hi x i

Adicionalmente, para todas las selecciones anteriores se requiere que:



lim
k

p
r k G g x k 0

i m 1...