Artículos

Resolución de los problemas de optimización con restricciones mediante los métodos de penalización y del Lagrangiano aumentado

Solving constraint optimization problems using the penalty and augmented Lagrangian methods

Manuel Vázquez Mourazos
Universidad de Santiago de Compostela, España

Resolución de los problemas de optimización con restricciones mediante los métodos de penalización y del Lagrangiano aumentado

Revista Digital: Matemática, Educación e Internet, vol. 21, núm. 2, pp. 1-23, 2021

Instituto Tecnológico de Costa Rica

Derechos Reservados © 2021 Revista digital Matemática, Educación e Internet

Recepción: 24 Abril 2019

Aprobación: 15 Septiembre 2020

Resumen: En la resolución de los problemas de optimización con restricciones (también conocida con el nombre de programación matemática) se pueden establecer diversidad de algoritmos. Como la investigación en este campo es muy amplia, continuamente se están desarrollando nuevos métodos, cada vez más sofisticados, que permiten resolver este tipo de problemas.

En este artículo se presentarán los métodos de penalización. Estos son los más intuitivos y permiten mostrar una introducción dentro de la resolución de este tipo de problemas. Se estudiarán sus pro- piedades y, luego, se procederá a su deducción, interpretación y demostración de su convergencia. Finalmente, se presentará el método del Lagrangiano aumentado. Este es un método que mejora a los anteriores y con una mayor velocidad de convergencia. Así mismo, este artículo supone una introducción a los algoritmos de resolución de problemas de optimización con restricciones, mostrando una iniciación a los métodos numéricos empleados en la programación matemática.

Palabras clave: optimización con restricciones, penalización, penalización exterior, penalización interior, Lagrangiano aumentado, condiciones KKT.

Abstract: In solving constrained optimization problems (also by the name of mathematical programming), a variety of algorithms can be established. As the research in this field is very extensive, new and increasingly sophisticated methods are continually being developed to solve this type of problem.

In this article the methods of penalization will be presented. These are the most intuitive and allow to show an introduction within the resolution of this type of problem. Their properties will be studied, and then their deduction, interpretation and demonstration of their convergence will proceed. Finally, the augmented Lagrangian method will be presented. This is a method that improves on the previous ones and allows for greater and better convergence. Likewise, this article supposes an introduction to the optimization algorithms of constraint optimization, showing an introduction to the numerical methods used in mathematical programming.

Keywords: constraint optimization, penalty methods, simple penalty, interior point penalty, Augmented Lagrangian, KKT conditions.

1. Introducción

La programación matemática es una rama que pretende estudiar la resolución de problemas de optimización. En este artículo se dará una serie de algoritmos para su resolución, siendo el objetivo de estudio el algoritmo del lagrangiano aumentado. A lo largo de las diferentes secciones se introducirán resultados teóricos sobre los que se apoyan estos métodos, haciendo una revisión básica por los más importantes. Los teoremas y resultados mostrados no son de producción propia, sino que son una recopilación sobre la que se basa el tema de estudio en este artículo. En este sentido, el aporte del artículo se centra en los ejemplos, la ejecuciones y las reflexiones que se vayan mostrando según se introduzcan los contenidos.

Notación 1

Antes de comenzar con la redacción, se hacen las siguientes aclaraciones correspondientes a la notación que se empleará en lo sucesivo:

  1. 1. A lo largo del artículo se emplearán escalares, vectores y matrices de forma frecuente. Para diferenciarlos, se escribirá a los vectores en letra negrita minúscula (por ejemplo v), a las matrices por letra negrita mayúscula (por ejemplo M) y en letra normal minúscula a los escalares (por ejemplo k).
  2. 2. 2. El empleo de los vectores será muy reiterado. Dado un vector v, si se desea referirse a su componente i-ésima, esta se denotará en letra normal minúscula con el subíndice, es decir, vi.
  3. 3. 3. En una sucesión de vectores, se denotará al vector k-ésimo de la sucesión con la siguiente escritura: v(k).
  4. 4. 4. A los conjuntos se les denotará en letra normal mayúscula, por ejemplo S. El término Int(S) se refiere al interior del conjunto.

Las diversas situaciones en las que es necesario el estudio de estos problemas, conlleva a que su formulación pueda ser muy variada y compleja. Normalmente, un problema que se asemeja bastante a una formulación genérica de un problema de este tipo es el siguiente:

(1)

El objetivo del problema (1) es la obtención del mínimo del funcional objetivo, J(v), dentro del conjunto que determinan las restricciones. Es decir, no se busca optimizar el funcional objetivo en todo su dominio, sino que se exige que la solución pertenezca al siguiente conjunto,

que se denominará como conjunto admisible o conjunto factible.

La resolución del problema (1) es bastante compleja y, para ello, hay diversas tácticas que permiten obtener una solución numérica del problema. Algunos de los algoritmos abordan el problema directamente, pero, por el contrario, otros métodos optan por el cálculo de puntos que cumplen una serie de condiciones cuyas propiedades hacen que sean candidatos muy probables a ser solución del problema.

Dentro de los algoritmos que opten por encontrar una posible solución hallando un punto que verifique las condiciones de Karush-Kuhn-Tucker, también conocidas como condiciones KKT. Estas condiciones permiten concluir, bajo ciertas hipótesis, que los puntos que las verifican son mínimos del problema genérico (1). Su definición se establece a continuación:

Definición 1

Se dice que un punto u n es un punto de Karush-Kuhn-Tucker para el problema (1), si y sólo si, existen multiplicadores de Lagrange y de Karush-Kuhn-Tucker (a los que se denotará por las letras griegas λ = ( λ 1 , . . . , λ p ) T y μ = ( μ 1 , . . . , μ m ) T , respectivamente) que verifican las condiciones de KKT, que son las siguientes:

- Condición estacionaria:

∇J ( u ) + i = 1 m μ i φ i ( u ) + j = 1 m λ j Φ j ( u ) = 0 , (2)

- Condición de factibilidad:

φ i ( u ) 0 i = 1 , . . . , m Φ j ( u ) = 0 j = 1 , . . . , p (3)

- Condición de holgura:

μ i φ i ( u ) = 0 i = 1 , . . . , m μ i 0 i = 1 , . . . , m (4)

Si se observa la definición 1, esta establece, mediante la condición (3), la factibilidad del punto. Las demás condiciones establecen una caracterización del punto que servirá para demostrar que un punto que verifica las condiciones KKT es un buen candidato a ser solución del problema (1). Dado que este artículo no versa sobre las condiciones KKT, se introducirán los siguientes resultados sin demostración. Además, se incluirá una referencia donde se pueden consultar.

Definición 2

Dado el punto v ∈S , se define el conjunto de restricciones activas de v como sigue:

I ( v ) : = { i { 1 , . . . , m } : ( v ) = 0 } .

Teorema 1 (Teorema de Karush-Kuhn-Tucker)

Sea u un mínimo local del problema (1). Si los vectores Φ j ( u ) con j = 1 , . . . , p y φ i ( u ) , con i I ( u ) , son linealmente independientes, entonces existen multiplicadores de Lagrange y de KKT que verifican las condiciones KKT.

