programación geométrica
TRANSCRIPT
UNIVERSIDAD NACIONAL DE INGENIERIA
FACULTAD DE CIENCIAS
ESCUELA PROFESIONAL DE MATEMATICA
PROGRAMACION GEOMETRICA
por
Naupay Gusukuma, Alvaro Miguel
Practicas
Pre Profesionales
en MATEMATICA
Mg. Echegaray Castillo, William Carlos
Asesor
Uni, 29 de Diciembre de 2014
Indice general
1. Antecedentes historicos 3
2. Programacion geometrica sin restricciones 5
2.1. Conocimientos previos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Primeros ejemplos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3. Programacion geometrica sin restricciones. . . . . . . . . . . . . . . . . . . 16
2.4. Ejemplos sin restricciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3. Progamacion geometrica con restricciones 26
3.1. Conocimientos previos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2. Ejemplo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3. Programacion geometrica con restricciones. . . . . . . . . . . . . . . . . . . 33
Bibliografıa 41
1
Agradecimientos
Quiero agradecer a mıs padres por apoyarme constantemente y a mi asesor por su apoyo
incondicional que dıa a dıa me guia a ser un mejor profesional.
2
Capıtulo 1
Antecedentes historicos
A Clarence Zener, Director de Ciencias en Westinghouse Electric en Pittsburgh,
Pennsylvania, USA, se le acredita como el padre de la Programacion Geometrica. En 1961,
publico un artıculo en el Proceedings del National Academy of Science sobre “A Mathema-
tical Aid in Optimizing Engineering Designs”, que es considerado como el primer artıculo
sobre programacion geometrica. Clarence Zener es mejor conocido en ingenierıa electrica
por el diodo Zener. Que mas tarde se asocio con Richard J. Duffin y Elmor L. Peterson del
Carnegie Institute of Technology (ahora Carnegie-Mellon University, USA) para escribir el
primer libro sobre programacion geometrica, llamado “Geometric Programming” en 1967.
Un reporte fue publicado en Agosto de 1966 por el profesor Douglas Wilde y el estudiante
de graduacion Ury Passey. El profesor Douglas Wilde del Stanford University y el profe-
sor Charles Beightler del University of Texas incluyeron un capıtulo sobre programacion
geometrica en el libro “Fundations of Optimization”.
Otros primeros libros por estos lıderes fueron “Engineering Design By Geometric Pro-
gramming” por Clarence Zener en 1971, “Applied Geometric Programming” por C.S.
Beightler y D.T. Phillips en 1976, y la segunda edicion del “Foundations of Optimiza-
tion” por C.S. Beightler, D.T. Phillips y D.Wilde en 1979. Muchos de las aplicaciones
iniciales fueron en el area del diseno de tranformadores cuando Clarence Zener trabajaba
para Westinghouse Electric en el area de ingenierıa quımica, que fue el area enfatizada
por Beightler y Wilde. Tambien es importante resaltar que muchos estudiantes de gra-
3
duacion jugaron un papel importante, a saber Elmor Peterson en el Carnegie Institute of
Technology y Ury Passy y Mordecai Avriel en el Stanford University.
4
Capıtulo 2
Programacion geometrica sin
restricciones
El nombre de programacion geometrica (P.G.) se debe a que se utiliza la generaliza-
cion de la desigualdad media aritmetica geometrica para resolver algunos problemas de
optimizacion.
2.1. Conocimientos previos.
Teorema 2.1.1. Sea f : C ⊂ Rn → R una funcion convexa donde C es un conjunto
convexo. Si λ1, λ2, . . . , λk son numeros no negativos con suma igual a 1 y si x1, x2, . . . , xk
son puntos de C, entonces
f
(
k∑
i=1
λixi
)
≤k∑
i=1
λif(xi) . (∗)
Si f es estrictamente convexa sobre C y si todos los λi’s son positivos, entonces la igualdad
en (∗) se cumple si y solo si todos los xi’s son iguales.
El nombre de Programacion Geometrica es debido a que esta tecnica utiliza variantes
de la desigualdad media aritmetica geometrica. A continuacion presentamos una de ellas.
Teorema 2.1.2. (Desigualdad Media Aritmetica-Geometrica o Desigualdad (A-
G)). Si x1, x2, . . . , xn son numeros reales positivos y si δ1, δ2, . . . , δn son numeros positivos
5
cuya suma es uno, entoncesn∏
i=1
(xi)δi ≤
n∑
i=1
δixi , (A-G)
con la igualdad en (A-G) si y solo si x1 = x2 = · · · = xn
El producto del lado izquierdo de A-G es llamada media geometrica de x1, x2, . . . , xn
con pesos δ1, δ2, . . . , δn mientras que la suma de la derecha de A-G es la media aritmetica
de x1, x2, . . . , xn con pesos δ1, δ2, . . . , δn.
La desigualdad (A-G) se puede demostrar usando la convexidad en la siguiente manera.
Primero, observe que la funcion f definida para x > 0 por
f(x) = − ln x
es estrictamente convexa ya que f ′′(x) =1
x2> 0. Consecuentemente, si x1, x2, . . . , xn y
δ1, δ2, . . . , δn son numeros positivos tales que
δ1 + δ2 + · · ·+ δn = 1
entonces (2.1.1) implica que
− ln
(
m∑
i=1
δixi
)
= f
(
m∑
i=1
δixi
)
≤n∑
i=1
δif(xi) = −n∑
i=1
δi ln xi
con la igualdad si y solo si todos los xi’s son iguales. La anterior desigualdad es equivalente
a
ln
(
n∑
i=1
δixi
)
≥n∑
i=1
ln(xδii ) = ln
(
n∏
i=1
xδii
)
.
Consecuentemente, como la funcion logarıtmo y exponencial son estrictamente creciente,
obtenemosn∑
i=1
δixi ≥n∏
i=1
(xi)δi
con la igualdad en esta desigualdad si y solo si todos los xi’s son iguales. �
Como veremos, la desigualdad (A-G) es muy adecuada para la solucion de una clase
considerable de problemas de optimizacion no lineal. Antes de intentar identificar esta clase
de problemas y formalizar el procedimiento de optimizacion, daremos algunos ejemplos en
los que se aplica (A-G) para proporcionar la solucion algunos problemas estandares de
maximos y mınimos del calculo.
6
2.2. Primeros ejemplos.
Ejemplo 2.2.1. Encontrar las dimensiones de una caja rectangular sin tapa con una area
fija de superficie S0 que tenga volumen maximo.
Solucion: Veamos la figura
x1
x2
x3
(x1, x2, x3)
Volumen = V = x1x2x3 .
Area de superficie = S0 = x1x2 + 2x1x3 + 2x2x3 .
Por consiguiente, nuestro trabajo es resolver el siguiente problema:
Maximizar V (x1, x2, x3) = x1x2x3 ,
sujeto a x1x2 + 2x1x3 + 2x2x3 = S0 ,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 .
En esta forma, al problema se le puede aplicar la desigualdad (A-G) de manera natural.
Observe que:
S0 = x1x2 + 2x1x3 + 2x2x3 = 3
(
x1x2 + 2x1x3 + 2x2x3
3
)
luego utilizando la desigualdad (A-G) tenemos
S0 = 3
(
x1x2 + 2x1x3 + 2x2x3
3
)
(A-G)
≥ 3((x1x2)1/3(2x1x3)
1/3(2x2x3)1/3)
= 3 · 41/3(x21x
22x
23)
1/3 = 3 · 41/3V 2/3
Notemos que el valor de V esta acotado y que esta cota (Maxima) es alcanzada cuando
hay igualdad en la desigualdad (A-G), esto es, supongamos que V es maximizado cuando
7
x1 = x∗1, x2 = x∗
2 y x3 = x∗3, de esto tendriamos que se debe cumplir y teniendo encuenta
el teorema 2.1.2
x∗1x
∗2 = 2x∗
1x∗3 = 2x∗
2x∗3 =
S0
3
resolviendo esto tenemos que las dimensiones son
x∗1 = x∗
2 =
√
S0
3, x∗
3 =1
2
√
S0
3,
y ademas el volumen maximo de la caja sera
V0 = x∗1x
∗2x
∗3 =
S3/20
2 · 33/2 .
�
Ejemplo 2.2.2. Encontrar las dimensiones de una caja rectangular sin tapa con volumen
fijo V0 que tiene la minima area de superficie.
Solucion: Apoyandonos en la figura del ejemplo anterior vemos que necesitamos resolver
el siguiente problema.
Minimizar S(x1, x2, x3) = x1x2 + 2x1x3 + 2x2x3 ,
sujeto a x1x2x3 = V0 ,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 .
procediendo exactamente como en el ejemplo anterior, obtenemos
S = x1x2 + 2x1x3 + 2x2x3 = 3
(
x1x2 + 2x1x3 + 2x2x3
3
)
(A-G)
≥ 3 · 41/3V 2/30 .
Por consiguiente, el valor de S es el menor cuando hay igualdad en la desigualdad (A-G),
esto es, S es minimizado cuando x1 = x∗1, x2 = x∗
2 y x3 = x∗3 de donde tenemos que (ver
teorema 2.1.2)
x∗1x
∗2 = 2x∗
1x∗3 = 2x∗
2x∗3 =
3 · 41/3V 2/30
3= 41/3V
2/30 .
Resolviendo esto tenemos que las dimensiones son
x∗1 = x∗
2 = 41/6V1/30 , x∗
3 =41/6V
1/30
2,
8
ademas el area mınima de la superficie es
S0 = x∗1x
∗2 + 2x∗
1x∗3 + 2x∗
2x∗3 = 3 · 4/3V 2/3
0 .
�
Ejemplo 2.2.3. Maximizar el volumen de una lata cilındrica de costo fijo c0 soles si el
costo del material, parte superior e inferior de la lata es c1 soles por metro cuadrado y el
costo del material, la parte lateral de la lata es de c2 soles por metro cuadrado.
Solucion: Si r es el radio y h es la altura de la lata en metros cuadrados, entocnes el
volumen de la lata es
r
h V (r, h) = πr2h
y el costo de la lata es
c0 = 2πr2c1 + 2πrhc2 .
Entonces vemos que necesitamos resolver el siguiente problema
Maximizar V (r, h) = πr2h ,
sujeto a 2πr2c1 + 2πrhc2 = c0 .
Ahora podemos proceder como en el ejemplo 2.2.1 , obtendremos
c0 = 2πr2c1 + 2πrhc2 = 4
(
πr2c12
+πrhc22
)
(A-G)
≥ 4(πr2c1)1/2(πrhc2)
1/2 = 4πr3/2h1/2(c1c2)1/2 .
9
Desafortunadamente, a diferencia de la situacion en el ejemplo 2.2.1, el termino en el lado
derecho de la desigualdad resultante no se reduce a un multiplo constante de una potencia
del volumen V, por lo que no se puede proceder como en el ejemplo 2.2.1. Lo que tenemos
que hacer es “dividir” c0 en una suma de terminos de tal manera que la aplicacion de
la desigualdad (A-G) produzca un multiplo constante de una potencia de V en el lado
derecho. Un poco de experimentacion mostrar que tal separacion puede llevarse a cabo
como sigue:
c0 = 2πr2c1 + πrhc2 + πrhc2 = 3
(
2πr2c1 + πrhc2 + πrhc23
)
(A-G)
≥ 3(2πr2c1)1/3(πrhc2)
1/3(πrhc2)1/3 = 3(2π)1/3(c1c
22)
1/3V 2/3 .
Ahora podemos ver que V es el mayor cuando hay igualdad en esta (A-G) desigualdad,
esto es, cuando
2πr2c1 = πrhc2 = πrhc2 =c03
,
resolviendo tenemos que
r =
√
c06πc1
, h =c0
3πc2
√
6πc1c0
,
luego el volumen maximo sera
Vmax =
√6
18π1/2× c
3/20
c1/21 c2
.
Sin embargo, queremos senalar un interesante analisis de los costos relacionados con nuestra
solucion del problema: Independientemente de los valores de c1 y c2, el optimo de las
dimensiones de la lata, asignar 13del coste total a la parte superior e inferior y 2
3del coste
total a la parte lateral. �
Ejemplo 2.2.4. Minimizar el costo de una lata cilındrica de volumen V0 fijo si el costo de
la parte superior e inferior de la lata es c1 soles por metro cuadrado y el costo de la parte
lateral de la lata es c2 soles por metro cuadrado.
10
Solucion: Si r y h denotan el radio y la altura de la lata, entonces nuestro problema puede
ser formulado como sigue:
Minimizar c(r, h) = 2πr2c1 + 2πrhc2 ,
sujeto a πr2h = V0 .
r ≥ 0, h ≥ 0
La misma “division” de la funcion de costo que usamos en el ejemplo anterior, en combi-
nacion con la desigualdad (A-G), nos da
c(r, h) = 2πr2c1 + πrhc2 + πrhc2 = 3
(
2πr2c1 + πrhc2 + πrhc23
)
A-G≥ 3(2π)1/3(c1c
22)
1/3V2/30 .
Por lo tanto, el costo es el menor cuando hay igualdad en la desigualdad (A-G), esto es,
cuando
2πr2c1 = πrhc2 = πrhc2 =3(2π)1/3(c1c
22)
1/3V2/30
3= (2π)1/3(c1c
22)
1/3V2/30 .
Vemos de nuevo que la asignacion de costo optimo es 13del costo de la parte superior e
inferior y 23del costo de los lados, independientemente de los valores de c1 y c2. Luego
resolviendo, las dimensiones del cilindro de costo mınimo son
r =c1/32 V
1/30
21/3π1/3c1/31
, h =22/3c
2/31 V
1/30
π1/3c2/32
,
luego el costo sera mınimo cuando la desigualdad (A-G) sea igualdad, por lo tanto
cmın = 3(2π)1/3(c1c22)
1/3V2/30
�
Los pares de ejemplos (2.2.1), (2.2.2) y (2.2.3), (2.2.4) proporcionan nuestros primeros
pasos de problemas duales. Los ejemplos anteriores tratan esencialmente con las mismas
funciones, excepto que la funcion objetivo en un problema es la funcion de restriccion
en el otro, y un problema es de minimizacion mientras que el otro es un problema de
maximizacion. El siguiente ejemplo proporciona una mayor ilustracion de la dualidad.
11
Ejemplo 2.2.5. Considere el siguiente problema:
Maximizar f(x1, x2, x3) = x1x22x3 ,
sujeto a x1 + x2 + x33 = k ,
donde k > 0 es fijo y x1, x2, x3 son numeros reales positivos.
(P)
Solucion: En este caso, el problema dual es
Minimizar g(x1, x2, x3) = x1 + x2 + x23 ,
sujeto a x1x22x3 = c ,
donde c > 0 es fijo y x1, x2, x3 son numeros reales positivos.
(D)
Desde luego, (P) es tambien el problema dual para (D).
Para resolver ambos problemas, necesitamos desdoblar x1 + x2 + x23 de tal manera que
la aplicacion de la desigualdad (A-G) produzca un multiplo constante de una potencia
adecuada de (x1x22x3) en el extremo inferior de la desigualdad. Esto se puede lograr como
sigue:
k = x1 + x2 + x23 =
x1
2+
x1
2+
x2
4+
x2
4+
x2
4+
x2
4+ x2
3
= 7
x1
2+
x1
2+
x2
4+
x2
4+
x2
4+
x2
4+ x2
3
7
(A-G)
≥ 7
(
1
2
)2/7(1
4
)4/7
(x1x22x3)
2/7 .
La igualdad se cumple en esta desigualdad precisamente cuando
x1
2=
x2
4= x2
3 =k
7.
Para maximizar x1x22x3 sujeto a la restriccion x1+x2+x2
3 = k, elegimos los valores optimos
x∗1, x
∗2, x
∗3 que fuerzan a la igualdad en la desigualdad (A-G) con el extremo superior de la
desigualdad igual a k, esto es,
x∗1 =
2k
7, x∗
2 =4k
7, x∗
3 =
√
k
7.
12
Para minimizar x1 + x2 + x23 sujeto a la restriccion x1x
22x3 = c, elegir los valores optimos
x∗1, x
∗2, x
∗3 que fuerzan a la igualdad en la desigualdad (A-G) con en el extremo inferior de
la desigualdad igual a(
12
)2/7 (14
)4/7c2/7, esto es,
x∗1 = 2
(
1
2
)2/7(1
4
)4/7
c2/7 , x∗2 = 2x∗
1 , x∗3 =
√
1
2x∗1 .
�
La desigualdad (A-G) puede tambien ser usada para resolver algunos problemas de
minimizacion sin restricciones. El truco es desdoblar la funcion objetivo de tal manera que
la aplicacion de la desigualdad (A-G) produzca una constante en el extremo inferior de la
desigualdad. Los siguientes ejemplos ilustran el procedimiento.
Ejemplo 2.2.6. Encontrar los valores de x > 0 que minimizan la funcion
f(x) = c1x3 +
c2x
,
donde c1, c2 son constantes positivas.
Solucion: Para resolver este problema con la desigualdad (A-G), procederemos como si-
gue:
f(x) = c1x3 +
c2x
= c1x3 +
1
3
c2x
+1
3
c2x
+1
3
c2x
= 4
c1x3 +
1
3
c2x
+1
3
c2x
+1
3
c2x
4
(A-G)
≥ 4
(
1
3
)3/4
c1/41 c
3/42 .
Para minimizar f , forzar la igualdad en (A-G). Esto equivale a la eleccion de x∗ de modo
que
c1(x∗)3 =
1
3
c2x∗
=
(
1
3
)3/4
c1/41 c
3/42 .
Esto da lugar a
x∗ =
(
1
3
)1/4
c−1/41 c
1/42
como el minimizador. �
13
En realidad, el ejemplo anterior podrıa haber sido facilmente resuelto como un problema
de calculo. El siguiente ejemplo no es facil de hacer con los metodos de calculo, pero es
bastante facil para una aplicacion de la desigualdad (A-G).
Ejemplo 2.2.7. Encontrar los minimizadores de
f(x1, x2) = 4x1 +x1
x22
+4x2
x1
para x1 > 0, x2 > 0.
Solucion: Este problema puede resolverse por la desigualdad (A-G) de la siguiente ma-
nera:
f(x1, x2) = 4
4x1 +x1
x22
+2x2
x1+
2x2
x1
4
(A-G)
≥ 4(41/4)(22/4)
(
x21x
22
x22x
21
)1/4
= 8 .
Si forzamos a la igualdad en la desigualdad anterior, vemos que los valores x∗1 y x∗
2 que
minimizan f(x1, x2) son dados por
4x∗1 =
x∗1
(x∗2)
2=
2x∗2
x∗1
= 2 ,
esto es,
x∗1 =
1
2, x∗
2 =1
2,
y que el mınimo valor es 8. �
Note que este ejemplo no es facil de atacar con los metodos del calculo. De hecho, los
puntos crıticos son soluciones del sistema
∂f
∂x1
= 4 +1
x22
− 4x2
x21
= 0 ,
∂f
∂x2= −2x1
x32
+4
x1= 0 .
14
Resolver este sistema por medios no faciles y ademas examinar el Hessiano
8x2
x31
− 2
x32
− 4
x21
− 2
x32
− 4
x21
6x1
x42
esto es una perspectiva ¡aterradora!.
Los ejemplos discutidos en esta seccion ciertamente indican que la desigualdad (A-G)
puede ser una herramienta importante para la solucion de problemas de optimizacion. La
unica parte de nuestro planteamiento, que no estaba completamente claro era “dividir” o
“desdoblar” la funcion apropiadamente en el extremo superior de la desigualdad (A-G).
Hicimos esto facilmente por inspeccion en los ejemplos considerados aquı porque las fun-
ciones que consideramos envolvian tres o menos variables. Sin embargo, es aparente que el
proceso de dividir (desdoblar) puede ser difıcil de aplicar para funciones con mas variables.
El otro punto en nuestro enfoque que es un poco nebuloso por el momento es el alcance del
metodo, es decir, todavıa tenemos que identificar con precision los tipos de problemas de
optimizacion que son tratables vıa la desigualdad (A-G). Abordaremos estas dos cuestiones
en la siguiente seccion. En particular, vamos a desarrollar un marco formal y un procedi-
miento sistematico llamado programacion geometrica aplicando la desigualdad (A-G) a los
problemas de optimizacion. En programacion geometrica, el proceso de dividir (desdoblar)
que fue desarrollado por inspeccion en los ejemplos de esta seccion es sustituido por la so-
lucion de un cierto sistema de ecuaciones lineales determinado por el problema en cuestion.
Esta sustitucion da lugar a un procedimiento sistematico y practico que se aplicara ruti-
nariamente a una amplia clase de problemas. Sin embargo, la esencia de la programacion
geometrica se encuentra en las soluciones informales de los ejemplos considerados en esta
seccion, el resto es solo una cuestion de hacer el procedimiento sistematico y rutinario.
15
2.3. Programacion geometrica sin restricciones.
Esta seccion presenta un procedimiento sistematico para manipular problemas de pro-
gramacion geometrica sin restricciones. Como demostramos en la seccion anterior, es con
frecuencia posible resolver estos problemas directamente de la desigualdad (A-G) y por
inspeccion. Sin embargo, algunos problemas son muy complicados para hacerlos de esta
manera, y el procedimiento que estamos apunto de discutir entonces viene al rescate.
Tambien tenemos otro objetivo en mente para esta seccion. Se habra notado ya, que
nunca probamos que siempre es posible forzar a la igualdad en la desigualdad (A-G) en los
ejemplos de la seccion anterior. Una vez que hallamos establecido nuestro procedimiento
sistematico para problemas de programacion geometrica sin restricciones, probaremos que
siempre es posible forzar a la igualdad.
Definicion 2.3.1. Una funcion g definida para todo
t = (t1, . . . , tm) ∈ Rm con tj > 0 para todo j = 1, . . . , m es
llamado posinomial si g(t) es de la forma
g(t) =
n∑
i=1
ci
m∏
j=1
(tj)αij ,
donde los ci’s son constantes positivas y los αij son exponentes
reales arbitrarios.
Ası pues, un posinomial es una combinacion lineal con coeficientes no negativos de terminos
que son productos de potencias reales de variables no negativas t1, . . . , tm. Por ejemplo,
g(t1, t2) = 3t−11 t
√2
2 + t31t1/22 +
√3t
−1/21
es un posinomial definido sobre en interior de el primer cuadrante en R2.
El objetivo de la programacion geometrica sin restricciones es resolver el siguiente pro-
16
grama geometrico primal :
Minimizar el posinomial g(t) =
n∑
i=1
ci
m∏
j=1
tαij
j , (GP)
donde t1 > 0, . . . , tm > 0 .
Por una solucion del (GP) sencillamente nos referimos a un minimizador global t∗ para g
sobre el conjunto de vectores t en Rm con componentes positivas.
Comenzaremos nuestro ataque sobre el programa (GP) observando que g puede ser
reescrito como
g(t) =n∑
i=1
δi
ci
m∏
j=1
tαij
j
δi
,
donde cada δi se supone que es un numero positivo (Condicion de Positividad). Si a esto
anadimos la restriccion de que
n∑
i=1
δi = 1 , (Condicion de Normalidad)
podemos aplicar la desigualdad (A-G) a esta nueva expresion de g para obtener
g(t)(A-G)
≥n∏
i=1
ci
m∏
j=1
tαij
j
δi
δi
=
n∏
i=1
(
ciδi
)δi(
n∏
i=1
m∏
j=1
tαijδij
)
=n∏
i=1
(
ciδi
)δi m∏
j=1
t∑
i αijδij
Por lo tanto, si se impone la restriccion adicional de que
n∑
i=1
αijδj = 0 ; j = 1, . . . , m , (Condicion de Ortogonalidad)
17
entonces la desigualdad anterior nos da el siguiente resultado
g(t) ≥n∏
i=1
(
ciδi
)δi
.
Ası, si definimos
v(δ) =
n∏
i=1
(
ciδi
)δi
entonces los calculos anteriores muestran que
g(t) ≥ v(δ) (Desigualdad Primal-Dual)
para cualquier t ∈ Rm con componentes positivas y cualquier δ ∈ R
n que satisface las
Condiciones de Positividad, Normalidad y Ortogonalidad.
Estas consideraciones nos lleva a considerar el siguiente programa geometrico dual :
Maximizar v(δ) =n∏
i=1
(
ciδi
)δi
, (PGD)
sujeto a δ1 > 0, . . . , δn > 0 , (Condicion de Positividad)
n∑
i=1
δi = 1 , (Condicion de Normalidad)
∀j :n∑
i=1
αijδi = 0 , (Condicion de Ortogonalidad)
Un vector δ ∈ Rn que satisface las Condiciones de Positividad, Normalidad y Ortogonalidad
es un vector factible para el (PGD). El programa dual es consistente si el conjunto de
vectores factibles para el (PGD) es no vacio. Finalmente, por una solucion para el progama
dual (PGD) nos referimos a un vector δ∗ ∈ Rn que es un maximizador global para v(δ)
sobre el conjunto de vectores factibles para el (PGD).
Note que si t∗ es una solucion al programa primal (GP) y si δ∗ es una solucion al
programa dual (PGD), entonces
g(t∗) ≥ v(δ∗)
por la desigualdad Primal-Dual. A continuacion se muestra, entre otras cosas, que en
realidad g(t∗) es igual a v(δ∗) y que de esta igualdad genera un procedimiento para calcular
las soluciones del programa (GP) y (PGD) cuando estos programas tienen soluciones.
18
Teorema 2.3.1. Si t∗ = (t∗1, . . . , t∗m) es una solucion del programa geometrico primal (GP),
entonces el correspondiente programa geometrico dual (PGD) es consistente. Ademas, el
vector δ∗ = (δ∗1 , . . . , δ∗n) definido por
δ∗i =ui(t
∗)
g(t∗), i = 1, . . . , n
(donde ui(t) = citαij
1 · · · tαimm es el i’esimo termino de g) es una solucion para el (PGD) y
la igualdad se cumple en la Desigualdad Primal-Dual, esto es,
g(t∗) = v(δ∗) .
Demostracion: Un termino tıpico de g en (GP) es
ui(t) = citαi1
1 · · · tαimm .
La derivada parcial de ui(t) respecto de tj tiene un efecto muy simple sobre ui(t), simple-
mente se multiplica ui(t) por αij y se reduce el exponente de tj en 1. Esto significa que la
siguiente ecuacion se cumple:
tj∂ui
∂tj= αijui .
Ya que t∗ = (t∗1, . . . , t∗m) es un minimizador para g en (GP), se deduce que
0 =∂g
∂tj(t∗) =
n∑
i=1
∂ui
∂tj(t∗) , j = 1, 2, . . . , m .
Pero entonces de las observaciones anteriores tenemos que
0 =
n∑
i=1
αijui(t∗) , j = 1, 2, . . . , m .
Ya que g(t∗) > 0 (ver (GP)), podemos dividir en ambos lados de la ultima ecuacion por
g(t∗) obteniendo
0 =
n∑
i=1
αij
(
ui(t∗)
g(t∗)
)
, j = 1, 2, . . . , m .
Consecuentemente, si definimos
δ∗i =ui(t
∗)
g(t∗), i = 1, . . . , n ,
19
entonces δ∗ = (δ∗1, . . . , δ∗n) satisfacen la Condicion de Ortogonalidad para el programa dual
(PGD). Por otra parte, δ∗i > 0 para i = 1, . . . , n por lo que la Condicion de Positividad es
satisfecha. Finalmente,n∑
i=1
δ∗i =
n∑
i=1
(
ui(t∗)
g(t∗)
)
=g(t∗)
g(t∗)= 1
por lo que la Condicion de Normalidad se cumple. Concluimos que el vector δ∗ es factible
para el programa dual, por lo que el programa dual (PGD) es consistente. Ademas
g(t∗) = g(t∗)δ∗
1+···+δ∗n = (g(t∗))δ
∗
1 · · · (g(t∗))δ∗n
=
(
u1(t∗)
δ∗1
)δ∗1
· · ·(
un(t∗)
δ∗n
)δ∗n
=
(
c1δ∗1
)δ∗1
· · ·(
cnδ∗n
)δ∗n
= v(δ∗) ,
asi que se cumple la igualdad en la desigualdad Primal-Dual. Esto implica que δ∗ es una
solucion del programa dual (PGD). Puesto que
δ∗i =ui(t
∗)
g(t∗), i = 1, 2, . . . , n ,
la prueba esta completa. �
Con el teorema anterior en manos, podemos formular el siguiente metodo para un
programa geometrico.
El procedimiento de Programacion Geometrica. Dado un programa geometrico
primal
Minimizar el posinomial g(t) =n∑
i=1
ui(t) , (PD)
donde ui(t) = citαi1
1 . . . tαim
m y ti > 0, . . . , tm > 0; ci > 0
procedemos como sigue:
Paso 1. Calcular el conjunto F de vectores facibles para el programa geometrico dual
20
(PGD), es decir, el conjunto de todos los vectores δ en Rn tales que
δ1 > 0, . . . , δn > 0 , (Condicion de Positivadad)
n∑
i=1
δi = 1 , (Condicion de Normalidad)
n∑
i=1
αijδi = 0 ; j = 1, . . . , m (Condicion de Ortogonalidad)
Paso 2. Si el conjunto F de vectores factibles para el (PGD):
(a) Es vacio, entonces parar. El programa dado (GP) no tiene solucion en este
caso;
(b) Consta de un solo vector δ∗, entonces δ∗ es un solucion del (PGD). Vaya al
Paso 4;
(c) Consta de mas de un vector, entonces vaya al Paso 3.
Paso 3. Encuentre un vector δ∗ que es un maximizador global para la funcion dual
v(δ) =n∏
i=1
(
ciδi
)δi
sobre el conjunto F de vectores factibles para el (PGD). Entonces δ∗ es una
solucion del (PGD). Vaya al Paso 4.
Paso 4. Dado una solucion δ∗ del (PGD), una solucion t∗ del programa primal es obtenido
de resolver las ecuaciones
δ∗1 =ui(t
∗)
v(δ∗), i = 1, . . . , n ,
para t∗1, . . . , t∗m. El valor mınimo g(t∗) de g es igual al valor maximo v(δ∗) para la
funcion dual v.
Comentarios.
(1) Para encontrar el conjunto F de vectores factibles para el programa dual, primero re-
solver el sistema lineal de ecuaciones que consiste de las Condiciones de Ortogonalidad
y Normalidad, y luego imponer la Condicion de Positividad en la solucion resultante.
21
(2) La instruccion en el Paso 2(a) de que el (GP) no tiene soluciones si el conjunto F
de vectores factibles de el programa dual es vacio es consecuencia del Teorema 2.3.1.
Porque si (GP) tiene un solucion t∗, entonces el Teorema 2.3.1 afirma que el programa
dual es consistente, es decir, F es no vacio.
(3) La alternativa “difıcil” es el Paso 2(c) , porque estamos obligados a encontrar un
maximizador δ∗ para v en el conjunto F de vectores factibles para (PGD) por algun
medio.
(4) La solucion del sistema de ecuaciones prescrito en la Paso 4 parece complicado porque
las ecuaciones no son lineales en la variables t∗1, . . . , t∗m. Sin embargo, debido
ui(t∗) = ci(t
∗1)
αi1 · · · (t∗m)αim ,
podemos obtener t∗1, . . . , t∗m resolviendo el sistema de ecuaciones lineales
αi1 log t∗1 + · · ·+ αim log t∗m = log δ∗i − log ci + log v(δ∗) , i = 1, . . . , n .
Por lo tanto, el procedimiento sistematico para la programacion geometrica que fue
descrito anteriormente es un proceso extremadamente lineal.
(5) La i -esima componente δ∗i de la solucion δ∗ del programa dual (PGD) especifica el
aporte realtivo del i -esimo termino ui(t∗) al valor mınimo g(t∗) del (GP).
2.4. Ejemplos sin restricciones.
Ejemplo 2.4.1. Sea c1, c2, c3, c4 y V constantes positivas. Considere el siguiente programa
geometrico:
Minimizar g(t) =c1V
t1t2t3+ 2c2t2t3 + 2c3t1t3 + c4t1t2 ,
donde t1 > 0, t2 > 0, t3 > 0 .
22
Solucion: Aquı el problema dual es
Maximizar V (δ) =
(
c1V
δ1
)δ1 (2c2δ2
)δ2 (2c3δ3
)δ3 (2c4δ4
)δ4
,
sujeto a δ1 + δ2 + δ3 + δ4 = 1 (Condicion de Normalidad),
δi > 0, 1 = 1, 2, 3, 4 (Condicion de Positividad),
−δ1 + + δ3 + δ4 = 0
−δ1 + δ2 + δ4 = 0
−δ1 + δ2 + δ3 = 0
Condicion de
Ortogonalidad
.
Si aplicamos el Paso 1 del precedimiento mostrado en seccion anterior, encontraremos que
el vector
δ∗ =
(
2
5,1
5,1
5,1
5
)
es el unico vector factible para el dual, por lo que seguimos la alternativa (b) en el Paso 3.
Por consiguiente, podemos encontrar las soluciones t∗1, t∗2, t
∗3 resolviendo el sistema.
c1V
t∗1t∗2t
∗3
= δ∗1v(δ∗) =
2
5v(δ∗) ,
2c2t∗2t
∗3 = δ∗2v(δ
∗) =1
5v(δ∗) ,
2c3t∗1t
∗3 = δ∗3v(δ
∗) =1
5v(δ∗) ,
c4t∗1t
∗2 = δ∗4v(δ
∗) =1
5v(δ∗) .
Omitiremos el resto de los detalles del calculo. Note que las contribuciones relativas de los
cuatro terminos en g(t∗) son 25, 15, 15, 15independiente de los valores de c1, c2, c3, c4. �
Ejemplo 2.4.2. Considere el programa geometrico
Minimizar g(t1, t2) =2
t1t2+ t1t2 + t1 ,
donde t1 > 0, t2 > 0 .
23
Solucion: El programa dual es
Maximizar v(δ) =
(
2
δ1
)δ1 ( 1
δ2
)δ2 ( 1
δ3
)δ3
,
sujeto a δ1, δ2, δ3 > 0 ,
δ1 + δ2 + δ3 = 1 ,
−δ1 + δ2 + δ3 = 0 ,
−δ1 + δ2 = 0 .
Resolviendoe stas ecuaciones, encontramos que la unica solucion es δ1 =12, δ2 =
12, y δ3 = 0.
Estos vector no es factible para el dual (porque δ3 = 0) y por lo tanto no hay vectores
factibles para el dual. Consecuentemente, la alternativa (a) en el Paso 2 nos dice que el
programa dado no tiene solucion. �
Ejemplo 2.4.3. Considere el programa geometrico
Minimizar g(t1, t2) =1
t1t2+ t1t2 + t1 + t2 ,
donde t1 > 0, t2 > 0 .
Solucion: El programa dual es
Maximizar v(δ) =
(
1
δ1
)δ1 ( 1
δ2
)δ2 ( 1
δ3
)δ3 ( 1
δ4
)δ4
,
sujeto a δ1, δ2, δ3, δ4 > 0 ,
δ1 + δ2 + δ3 + δ4 = 1 ,
−δ1 + δ2 + δ3 = 0 ,
−δ1 + δ2 + δ4 = 0 .
24
Un poco de trabajo muestra que este sistema es equivalente al siguiente:
δ1 = δ1 > 0 ,
δ2 = 3δ1 − 1 > 0 ,
δ3 = 1− 2δ1 > 0 ,
δ4 = 1− 2δ1 > 0 ,
y estas desigualdades restringen δ1 al rango 13< δ1 < 1
2. Ası, la maximizacion de v(δ)
equivale a la maximizacion de
f(s) =
(
1
2
)s(1
1− 2s
)1−2s(1
1− 2s
)1−2s(1
3s− 1
)3s−1
en el intervalo 13< s < 1
2. Tomando logaritmos, maximizamos
ln f(s) = −s ln 2− 2(1− 2s) ln(1− 2s)− (3s− 1) ln(3s− 1) ,
que es posible resolver por metodos iterativos sin ningun problema. �
25
Capıtulo 3
Progamacion geometrica con
restricciones
3.1. Conocimientos previos.
Teorema 3.1.1 (Desigualdad Media Aritmetica-Geometrica Extendida). Suponga que
x1, . . . , xn son numeros positivos. Si δ1, . . . , δn son numeros que son todos positivos o todos
ceros y si λ = δ1 + · · ·+ δn, entonces
(
n∑
i=1
xi
)λ
≥ λλ
(
n∏
i=1
(
xi
δi
)δi)
bajo la convencion 00 = 1 y (xi/0)0 = 1.
La igualdad se cumple en esta desigualdad si y solo si δ1 = δ2 = · · · = δn = 0 o
xi =δiλ
(
n∑
j=1
xj
)
para i = 1, . . . , n.
Demostracion: Suponga primero que todos los δi’s son numeros positivos. Note que δi/λ
es positivo para i = 1, 2, . . . , n y que
δ1λ
+δ2λ
+ · · ·+ δnλ
= 1 .
26
Consequentemente, si aplicamos la desidgualdad Media Aritmetica Geometrica (A-G) Teo-
rema 1.2.1 a (λxi)/δi y δi/λ para i = 1, 2, . . . , n, obtenemos
n∑
i=1
xi =
n∑
i=1
(
δiλ
)(
λxi
δi
)
≥n∏
i=1
(
λxi
δi
)δi/λ
,
cumpliendose la igualdad si y solo si
λx1
δ1=
λx2
δ2= · · · = λxn
δn.
Pero luego(
n∑
i=1
xi
)λ
≥n∏
i=1
(
λxi
δi
)δi
= λλn∏
i=1
(
xi
δi
)δi
.
Por otra parte, si λxi/δi = M para i = 1, 2, . . . , n, entonces
n∑
i=2
xi =
n∑
i=1
Mδiλ
=M
λ
n∑
i=1
δi = M ,
luego con λxi
δi= M tenemos que
xi =Mδiλ
=δiλ
(
n∑
i=1
xi
)
,
por lo tanto la condicion de igualdad se cumple.
Finalmente, note que si todos los δi’s son iguales a cero, entonces ambos lados de la
desigualdad prescrita son iguales a 1. Esto completa la prueba. �
La siguiente definicion describe el marco de la programacion geometrica con restriccio-
nes.
27
Definicion 3.1.1. Suponga que g0, g1, . . . , gk son posinomiales
con m-variables reales positivas t = (t1, t2, . . . , tm). Entonces el
programa
(PG)
Minimizar g0(t)
s.a. g1(t) ≤ 1, g2(t) ≤ 1, . . . , gk(t) ≤ 1 ,
donde t1 > 0, t2 > 0, . . . , tm > 0
es llamado un programa geometrico con restricciones.
La siguiente definicion define el marco de la programacion convexa.
Definicion 3.1.2. Suponga que f, g1, . . . , gm son funcioines
real-valuadas definidas sobre un subconjunto C de Rn.
(PC)
Minimizar f
s.a. g1(x) ≤ 0, g2(x) ≤ 0, . . . , gm(x) ≤ 0 ,
donde x ∈ C ⊂ Rn .
La funcion f es llamada la funcion objetivo de (PC) y las desigualdades de funciones
g1(x) ≤ 0, . . . , gm(x) ≤ 0 son llamadas las restricciones (desigualdades) para (PC). Un
punto x ∈ C que satisface todas las restricciones del programa (PC) es llamado un punto
factible para (PC), y el conjunto F de todos los puntos factibles para (PC) es llamado region
de factibilidad para (PC). Si la region factible para (PC) es no vacia, diremos que (PC)
es consistente. Si hay un punto factible x para (PC) tal que gi(x) < 0 para i = 1, . . . , m,
entonces (PC) es superconsistente y el punto x es llamado un punto de Slater para (PC).
Teorema 3.1.2 (Karush-Kuhn-Tucker(Forma de Gradiente)). Suponga que (PC)
es un programa convexo superconsistente tal que la funcion objetivo f y las funciones de
restriccion g1, . . . , gm tienen la primera de derivada continua en el conjunto C para (PC).
28
Si x∗ es factible para (PC) y es un punto interior de C, entonces x∗ es una solucion de
(PC) si y solo si existe un λ∗ ∈ Rm tal que:
(1) λ∗i ≥ 0 para i = 1, 2, . . . , m;
(2) λ∗i gi(x
∗) = 0 para i = 1, 2, . . . , m;
(3) ∇f(x∗) +
m∑
i=1
λ∗i∇gi(x
∗) = 0.
Teorema 3.1.3.
(a) Si f1, . . . , fk son funciones convexas en el conjunto convexo C de Rn, entonces
f(x) = f1(x) + f2(x) + · · ·+ fk(x)
es convexa. Ademas, si al menos uno de los fi es estrictamente convexa en C, entonces
la suma f(x) es estrictamente convexa.
(b) Si f es convexa (estrictamente convexa) en el conjunto convexo C de Rn y si α es un
numero positivo, entonces αf es convexo (estrictamente convexo) en C.
(c) Si f es una funcion convexa (estrictamente convexa) definida en un conjunto convexo
C de Rn, y si g es una funcion convexa creciente (estrictamente creciente) definida en
el rango de f de R, entonces la funcion composicion g ◦ f es convexa (estrictamente
convexa) en C.
3.2. Ejemplo.
Ejemplo 3.2.1. Considere el siguiente programa
Minimizar40
t1t2t3+ 40t2t3
sujeto a 2t1t3 + t1t2 ≤ 4 ,
donde t1 > 0, t2 > 0, t3 > 0 .
29
Solucion: Si dividimos la desigualdad de restriccion por 4, obtenemos un programa
geometrico de la forma 3.1.1 con
g0(t1, t2, t3) =40
t1t2t3+ 40t2t3 ,
g1(t1, t2, t3) =t1t32
+t1t24
.
Ahora procedemos como sigue: Para cualquier λ > 0, (g1(t))λ ≤ 1 ası que para cualesquiera
δ1 > 0, δ2 > 0, tenemos
g0(t) ≥ g0(t)(g1(t))λ =
(
40
t1t2t3+ 40t2t3
)
(g1(t))λ
=
(
δ1
(
40
δ1t1t2t3
)
+ δ2
(
40t2t3δ2
))
(g1(t))λ .
Si ahora imponemos la restriccion de que δ1 + δ2 = 1 y aplicamos la Desigualdad Media
Aritmetica-Geometrica Teorema 2.1.2, obtenemos
g0(t) ≥(
(
40
δ1t1t2t3
)δ1 (40t2t3δ2
)δ2)
(g1(t))λ
=
(
(
40
δ1
)δ1 (40
δ2
)δ2
(t1)−δ1(t2)
(−δ1+δ2)(t3)(−δ1+δ2)
)
(g1(t))λ .
Luego, nos enfocamos en el factor (g1(t))λ en la ultima expresion y aplicamos la Desigualdad
Media Aritmetica Geometrica Extendida Teorema 3.1.1, luego tenemos
g1(t)λ =
(
t1t32
+t1t24
)λ
≥ λλ
(
(
t1t32δ3
)δ3 ( t1t24δ4
)δ4)
= λλ
(
(
1
2δ3
)δ3 ( 1
4δ4
)δ4)
t(δ3+δ4)1 tδ42 t
δ33 ,
siempre que λ = δ3 + δ4. Si combinamos las conclusiones de los calculos anteriores, vemos
que
g0(t) ≥(
(
40
δ1
)δ1 (40
δ2
)δ2 ( 1
2δ3
)δ3 ( 1
4δ4
)δ4)
(δ3 + δ4)δ3+δ4
= v(δ1, δ2, δ3, δ4)
30
siempre que
δ1 + δ2 = 1 ,
δ3 + δ4 = λ ,
−δ1 + δ3 + δ4 = 0 ,
−δ1 + δ2 + δ4 = 0 ,
−δ1 + δ2 + δ3 = 0 ,
δ1 > 0, δ2 > 0, δ3 > 0, δ4 > 0 .
(Las tres ultimas ecuaciones resultan de igualar los exponentes de t1, t2, t3 a cero.) Este
sistema tiene la solucion unica
δ∗1 =2
3, δ∗2 =
1
3, δ∗3 =
1
3, δ∗4 =
1
3,
y el correspondiente valor de v(δ1, δ2, δ3, δ4) es
v
(
2
3,1
3,1
3,1
3
)
= 60 .
Ası, 60 es una cota inferior para el valor de g0 sujeto a la restriccion g1(t) ≤ 1. Encon-
trar el valor mınimo de g0 y un minimizador t∗ = (t∗1, t∗2, t
∗3) que conduce a este valor
mınimo, buscamos esos valores t∗1, t∗2, t
∗3 que fuerzan a la igualdad en las Desigualdades
Media-Geometrica de 2.1.2 y 3.1.1 y simultaneamente en la restriccion g1(t) ≤ 1. Si po-
demos encontrar tales t∗1, t∗2, t
∗3, entonces sabremos que el mınimo de g0(t) sujeto a esta
restriccion es actualmente 60 y que t∗ = (t∗1, t∗2, t
∗3) es el punto minimizador.
Las condiciones de igualdad para las Desigualdades Media Geometrica Aritmetica 2.1.2
y 3.1.1 implican que40
23t∗1t
∗2t
∗3
=40t∗2t
∗3
13
= 60 ,
t∗1t∗3
23
=t∗1t
∗2
43
= K .
(¿Por que los dos terminos en la primera ecuacion es igual a 60?) Ya que δ∗3, δ∗4 son positivos,
la igualdad se debe tener en la restriccion g1(t) ≤ 1 de modo que
1 = δ3K + δ4K =2
3K ,
31
y por lo tanto K = 32. Estas consideraciones nos llevan al siguiente sistema de ecuaciones:
t∗1t∗2t
∗3 = 1 ,
2t∗2t∗3 = 1 ,
t∗1t∗3 = 1 ,
t∗1t∗2 = 2 .
Podemos convertir este sistema a un sistema de ecuaciones lineales en log t∗1, log t∗2, log t
∗3
tomando logaritmos
log t∗1 + log t∗2 + log t∗3 = 0 ,
log t∗2 + log t∗3 = − log 2 ,
log t∗1 + log t∗3 = 0 ,
log t∗1 + log t∗2 = log 2 .
Resolviendo este ultimo sistema tenemos que la unica solucion es t∗1 = 2, t∗2 = 1 y t∗3 =12,
que son los valores que minimizan el problema inicial. �
Comentarios sobre el problema anterior: Resolvimos el programa geometrico del
ejemplo anterior aplicando la Desigualdad Media Geometrica Aritmetica 2.1.2 a la funcion
obgetivo g0(t) y la Desigualdad Media Geometrica Aritmetica Extendida 3.1.1 a la restric-
cion g1(t) ≤ 1. ¿Que pasarıa si hubieramos aplicado 2.1.2 a las dos funciones?. Esto habrıa
resultado en el siguiente sistema de ecuaciones de δ1, δ2, δ3, δ4:
δ1 + δ2 = 1 ,
δ3 + δ4 = 1 ,
−δ1 + δ3 + δ4 = 0 ,
−δ1 + δ2 + δ4 = 0 ,
−δ1 + δ2 + δ3 = 0 .
Este es un sistema de ecuaciones inconsistente. En otra palabras, si usamos 2.1.2 en las
funciones objetivo y de restriccion, y si a continuacion anadimos las ecuacionies resultan-
32
tes de establecer los exponentes de t1, t2, t3 iguales a cero, se han impuesto demasiadas
restricciones sobre δ1, δ2, δ3, δ4.
Con la ayuda del Teorema de Karush-Kuhn-Tucker, podemos mostrar que la tecnica
aplicada al problema anterior funciona realmente, en general.
3.3. Programacion geometrica con restricciones.
Ahora desarrollaremos la tecnica mostradad en la seccion anterior en el contexto general
de la programacion geometrica con restricciones (PG) definido en 3.1.1.
Debido a que cada uno de los k + 1 posinomiales en el programa geometrico con res-
triccioines estandar (PG) Definicion 3.1.1 puede consistir de varios terminos, tenemos que
organizar todos los terminos de manera que la notacion resultante sea simple y descriptiva.
Una forma razonable de hacerlo es empezar por contar los terminos de la funcion objetivo
g0(t) de izquierda a derecha, enumerandolos desde 1 hasta n0, y luego continuar contando
los terminos de la primera restriccion posinomial g1(t) de izquierda a derecha, enumeran-
dolos desde n0 + 1 hasta n1, y ası sucesivamente hasta contar los terminos de la ultima
restriccion posinomial gk(t) de izquierda a derecha, enumerandolos desde nk−1 + 1 hasta
nk = p. El termino j ’esimo en este esquema de recuento se indica como sigue:
uj(t) = cjtαj1
1 tαj2
2 . . . tαjm
m .
Con este esquema notacional, podemos reescribir el programa geometrico con restricciones
33
estandar (GP) como
(GP)
Minimizar g0(t) = u1(t) + · · ·+ un0(t)
sujeto a las restricciones
g1(t) = un0+1(t) + · · ·+ un1(t) ≤ 1 ,
· · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · ·
gk(t) = unk−1+1(t) + · · ·+ unk(t) ≤ 1 ,
donde t1 > 0, t2 > 0, . . . , tm > 0, y nk = p .
La aplicacion de la Desigualdades Media Geometrica Aritmetica 2.1.2 y 3.1.1 solo a las
funciones g0(t), g1(t), . . . , gk(t) como en el ejemplo de la seccion anterior 3.2.1 nos lleva a
considerar el siguiente programa:
(PGD)
Maximizar v(δ) =
(
∏pj=1
(
cjδj
)δj)
∏ki=1 λi(δ)
λi(δ)
sujeto a las restricciones
δ1 + · · ·+ δn0= 1 ,
α11δ1 + · · ·+ αp1δp = 0 ,
......
......
α1mδ1 + · · ·+ αpmδp = 0 ,
donde δi > 0 para i = 1, . . . , n0, y para cada k ≥ 1, ya sea
δi > 0 para todo i con nk−1 + 1 ≤ i ≤ nk o δi = 0 para todo i
con nk−1 + 1 ≤ i ≤ nk. Donde, λi(δ) = δni−1+1 + · · ·+ δni.
El programa (PGD) es llamado el programa dual del (GP), la funcion v(δ) es la funcion
objetivo dual y las restricciones en (PGD) son las restricciones dual. Si δ1, δ2, . . . , δp son
numeros que satisfacen las restricciones dual en (PGD), entonces δ = (δ1, . . . , δp) es un
vector fatible para (PGD) y el (PGD) se dice que es consistente. Un vector δ∗ = (δ∗1, . . . , δ∗p)
34
que maximiza v(δ) en el conjunto de vectores factibles para (PGD) es una solucion de
(PGD).
Para el programa geometrico con restricciones considerado en el ejemplo de la seccion
anterior, hay cuatro variables duales δ1, δ2, δ3, δ4 porque la funcion objetivo y la unica
funcion de restriccion cada una contienen dos terminos. Hay un y solo vector δ =(
23, 13, 13, 13
)
que es factible para (PGD) por lo que es automaticamente una solucion de (PGD).
En general, el numero de variables dual en (PGD) es igual al numero total p(= nk)
de terminos en las funciones de restriccion y objetivo de (GP). Note que las ecuaciones
de restriccion en (PGD) son lineales, por lo que el problema de identificar los vectores
factibles de (PGD) se reduce a encontrar las soluciones del sistema de ecuaciones lineales
que tiene componentes no negativos. Tambien note que λi(δ) es simplimente la suma de
las componentes de δ que corresponden a los terminos de la i ’esima funcion de restriccion
gi(t) para i = 1, 2, . . . , k.
Antes de proceder al desarrollo de la relacion entre las soluciones del programa (GP)
y el correspondiente programa dual (PGD), vamos a resolver el dual de otro programa
geometrico concreto.
Ejemplo 3.3.1. Considere el programa geometrico.
Minimizar t1t−12 t23
sujeto a las restricciones
1
2t31t2t
−13 ≤ 1 ,
1
4t−1/21 +
1
4t−1/22 +
1
4t3 ≤ 1 ,
donde t1 > 0, t2 > 0, t3 > 0 .
Solucion: La funcion objetivo y las dos restricciones contienen un total de 5 terminos por
35
lo que hay 5 variables duales. las restricciones duales son
δ1 = 1 ,
δ1 + 3δ2 − 1
2δ3 = 0 ,
−δ1 + δ2 − 1
2δ4 = 0 ,
2δ1 − δ2 + δ5 = 0 ,
donde
δ1 > 0, δ2 ≥ 0, δ3 ≥ 0, δ4 ≥ 0, δ5 ≥ 0,
y la funcion objetivo dual es
v(δ) =
(
1
δ1
)δ1 ( 1
2δ2
)δ2 ( 1
4δ3
)δ3 ( 1
4δ4
)δ4 ( 1
4δ5
)δ5
(δ2)δ2(δ3 + δ4 + δ5)
δ3+δ4+δ5
El programa dado es consistente; de hecho, es incluso superconsistente porque, por ejemplo,
los valores t1 = 1, t2 = 1, t3 = 1 satisfacen ambas restricciones con desigualdades estrictas.
El programa dual es consistente; de hecho, es materia rutinaria verificar que la solucion
general de las cuatro ecuaciones de restriccion dual son
δ1 = 1, δ2 = −1
3+
1
6r, δ3 = r, δ4 = −8
3+
1
3r, δ5 = −7
3+
1
6r ,
donde r es un numero real arbitrario. Los requisito de que δi ≥ 0 para i = 1, 2, 3, 4, 5 anade
la restriccionadicional de que r ≥ 14 Ası, el conjunto de puntos factibles para el programa
dual es
F =
{(
1,
[
−1
3
]
, r,
[
−1
8+
1
3r
]
,
[
−7
3+
1
6r
])
: r ≥ 14
}
.
�
El teorema de Karush-Khun-Tucker no parece ser apliclable a los programas geometri-
cos, porque los posinomiales no necesariamente son funciones convexas. Por ejemplo, el
posinomial en un variable
g(t) = t1/2, t > 0 ,
36
no es convexo. Sin embargo, cualquier posinomial g(t) puede ser transformado en una
funcion convexa h(x) por los cambios de variables
tj = exj , j = 1, 2, . . . , m . (∗)
Mas precisamente, si el cambio de variables (∗) es aplicado al posinomial
g(t) =n∑
i=1
citαi1
1 tαi2
2 . . . tαim
m , ci > 0 ,
la correspondiente funcion de x = (x1, x2, . . . , xm) es
h(x) =
n∑
i=1
cie∑m
j=1αijxj ,
y h(x) es convexo en Rn en virtud del Teorema 3.1.3.
Esta observacion nos permite transformar el programa geometrico con restricciones
estandar
(PG)
Minimizar g0
s.a. g1(t) ≤ 1, g2(t) ≤ 1, . . . , gk(t) ≤ 1 ,
donde t1 > 0, t2 > 0, . . . , tm > 0
en un programa convexo asociado
(GP)∗
Minimizar h0(x) sujeto a las restricciones
h1(x)− 1 ≤ 0, h2(x)− 1 ≤, . . . , hk(x)− 1 ≤ 0 ,
donde x ∈ Rm ,
via los cambios de variables ti = exi para i = 1, 2, . . . , m. Es mas, porque t = ex es una
funcion estrictamente convexa. Los programas (GP) y (GP)∗ son equivalentes en el sentido
de que t∗ = (t∗1, t∗2, . . . , t
∗m) es una solucion para (GP) si y solo si x∗ = (x∗
1x∗2, . . . , x
∗m) es
una solucion de (GP)∗ donde t∗i = ex∗
i para i = 1, 2, . . . , m.
Estamos preparados para enunciar y demostrar el resultado central en la teorıa de
programacion geometrica con restricciones.
Teorema 3.3.1.
37
(1) Si t es un vector factible para el programa geometrico con restricciones (GP) y si δ es
un vector factible para el programa dual correspondiente (PGD), entonces
g0(t) ≥ v(δ) (la Desigualdad Primal− Dual) .
(2) Supongamos que el programa geometrico con restricciones (GP) es superconsistente y
que t∗ es una solucion para (GP). Entonces el correspondiente programa dual (PGD)
es consistente y tiene una solucion δ∗ que satisface
g0(t∗) = v(δ∗) ,
y
δ∗i =
ui(t∗)
g0(t∗), i = 1, . . . , n0 ,
λj(δ∗)ui(t
∗) , i = nj−1 + 1, . . . , nj ; j = 1, . . . , k .
Demostracion:
(1) La Desigualdad Primal-Dual sigue inmediatamente de la definicion de el programa dual
(PGD) y las Desigualdades Media Aritmetica-Geometrica 2.1.2 y 3.1.1.
(2) Ya que (GP) es superconsistente, por lo que es el programa convexo asociado de (GP)∗.
Tambien desde que (GP) tiene una solucion t∗ = (t∗1, t∗2, . . . , t
∗m), el programa convexo
asociado (GP)∗ tiene una solucion x∗ = (x∗1, x
∗2, . . . , x
∗m) dada por
x∗i = ln t∗i , i = 1, 2, . . . , m .
De acuerdo al Teorema de Karush-Kuhn-Tucker 3.1.2, existe un vector λ∗ =
(λ∗1, . . . , λ
∗k) tal que:
(a) λ∗i ≥ 0 para i = 1, 2, . . . , k;
(b) λ∗i (hi(x
∗)− 1) = 0 para i = 1, 2, . . . , k;
(c)∂h0
∂xj(x∗) +
k∑
i=1
λ∗i
∂hi
∂xj(x∗) = 0 para j = 1, . . . , m.
38
porque ti = exi para i = 1, . . . , m, se deduce que para i = 0, 1, . . . , k
∂hi
∂xj=
∂hi
∂tj
dtjdxj
=∂gi∂tj
exj ,
ası la condicion (c) es equivalente a
∂g0∂tj
(t∗) +k∑
i=1
λ∗i
∂gi∂tj
(t∗) = 0 , j = 1, 2, . . . , m (c’)
ya que exj > 0 para j = 1, . . . , m. Pero t∗j > 0 para j = 1, 2, . . . , m, por lo que (c’) es
equivalente a
t∗j∂g0∂tj
(t∗) +
k∑
i=1
λ∗i t
∗j
∂gi∂tj
(t∗) = 0 , j = 1, . . . , m . (c”)
Porque los terminos de gi(t) son de la forma
uq(t) = cqtαq1
1 tαq2
2 . . . tαqm
m ,
es claro que
t∗j∂gi∂tj
(t∗) =
ni∑
q=ni−1+1
αqjuq(t∗) , j = 1, . . . , m ,
ası (c”) implica que
0 =
n0∑
q=1
αqjuq(t∗) +
k∑
r=1
nr∑
q=nr−1+1
λ∗rαqjuq(t
∗) .
si dividimos la ultima ecuacion por
g0(t∗) =
n0∑
q=1
uq(t∗) ,
obtenemos
0 =
n0∑
q=1
αqj
(
uq(t∗)
g0(t∗)
)
+k∑
r=1
nr∑
q=nr−1+1
αqj
(
λ∗ruq(t
∗)
g0(t∗)
)
.
Definir el vector δ∗ por
δ∗q =
uq(t∗)
g0(t∗), q = 1, 2, . . . , n0 ,
λ∗ruq(t
∗)
g0(t∗), q = nr−1 + 1, . . . , nr, r = 1, . . . , k .
39
Note que δ∗q > 0 para q = 1, 2, . . . , n0 y que, para cada r ≥ 1, ya sea δ∗i > 0 para todo
i con nr−1 + 1 ≤ i ≤ nr o δ∗i = 0 para todo i con nr−1 + 1 ≤ i ≤ nr de acuerdo al
correspondiente multiplicador λ∗r de Karush-kuhn-Tucker, es positivo o cero. Tambien
observe que el vector δ∗ satisface todas las m ecuaciones de restriccion exponenciales
en (PGD) ası como la restriccion
n0∑
q=1
δ∗q =
n0∑
q=1
uq(t∗)
g0(t∗)= 1 .
Por lo tanto, δ∗ = (δ∗1, . . . , δ∗p) es un vector factible para (PGD).
Los multiplicadores λ∗r de Karush-kuhn-Tucker estan relacionados con las correspon-
dientes λr(δ∗) en (PGD) com sigue:
λr(δ∗) =
nr∑
q=nr−1+1
δ∗q
nr∑
q=nr−1+1
λ∗r
uq(t∗)
g0(t∗)= λ∗
r
gr(t∗)
g0(t∗)
para r = 1, . . . , k. La condicion (b) de Karush-Kuhn-Tucker nos da
λ∗r(gr(t
∗)− 1) = 0 , r = 1, . . . , k , (b’)
por lo que λ∗rgr(t
∗) = λ∗r para r = 1, . . . , k. Por lo tanto, para r = 1, . . . , k y q =
nr−1 + 1, . . . , nr, vemos que
δ∗q =λ∗ruq(t
∗)
g0(t∗)=
λ∗rgr(t
∗)uq(t∗)
g0(t∗)= λr(δ
∗)uq(t∗) . (∗)
El hecho de que δ∗ es factible en (PGD) y que t∗ es factible en (GP) implica que
g0(t∗) ≥ v(t∗)
debido a la Desigualdad Prima-Dual (1). Por otra parte, los valores de δ∗q en q =
1, 2, . . . , p son precisamente los que fuerzan a la igualdad en las Desigualdades Media
Aritmetica-Geometrica 2.1.2 y 3.1.1 que se utiliza para obtener la Desigualdad de
Dualidad. Finalmente, la ecuacion (b’) muestra que o bien gr(t∗) = 1 o λ∗
r = 0 para
r = 1, 2, . . . , k y la ecuacion (∗) muestra que λ∗r = 0 si y solo si λr(δ
∗) = 0 para
r = 1, . . . , k. Esto significa que los valores de δ∗q en ralidad fuerzan a la igualdad en la
Desigualdad Prima-Dual. Esto completa la demostracion.
40
�
La segunda afirmacion del teorema anterior implica que si (GP) es un programa
geometrico superconsistente para el cual el dual (PGD) es no consistente, entonces (GP)
no tiene solucion.
41
Bibliografıa
[1] R.J. Duffin, E.L. Peterson, and C. Zener. Geometric Programming, Wiley, New York,
1967
[2] M. Avriel and D.J. Wilde. Optimal condenser design by geometric programming, Ind.
Eng. Chem. Process Des. Develop. 6 (1967), 256-263.
[3] M. Avriel. Fudamentals of geometric, in Applications of Mathematical Programming
Techniques, (E.M.L. Beale, ed.), American Elsevier, New York, 1970, pp. 295-316.
[4] E. Peterson. The Origins of Geometric Programming. Annals of Operations Research
105, pp. 15-19, 2001.
[5] Robert C. Creese. Geometric Programming for Design and Cost Optimization. Morgan
& Claypool Publisher, 2010.
[6] Mung Chaing,. Goemetric Programming for Communication Systems. now Publisher,
2010.
[7] Stephen Boyd, Seung Jean Kim. A tutorial on geometric programming. Opt. Eng.
(2007) 8: pp. 67-127.
[8] O. Guler. Fundations of Optimization. Springer. 2010.
[9] M. Avriel, A.C.Williams. An Extension of Geometric Programming with Applications
in Engineering Optimization. Journal of Engineering Mathematics, Vol. 5, No. 3. pp.
187-194. 1971.
42