FUNDAMENTOS DE LA OPTIMIZACIÓN RESTRINGIDA

CAPÍTULO 10

FUNDAMENTOS DE LA OPTIMIZACIÓN RESTRINGIDA

1.  Introducción

El material presentado hasta ahora se ocupó en gran medida de los principios, métodos y algoritmos para la optimización sin restricciones. En este y los próximos cinco capítulos, nos basamos en los principios introductorios de optimización restringida discutidos en secciones. 1.4-1.6 y proceda a examinar la teoría y la estructura subyacente de algunos algoritmos de optimización restringidos muy sofisticados y eficientes.

La presencia de restricciones da lugar a una serie de problemas técnicos que no se encuentran en problemas no restringidos. Por ejemplo, una búsqueda a lo largo de la dirección del negativo del gradiente de la función objetivo es una técnica bien justificada para la minimización sin restricciones. Sin embargo, en un problema de optimización restringido, los puntos a lo largo de dicha dirección pueden no satisfacer las restricciones y, en tal caso, la búsqueda no dará una solución al problema. En consecuencia, deben buscarse nuevos métodos para determinar las direcciones de búsqueda factibles.

Muchas técnicas potentes desarrolladas para problemas de optimización restringida se basan en métodos de optimización sin restricciones. Si las restricciones simplemente se dan en términos de límites inferiores y / o superiores en los parámetros, el problema puede convertirse fácilmente en un problema no restringido. Además, existen métodos para transformar un problema de minimización restringido en una secuencia de minimizaciones no restringidas de una función auxiliar apropiada.

El propósito de este capítulo es establecer una base teórica para el desarrollo de varios algoritmos de optimización restringida. Las restricciones de igualdad y desigualdad se discuten en términos generales en la sección 10.2. Después de una breve discusión sobre la clasificación de los problemas de optimización restringida en la sección 10.3, varias técnicas de transformación variable para convertir problemas de optimización con restricciones simples en problemas no restringidos se estudian en la sección 10.4. Se presenta uno de los conceptos más importantes en optimización restringida, el concepto de multiplicadores de Lagrange, y se da una interpretación geométrica de los multiplicadores de Lagrange en sección 10.5. Las condiciones necesarias de primer orden para que un punto x * sea una solución de un problema restringido, conocido como las condiciones de Karush-Kuhn-Tucker, se estudian en la sección 10.6 y las condiciones de segundo orden se discuten en la sección 10.7. Como en el caso no restringido, el concepto de convexidad juega un papel importante en el estudio de la optimización restringida y se discute en la sección 10.8. Finalmente, el concepto de dualidad, que es de importancia significativa en el desarrollo y la unificación de la teoría de la optimización, se trata en la sección 10.9.

1. Restricciones

1. Notación y suposiciones básicas

En su forma más general, un problema de optimización restringido es encontrar un vector x * que resuelva el problema

                        Minimizar [pic 1]                                     [pic 2]

Sujeto a :                         [pic 3] 

A lo largo del capítulo, asumimos que la función objetivo [pic 4] así como también las funciones involucradas en las restricciones en las ecuaciones [pic 5] y [pic 6], a saber,[pic 7]y[pic 8] son continuas y tienen segundas derivadas parciales continuas, es decir, [pic 9]. Deje que R denote la región factible para el problema en la ecuación. (10.1), que se definió en la sección 1.5 como el conjunto de puntos que satisfacen las ecuaciones [pic 10] y [pic 11], es decir,

        [pic 12] 

En este capítulo, así como en el resto del libro, a menudo necesitamos comparar dos vectores o matrices de entrada por entrada. Para dos matrices [pic 13] y [pic 14] de la misma dimensión [pic 15] para denotar [pic 16] para todo [pic 17]. En consecuencia, [pic 18] significa [pic 19] para todo [pic 20]. Escribimos [pic 21] para denotar que la matriz A es definida positiva, semidefinida positiva, definida negativa y semidefinida negativa, respectivamente.

1. Restricciones de igualdad

El conjunto de restricciones de igualdad

[pic 22]                                                 [pic 23] 

Define una hipersuperficie en [pic 24]. Usando la notación vectorial, podemos escribir

[pic 25] 

Y de la ecuación [pic 26], tenemos

                        [pic 27]                                                         [pic 28]

Definición 10.1 el punto [pic 29] se llama un punto regular de las restricciones en la ecuación [pic 30]si [pic 31] satisface la ecuación [pic 32]y los vectores de columna [pic 33] son linealmente independientes

La definición establece, en efecto, que [pic 34] es un punto regular de las restricciones, si es una solución de la ecuación  [pic 35] y el [pic 36] [pic 37] tiene un rango de fila completo. La importancia de que un punto [pic 38] sea regular para un conjunto dado de restricciones de igualdad radica en el hecho de que un “plano tangente” de la hipersuperficie determinado por las restricciones en un punto regular [pic 39] está bien definido. Más adelante en este capítulo, el término "plano tangente" se usará para expresar y describir las condiciones importantes necesarias y necesarias tanto para problemas de optimización limitados. Como [pic 40] es una matriz [pic 41], no sería posible que [pic 42] sea un punto regular de las restricciones si [pic 43]. Esto conduce a un límite superior para el número de restricciones de igualdad independientes, es decir,[pic 44]. Además, si [pic 45], en muchos casos la cantidad de vectores [pic 46] que satisfacen la ecuación [pic 47]es finito y el problema de optimización se vuelve trivial. Por estas razones, asumiremos que [pic 48]durante el resto del libro.

...