Demostración. Se puede consultar en [13, Teorema 8.2.7].

Este resultado permite establecer que las condiciones KKT son una condición necesaria bajo una hipótesis. La hipótesis establecida en el Teorema 1 se denomina condición de cualificación y esta se puede cambiar por otras que permiten demostrar el mismo resultado. Para más información de este tema, consultar [13, Cap. 8] ó [5, Sec. 6.3].

Sin embargo, el resultado visto es necesario, pero no es suficiente. Para ello, se pueden robustecerlas hipótesis del problema de optimización haciendo que este sea convexo. Esto quiere decir que tanto el funcional objetivo como el conjunto admisible sean convexos (se puede consultar para ello la Definición 1). El resultado se puede ver en el Teorema 1.

Definición 3

Un conjunto S se dice convexo si verifica que para cualesquiera a , b ∈S se cumple que

( 1 t ) a + t b ∈S , t 0 1

Además, dada una función f , definida sobre un conjunto convexo, se dice que es convexa si para cualesquiera dos puntos a y b de su dominio se verifica que

f ( ( 1 t ) a + t b ) ( 1 t ) f ( a ) + t f ( b ) , t 0 1

Teorema 2

Se considera el problema de optimización (1). Si este es convexo, se tiene que dado un punto admisible u ∈S , para el cual existen multiplicadores de Lagrange y KKT ( λ y μ , respectivamente),entonces u es un mínimo del problema.

Demostración. Se puede consultar en [13, Teorema 8.2.18].

De esta forma, se comprueba que los puntos que verifican las condiciones KKT, bajo ciertas condiciones, son puntos que pueden ser mínimos del problema original (1) o incluso ser los únicos mínimos. Así, algunos métodos numéricos optan por calcular numéricamente este tipo de puntos para hacer un estudio posterior y comprobar si efectivamente son soluciones al problema.

En este artículo se presentarán los métodos de penalización. Estos algoritmos se basan en una serie de ideas muy intuitivas que permiten resolver el problema genérico (1) de forma directa. Sin embargo, en la práctica no resultan del todo favorables y, por ello, se mostrará finalmente el método del Lagrangiano aumentado que fue desarrollado primeramente entre 1973 y 1974 por Rockafellar ([10],[11] y [12]) a partir de la idea inicial de Hestenes [7] y Powell [9] en 1969. Aunque este método se basa en parte en la penalización, este opta por la obtención y cálculo de un punto que verifican las condiciones KKT.

2. Métodos de penalización

En esta sección se estudiarán los métodos de penalización, existen diversos tipos, pero una característica común que los define. Esta consiste en reducir el problema con restricciones (1), a un problema sin restricciones. Es decir, se reduce el problema genérico principal a uno del siguiente tipo:

mín v n J ( v ) , (5)

donde se optimiza el funcional objetivo en todo su domino en lugar de en un conjunto admisible. La optimización sin restricciones resulta más sencilla y se ha estudiado con mayor profundidad a lo largo de la historia. Para su resolución existen diversos algoritmos, algunos de ellos muy sofisticados y con muy buenos resultados en la práctica. Por este motivo, se opta por esta reducción de un problema más complejo a uno más sencillo. Si se desean conocer los detalles acerca de los algoritmos que permiten resolver los problemas de optimización sin restricciones, se puede consultar [2, Cap. 5] para tener una visión general o, también, se puede consultar [8, Cap. 6] donde se hace hincapié en los métodos Quasi-Newton, que son los más empleados.

La idea principal de los métodos de penalización consiste en construir un nuevo funcional objetivo de tal manera que si se toma un elemento fuera del conjunto admisible, se penalice esa elección aumentando el valor que toma el funcional. De ahí proviene el nombre de penalización, pues se castigala toma de un punto no factible y, dependiendo del tipo de penalización, se pueden diferenciar los distintos tipos de métodos que se presentan a continuación.

2.1 Penalización exterior

Este primer método reside en el diseño de una sucesión de subproblemas de optimización sin restricciones. La sucesión formada por las soluciones de los subproblemas converge a la solución del problema original (1). Con este motivo se crea una función P : n , denominada función de penalización, y que viene caracterizada del siguiente modo:

P ( v ) : = P ( v ) > 0 s i v ∉S P ( v ) = 0 s i v ∈S

Con base en esta función se define una sucesión de problemas que pretenden minimizar al funcional J ε ( v ) sin restricciones, de tal manera que:

mín v n J ε ( v ) =J ( v ) + 1 ε P ( v ) (6)

Entonces, dada una sucesión de elementos { ε k } k n positivos convergentes a cero, se obtiene una sucesión { u ( ε n ) } n de soluciones de (6), la cual convergerá a un elemento u , que es solución de (1).Para comenzar, se verán algunas propiedades de las funciones de penalización y de las soluciones u ( ε k ) .

Lema 1 Dado 0 < 1 / ε 1 < 1 / ε 2 , se tienen las siguientes propiedades:

1. J ε 1 ( u ( ε 1 ) ) J ε 1 ( u ( ε 2 ) ) .

2. J ( u ( ε 1 ) ) J ( u ( ε 2 ) ) .

3. P ( u ( ε 1 ) ) P ( u ( ε 2 ) ) .

Demostración. Aplicando la definición de solución del problema (6), se tiene que:

J ε 1 ( u ( ε 1 ) ) J ε 1 ( u ( ε 2 ) ) J ε 2 ( u ( ε 2 ) ) J ε 2 ( u ( ε 1 ) ) . (7)

Por tanto, ya se ha obtenido (1). Ahora, usando la propiedad (1) demostrada y (7), se llega a,

0 J ε 1 ( u ( ε 2 ) ) J ε 2 ( u ( ε 2 ) ) [ J ε 1 ( u ( ε 1 ) ) J ε 2 ( u ( ε 1 ) ) ] = 1 ε 1 P ( u ( ε 2 ) ) 1 ε 2 P ( u ( ε 2 ) )

[ 1 ε 1 P ( u ( ε 1 ) ) 1 ε 2 P ( u ( ε 1 ) ) ] = ( 1 ε 1 1 ε 2 ) ( P ( u ( ε 2 ) ) P ( u ( ε 1 ) ) )

de lo que se deduce (3). Y, usando ahora (3) y (7), se tiene que,

J ( u ( ε 1 ) ) J ( u ( ε 2 ) ) + 1 ε 1 ( P ( u ( ε 2 ) ) P ( u ( ε 1 ) ) ) <J ( u ( ε 2 ) ) .

lo cual demuestra (2) y finaliza la prueba.

Lema 2 Sea u la solución del problema (1) considerado. Entonces, para cada k se tiene que:

J ( u ) J ε k ( u ( ε k ) ) J ( u ( ε k ) ) .

Demostración. El resultado es inmediato considerando el siguiente desarrollo:

J ( u ) = J ( u ) + 1 ε k P ( u ) J ( u ( ε k ) ) + 1 ε k +P ( u ( ε k ) ) +J ( u ( ε k ) )

Lema 3 Se considera el problema (1) y u ( ε ) la solución al problema (6). Entonces, tomando δ = P ( u ( ε ) ) , se tiene que u ( ε ) también es solución del problema:

(8)

Demostración. Para cualquier v que satisfaga la condición P ( v ) δ se tiene que:

0 1 ε ( P ( u ( ε ) ) P ( v ) ) = J ε ( u ( ε ) ) J ( u ( ε ) ) J ε ( v ) + J ( v )

= [ J ε ( u ( ε ) ) J ε ( v ) ] + J ( v ) J ( u ( ε ) ) J ( v ) J ( u ( ε ) ) J ( v ) J ( u ( ε ) ) ,

obteniendo así la definición de mínimo y concluyendo así la demostración.

Llegados a este punto, se está en condiciones de deducir el algoritmo del método. Entonces, al considerar el problema (1), teniendo en cuenta cómo se define la función de penalización, este se puede reescribir como:

(9)

Ahora bien, tomando δ lo suficientemente pequeño, el problema (8) será una aproximación del problema original (1). Por tanto, aplicando el Lema 2.1, u ( ε ) es una aproximación de u (solución del problema inicial).

La idea básica de este método se basa en que, según se reduce el parámetro de penalización ε , se reduce el valor de P ( u ( ε ) ) , como se vió en el Lema 2.1. Por este motivo, si se fija un valor de tolerancia δ para aproximar el problema (1) mediante (8), se puede establecer el Algoritmo 2.1.

Algoritmo 1 Penalización exterior

Se sigue el siguiente procedimiento:

PASO 0: Se toma ε 0 > 0 , δ > 0 y k = 0 .

PASO 1: Se calcula u ( ε k + 1 ) , solución de (6).

PASO 2: Si la penalización P ( u ( ε k + 1 ) ) < δ , entonces se finaliza. En caso contrario, se toma ε k + 1 = ε / 1 0 , k = k + 1 y se vuelve al PASO 1.

Observación 1

La actualización del valor ε no tiene porqué ser la utilizada en el algoritmo. Esta puede variaren función de nuestros intereses, haciendo que la sucesión { ε k } k decrezca con mayor o menor rapidez. Lo ideal es que la sucesión decrezca paulatinamente, para que la sucesión de soluciones no sufra cambios bruscos. En caso de construir una sucesión { ε k } k que decrezca muy rápidamente, es posible que alguno de los subproblemas asociados no tenga solución o sea muy complicado calcularla, por lo que es preferible observar un comportamiento progresivo dela sucesión. Además, en la resolución de los subproblemas (6), se tendrá que usar algún método de resolución de problemas de optimización sin restricciones. En dichos métodos se debe aportar un iterante inicial. En este caso, un buen iterante inicial, la solución u ( ε k ) calculada en la iteración anterior. Por otro lado, nótese que la función de penalización debe ser elegida de tal forma que el funcional J ε ( v ) tenga mínimo finito, ya que si no es así, el algoritmo diverge. Esta situación se puede dar en casos donde el funcional objetivo decrezca según ν + y la función de penalización no crezca con la misma rapidez que decrece J ( v ) .

Ahora bien, una cuestión importante es el estudio de la convergencia del método. Para ello se introduceel Teorema 2.1.

Teorema 3

Dado el problema (1) con un funcional continuo. Entonces, cualquier punto límite de la sucesión { u ( ε k ) } generada por el Algoritmo 2.1 es solución del problema original (1).

Demostración. Suponga que { u ( ε k ' ) } es una subsucesión convergente con límite u. Entonces, por la continuidad del funcional J , se tiene que:

lim k ' + J ( u ( ε k ' ) ) = J ( u ) (10)

Denotando por J * el valor del funcional en la solución del problema (1), y teniendo en cuenta los Lemas 2.1 y 2.1, la sucesión { J ε k ' ( u ( ε k ' ) ) } es creciente y está limitada superiormente por J * . Entonces:

lim k ' + J ε k ' ( u ( ε k ' ) ) = q J * (11)

De manera que, extrayendo (10) de la ecuación (11) se tiene:

lim k ' + 1 ε k ' P ( u ( e k ' ) ) = q J ( u ) (12)

Como P ( u ( e k ' ) ) 0 y 1 / ε k ' + por (12), implica que:

lim k ' + P ( u ( e k ' ) ) = 0

Usando ahora la continuidad de P ( t b f v ) , se obtiene que P ( u ) = 0 , por lo que u es un punto admisible para el problema. Además, por el Lema 2.1, J ( u ( e k ' ) ) J * y por lo tanto:

J ( u ) = lim k ' + J ( u ( e k ' ) ) J *

Por lo que u es una solución óptima factible del problema original (1).

Observación 2

Del Teorema 2.1 se deduce que si la sucesión generada por el Algoritmo 2.1 converge a un punto, este será solución del problema general (1). Sin embargo, esta sucesión no tiene porqué ser convergente siempre. Por ejemplo, puede darse que el mínimo de algún subproblema no sea finito y, por tanto, la sucesión comience a divergir. Por este motivo sería importante poder demostrarla existencia y unicidad de solución en los subproblemas sin restricciones del Algoritmo 2.1. Este hecho es bastante complicado en la práctica y se podría consultar [3] para conoce más acerca de esta temática.

Una cuestión interesante es cómo crear una función de penalización P ( v ) . En realidad, cualquier función que cumpla las propiedades dadas en el Lema 2.1, se puede usar. Sin embargo, algunas tiene mejores propiedades que otras. Una posible opción, es usar la función (13) denominada penalización cuadrática:

P ( v ) = i = 1 m ( máx { 0 , φ i ( v ) } ) 2 + j = 1 p | Φ j ( v ) | 2 . (13)

Tal y como está definida esta penalización, el funcional J ε ( v ) será derivable y continuo. Pero al no ser continua la segunda derivada, puede conllevar problemas si se utiliza un método de resolución de optimización sin restricciones que involucre a la segunda derivada del funcional objetivo.

Ejemplo 1

Para ejemplificar visualmente lo que produce la penalización, tomando la función de penalización (13), se va a aplicar ahora al siguiente problema unidimensional:

(14)

Representación gráfica del problema (14).
Figura 1
Representación gráfica del problema (14).

En la gráfica de la izquierda se muestra el funcional, las restricciones y el conjunto factible. Mientras que en la segunda gráfica se muestra el funcional objetivo J ( v ) y los diferentes J ε ( v ) , a medida que se afina el valor de ε , según se indica en las gráficas. Se observa que los funcionales J ε ( v ) aumentan su valor fuera de la región factible, mientras que se mantiene el funcional original dentro del conjunto admisible. Una vez vista la intuición del método de forma gráfica, se puede introducir una visión práctica. En este sentido, se presenta el siguiente problema del que se mostrarán los resultados obtenidos en algunas iteraciones del método de penalización exterior:

(15)

Tabla 1
Tabla 1: Resultados obtenidos con el método de penalización exterior en el problema (15).
Tabla 1: Resultados obtenidos con el método de penalización exterior en el problema (15).

En la Tabla 1 se puede ver la convergencia hacia un punto de la circunferencia de radio uno (pues el mínimo es cualquier punto de la circunferencia unidad). Pero, además, se pueden apreciarlas propiedades vistas en el Lema 2.1.

Observación 3

Los resultados mostrados en la Tabla 1 no son únicos. Dependiendo del algoritmo que se utilice en la resolución de los subproblemas de optimización sin restricciones se obtendrán unos valores u otros, pero en cualquier caso los comportamientos que se observan deben ser similares a los mostrados en la Tabla 1.

2.2. Penalización interior

Otro método similar al anterior es el método de la penalización interior o de la barrera. En este nuevo caso, se vuelve a usar una función de penalización a partir de la cual se definirá un nuevo funcional objetivo y. A partir del funcional se construye una sucesión de subproblemas cuya sucesión de soluciones converge a la solución del problema inicial.

Sin embargo, se presentan diferencias respecto al caso anterior. En primer lugar, este tipo de método solo es aplicable a problemas de optimización, como el visto en (1), pero considerando únicamente las restricciones de desigualdad. Es decir, únicamente se aplicará el método al siguiente problema:

(16)

Entonces, siguiendo una filosofía similar al caso de la penalización exterior, se busca construir una sucesión de soluciones factibles, por lo que cada u ( ε ) ∈S . Para introducirse en el método se comenzará por la definición de la función de penalización, que se define, para este método, como P : n + tal que:

lim d ( v , ∂S ) 0 P ( v ) = ± ,

donde d ( v , ∂S ) denota la distancia del punto v a la frontera de S , por lo tanto, la penalización aumenta según se aproxima a la frontera del conjunto admisible. Con base en esta penalización, se define el siguiente problema:

mín v n J ε ( v ) =J ( v ) + εP ( v ) , (17)

que es un problema sin restricciones. A continuación se presentan varias propiedades de esta función de penalización que son análogas a las del caso anterior.

Lema 4 Dado 0 < ε 2 < ε 1 , se tiene;

1. J ε 2 ( u ( ε 2 ) ) J ε 1 ( u ( ε 1 ) )

2. J ( u ( ε 2 ) ) J ( u ( ε 1 ) )

3. P ( u ( ε 2 ) ) P ( u ( ε 1 ) )

Demostración. Teniendo en cuenta la definición de J ε ( v ) y de mínimo, se tiene:

J ε 2 ( u ( ε 2 ) ) J ε 2 ( u ( ε 1 ) ) J ε 1 ( u ( ε 1 ) ) J ε 1 ( u ( ε 2 ) ) (18)

de lo que se obtiene (1). Además;

0 J ε 2 ( u ( ε 1 ) ) J ε 1 ( u ( ε 1 ) ) [ J ε 2 ( u ( ε 2 ) ) J ε 1 ( u ( ε 2 ) ) ]

= ε 2 P ( u ( ε 1 ) ) ε 1 P ( u ( ε 1 ) ) [ ε 2 P ( u ( ε 2 ) ) ε 1 P ( u ( ε 2 ) ) ] = ( ε 1 ε 2 ) ( P ( u ( ε 2 ) ) P ( u ( ε 1 ) ) )

Como ε 1 ε 2 > 0 , entonces se deduce (3). Y, finalmente, usando (18) y (3) se tiene.

J ( u ( ε 2 ) ) J ( u ( ε 1 ) ) + ε 2 ( P ( u ( ε 1 ) ) P ( u ( ε 2 ) ) ) ,

de lo que se deduce (2).

Lema 5 Siendo u ( ε ) solución del problema (17) y tomando δ = P ( u ( ε ) ) , entonces u ( ε ) es solución del problema

(19)

Demostración. Para todo v n tal que P ( v ) δ , se tiene:

0 ε ( P ( u ( ε ) ) −P ( v ) ) = J ε ( u ( ε ) ) J ( u ( ε ) ) J ε ( v ) + J ( v ) = ]

[ J ε ( u ( ε ) ) J ε ( v ) ] + J ( v ) J ( u ( ε ) ) J ( u ( ε ) ) J ( v ) J ( u ( ε ) ) J ( u ( ε ) ) ≤J ( v )

de lo que se obtiene la definición de mínimo y, por tanto, lo que se quería probar.

Cuando el valor de δ del Lema 2.2 es lo suficientemente grande, este sirve para aproximar el siguiente problema:

(20)

Ahora bien, del modo en que se ha definido la función de penalización, la restricción del problema(20) es equivalente a que su solución sea factible para el problema inicial (1). Sin embargo, dicha solución no se encontrará sobre la frontera de S, ya que en dichos puntos la penalización tiende a infinito.

Además, si ε > 0 es suficientemente pequeño y el δ del Lema 2.2 es lo bastante grande, entonces u ( ε ) se encuentra dentro de la región factible S y aproxima el valor de la solución del problema original. Entonces, se puede deducir el algoritmo 2.2.

Algoritmo 2 Penalización interior

Se aporta el siguiente pseudocódigo:

PASO 0: Se toma ε 1 > 0 , δ > 0 y k = 1 .

PASO 1: Se calcula u ( ε k + 1 ) , solución de (17).

PASO 2: Si ε k P ( u ( ε k + 1 ) ) < δ , se finaliza. En caso contrario, se toma ε k + 1 = ε k / 1 0 , k = k + 1 y se vuelve al PASO 1.

Observación 4

Al igual que sucedía en el método de penalización exterior, el decrecimiento de ε en el PASO 2,no tiene que ser la indicada, sino que puede ser cualquiera. Lo ideal es que el decrecimiento, al igual que en la Observación 2.1, sea paulatina debido a que esto ayuda en la resolución delos subproblemas. Si el decrecimiento de ε es demasiado pronunciado, se corre el riesgo de que los algoritmos de resolución de los subproblemas no encuentren una solución finita, lo que conllevaría a no obtener información acerca de la sucesión de soluciones aportada por el Algoritmo 2.2.

Una vez visto el Algoritmo 2.2, se introduce a continuación el Teorema 2.2 que aporta resultados sobre la convergencia de dicho método.

Teorema 4

Sea J ( v ) un funcional limitado inferiormente en la región factible S . Entonces, el algoritmo de penalización interior termina de forma finita para δ > 0 y, cuando no lo hace, entonces se verifica que:

1. lim k ε k P ( u ( k + 1 ) ) = 0 ,

2. lim k J ( u ( k + 1 ) ) = ínf v Int ( S ) J ( v )

Y, además, cualquier punto de acumulación de la sucesión { u k } k es solución del problema(16).

Demostración. Solo será necesario probar (1) y (2) cuando el algoritmo no termina de forma finita. Para ello, se toma η > 0 arbitrario, por lo que existirá un elemento (que depende de η ), al que se denotará por u η Int ( S ) , de tal forma que:

J ( u η ) < ínf v Int ( S ) J ( v ) + η 2 (21)

Entonces, como { ε k } 0 y u η Int ( S ) , debe existir un k tal que:

ε k P ( u η ) < η 2 , k k (22)

Usando ahora que u ( k + 1 ) es el mínimo del funcional J ε ( v ) :

( u ( k + 1 ) ) ε k ( u η ) ε k P ( u ( k + 1 ) ) J ( u η ) + ε k P ( u η ) J ( u ( k + 1 ) ) (23)

Por lo que usando (21), (22) y (23), se obtiene que:

ε k P ( u ( k + 1 ) ) J ( u η ) + ε k P ( u η ) J ( u ( k + 1 ) )

ínf v Int ( S ) J ( v ) + η 2 + η 2 J ( u ( k + 1 ) ) η , k k

Como η > 0 es arbitrario, se concluye (1). Ahora, para probar (2), utilizando la desigualdad anterior, se tiene:

J ( u ( k + 1 ) ) J ( u η ) + ε k P ( u η ) ínf v Int ( S ) J ( v ) + η , k k

Como η > 0 es arbitrario, se concluye (2).

Una vez vistos estos resultados, es natural plantear la cuestión sobre cómo tomar la función de penalización P ( v ) . Con este motivo, se plantean las opciones reflejadas en (24) que son las más generales:

(24)

Para mostrar el efecto de la penalización interior de un modo visual, se considera el siguiente problema:

(25)

del que se obtiene los siguientes resultados.

Representación gráfica del problema (25).
Figura 2:
Representación gráfica del problema (25).

En la primera gráfica de la figura 2 se muestra el funcional objetivo con las restricciones y el conjunto factible. Luego, en la segunda gráfica se muestra de nuevo el funcional objetivo y, además, los funcionales J ε ( v ) para distintos valores de ε . De este modo, se observa la convergencia de los funcionales J ε ( v ) al funcional del problema original dentro de la región factible. Sin embargo, existe una peculiaridad dado que en la frontera del conjunto los valores de J ε ( v ) tienden al infinito, lo que muestra que el método sólo convergerá a un punto del interior del conjunto admisible.

De este modo, se muestra visualmente cómo es necesario inicializar el método desde un punto factible, además de que, para restricciones de igualdad, el método no serviría dado que los funcionales J ε ( v ) no estarían definidos en esos puntos.

3. Método del lagrangiano aumentado

Una vez vistos los métodos basados en penalización, se puede observar la necesidad de que el parámetro ε k tienda a cero cuando k tiende a infinito. Este hecho es una gran desventaja desde el punto de vista numérico, debido a que según se toma ε k más pequeño, la resolución numérica de los subproblemas generados puede resultar más compleja de lo previsto.

Para solventar esta dificultad se introduce el concepto de Lagrangiano aumentado. Este concepto se deriva de la función Lagrangiano y permite solventar ese problema que presentan los métodos de penalización. Para ello, se planteará, en primer lugar, el concepto de Lagrangiano aumentado para el problema con restricciones de igualdad. Esto es, se considerará en primera estancia el siguiente problema de optimización:

(26)

Definición 4

Se define la función Lagrangiano aumentado para el problema (26) como sigue:

L ε ( v , ε ) = J ( v ) + j = 1 p ξ j Φ j ( v ) + 1 2 ε j = 1 p ( φ j ( v ) ) 2 = J ( v ) + ξ T Φ ( v ) + 1 2 ε | | Φ ( v ) | | 2

Observación 5

Es fácil observar cómo la definición anterior es precisamente el Lagrangiano del problema de minimización:

que tiene el mismo mínimo local que el problema (26).

El Lema 3 y el Teorema 3 serán la base para justificar el método del Lagrangiano aumentado.

Lema 6

Sean P y Q dos matrices simétricas. Se asume que Q es semidefinida positiva y que P es definida positiva en el espacio nulo de Q , es decir, d T P d > 0 para todo d 0 , con d T Q d = 0 . Entonces, existe un escalar p ~ tal que:

P + p Q es definida positiva p > p ~ .

Demostración. Se puede ver en [1, Lema 3.2.1].

Teorema 5 Condición suficiente de Lagrange

Se considera el problema (26), bajo las hipótesis de derivabilidad del funcional objetivo y delas restricciones. Entonces, suponiendo que u ∈S es un punto que verifica las condiciones KKT con multiplicadores de Lagrange λ , y que cumple que,

d T H L v ( u , λ ) d > 0 para todo d 0 , con Φ ( u ) ' d = 0 ,

entonces u es un mínimo local estricto del problema (26).

Demostración. Se puede consultar en [1, Proposición 3.2.1].

Llegado a este punto, se está en condiciones de demostrar el siguiente resultado que justifica lo que se ha comentado hasta el momento.

Teorema 6

Dado el problema (26), si u ∈S cumple las condiciones suficientes de segundo orden del Teorema 3 con su multiplicador de Lagrange asociado λ . Entonces, existe un valor ε tal que u es un mínimo local de la función L ε ( v , λ ) , para todo ε < ε .

Demostración. Calculando el gradiente y la matriz hessiana de la función L ε ( v , ξ ) respecto de la variable v , se tiene:

v L ε ( v , ξ ) = ∇J ( v ) + Φ ' ( v ) T ( ξ + 1 ε Φ ( v ) )

y

H v L ε ( v , ξ ) = HJ ( v ) + j = 1 p ( ξ j + 1 ε Φ j ( v ) ) H Φ j ( v ) + 1 ε Φ ' ( v ) T Φ ' ( v ) .

En particular, si u y λ satisfacen las condiciones del Teorema 3, se tiene:

v L ε ( u , λ ) = ∇J ( u ) + Φ ' ( u ) T ( λ + 1 ε Φ ( u ) ) = v L ( u , λ ) = 0 (27)

H v L ε ( u , λ ) = HJ ( u ) + j = 1 p ( λ j + 1 ε Φ j ( u ) ) H Φ j ( u ) + 1 ε Φ ( u ) Φ ( u ) T .

H v L ( u , λ ) + 1 ε Φ ' ( u ) T Φ ' ( u )

Usando la condición suficiente del Teorema, se sabe que:

d T H L ( u , λ ) d > 0 para todo d 0 tal que d T Φ ' ( u ) T Φ ' ( u ) d = 0 .

Entonces, haciendo uso del Lema 3, implica que existe un ε tal que:

(28)

Teniendo en cuenta (27) y (28), se está en hipótesis del Teorema 3, por lo que se verifica que para todo ε < ε , u es un mínimo local de la función L ε ( v , λ ) .

Por tanto, si se conocen de antemano los valores de los multiplicadores de Lagrange λ bastaría con un número finito de subproblemas sin restricciones que minimicen al funcional L ε ( v , λ ) para llegara obtener la solución del problema (26). Sin embargo, esta es una situación idílica, debido a que en la práctica dichos multiplicadores no se conocerán. Por este motivo, se recurre a una estimación de los multiplicadores. Para ver su deducción, se considera el siguiente problema de minimización que, para un valor fijo de λ , es equivalente al problema (26):

que al aplicarle el método de penalización exterior, tomando como función penalizadora P ( v ) = 1 / 2 j = 1 p ( Φ j ( v ) ) 2 , se obtiene el siguiente subproblema en cada iteración:

mín v n = J ( v ) + j = 1 p λ j Φ j ( v ) + 1 2 ε j = 1 p ( Φ j ( v ) ) 2

Al suponer que el valor de los λ j varía, entonces los subproblemas también cambian. Pero, suponiendo que se busca un punto estacionario, entonces:

∇J ( v ) + j = 1 p λ j Φ j ( v ) + 1 ε j = 1 p Φ j ( v ) Φ j ( v ) = 0 ∇J ( v ) + j = 1 p ( λ j + 1 ε Φ j ( v ) ) Φ j ( v ) = 0 .

De este modo, teniendo en cuenta las condiciones KKT del problema original (26), para un valor fijo de λ se observa que un buen estimador de los multiplicadores de Lagrange sería λ + 1 ε Φ ( v ) . Por tanto, se puede plantear el siguiente algoritmo basado en el Lagrangiano aumentado para la resolución delos problemas de tipo (26).

Algoritmo 3 Método de Langragiano aumentado

Se procede con el siguiente método iterativo:

PASO 0: Se toma un punto inicial, ε 0 > 0 , δ > 0 y λ ( 0 ) p .

PASO 1: Se toma como u ( k ) la solución del problema de minimización sin restricciones definido por el funcional L ε k ( v , λ ( k ) ) .

PASO 2: Si | | v L ε k ( u ( k ) , λ ( k ) ) | | < δ , entonces se para. En caso contrario, se toma ε k + 1 = 1 / 1 0 ε k , u ( k + 1 ) = u ( k ) y λ ( k + 1 ) = λ ( k ) + 1 ε k Φ ( u ( k ) ) para volver al PASO 1.

Observación 6

Como se ha comentado en los anteriores métodos de penalización, δ es el parámetro de tolerancia, un valor muy pequeño que permite comprobar que la solución obtenida es factible o está próxima al conjunto admisible. Luego, si este criterio de parada no se cumple, se pasa a reducir el valor de ε , que en este caso se reduce multiplicando por 1/10. Lo ideal es que el decrecimiento del valor de ε , en cada iteración, sea paulatino y no muy pronunciado.

Una vez visto el Algoritmo 3, es necesario probar que efectivamente converge y que la deducción del método es correcta. Para ello, se introducen los siguientes resultados.

Teorema 7

Dado el problema (26), se supone que el funcional objetivo y las restricciones son continuas. Si u ( k ) es la solución global de minimizar sin restricciones L ε k ( v , λ ( k ) ) , donde { λ ( k ) } k es una sucesión acotada y { ε k } 0 con 0 < ε k + 1 < ε k . Entonces cualquier punto límite de la sucesión { u ( k ) } es un mínimo global del problema original (26).

Demostración. Sea u el límite de la sucesión { u ( k ) } k . Como u ( k ) se define como el mínimo global de L ε k ( v , λ ( k ) ) , entonces:

L ε k ( u ( k ) , λ ( k ) ) L ε k ( v , λ ( k ) ) , v n (29)

Tomando como χ el valor del funcional objetivo en el óptimo para el problema (26), entonces:

χ = mín v ∈S J ( v ) = mín v ∈S { J ( v ) + ( λ ( k ) ) T Φ ( v ) + 1 2 ε k | | Φ ( v ) | | 2 } = mín v ∈S L ε k ( v , λ ( k ) )

Por lo que, tomando el mínimo en el extremo derecho de la ecuación (29) en v ∈S , se obtiene:

L ε k ( u ( k ) , λ ( k ) ) = J ( u ( k ) ) + ( λ ( k ) ) T Φ ( u ( k ) ) + 1 2 ε k | | Φ ( u ( k ) ) | | 2 χ (30)

Ahora bien, la sucesión { λ ( k ) } k es acotada y tiene como límite λ . Tomando el límite superior en la ecuación (30) y usando la continuidad de las funciones J ( v ) y Φ ( v ) , se obtiene que:

J ( u ) + λ T Φ ( u ) + lim sup k 1 2 ε k | | Φ ( u ( k ) ) | | 2 χ

Como | | Φ ( u ( k ) ) | | 2 0 y ε k , se deduce que Φ ( u ( k ) ) 0 y por tanto Φ ( u ) = 0 . Por consiguiente, u es factible y además J ( u ) χ , por lo que u es el óptimo del problema (26).

Sin embargo, este resultado implica que el mínimo de la función Lagrangiano aumentado es calculado de forma exacta. Pero esto no sucede numéricamente, por lo que se necesita un resultado más fuerte. En este sentido, se introduce el Teorema 3.

Teorema 8

Sea u ( k ) tal que | | v L ε k ( v , λ ( k ) ) | | δ k , siendo la sucesión { λ ( k ) } k acotada, { ε k } k 0 decreciente y { δ k } k 0 . Entonces, si la sucesión de { u ( k ) } k u con u un punto regular, entonces u es un punto KKT para el problema (26) y, además, { λ ( k ) + 1 ε k Φ ( u ( k ) ) } k λ ,siendo λ los multiplicadores de Lagrange asociados a u .

Demostración. Sin pérdida de generalidad se supone que { u ( k ) } k u y se define, para todo k , λ ~ ( k ) = λ ( k ) + 1 / ε k Φ ( u ( k ) ) . Entonces se obtiene que:

(31)

Como u es regular, Φ ' ( u ) tiene rango p y Φ ' ( u ( k ) ) tiene rango p para todo k suficientemente grande. Sin pérdida de generalidad se asume que Φ ' ( u ( k ) ) tiene rango p para todo k . Entonces, multiplicando la ecuación (31) por ( Φ ' ( u ( k ) ) ( Φ ' ( u ( k ) ) ) T ) - 1 Φ ' ( u ( k ) ) se obtiene que:

λ ~ ( k ) = ( Φ ' ( u ( k ) ) ( Φ ' ( u ( k ) ) ) T ) - 1 Φ ' ( u ( k ) ) ∇J ( u ( k ) ) ( v L ε k ( u ( k ) , λ ( k ) ) ∇J ( u ( k ) ) ) .

Luego, por hipótesis, v L ε k ( u ( k ) , λ ( k ) ) 0 , entonces λ ~ ( k ) λ , donde:

λ = ( Φ ' ( u ( k ) ) ( Φ ' ( u ( k ) ) ) T ) - 1 Φ ' ( u ( k ) ) ∇J ( u ( k ) )

Nuevamente, como v L ε k ( u ( k ) , λ ( k ) ) 0 , entonces de la ecuación (31) se obtiene que

∇J ( u ( k ) ) + Φ ' ( u ( k ) ) T λ ~ ( k ) = 0

Ahora bien, como { λ ( k ) } k es acotada y λ ( k ) + 1 / ε k Φ ( u ( k ) ) λ , esto implica que { 1 / ε k Φ ( u ( k ) ) } es acotada. Pero como 1 / ε k + , se deduce que Φ ( u ) = 0 .

Por tanto, este resultado muestra que si el punto u , al que converge la sucesión creada por el método del Lagrangiano aumentado, es regular y los multiplicadores de Lagrange convergen a un valor finito, entonces, u es un punto KKT. Por consiguiente, un buen candidato a ser mínimo del problema (26).

Este método ha sido desarrollado para un problema del tipo (26), pero sería interesante desarrollarlo para resolver un problema general del tipo (1). Con este objetivo, se pretende reescribir el problema (1) de una forma equivalente en la que sólo haya restricciones de igualdad. Así pues, se puede introducir el problema,

(32)

donde z i , i = 1 , . . . , m , son variables adicionales. Esta transformación del problema original (1) en uno de este estilo de tipo (26), se puede consultar en [1, págs. 286-287].

De este modo, se puede aplicar el algoritmo del Lagrangiano aumentado al problema (32) para así obtener un punto KKT de dicho problema y, en consecuencia, del problema original (1). En esta línea, se plantea minimizar el Lagrangiano aumentado asociado al problema (32), que sería el siguiente:

L ε ( v , z , ε , ν ) = J ( v ) + ε T Φ ( v ) + 1 2 ε | | Φ ( v ) | | 2 + i = 1 m { ν i ( φ j ( v ) + z i 2 ) + 1 2 ε | φ i ( v ) + z i 2 | 2 } (33)

Para resolver el problema (1) se aplicará el Algoritmo 3, tomando como función Lagrangiano aumentado la (33). Además, a esta función se le pueden aplicar los resultados anteriores y, por tanto, si se conocen los valores exactos de los multiplicadores de Lagrange ( λ ) y de KKT ( μ ), se puede aplicar el Teorema 3, que nos permite concluir que bastarían un número finito de subproblemas sin restricciones que minimicen el funcional L ε ( v , z , λ , μ ) , para hallar la solución del problema (1).

Sin embargo, bastaría con resolver el problema de minimización respecto de la variable v n , debido a que la minimización referente a la variable auxiliar z m , se puede calcular analíticamente. Pues bien, minimizando en primer lugar L ε ( v , z , λ , μ ) respecto de z , es equivalente a minimizar:

mín w i 0 { μ i ( φ i ( v ) + w i ) + 1 2 ε ( φ i ( v ) + w i ) 2 } , i = 1 , . . . , m ,

que es una función cuadrática en w i . Su mínimo, teniendo en cuenta las restricciones, es w i * = máx { 0 , w i ~ } ,donde w ~ i es el mínimo del problema sin restricciones y, que por tanto, cumple que anula la derivada, es decir,

μ i + 1 / ε ( φ i ( v ) + w ~ i ) = 0

luego:

w i * = a { 0 , ( ε μ i + φ i ( v ) ) } (34)

Una vez hallado el mínimo respecto de la variable z m , se puede substituir la expresión (34) en la ecuación (33), de tal modo que, para los valores fijos de los multiplicadores de Lagrange y KKT, se tiene que minimizar respecto de v n la siguiente función,

L ε ( v , λ , μ ) = J ( v ) + λ T Φ ( v ) + 1 2 ε | | Φ ( v ) | | 2 + ε 2 i = 1 m { ( máx { 0 , μ i + 1 ε φ i ( v ) } ) 2 μ i 2 } (35)

que se considerará como la función Lagrangiano aumentado para el problema (1). Entonces, llegado este punto, con seguir el mismo procedimiento del Algoritmo 3, con el funcional (35), se obtendría numéricamente un punto KKT para el problema (1).

Claro que, en este caso, se saben los valores fijos de los multiplicadores, que se desconocen en la realidad. Para ello, se deben aproximar mediante un procedimiento iterativo. En el caso de los multiplicadores de Lagrange ya se dedujo anteriormente, pero teniendo en cuenta la conversión hecha para el caso de restricciones de desigualdad, haciendo el mismo procedimiento, se llega a que sus actualizaciones se corresponden respectivamente con los valores:

{ λ ( k ) + 1 ε k Φ ( u ( k ) ) } y máx { 0 , μ ( k ) + 1 ε k Ψ ( u ( k ) ) }

Hechas estas conclusiones, se puede reescribir el algoritmo del Lagrangiano aumentando para el caso del problema genérico (1). Entonces, se puede concluir el siguiente método:

Algoritmo 4 Método del Lagrangiano aumentado

Se procede con el siguiente método iterativo:

PASO 0: Se toma un punto inicial, ε 0 > 0 ., δ > 0 y λ ( 0 ) p .

PASO 1: Se toma como la solución del problema de minimización sin restricciones definido por el funcional L ε k ( v , λ ( k ) ) .

PASO 2: Si | | v L ε k ( u ( k ) , λ ( k ) ) | | < δ entonces se para. En caso contrario, se toma ε k + 1 = 1 / 1 0 ε k , u ( k + 1 ) = u ( k ) , λ ( k + 1 ) = λ ( k ) + 1 ε k Φ ( u ( k ) ) y μ ( k + 1 ) = máx { 0 , μ ( k ) + 1 ε k Ψ ( u ( k ) ) } para volver al PASO 1.

Observación 7

Debido a la construcción del método para el caso genérico, se pueden aplicar los mismos resultados que se mostraron con anterioridad. Esto es debido a que este algoritmo es una simple consecuencia de aplicar el Algoritmo 3 al problema (32).

Ejemplo 2

Para ejemplificar el método propuesto en el Algoritmo 3, se aplicará el código propuesto al problema

(36)

del que se obtiene los resultado mostrados en la Tabla 2.

Tabla 2:
Tabla 2: Resultados obtenidos con el método del Lagrangiano aumentado para el problema (36).
Tabla 2: Resultados obtenidos con el método del Lagrangiano aumentado para el problema (36).

Como se puede apreciar, según decrece el valor de ε k en cada iteración, las soluciones obtenidas se aproximan a la solución de forma pronunciada. Aunque el valor del funcional en las soluciones no decrezca en cada iteración, esto es debido a que los puntos obtenidos no son siempre factibles y se van aproximando al conjunto factible según se suceden las iteraciones.

4. Ejecuciones y pruebas prácticas

Con el objetivo de probar el funcionamiento de los anteriores métodos en la práctica, se mostrará un par de ejecuciones en problemas reales. Para ello, se programaron los Algoritmos 2.1, 2.2 y 3 en MatLab, donde se utilizó un algoritmo Quasi-Newton en la resolución de los subproblemas de optimizaciónsin restricciones (estos son los más empleados en este ámbito).

4.1. El problema de la geodésica

Un problema usual en las compañías aéreas es el cálculo de la menor trayectoria en el recorrido delos aviones. Intuitivamente dicha trayectoria es la línea recta. Sin embargo, al aproximarse la Tierra a una esfera, la trayectoria más corta es el arco de geodésica que une ambos puntos.

El objetivo de este primer problema es una versión de la situación planteada. Se considerará la esfera unidad y se querrá calcular la curva de longitud mínima que una dos puntos dados. La solución exacta es conocida y se puede consultar sus detalles en [6, Cap. V]. Para plantear el problema deforma numérica se desea hallar una discretización de dicha curva para aproximarla por la curva que une los puntos de la discretización solución. Así, se plantea el siguiente problema:

(37)

donde A M n × 3 es la matriz que en cada fila contiene las coordenadas de cada punto. Entonces, en la primera fila se tiene el punto de partida y, en la última, el punto de destino. Así, las variables son las coordenadas de los puntos incluidos en las filas interiores de la matriz. De esta forma, se tiene un problema 3 ( n 2 ) -dimensional con n 2 puntos que definen la discretización de la curva buscada.

Respecto a las restricciones, se tienen n 2 primeras restricciones de igualdad que aseguran que los puntos calculados pertenezcan a la esfera unidad. Finalmente, para asegurar que la discretización sea útil para visualizar la trayectoria, se fija una de las coordenadas de los puntos a un valor a elegir ( σ i ),dejando los demás libres.

En este caso se tomará como punto de partida ( 2 / 2 , 0 , 2 / 2 ) y como punto de destino ( 0 , 2 / 2 , 2 / 2 ) con 100 puntos de discretización. Con estas bases se han obtenido los siguientes resultados:

Tabla 3:
Tabla 3: Ejecuciones del problema de la geodésica
Tabla 3: Ejecuciones del problema de la geodésica

La solución se representa en la siguiente Figura 3, donde se muestra en rojo la geodésica obtenidanuméricamente y, en azul, el recorrido en línea recta (el intuitivo en un primer lugar).

La distancia del recorrido azul es de 1.1107 u.d, mientras que la distancia de la geodésica exacta es arccos(0.5) = 1.0472 u.d. Por tanto, dentro de las soluciones obtenidas, sería la del Lagrangiano aumentado la más aproximada. Por otra parte, el método de penalización exterior converge en dos iteraciones, lo que impide la convergencia de { ε k } k 0 y, por consiguiente, de que sea fiable el método. Por ello, sería conveniente aumentar el criterio de tolerancia para ver cómo se suceden las soluciones según siguiese decreciendo ε k en cada iteración. Aunque si se lleva a cabo este último consejo, entonces el tiempo de ejecución del método de penalización exterior se dispara en más de media hora, por lo que se descarta su utilidad en este caso. Finalmente, el método de penalización interior no se muestra en los recuadros de soluciones debido a que este método no se puede emplear en contextos donde aparezcan restricciones de igualdad.

Figura 3: Soluciones al problema de la geodésica
Figura 3
Figura 3: Soluciones al problema de la geodésica

4.2 El problema de la bancarrota

Otra de las aplicaciones de la optimización es en la Teoría de Juegos. Pues bien, en esta rama delas matemáticas es necesario resolver problemas de optimización con restricciones para obtener las soluciones requeridas. Un ejemplo de ello sería en la obtención de la solución de Nash en los juegos de negociación.

En [4] se pueden ver los detalles relativos a esta disciplina y uno de los problemas que se plantea es el problema de la bancarrota. En él se presenta una empresa en quiebra, cuyo capital es insuficiente para pagar las deudas contraídas. Además, la legislación del país obliga a que el capital de la empresa se reparta entre los acreedores, sin que ninguno de ellos reciba más de lo que se le adeuda y de un modo que sea aceptado por todos.

Entonces, se denota por n el número de acreedores, por E > 0 al capital de la empresa y por a a un vector de n componentes que contiene en la componente i-ésima los adeudamientos del i-ésimo acreedor. Así, en [4, págs. 105-112], se plantea como posible respuesta la solución de Nash, la cuál es la solución al problema:

(38)

Este se ha resuelto, en su versión equivalente a un problema de minimización, con los distintos algoritmos estudiados para el caso particular en el que n = 1 0 , E = 5 millones de euros, y el vector a de los adeudamientos es aquel que viene dado por

a =(1 0.8 0.5 1.1 0.7 0.2 0.9 1.5 0.1 1.2)

en millones de euros. Así pues, con una tolerancia común de 10-5, se han obtenido los resultado mostrados en la Tabla 4.

Tabla 4
Tabla 4: Ejecuciones del problema de la bancarrota
Tabla 4: Ejecuciones del problema de la bancarrota

Entonces, a pesar de que se trata de un problema aparentemente sencillo (con pocas dimensiones y restricciones lineales), el método de penalización exterior diverge debido a que la penalización 13 no es capaz de compensar el decrecimiento del funcional objetivo (motivo por el cuál el mínimo delos funcionales J ε ( v ) no es finito). El método de penalización interior no aporta una solución. Esto es debido a que, en la práctica, al resolver en MatLab los subproblemas sin restricciones, estos aportan soluciones no finitas o que se encuentran fuera del conjunto admisible. Así, el método de penalización interior conlleva serios problemas en la implementación del algoritmo en la práctica. Por consiguiente, es el Lagrangiano aumentado el único método estudiado que realmente aporta una solución al problema en un tiempo razonable.

5. Conclusiones

En base al trabajo desarrollado en el presente artículo, se obtienen las siguientes conclusiones:

Referencias

[1] Bertsekas D.P. Nonlinear Programming. 2nd. Athena Scientific. 1999.

[2] Boglárka G.-Tóth; Eligius M.T.Hendrix. Introduction to Nonlinear and Global Optimization.

[3] Bruguera M; Viaño, J.M. Lecciones de Métodos Numéricos. Volumen 4: Optimización. Andavira.2013.

[4] Casas B., Fiestras Janeiro G., García Jurado I., González Díaz J., Introducción a la Teoría deJuegos, USC editora, (2012)

[5] Clark, F.H. Optimization and Non-Smooth Analysis. Society for Industrial and AppliedMathematics. 1990.

[6] Hernández Cifre M.A., Pastor González J.A., Un curso de geometría diferencial. Teoría, problemas,soluciones y prácticas con ordenador, Ediciones Doce Calles S.L (2010)

[7] Hestenes, M.R, Multiplier and gradient methods. Journal of Optimization Theory and Applications4, pp. 303-320, 1969.

[8] Nocedal, J; Stephen J.Wright. Numerical Optimization. Springer. 2nd. 2006.

[9] Powell, M.J.D., A method for nonlinear constraints in minimization problems. Optimization,R. Fletcher (ed.) Academic Press, New York, NY, pp. 283-298, 1969.

[10] Rockafellar, R.T., Augmented Lagrange multiplier functions and duality in nonconvexprogramming. SIAM Journal on Control and Optimization 12, pp. 268-285, 1974. Colletionof articles dedicated to the memory of LucienW. Neustadt.

[11] Rockafellar, R.T., A dual approach to solving nonlinear programming problems y unconstrainedoptimization. Mathematical Programming 5, pp. 354-373, 1973.

[12] Rockafellar, R.T., The multiplier method of Hestenes and Powell applied to convex programming.Journal of Optimization Theory and Applications, 12, pp. 555-562, 1973.

[13] W. Sun; Y-X Yuan. Optimization Theory and Methods. Nonlinear Programming. Springer.2006.

HTML generado a partir de XML-JATS4R por