Chapter 1

Introduccin
El objetivo principal de estos apuntes es que permitan aprender y entender la esencia de los mtodos
de optimizacin en forma clara y didctica. El objetivo no es slo que los alumnos sepan modelar
y resolver problemas, sino que tambin puedan comprender su resolucin.
Los mtodos de optimizacin son un conjunto de herramientas cuantitativas muy poderosas
para enfrentar, modelar y resolver importantes problemas reales en los ms diversos mbitos (no se
limita slo a ingeniera). El objetivo de este texto es apoyar al curso de Optimizacin de la Escuela
de Ingeniera de la Pontificia Universidad Catlica de Chile para que los alumnos puedan llegar un
poco ms lejos que las clases, o para que lo puedan utilizar como apoyo en el futuro para enfrentar
problemas de optimizacin en otros cursos de la carrera o en sus trabajos.
Creemos muy necesario que la recopilacin y creacin de estos apuntes de mtodos de optimizacin debe ser muy clara y didctica para explicar los conceptos. El lector podr entender
el mecanismo detrs de los diferentes mtodos y as estar preparado para poder discernir entre
soluciones correctas e incorrectas.
Durante nuestros aos de doctorado en M.I.T. y Berkeley (1997-2002) tuvimos la oportunidad
de tomar varios cursos de investigacin de operaciones donde juntamos bastante material de primer
nivel, que se ha incorporado en estos apuntes.
El contenido de estos apuntes a nivel general es:
Introduccin: Se dan algunas nociones de qu es un modelo y de cmo se construyen. Se
presentan algunos modelos equivalentes, y se revisan algunas nociones de convexidad.
Programacin No Lineal: Condiciones necesarias y suficientes para un mnimo local o global;
Mtodos de bsqueda de soluciones ptimas (Gradiente, Newton, etc.)
Programacin Lineal: Formulacin y forma estndar de problemas lineales; Geometra de
problemas lineales; Mtodo Simplex; Anlisis de sensibilidad; Teora de dualidad.
Programacin Entera: Formulacin de modelos de programacin entera; Algoritmo Branch
& Bound; Algoritmo de planos cortantes.
Flujo en Redes: Modelos clsicos como ruta ms corta y mximo flujo.
1

CHAPTER 1. INTRODUCCIN
Programacin Dinmica: Mtodo de resolucin cuando hay relaciones intertemporales entre
las variables del problema.

A pesar de que estos apuntes no pretenden ser una gua de ejercicios, incorporan ejercicios
resueltos en su gran mayora a modo de ilustrar mejor cada uno de los conceptos tratados. Adems
se incorporar breves instrucciones de cmo operar el mdulo de optimizacin de Microsoft Excel,
y de lenguajes de modelacin algebraica como AMPL y SML.
Este texto se encuentra en formato PDF en la pgina web del curso de Optimizacin, de manera
que los alumnos (y ex-alumnos) puedan tener acceso a la ms reciente versin.

1.1

Introduccin al Modelamiento

Cotidianamente nos enfrentamos a la necesidad de decidir, evaluando opciones o cursos de accin

a seguir entre los cuales escoger la mejor alternativa. Si la opcin es nica, la decisin ya est
tomada, pero si son muchas o infinitas, entonces identificarlas y escoger la preferida puede ser muy
complejo. Incluso, cuando la opcin debe ser tomada por un grupo de personas, unos pueden tener
diferentes visiones que otros. Para poder comparar las distintas alternativas hay que establecer
explcitamente los objetivos que se persiguen con la decisin, y as lograr ordenar las opciones
disponibles de la mejor forma. Esta tarea (identificar opciones y clasificar objetivos) suele ser no
trivial.
Cuando el problema es complejo y resulta difcil identificar las opciones disponibles y/o escoger
la mejor, muchas veces se recurre a modelos como un recurso de apoyo. Los modelos permiten tomar
una decisin ms eficientemente; esto es ms rpidamente, econmicamente, informadamente, etc.

1.2

Qu es un modelo?

El trmino modelo se usa para hablar de una estructura que se ha construido y que exhibe
caractersticas de un sistema. Philippi (1981) define un modelo como una simplificacin de alguna
realidad concreta orientada a nuestros propsitos. En otras palabras, es una caricatura de la
realidad, que captura los factores dominantes que determinan el comportamiento del sistema en
estudio.
Un modelo debe seleccionar las caractersticas ms relevantes de la realidad, pues normalmente
no pueden considerarse todos sus aspectos. Las caractersticas a considerar dependern del uso
que se le dar al modelo. Esto produce un trade-off entre la complejidad del modelo y las
caractersticas consideradas. As, la simplicidad debe estar en la mente de todo modelador.
Algunos modelos son tangibles como por ejemplo los aeromodelos, mapas y maquetas arquitectnicas. Por ejemplo los aeromodelos renen las caractersticas de vuelo de los aviones reales, ya que
ese es el uso que se les dar, es decir, la atencin se centra en su diseo, resistencia, aerodinmica,
por lo que, en este caso, los asientos no se ponen ya que son irrelevantes para el objetivo.

1.3. POR QU SE CONSTRUYEN MODELOS?

Normalmente en Investigacin de Operaciones (IO1 ) se usan modelos abstractos. Estos por

lo general, sern matemticos, donde los smbolos algebraicos reflejarn las relaciones internas del
sistema modelado. As, una caracterstica esencial de un modelo matemtico en IO, es que contiene
las relaciones matemticas relevantes (ecuaciones, inecuaciones, dependencias lgicas, etc) que se
extraen al observar el mundo real.

1.3

Por qu se construyen modelos?

i) Clarifica las relaciones existentes, no siempre claras para el observador. Se comprende mejor
el sistema. Ayuda a identificar las alternativas. Es como una metodologa de aprendizaje. Por
ejemplo en un mapa se clarifican las rutas posibles para llegar de un lugar a otro. En muchas
disciplinas (la fsica por ejemplo) los modelos no se usan para decidir sino que para comprender
mejor.
ii) Permite un anlisis metdico cuyo fin sea sugerir lneas de accin, no evidentes de otro
modo. Por ejemplo una maqueta de una casa ayuda a decidir mejor como orientar los espacios, la
iluminacin, etc.
iii) Un modelo permite experimentar en l, cosa que no siempre es posible en el sistema real
(Ej: avin, planta manufacturera, economa de un pas, etc).
Estas tres razones son tambin vlidas para construir modelos matemticos que permiten experimentar con sistemas complejos de gran tamao, considerar muchas alternativas simultneamente
(sin necesidad de enumerarlas a priori) e identificar un mejor (u ptimo) curso de accin.
Es importante distinguir entre modelo y datos. El modelo queda definido por las relaciones
que tiene incorporado. La idea es que los modelos tengan validez independiente de los datos que
se incorporarn. Sin embargo, hay veces que los modelos tienen validez slo en un rango de datos
permitido. (Ej: Fluidez de un slido sujeto a tensiones (Resistencia de materiales)).
Los modelos de Programacin Matemtica son los ms comnmente usados. Otros ejemplos
de modelos de uso frecuente son: simulacin (modelos muy complejos de resolver), planificacin
en red, economtricos (predecir una variable en funcin de otra), series de tiempo (modelos que
indican qu hacer en base a datos pasados).
Los problemas pueden ser modelados en ms de una forma. Es interesante observar qu tipo
de modelacin es ms eficiente (tiempo, resultado, memoria).
Cuando se plantea modelar un sistema existen muchos conceptos errados al respecto. Hay
quienes se niegan a su utilidad argumentando que hay muchas hiptesis cuestionables como que
hay factores difciles de cuantificar, o bien, que siempre los datos carecen de precisin. Es clave ver
si el resultado es sensible o no respecto a dicha hiptesis.
En otro extremo hay quienes profieren una fe metafsica a los modelos matemticos para la toma
de decisiones (y an ms si provienen de un computador). Obviamente la calidad de la solucin
1

IO: Ciencia de la toma de decisiones, o, la aplicacin de mtodos cientficos a la administracin y gestin de

organizaciones.

CHAPTER 1. INTRODUCCIN

depender de la precisin de la estructura y de los datos del modelo.

Hay que considerar que la fe sin crtica a un modelo es obviamente peligrosa. No se recomienda
en absoluto aceptar la primera respuesta que un modelo matemtico produce sin un anlisis y
cuestionamiento posterior profundo. Normalmente un modelo ser una herramienta dentro de un
conjunto, a la hora de tomar una decisin.
La respuesta de un modelo deber enfrentarse a un cuidadoso examen, y si sta es inaceptable,
deber comprenderse el por qu y probablemente incorporarse a un modelo modificado. Si la
respuesta es aceptable, puede ser prudente mantenerlo como una opcin. Por medio de un sucesivo
cuestionamiento de las respuestas y alternando el modelo, es posible clarificar las opciones factibles
y comprender mejor lo que es posible.

1.4

Modelos de Programacin Matemtica

En muchas ocasiones uno enfrenta problemas en que es necesario determinar la mejor opcin dentro
de un conjunto de alternativas disponibles. A esta accin se le denomina Optimizar. Dentro
del proceso de optimizar existen algunos mtodos que son de mucha utilidad, los mtodos de
Programacin Matemtica, que se basan en la creacin de un modelo que represente el sistema
de inters para luego trabajar en torno a esta reduccin o caricatura de la realidad, y as facilitar
la toma de decisin.
A los estudiantes de ingeniera la palabra programar seguramente les evoca largas horas frente
al computador diseando un software. Sin embargo en Programacin Matemtica (PM) la palabra
se usa con el significado de planificar. De hecho, PM en su esencia no tiene nada que ver con
computadores. Lo que sucede posteriormente, es que los problemas de PM son tan grandes que
requieren apoyo computacional para su resolucin.
La caracterstica comn de todos los problemas de PM es que pretenden optimizar algo (minimizar o maximizar). Lo que se pretende optimizar se le denomina funcin objetivo. Cuando
uno observa que se requiere optimizar considerando ms de un objetivo, tenemos una funcin
multi-objetivo, o con objetivos difusos. En ese caso existen al menos dos alternativas para abordar el problema: priorizar o ponderar. Priorizar se refiere a resolver mltiples problemas en forma
secuencial de acuerdo a un orden (priorizacin) de los objetivos. Ponderar apunta a la resolucin
conjunta de los objetivos, llevndolos a una unidad comn.

La Figura 1.1 muestra una clasificacin general de los modelos matemticos. En este texto
trataremos principalmente modelos determinsticos de programacin no-lineal y de programacin
lineal, tal como se destacan en dicha figura.
El problema general de Programacin Matemtica consiste en determinar un vector xT =
(x1 , ..., xn ) que perteneciendo a un conjunto D, subconjunto de un espacio vectorial de orden n,

1.5. CARACTERIZACIN DE PUNTOS EXTREMOS DE UNA FUNCIN

Modelos Matemticos

Estticos

Dinmicos

Continuos

Discretos

Estocsticos

Determinsticos

Lineales

No-Lineales

Figure 1.1: Clasificacin de Modelos Matemticos

maximiza (o minimiza) una funcin objetivo f(x1 , ..., xn ). Esto es,
max f (xT )

P)

(1.1)

s.a. xT D,
donde el dominio o set de oportunidades D estar formado por los siguientes tipos de restricciones: (i) restricciones funcionales
hi (xT ) = 0

con i = 1, ..., m

gj (x ) 0 con j = 1, ..., s
y (ii ) restricciones de conjuntos
x

E n.

A la funcin objetivo f (xT ) tambin se le denomina funcin econmica o de utilidad (costos).

Cabe mencionar que maximizar una funcin equivale a minimizar dicha funcin, pero con signo
contrario. Por otra parte, en Programacin Lineal, f(x) y las restricciones h(x) y g(x), son lineales.
En esta seccin se entregan conceptos matemticos bsicos para la solucin de problemas de
programacin matemtica. En particular, se caracterizan las soluciones ptimas de un problema y
se discute en qu casos es posible garantizar la existencia de una solucin ptima. Ms adelante se
introduce el concepto de modelos equivalentes, esto es, modelos cuya solucin ptima es necesariamente equivalente. Por ltimo, se introduce la convexidad en conjuntos y funciones, pues sta ser
de gran ayuda para decidir si un ptimo local es solucin al problema.

1.5

Caracterizacin de puntos extremos de una funcin

Definicin 1 Un punto extremo de una funcin definida sobre un dominio D puede ser local o
global, estricto o no estricto, segn se define a continuacin (la Figura 1.2 muestra grficamente
cada una de estos puntos):
x es mximo global si x es punto factible y si f(x ) f (x) x D.

CHAPTER 1. INTRODUCCIN

x es mximo global estricto si x es punto factible y si f(x ) > f(x) x D \ {x } .

x es mximo local si x es punto factible y si f (x ) f(x)x Vecindad de x y x D.
x es mximo local estricto si x es punto factible y si f(x ) > f (x) x Vecindad de x y x
D \ {x } .

Max. local
no estricto

Min. local
estricto

Max. global
estricto

Max. global
de borde

Min. global
de borde
(b)

(a)

Figure 1.2: Soluciones locales vs. globales

1.6

Existencia de solucin ptima

Definicin 2 Todo punto x D define una solucin factible o realizable de P ).

Definicin 3 Un punto factible x

define una solucin ptima del problema de optimizacin min f(x)
ssi f(

x) f(x) x D y x

D.

xD

Nota: En el caso particular en que D = Rn , se dice que el problema es no-restringido o irrestricto.

Definicin 4 En un problema de maximizacin, v
define el valor ptimo de P ) si: v
= sup(f (x)),

x D. (sup: supremo, cota superior de la funcin sobre el dominio). En particular, si x

es solucin
ptima de P ) = v
= f(

x). Anlogamente para un problema de minimizacin, v
= inf(f (x)),
x D. (inf: nfimo, cota inferior de la funcin sobre el dominio).
Nota: No todos los problemas tienen solucin ptima. Podemos pensar en cuatro familias de
problemas que podran carecer (o carecen) de ella:
a) Problemas cuyo conjunto de restricciones define un dominio de puntos factibles vaco.
b) Problemas que contemplan alguna restriccin de desigualdad estricta, es decir que define
una regin que no incluye a su borde. Si en este caso la funcin objetivo mejora en cuanto ms se
acerque al borde, se estar en una situacin en que la solucin ptima no se podr identificar.
c) Problemas que contemplan un dominio no acotado, es decir que incluye puntos cuyas variables
toman valores tan grandes (en valor absoluto) como sea necesario. Si en este caso la funcin objetivo

1.6. EXISTENCIA DE SOLUCIN PTIMA

mejora en cuanto ms se acerque a estos puntos de valor absoluto ilimitado, entonces la solucin
ptima no se podr identificar.
d) Problemas con una funcin objetivo discontinua sobre el dominio factible. Si en este caso la
funcin objetivo evaluada en el punto de discontinuidad no es ptima, pero sta mejora en cuanto
ms se acerque al punto de discontinuidad desde alguna direccin, entonces la solucin ptima no
se podr identificar.
Evidentemente, no todos los problemas con dominio no acotado carecen de solucin. Tampoco
todos los problemas con restricciones de desigualdad estricta o todos los con funcin objetivo
discontinua. Sin embargo, en presencia de estos eventos, la solucin ptima no est garantizada.
Estas observaciones nos conducen naturalmente al siguiente teorema de existencia de solucin
ptima.
Teorema 1 (Existencia de soluciones ptimas) Consideremos el siguiente problema de optimizacin
P)

Min f(x)
xD

Si f (x) es continua sobre D, con D cerrado y no vaco sobre Rn , entonces bajo la hiptesis:
(1.2)

H) f(x) + si ||x|| +, x D
P ) admite al menos una solucin ptima.

f (x)

Figure 1.3: Ejemplo de Teorema de Existencia

Nota: Un problema P ) puede tener valor ptimo finito y, sin embargo, no admitir solucin
ptima. Para ilustrar esto veamos el siguiente ejemplo:
P ) min ex
x0

CHAPTER 1. INTRODUCCIN

donde v
= v(P ) = 0.

x 0 / ex = 0? No! Por lo tanto P ) no tiene solucin, aunque v
R (ver
e-x

ex

x
(b)

(a)

Figure 1.4: Ejemplos de valores y soluciones ptimas

Figura 1.4a).
Se podra pensar que no existe solucin ptima porque D es no acotado. Sin embargo, muchos
problemas no acotados admiten solucin ptima. Basta considerar,
P ) min ex ,
x0

en que v(P ) = 1 y x

= 0 es la solucin ptima (ver Figura 1.4b).

Nota: Un conjunto es cerrado si contiene a todos los puntos frontera. El caso de D = R es

cerrado, ya que el conjunto de los puntos frontera es vaco, y todo conjunto contiene al conjunto
vaco. Como ejemplo de un conjunto no cerrado considere x > 0 que no contiene a su frontera
(x = 0).
Corolario 2 (Bolzano-Weierstrass) Si f es continua, sobre un dominio no vaco, cerrado y acotado, entonces el problema necesariamente tendr solucin ptima, ya que la imagen de una funcin
continua sobre un set compacto, es tambin compacta (cerrada y acotada).
Demostracin. D es acotado ninguna sucesin de puntos {xk D}k0 tal que:
||xk || +
xk

k
Luego, la hiptesis H) en (1.2) se cumple por vacuidad en este caso.
Nota: Es importante notar que estos teoremas identifican condiciones suficientes para existencia
de optimalidad, pero no condiciones necesarias. As, muchos problemas que no satisfacen las
condiciones identificadas en el Teorema 1 o en el Corolario 2 tienen solucin ptima.

1.7. PROBLEMAS EQUIVALENTES

1.7

Problemas Equivalentes

Un problema se puede modelar de varias formas diferentes. En programacin matemtica se denominan problemas equivalentes a problemas que garantizan el mismo conjunto de soluciones ptimas.
Evidentemente, para un mismo problema, se busca aquel modelo que facilita su resolucin.
Considere el problema de localizar una estacin de bomberos en una ciudad con el siguiente
criterio: que el tiempo mximo de respuesta de la bomba a eventos en cinco edificios de asistencia
masiva sea lo ms breve posible. En este caso para cada punto posible de instalar la bomba se evala
el tiempo de respuesta a cada uno de los cinco edificios; el mayor de estos cuatro valores representa
la funcin objetivo evaluada en el punto. Es interesante notar que en este caso la funcin objetivo
es minimizar el valor maximo entre otras cinco funciones, es decir si denominamos la posicin de
la bomba x, entonces la funcin objetivo es:
Min (max {d1 (x), d2 (x), d3 (x), d4 (x), d5 (x)}).
Una funcin objetivo como esta presenta serios problemas pues es difcil de tratar algebraicamente y presenta discontinuidades en su derivada. As, sera deseable poder modelar este problema
mediante un modelo equivalente que no presente estas dificultades.
A continuacin se presentan siete equivalencias que pueden facilitar la modelacin de muchos
problemas, entre ellos el problema de la localizacin de la estacin de bomberos.

1.7.1

Equivalencia I
P)

Max f (x)

x D.

P) Min (f(x))

x D.

x

es solucin ptima de P ), con valor ptimo v
, si y slo si x

es solucin ptima de P), con
v(P) =

v.
f (x )

f (x)

Figure 1.5: Equivalencia I

10

CHAPTER 1. INTRODUCCIN

Ejemplo 1 Algunos ejemplos de esta equivalencia son:

Maximizar utilidad = Minimizar prdida.
Maximizar probabilidad de sano = Minimizar probabilidad de enfermo.
Por lo tanto, dado un problema de maximizacin, procedemos a cambiar el signo de la funcin
de costo, para luego resolver el problema de minimizacin equivalente. Conocida la solucin ptima
x y el valor ptimo v(P ), la solucin ptima de P ) es x y el valor ptimo v(P ) = v(P).

1.7.2

Equivalencia II

P ) Min f (x)
x D Rn
Equivalente a,
P)

M in
f (x)

x D Rn

R

P)

Min
f(x) =
x D Rn


 = D R Rn+1 , donde x
Considerando el problema P) o P), el nuevo dominio ser: D

es solucin
ptima de P ) con valor ptimo v
= v(P ), si y slo si (

x, ) es solucin ptima de P) con valor
ptimo v
.

Comprobaremos esta equivalencia por contradiccin. Supongamos que el problema P ) tiene


solucin ptima x0 y definimos f(x0 ) = 0 . Por una parte el problema P ) o P) no puede tener
valor ptimo 1 > 0 pues el punto (x0 , 0 ) es factible para el problema y evaluado en la funcin

objetivo es mejor que 1 . Por otra parte, el problema P ) o P) no puede tener valor ptimo 1 < 0
pues entonces existira un punto x1 en D tal que f(x1 ) 1 en cuyo caso la solucin ptima a P )
sera x1 y no x0 .

Es importante destacar que en el nuevo problema el objetivo es encontrar un lo ms pequeo

posible tal que exista un x que satisfaga f(x) . As, en la Figura 1.6 se observa que cumple
con ser el ptimo al problema pues existe un x D tal que f(x ) y para todo valor de
menor a no existe un x en D tal que f (x) .

1.7. PROBLEMAS EQUIVALENTES

11

f (x )
( x, )

f ( x) = v(P )

Figure 1.6: Equivalencia II

Ejemplo 2 En un callejn de 100 metros de largo hay un prfugo que necesita ubicarse en el lugar
que tenga menos luz. En el callejn hay 4 focos con diferentes caractersticas (altura, potencia,
posicin). Suponga que la intensidad de luz que llega al prfugo es slamente la del foco que
alumbra ms en dicho punto y que para estos efectos los postes (si los hubiera) se pueden considerar
transparentes (ver Figura 1.7). Suponga que la intensidad de luz de cada foco se puede considerar
inversamente proporcional a la distancia entre el foco y el prfugo y directamente proporcional a la
potencia del foco. De esta forma, al prfugo le interesar pararse en el lugar que haya menos luz,
F1
F4
F2

F3

Figure 1.7: Ejemplo de Equivalencia II

es decir, su funcin objetivo ser:
Min (max {f1 , f2 , f3 , f4 })
donde
fi =

ki

.
h2i + (xi x)2

0 x 100

en que ki , xi y hi corresponden a la potencia, ubicacin y altura respectivamente de cada foco. La

12

CHAPTER 1. INTRODUCCIN

nica variable del problema es la ubicacin del prfugo, x.

Al igual que el problema de la estacin de bomberos, este modelo es complicado de abordar

pues presenta una funcin objetivo cuya derivada no es continua. As, resulta deseable identificar
un modelo equivalente para este problema que no presente dicha complicacin. La siguiente seccin
presenta dicha equivalencia.

1.7.3

Equivalencia III

Consideremos un problema como el anterior donde el objetivo consiste en encontrar un punto tal
que el mximo entre n funciones evaluadas en el punto sea mnimo. Algebraicamente, esto puede
expresarse del siguiente modo:
P ) MinxD ( max fi (x))
i=1,...,n

Grficamente, el problema se ilustra en la Figura 1.8, en que las funciones fi (x) se dibujan con
lneas tenues mientras la funcin objetivo se ilustra con una lnea gruesa. Es importante destacar
que esta ltima funcin no gozar necesariamente de una derivada continua (e.g., en los puntos A
y B de la figura 1.8). As, estamos minimizando una funcin no diferenciable.

f3

f2
B

f1

Figure 1.8: Equivalencia III

Sin embargo, de acuerdo a la equivalencia II, el problema P ) puede convertirse en el siguiente
problema equivalente:
P) M in

max fi (x)

i=1,...,n

x D

1.7. PROBLEMAS EQUIVALENTES

13

Naturalmente la nueva desigualdad puede expresarse como n desigualdades individuales:


P) Min

fi (x)

i = 1, ..., n

x D

Este ltimo problema contempla slo funciones diferenciables.

Consideremos el siguiente ejemplo cuya funcin objetivo es no lineal y cuya derivada no es

continua.


7x1 + 6x2 + 5x3 5x1 + 9x2 + 4x3
P ) Max (min
,
)
4
3
s.a
8x1 + 5x2 + 3x3 100
6x1 + 9x2 + 8x3 200
x1 , x2 , x3 0
A continuacin identificaremos un problema equivalente cuyas funciones tengan derivadas continuas.
De la regla I), P ) es equivalente a:
P) min( min {f1 (x), f2 (x)})
xD

Es fcil notar que: min {f1 (x), f2 (x)} = max {f1 (x), f2 (x)} , por lo tanto P) es equivalente a

P) min(max {f1 (x), f2 (x)})
xD


de la regla III P) es equivalente a

s.a.



P) min

f1 (x)
f2 (x)
x D

R.

14

CHAPTER 1. INTRODUCCIN

o equivalentemente:



P) max

s.a. f1 (x)
f2 (x)
x D

R.
Y este problema es derivable en el espacio D R. Es decir,
P) max( min {fi (x)})
i=1,...,n

s.a. x D
es equivalente a


P) max

s.a. fi (x) i = 1, ..., n

x D

R.

Como se observa, este problema lineal es equivalente al problema original. Estas equivalencias
suelen resultar muy tiles en presencia de mdulos de funciones en la funcin objetivo. Por ejemplo:
P ) min |3x 2|
s.a.

1 x 2
x R

En este caso vemos que la funcin objetivo no es derivable en x = 2/3 (ver Figura 1.9).

Ocupando la regla II vemos que P ) es equivalente a:

P)

min

s.a |3x 2|
1 x 2
x R

(Restriccin no-lineal)

1.7. PROBLEMAS EQUIVALENTES

15

-1

Figure 1.9: Ejemplo de minimizacin del mdulo

Pero tambin P) es equivalente a:
s.a.


P)

min
3x 2

(3x 2)
1 x 2
x R

R
Ahora todas las funciones que intervienen son derivables (y en este caso lineales). Es importante
notar que en esta formulacin se utiliz la equivalencia |3x 2| 3x 2 y (3x 2) .
Esta equivalencia es posible ya que la expresin |3x 2| es satisfecha por un conjunto convexo
de puntos (x, ). Este conjunto queda bien recogido por las dos restricciones equivalentes. Sin
embargo una expresin como |f(x)| ( 0) no tiene un conjunto de restricciones diferenciables
equivalente ya que el conjunto de puntos (x, ) que la satisface no es convexo. Dicha expresin ser
equivalente al conjunto de puntos (x, ) tal que f (x) o bien f(x)
En el ejemplo anterior se puede ver que en el ptimo, |3x 2| = 3x 2 = o bien
3x 2 = ; esta relacin puede representarse mediante (3x 2 )(3x 2 + ) = 0.

Por lo tanto, P) tambin es equivalente a:


P)

min

s.a. (3x 2 )(3x 2 + ) = 0

1 x 2
x R

R

En este caso, como el problema P) es lineal, lo preferimos a este ltimo problema.

16

CHAPTER 1. INTRODUCCIN

Es importante notar que aunque 1 x 2 est dems en este caso, muchas veces no es
recomendable eliminar (o relajar) restricciones reales de un problema an cuando se sepa que
la solucin ptima del problema permanecera inalterable (a menos que la relajacin simplifique
considerablemente la resolucin del problema). Esto se debe a que a veces falla la intuicin del
modelador y porque el modelo puede ser usado ms adelante con otros parmetros que activen la
restriccin relajada.

En trminos generales, los siguientes modelos resultan equivalentes:

P)

min |f(x)|
xD

P)

min
f(x)
f(x)

x R

R

P) min

(f(x) )(f(x) + ) = 0

x R

R
Al realizar estas equivalencias, el lector debe cuidarse de no incurrir en equivalencias errneas. Por
ejemplo:
P ) max( max {fi (x)})
i=1,...,n

s.a. x D
no es equivalente a
P) max

s.a. fi (x) i = 1, ..., n

x D

R.

1.7. PROBLEMAS EQUIVALENTES

17

pues todo lo que se puede decir es que P ) es equivalente a

s.a.


P) max

max {fi (x)}

i=1,...,n

x D

R.
Sin embargo, que sea inferior al mximo de un conjunto de funciones no es equivalente a que
sea inferior a cada una de ellas (equivaldra a ser inferior al mnimo de ellas). Lo que se requerira
es exigir que sea inferior a al menos una de las funciones, es decir f1 (x) f2 (x)
.... fn (x). En cambio al exigir fi (x) i = 1, ..., n se est exigiendo f1 (x) y f2 (x) y
.... y fn (x). Incorporar las relaciones lgicas asociadas al operador tpicamente requieren
de variables binarias asociadas a cada relacin. Estas variables binarias no son continuas por lo que
tampoco son diferenciables. As, no existe un modelo equivalente diferenciable a P ) en este caso.

Por ejemplo, consideremos el siguiente problema

P ) max |3x 2|
s.a.

1 x2
x R

La solucin ptima a este problema ser x = 1 con un valor ptimo v
= 5. Podemos ver que el
siguiente modelo:
P ) max
s.a. 3x 2
(3x 2)
1 x 2
x R

no es equivalente pues la solucin x = 1, = 5 no es factible, ya que no satisface la primera

restriccin.

Considere el siguiente problema:

P)
s.a.

min z = (max {|x1 |, |x2 |})

x1 + 2x2 1
x1 , x2 0

18

CHAPTER 1. INTRODUCCIN
x2

1/2

11

x1

Figure 1.10: Ejemplo equivalencia III

Aplicando la regla III, P ) es equivalente a:

P)

min
x1
x1
x2
x2

x1 + 2x2 1
x1 , x2 0

(x1 , x2 ) R2
R

Una ventaja de los problemas bidimensionales como el anterior es que pueden resolverse mediante curvas de nivel. En este procedimiento se dibuja en el plano R2 un conjunto de curvas tal que
cada una de ellas represente el lugar geomtrico de todos los puntos de R2 que reemplazados en
la funcin objetivo den el mismo valor o cota. A continuacin se debe graficar en el mismo plano
los puntos que satisfacen las restricciones del dominio. As, es posible identificar visualmente la
solucin ptima al problema. Por ejemplo, en la Figura 1.10 podemos ver el dominio del problema
P ), y la Figura 1.11 ilustra el dominio al agregar las curvas de nivel.
En este caso, las curvas de nivel permiten observar que la funcin objetivo corresponde a una
pirmide invertida de base cuadrada en que las aristas de la base son paralelas a los ejes cartesianos.
El problema P ) busca el punto del dominio que pertenezca a la curva de nivel de mnima cota (ver
Figura 1.11).
La figura permite identificar que en el ptimo x1 = x2 , y como x1 + 2x2 = 1, entonces x1 =
y x2 = 13 . Por lo tanto v
(P ) = 13 .

1
3

1.7. PROBLEMAS EQUIVALENTES

19

x2
1

Z=1

Z=1/2

-1

x1

-1

Figure 1.11: Curvas de nivel

1.7.4

Equivalencia IV

Considere el siguiente problema:

P)

min

r


fi (
x)

i=1

x D Rn

Este problema puede expresarse en forma equivalente como:

P) min

r


i=1

fi (
x ) i ;

x D

Rr

i = 1, ..., r

Esta equivalencia puede demostrarse por contradiccin al igual que la equivalencia II. Se deja al
lector como ejercicio.
Esta equivalencia es de especial inters en casos en que algunas funciones fi (x) son no diferenciables y al pasarlas al dominio permiten encontrar una equivalencia que s lo sea. Por ejemplo:
P ) min(|x1 | + |x2 |)
s.a.

x1 + 2x2 1

20

CHAPTER 1. INTRODUCCIN
P)

min 1 + 2
s.a.

|x1 | 1
|x2 | 2

x1 + 2x2 1
Lo que tambin equivale a: (Problema Lineal Equivalente)

P) min 1 + 2
s.a.

x1 1

x1 1
x2 2
x2 2
x1 + 2x2 1

1 , 2 R

En trminos generales se puede decir que:

P)

min

r

i=1

x D Rn

s.a.

P) min

r


|fi (x)|

i=1

fi (x) i ;

i = 1, ..., r

fi (x) i ;

i = 1, ..., r

x D

Rr
Ejemplo: son los siguientes problemas equivalentes?:
P)

min x 2

s.a

x0

P)

s.a

min (x 2)2
x0

Claramente no lo es porque la funcin g(x) = x2 es estrictamente creciente sobre los nmeros

1.7. PROBLEMAS EQUIVALENTES

21

no negativos. Sin embargo, aqu se aplica sobre una funcin que puede arrojar nmeros negativos
(e.g. si x = 0, entonces f(x) = 2). De hecho la solucin ptima al primer problema es x = 0,
mientras el del segundo es x = 2.

1.7.5

Equivalencia V

El problema de minimizacin MinxD f(x) es equivalente al problema MinxD g(f (x)), donde la
funcin g : f (D) R R es estrictamente creciente sobre f(D) = {y R / x D : y = f(x)} ,
por lo que la solucin ptima ser la misma en ambos casos, pero no as los valores ptimos. Para
comprobar esta equivalencia, considere a x como el ptimo del problema original. Esto significa que
f(x ) f(x) x D. Como g(x) es estrictamente creciente, si x1 x2 entonces g(x1 ) g(x2 ).As,
necesariamente g(f (x )) g(f (x)) x D y por lo tanto ambos problemas arrojarn la misma
solucin ptima. Por ejemplo, al cambiar la escala de unidades de la funcin objetivo de dlares a
pesos (U S$ $), se est aplicando una funcin g(x) lineal y creciente sobre todo el dominio por
lo que la solucin ptima al problema es la misma independiente de las unidades.
Ejemplo 3 Determinar el punto ms cercano al origen (0,0) que satisfaga 2x1 + x2 2.

En este caso la funcin de costos sera x21 + x22 , y el dominio D = {(x1 , x2 )/2x1 + x2 2} .
La funcin raz cuadrada suele presentar complicaciones pues no es diferenciable en cero. Por lo
tanto, resulta conveniente modificar la funcin objetivo con el fin de eliminar la raz.
Tomemos g(y) = y 2 . Esta funcin es estrictamente creciente sobre el recorrido de la funcin
objetivo original, esto es, los nmeros no negativos R+ , ya que f(x) 0 x D.
Por lo tanto, los siguientes problemas son equivalentes:


min x21 + x22

P)
s.a

2x1 + x2 2

P )

min x21 + x22

s.a

2x1 + x2 2

 1 , x2 ) = x2 + x2 es difereny este ltimo problema presenta la ventaja que su funcin objetivo: f(x
1
2
ciable sobre todo R2 .

Nota: Si el problema P ) est bien formulado (i.e. el argumento de la raz sea no negativo para
todo x D) se puede siempre prescindir de la raiz.
P)
con

min
xD


r(x)

r(x) 0 x D
P)

min r(x)
xD

22

CHAPTER 1. INTRODUCCIN

En este caso es importante recordar que si x

es solucin ptima de P) con v(P ) = r(

x), entonces

x

es solucin ptima de P ) con v(P ) = r(

x).

1.7.6

Equivalencia VI

Basndose en las equivalencias anteriores podemos decir que el problema

1
f(x)
f(x) = 0, x D

P)
con
y

min
xD

f(x) > 0

es equivalente a
P )

max f (x).
xD

Para probar lo anterior basta con suponer el caso particular en que g(y) = ln y, estrictamente
creciente y > 0. Aplicando la regla V P ) es equivalente a:

P)

1
min ln
xD
f(x)


Finalmente, de la regla I, P) es equivalente a:


P)

= min ln f(x)
xD

max ln f (x)
xD



De la regla V, con g(y) = ey , P ) es equivalente a:



P )

max f (x).
xD

Es importante destacar que esta equivalencia ocurre slo si f (x) es estrictamente positivo para todo
x. Si la funcin puede tomar valores negativos para algunos puntos del dominio, entonces aplicar
esta equivalencia puede conducir a error.

1.7.7

Equivalencia VII

Aunando las equivalencias anteriores, podemos decir que el problema

P)

min(g(x) + max {fi (x)})

xD

i=1,...,r

1.8. NOCIONES BSICAS DE CONVEXIDAD

23

Geomtricamente
D no convexo

D convexo

Figure 1.12: Conjuntos convexos y no convexos

es equivalente a:
P)

min 1 + 2
xD

g(x) 1
fi (x) 2
1 , 2

1.8

R.

i = 1, ..., r

Nociones Bsicas de Convexidad

Los problemas de optimizacin pueden ser sumamente complejos y contener mltiples soluciones
ptimas locales lo que puede dificultar enormemente su resolucin. Estas dificultades pueden reducirse si se identifican adecuadamente algunas caractersticas tanto de la funcin objetivo como
del dominio del problema. En esta seccin se revisan las caractersticas de los conjuntos convexos,
las funciones convexas y los problemas convexos.

1.8.1

Conjuntos Convexos

Intuitivamente un conjunto se dice convexo si para cualquier par de puntos en el conjunto, todos
los puntos en la lnea recta que los une tambin pertenecen al conjunto. Basta que haya un par de
puntos en el dominio que no satisfaga esta condicin para que el conjunto se diga no convexo. En
la Figura 1.12 se observa un ejemplo de un conjunto convexo y uno no convexo.Formalmente,
Definicin 5 Un conjunto D Rn se dice convexo si para todo par de puntos x1 D y x2 D y
cada nmero real con 0 1, x = x1 + (1 )x2 D.
Definicin 6 Segmento [x1 , x2 ] = {z Rn / z = (1 )x1 + x2 , [0, 1]} . Dado lo anterior,
un dominio D ser convexo si: x1 y x2 D [x1 , x2 ] D.
Claim 1 Todos los poliedros definidos por desigualdades lineales son convexos. Esta demostracin
se deja al lector.
Proposicin 3 El conjunto formado por la interseccin de conjuntos convexos es convexo (ver
Figura 1.13).

24

CHAPTER 1. INTRODUCCIN

Demostracin. Sean A y B conjuntos convexos, y su interseccin denominmosla C = A B.

Se debe demostrar que si x1 y x2 C, entonces [x1 , x2 ] C. Si x1 y x2 C, entonces x1 y x2 A y
x1 y x2 B. Como A y B son convexos, [x1 , x2 ] A y [x1 , x2 ] B, por lo tanto, [x1 , x2 ] C. C
es convexo. Ver Figura 1.13.

B
AIB

Figure 1.13: Interseccin de Conjuntos

1.8.2

Funciones Convexas

En optimizacin, estamos especialmente interesados en identificar puntos extremos de la funcin

objetivo. Para algunas funciones esto resulta particularmente sencillo. Desde esta perspectiva, en
la Figura 1.14 se entrega una clasificacin del universo de funciones. En esta figura se destacan las
funciones convexas, estrictamente convexas y cuasi-convexas que a continuacin se describen.

Cuasi-Convexas

Convexas
Estrictamente
Convexas

Figure 1.14: Universo de funciones

Definicin 7 (Funcin convexa) Sea f(x) : D R, con D convexo. Entonces, f(x) es convexa
sobre D si:
f((1 )x1 + x2 ) (1 )f(x1 ) + f (x2 )

x1 , x2 D, [0, 1] .

En otras palabras, lo que dice la Definicin 7, es que si en cualquier intervalo [x1 , x2 ] todo punto
del grafo de f(x) est siempre bajo la cuerda que une los puntos (x1 , f (x1 )) y (x2 , f (x2 )), entonces
f(x) es una funcin convexa. La Figura 1.15 lo muestra grficamente. Es importante notar que
una funcin definida sobre un dominio no convexo no puede ser convexa.
Qu ocurre con la funcin de la Figura 1.16? El grafo de f (x) sobre la regin [x1 , x2 ] est por
encima de la cuerda, por lo tanto f(x) no es convexa sobre D.

1.8. NOCIONES BSICAS DE CONVEXIDAD

25

fx 2

1 fx 1 + fx 2
fx 1

f1 x 1 + x 2

x1

x2

Figure 1.15: Funcin convexa

f(x)

x1

x2

Figure 1.16: Funcin no convexa

Al observar los grficos de funciones convexas y no convexas, se deduce la siguiente propiedad:
Proposicin 4 Si la funcin f(x) es diferenciable y convexa sobre D, entonces la tangente en
cualquier punto de f(x) no podr exceder a f(x) para cualquier x en el dominio (ver Figura 1.17).
df(x)
Es decir, para que f(x) sea convexa, f (x) f (x) +
(x x), x, x D.
dx
Proposicin 5 La suma de funciones convexas es tambin convexa.
Demostracin. Sean f1 y f2 las funciones. Sea x1 , x2 D, y 0 1, tal que
f1 ((1 )x1 + x2 ) (1 )f1 (x1 ) + f1 (x2 )
f2 ((1 )x1 + x2 ) (1 )f2 (x1 ) + f2 (x2 ).
Sumando obtenemos
f1 ((1 )x1 + x2 ) + f2 ((1 )x1 + x2 ) (1 )f1 (x1 ) + f1 (x2 ) + (1 )f2 (x1 ) + f2 (x2 ).
Si f1 (x) + f2 (x) = g(x) entonces g((1 )x1 + x2 ) (1 )g(x1 ) + g(x2 ). Por lo tanto g(x), es
decir f1 (x) + f2 (x), es convexa.

26

CHAPTER 1. INTRODUCCIN

f (x)
f ( x) +

df ( x)
( x x)
dx

Figure 1.17: Tangente de funcin convexa

R

( x, r )

f (x)

Figure 1.18: Epgrafo de la funcin f(x)

Anlogamente, es fcil demostrar que una funcin convexa multiplicada por cualquier parmetro
positivo sigue siendo convexa.
Definicin 8 (Funcin cncava) Sea f(x) : D R, con D convexo. Entonces, f(x) es cncava
sobre D si:
f((1 )x1 + x2 ) (1 )f(x1 ) + f (x2 )

x1 , x2 D, [0, 1] .

As, resulta claro que si f(x) es una funcin convexa, entonces f (x) ser una funcin cncava.
Proposicin 6 Si D es convexo, f : D R es convexa sobre D si y solo si el epgrafo de f sobre
D, ED (f) = {(x, r) : x D, r f (x)} , es una parte convexa de Rn R. Ver Figura 1.18.
Proposicin 7 Sean D Rn convexo, y fi (x) i = 1, ..., p convexas sobre D, entonces f (x) =
max {fi (x)} define una funcin convexa sobre D.

1.8. NOCIONES BSICAS DE CONVEXIDAD

27

f2

ED ( f )
f3

f1

Figure 1.19: Interseccin de epgrafos

Demostracin. Dado que la interseccin (cualquiera) de conjuntos convexos es un conjunto
convexo, podemos decir:
f(x) =
ED (f) =

max {fi (x)}

i=1,...,p
pi=1 ED (fi ).

Como cada uno de los epgrafos de las funciones fi (x) es convexo, su interseccin tambin lo es.
As, ED (f ) es convexo, por lo que f(x) es convexa sobre D (ver Figura 1.19).
Las funciones convexas presentan favorables propiedades al optimizar. Por ejemplo, un punto
mnimo local es siempre mnimo global. Sin embargo, no necesariamente este ptimo ser nico.
Por ejemplo, la funcin f (x) en la Figura 1.20 tiene varias soluciones ptimas.
f(x)

Conjunto de soluciones ptimas

Figure 1.20: Ejemplo de mltiples soluciones ptimas

As, surge la necesidad de definir las funciones estrictamente convexas.
Definicin 9 (Funcin estrictamente convexa) Sea f(x) : D R, con D convexo. Entonces,
f(x) es estrictamente convexa sobre D si:
f ((1 )x1 + x2 )) < (1 )f (x1 ) + f(x2 )

x1 , x2 D, [0, 1] .

28

CHAPTER 1. INTRODUCCIN

Es decir toda funcin estrictamente convexa es tambin convexa. En forma anloga se definen
las funciones estrictamente cncavas.
La Figura 1.21a presenta una nueva funcin convexa, pero no estricta. Cabe mencionar que
toda funcin lineal f(x) = ax + b es cncava y convexa a la vez, pero ni estrictamente cncava ni
estrictamente convexa. Por otra parte, la Figura 1.21b muestra una funcin que no es ni cncava
ni convexa, pero que localmente cerca de x1 es cncava y localmente cerca de x2 es convexa.
f(x)

f(x)

x1

x2
(b)

(a)

Figure 1.21: Casos especiales de funciones

A continuacin se demostrar que si f(x) es convexa, entonces el lugar geomtrico de los puntos
que satisfacen f(x) debe constituir un conjunto convexo para cualquier .
Proposicin 8 Si : D R, D Rn , D convexo, convexa, entonces los conjuntos de nivel
C () = {x D/(x) } son convexos R .
Demostracin. Sean x1 , x2 C (), con R fijo, y [0, 1] . Mostremos que (1 )x1 +
x2 C (). Si x1 y x2 C () x1 , x2 D, y
(x1 ) y

(x2 ) .

(1.3)

Como D es convexo (1 )x1 + x2 D, [0, 1] y como () es convexa sobre D, entonces

((1 )x1 + x2 ) (1 )(x1 ) + (x2 ). Por lo tanto de (1.3) tenemos que ((1 )x1 + x2 )
(1 ) + = . As, (1 )x1 + x2 C ().
Corolario 9 Si el dominio de restriccin est definido como: D = {x Rn : gi (x) 0, i =
1, . . . , m} con gi : Rn R funciones convexas, entonces D es una parte convexa de Rn .
Demostracin. Dado que las funciones gi (x) son convexas, las regiones definidas por las restricciones gi (x) 0 son tambin convexas (conjuntos de nivel). El dominio D queda definido como
la interseccin de las regiones de puntos definidos por cada una de las m restricciones, formalmente
D = m
i=1 C0 (gi ). Como cada uno de las regiones C0 (gi ) es convexa y la interseccin de conjuntos
convexos es convexa, entonces D es convexo.
Es importante destacar que restricciones del tipo hi (x) = 0, slo definen regiones convexas si la
funcin es lineal (no basta que hi (x) sea convexa).

1.8. NOCIONES BSICAS DE CONVEXIDAD

29

Figure 1.22: Dominio D formado por semi-espacios

Caso particular: Si tenemos restricciones lineales del tipo gi (x) = ai x bi (funciones lineales
son cncavas y convexas a la vez), entonces D es un poliedro convexo (interseccin finita de semiespacios, ver Figura 1.22). Las funciones convexas no son las nicas en satisfacer que el lugar
geomtrico de los puntos que cumplen con f(x) son conjuntos convexos, para cualquier .
Existen muchas funciones que satisfacen la propiedad sin ser convexas. Al conjunto de funciones
que satisface esta propiedad se le denomina funciones cuasi-convexas. Alternativamente, estas
funciones pueden describirse del siguente modo:
Definicin 10 (Funcin cuasi-convexa) Si D es una parte convexa de Rn , una funcin f :
D R se dice cuasi-convexa sobre D si:
f(z) max{f (x), f(y)}

x, y D, x = y, z ]x, y[.

Es decir, tomando cualquier par de puntos en el dominio, todos los puntos en la recta que los
une tendrn una imagen no superior a las imgenes de los dos puntos. Cuando f (x) es una funcin
cuasi-convexa, sta posee a lo ms un valle, como es el caso de la funcin cuasi-convexa de la Figura
1.23. Es importante notar que esta funcin no es convexa.
f(x)

x
D convexo

Figure 1.23: Funcin cuasi-convexa

Una caracterstica importante de las funciones cuasi-convexas radica en que un mnimo local de
estas funciones es siempre tambin su mnimo global. Como se mencion anteriormente, otra caracterstica importante es que para toda funcin f(x) cuasi-convexa se cumple que el lugar geomtrico

30

CHAPTER 1. INTRODUCCIN

de los puntos tal que satisfacen f(x) a conforman necesariamente un conjunto convexo. As, un
conjunto definido por una serie de restricciones del tipo fi (x) ai en que todas las funciones fi (x)
son cuasi-convexas es un conjunto convexo.

Definicin 11 (problema convexo) El problema de minimizacin

P)

M in f(x)
x D.

se dice convexo, si D es una parte convexa de Rn y f(x) es convexo sobre D.

Es importante notar que basta una variable discreta que incida en el conjunto D para que ste
no sea convexo. Por ende los problemas con variables discretas tpicamente no son convexos.

Proposicin 10 Si P ) es convexo, todo punto mnimo local del problema es tambin su ptimo
global.
Demostracin. Sea x
punto mnimo local de P ). Entonces definamos un conjunto vecindad de
x
que denominaremos B(
x, R) en que todos los puntos del conjunto estn a una distancia menor a R
de x
y tal que f(
x) f(x) x DB(
x, R); de otro modo x
no sera mnimo local. Supongamos que
x
no es mnimo global. En ese caso existira un punto z D (
z = x
) tal que f(
z ) < f (
x). Definimos
ahora el conjunto de puntos en la recta entre x
y z como: y() = (1 )
x +
zD
[0, 1] .
Todos estos puntos pertenecen a D pues x
D, z D y D es convexo.
Entonces

i) debe existir un suficientemente pequeo tal que , y() B(

x, R), y por lo tanto, f (y()) >
f(
x)
Sin embargo,
ii) f(x) es convexa f(y()) (1 )f(
x) + f (
z ), y como f(
z ) < f(
x), esto implicara que
f(y()) f(
x) lo que contradice el punto i) anterior.
As, se demuestra que x
debe ser un punto mnimo global de P ).

Esta propiedad de los problemas convexos es altamente deseable, pues permite focalizar el
objetivo en encontrar un punto localmente ptimo. Esto se traduce en que dado un punto candidato
a ptimo global del problema, no importa cuan grande sea el dominio, nos basta compararlo con
los puntos de su vecindad inmediata para determinar su optimalidad. Por ltimo,

Proposicin 11 Corolario 12 Si f (x) es estrictamente convexa sobre D (convexo), entonces

todo punto mnimo local de f(x) es tambin su nico mnimo global.

1.8. NOCIONES BSICAS DE CONVEXIDAD

1

31
3

Figure 1.24: Determinantes menores de una matriz

1.8.3

Criterios prcticos de convexidad de funciones

Sea f(x) = f(x1 , x2 , ..., xn ) continua y dos veces diferenciable. Su matriz Hessiana ser:

H=

2f
x21
2f
x2 x1

..
.

2f
x1 x2
2f
x22

2f
xn x1

...
..

2f
x1 xn

.
2f
x2n

la cual es una matriz simtrica. La Figura 1.24 muestra las matrices menores de esta matriz, cuyos
determinantes se denominarn i .
Definicin 12 Caracterizacin de la matriz Hessiana
1. Si todos los determinantes de las matrices menores son estrictamente positivos (i > 0)
H se dir definida positiva. Esto significa que para cualquier vector d en Rn se cumple
que dT Hd > 0.
2. Si todos los determinantes de las matrices menores son no negativos (i 0) H se dir
semidefinida positiva. Esto significa que para cualquier vector d en Rn se cumple que dT Hd
0.
3. Si los determinantes de las matrices menores impares son estrictamente negativos y los de
las matrices menores pares estrictamente positivos (1 < 0, 2 > 0, 3 < 0, ...,) H es
definida negativa. Esto significa que para cualquier vector d en Rn se cumple que dT Hd < 0.
4. Si los determinantes de las matrices menores impares son no positivos y los de las matrices
menores pares no negativos (1 0, 2 0, 3 0, ...,) H es semidefinida negativa.
Esto significa que para cualquier vector d en Rn se cumple que dT Hd 0.
Sea f() dos veces diferenciable sobre D, con D Rn y convexo. Entonces f() es convexa sobre
D si y solo si D2 f(x) = H es semidefinida positiva x D. Es decir, dT D2 f(x)d 0, d Rn ,
x D.

32

CHAPTER 1. INTRODUCCIN
Ejemplo: Sea f(x1 , x2 ) = 2x1 3x2 + x41 + x1 x2 + x22 . Las derivadas parciales son:
f
x1
f
x2

= 2 + 4x31 + x2
= 3 + x1 + 2x2

y las segundas derivadas seran:

2f
= 12x21
2
x1

2f
=1
x1 x2

2f
=1
x2 x1

2f
= 2.
x22

De esta forma, la matriz Hessiana es:

H=

12x21 1
1
2

Los determinantes menores son 1 = 12x21 , no negativo para

 todo punto del dominio, y 2 =
1
1
2
2
24x1 1. Pero, 2 0? Slo si x1 24 , es decir, si |x1 | 24
.

x2
D

1
24

1
24

x1

Figure 1.25: Dominio de f(x1 , x2 )

Es importante destacar que f(x) no es convexa sobre toda la regin achurada en la Figura
1.25, ya que esta regin no es convexa. Asimismo, basta que la funcin
 sobre un dominio
  sedefina
1
1
convexo que incluya alguna regin no achurada (algn punto en 24 , 24 para que la funcin
no sea convexa pues el Hessiano no sera semidefinido positivo).
Proposicin 13 Si D es una parte convexa de Rn y D2 f(x) es definida positiva, es decir, dT D2 f(x)d >
0, d Rn , d = 0, entonces f (x) es estrictamente convexa sobre D.
En el ejemplo anterior, f() es estrictamente convexa sobre toda regin convexa contenida en
la regin x1 < 1
o en la regin x1 > 124 ; x2 R. Estas regiones excluyen explcitamente a los
24
puntos en que x1 = 1
x1 = 124 (ver Figura 1.26).
24
Es importante destacar la causalidad de esta proposicin: si el Hessiano es definido positivo,
entonces la funcin es estrictamente convexa, pero no al revs. Es decir, si f(x) es estrictamente
convexa y dos veces diferenciable en una regin, no implica que D2 f (x) sea definida positiva en
la regin. Por ejemplo, si f(x) = x4 que es estrictamente convexa, D2 f(x) = 12x2 no es definida
positiva en x = 0.

1.8. NOCIONES BSICAS DE CONVEXIDAD

33

x2
D

1
24

1
24

x1

Figure 1.26: Dominio no convexo de f(x1 , x2 )

Ejemplo: Considere el siguiente problema de optimizacin:

P)
s.a

min x2 + y 2 + z 2 6000(x + y + z)
x + 2y + 4z 4000
x, y, z 0

Tenemos un problema con funcin objetivo cuadrtica, estrictamente convexa. Veamos su matriz
Hessiana para comprobar esto.

2 0 0

D2 f(x, y, z) = 0 2 0 = H
0 0 2
Por lo tanto, H es definida positiva (constante), y como D es un dominio acotado, cerrado y no vaco,
entonces por el Teorema de Existencia tenemos que P ) admite solucin ptima. Como observamos
que H es definida positiva en cualquier punto, decimos que f () es estrictamente convexa. Como
adems el dominio es convexo, decimos que el problema admite solucin ptima nica.
Ejemplo: En una fbrica de chocolates necesitan determinar el precio de venta ptimo para su
producto de modo de maximizar la utilidad obtenida. El precio no puede superar el precio de 60c/
de un producto de la competencia. El costo de produccin de la barra es de 8, 5c/, y la demanda se
representa mediante la funcin f (P ) = 1000
, donde P es el precio de venta expresado en centavos.
P2
De esta forma, la formulacin del modelo sera:
P)

Max(P 8, 5)(

s.a

8, 5 P 60

1.000
)
P2

Existe un precio ptimo? S, pues f (P ) es continua sobre el intervalo [8, 5; 60] , cerrado, acotado
y no vaco (notar que el dominio es convexo). La condicin de primer orden es:
df(P )
1
= 3 (17.000 1.000P ) = 0
dP
P

34

CHAPTER 1. INTRODUCCIN

de la cual se obtiene P = 17c/ como un punto de derivada nula y por lo tanto posible precio
ptimo. A continuacin es necesario analizar la convexidad de f (P ) para ver si P corresponde
efectivamente a un mximo. Para esto se analiza la segunda derivada de f(P ),
f (P ) = 2.000P 3 51.000P 4 .

(1.4)

f (P )
Es d dP
0 P [8, 5; 60]? No, si se iguala (1.4) a cero se obtiene que en P = 25, 5 hay un
2
cambio de signo en la segunda derivada de f (P ), donde f (P ) < 0 si P < 25, 5 y f (P ) > 0 si
P > 25, 5. Por lo tanto, P ) es no convexo globalmente (ver Figura 1.27). Por lo anterior se deduce
que en P = 17c/ la funcin es cncava localmente, por lo cual este precio corresponde a una solucin
ptima local. Para garantizar que la solucin es ptima global se puede argumentar que la funcin
es estrictamente decreciente para valores superiores a P = 17c/ por lo que este precio maximiza la
utilidad (

v = 29, 4c/).

f (P )
Cambio de convexidad

17,5

25,5

Figure 1.27: Convexidad de la funcin de utilidad f(P )

1.9

Problemas resueltos

Problema 14 (Equivalencia) Considere el siguiente problema y escriba uno equivalente que sea
diferenciable en el dominio.
P ) Max ln(|x1 + x2 + 1|)1
s.a.

x1 + 2x2 5
x1 , x2 0

Solucin:
Aplicando la regla I de Problemas equivalentes (y reglas bsicas de logaritmos) transformamos
P en un problema de minimizacin.
P ) Min ln(|x1 + x2 + 1|)
x D

1.9. PROBLEMAS RESUELTOS

35

Utilizando la equivalencia V aplicamos una funcin g(y) = ey que es creciente x, para eliminar el
ln . Luego:
P ) Min |x1 + x2 + 1|
x D
Y aplicando la regla II llegamos a
P ) Min
s.a.
x1 + x2 + 1
x1 x2 1
x1 + 2x2 5
x1 , x2 0
Problema 15 Se quiere instalar una antena de telecomunicaciones, cuya cobertura incluya a cinco
ciudades aledaas de ubicaciones (xi , yi , zi ). Para lograrlo se debe buscar una posicin en el que la
intensidad de la seal sea lo mayor posible para las ciudades, sin salir de los ciertos lmites dados
( (x, y, z) D). Adems se sabe que la intensidad en cierta ciudad es proporcional a la potencia
de la antena (k), e inversamente proporcional a la distancia desde la antena hasta la ciudad. En
qu ubicacin debe instalarse la antena? Modele un problema de optimizacin que sea diferenciable
en el dominio.
Solucin:

La intensidad de la antena en la ciudad de posicin

xi ser
k

Ii (
x)
,

|x
xi |

es decir, Ii (
x) 
2
(z zi ) + (x xi )2 + (y yi )2

As la intensidad de la seal que recibe la ciudad con menor cobertura ser

I(
x ) = min Ii (
x)
i=1...5

As el modelo de optimizacin ser

Max
x D I ( x ) = Max
x D

k
min 
2
i=1...5
(z zi ) + (x xi )2 + (y yi )2

que se puede reescribir como

Max
x D

I (
x ) = Min
x D

k
max 
2
i=1...5
(z zi ) + (x xi )2 + (y yi )2

36

CHAPTER 1. INTRODUCCIN
Esto es equivalente al problema
Min
k

, i = 1...5
(z zi )2 + (x xi )2 + (y yi )2

x D,
R

s.a.

Problema 16 Considere los siguientes problemas de optimizacin, y escriba uno equivalente que
sea diferenciable en el dominio.





Max 7x3 + x2 + y  min x2 , |x + y|

(a)

s.a.

(b)

x3 + 8y 2 250,

x0


 


Maxx0 min x2 7x 10 , min x3 4x, x4 7

Solucin:
(a)






Max 7x3 + x2 + y  min x2 , |x + y|




Min 7x3 + x2 + y  min x2 , |x + y|


s.a.
(x, y) D, conD = (x, y) / x3 + 8y 2 250, x 0




Min 7x3 + x2 + y  + max x2 , |x + y|
s.a.

(x, y) D

Min 1 + 2 + 3


s.a.
7x3 1 , x2 + y  2 ,


max x2 , |x + y| 3 , (x, y) D, i R i

Min 1 + 2 + 3
s.a.

7x3 1 , x2 + y 2 , x2 y 2 ,

x2 3 , |x + y| 3 , (x, y) D, i Ri

Min 1 + 2 + 3
s.a.

7x3 1 , x2 + y 2 , x2 y 2 ,

x2 3 , x + y 3 , (x + y) 3 ,
(x, y) D, i R i

(1.5)

1.9. PROBLEMAS RESUELTOS

37

(b)


 


M axx0 min x2 7x 10 , min x3 4x, x4 7

 


M inx0 min x2 7x 10 , min x3 4x, x4 7




M inx0 max x2 7x 10 , min x3 4x, x4 7




M inx0 max x2 7x 10 , max x3 + 4x, x4 + 7
M in
s.a.

 2

x 7x 10 , x3 + 4x ,
x4 + 7 , x 0, R

M in
s.a.

x2 7x 10 , (x2 7x 10) ,

x3 + 4x , x4 + 7 , x 0, R

Problema 17 Considere el siguiente problema de optimizacin, y escriba uno equivalente que sea
diferenciable en el dominio.
Max





1 
ln 7x3 + x2 + y  min x2 , |x + y|
2
s.a.
x3 + 8y 2 250, x 0

Solucin:





1/2
Min ln 7x3 + x2 + y  min x2 , |x + y|


s.a.
(x, y) D, conD = (x, y) / x3 + 8y 2 250, x 0

Utilizando la funcin estrictamente creciente ex se obtiene





1/2
Min 7x3 + x2 + y  + max x2 , |x + y|
s.a.

(x, y) D.

Luego utilizando la funcin estrictamente creciente en x 0, x2 se obtiene






Min 7x3 + x2 + y  + max x2 , |x + y|

s.a.

(x, y) D.

Este problema es el mismo que se describe en la Ecuacin 1.5, y puede ser resuelto del modo
ah expuesto. Otras funciones estrictamente crecientes de inters: ln x, 1/x, ex , etc.

38

CHAPTER 1. INTRODUCCIN
A
B

Figure 1.28:
Problema 18 (Convexidad (I21 03)) Responda:
(a) Qu condiciones debe cumplir un problema para ser denominado convexo?
(b) Por qu interesa verificar si un problema es convexo?
(c) Si una funcin definida sobre un conjunto A convexo, es convexa, entonces definida sobre
un conjunto B A tambin lo es?
Solucin:
(a) Debe tener una funcin objetivo convexa sobre un dominio convexo.
(b) Porque esto garantiza que un ptimo local sea global.
(c) No, ya que B debe ser convexa tambin. Por ejemplo, como vemos en la figura 1.28,
B A, pero el conjunto A es convexo y B no lo es.
Problema 19 (Convexidad) Comente acerca de la convexidad de la funcin f(x, y) = 2x2 +
3y 2 y 3 .
Solucin: Para poder entender la convexidad de esta funcin lo primero que hacemos es
identificar su Hessiano:
f
x
f
y
entonces
H=

= 4x
= 6y 3y 2


4
0

0
6 6y

con lo que 1 = 4, 2 = 24 24y, por lo que el Hessiano es semi definido positivo x R, y 1

y por lo tanto la funcin es convexa en esta regin. Al excluir el borde y = 1 (x R, y < 1) el
Hessiano se vuelve definido positivo y la funcin, estrictamente convexa.
Problema 20 (Caracterizacion de soluciones) Encuentre y caracterice la(s) solucin(es) p-

1.9. PROBLEMAS RESUELTOS

39

tima(s) del siguiente problema:

P ) Min f(x, y, z) = x2 + y 2 + z 2 + xz + yz
(x, y, z) R3
Solucin:
f
x
f
y
f
z

= 2x + z = 0
= 2y + z = 0
= 2z + x + y = 0

Por lo tanto hay slo un punto extremo: x = (0, 0, 0)

Veamos el Hessiano:

2 0 1

H = 0 2 1
1 1 2

1 = 2 > 0, 2 = 4 > 0, 3 = 4 > 0 = H es positivo definido. Por lo tanto, f (x, y, z) es

estrictamente convexa en todo el dominio, por lo tanto x = (0, 0, 0) es un mnimo global estricto.
Problema 21 Considere la funcin
f (x, y) = 2x3 + y + 20.
a)Existe alguna regin en que f(x, y) sea definida positiva?
b)Existe alguna regin en que f(x, y) sea semidefinida positiva?
c)Existe alguna regin en que f (x, y) sea semidefinida negativa?
Solucin:
En primer lugar se ve que
f
= 6x2
x

f
=1
y

H=

12x 0
0 0

a) Se necesita i > 0. En este caso 1 = 12x > 0 x > 0, pero 2 = 0 por lo que nunca
podr ser definida positiva.
b) Se necesita i 0.Esto se cumple x 0.
c) Se necesita 2i1 0 y 2i 0. Esto se cumple x 0.

Problema 22 Qu condiciones deben cumplir los parmetros a y b para que un punto de la

funcin
f(x, y) = x2 + axy + by 2 + x + y

40

CHAPTER 1. INTRODUCCIN

cumpla con las condiciones necesarias, pero no suficientes para ser mnimo?
Solucin:
i) Condicin necesaria de 1er orden:
f
x
f
y

= 2x + ay + 1 0
= ax + 2by + 1 0

ii) Condicin necesaria de 2do orden:

H=

2f
x2
2f
yx

2f
xy
2f
y2

2 a
a 2b

Para que se cumpla la segunda condicin necesaria, se necesita que H sea semidefinida positiva
(i 0). En este caso 1 = 2 > 0 y se necesita 2 = 4b a2 0.
iii) Condicin suficiente: H definida positiva (i > 0). En este caso 1 = 2 > 0 y se necesitara
2 = 4b a2 > 0.
= Para que se cumpla ii) pero no iii) se necesita: 4b a2 = 0 4b = a2
Problema 23 Responda las siguientes preguntas:
a) Sean f (x) y g(x) funciones convexas. Es el siguiente problema de optimizacin convexo?
Min

f(x)
s.a. g(x) 0

b) Demuestre que si el dominio de restricciones est definido como

D = {x Rn : gi 0, i = 1...m}
donde gi : Rn R son funciones convexas, entonces D es una parte convexa de Rn .
c) Comente acerca de la convexidad de la funcin
f(x, y) = 2x2 + 3y 2 y 3 .
d) Qu condiciones debe cumplir un problema para ser denominado convexo?
e) Si una funcin definida sobre un conjunto A convexo, es convexa, entonces definida sobre un
conjunto B A tambin lo es?
f) Encuentre y caracterice las soluciones ptimas del siguiente problema
M in

f (x, y, z) = x2 + y 2 + z 2 + xz + yz
s.a.(x, y, z) R3

1.9. PROBLEMAS RESUELTOS

41

Solucin:
a) Para que el problema sea convexo, f (x) debe ser convexa y las restricciones deben formar
un dominio convexo. En este caso, pese a g(x) ser convexa, el dominio no necesariamente lo es.
Ver Figura 1.29. As el problema de optimizacin no necesariamente es convexo.

Figure 1.29: Ejemplo de dominio no convexo

b) Si gi (x) es una funcin convexa, entonces el conjunto gi (x) 0 es convexo. Adems se sabe
que la interseccin de conjuntos convexos, es un conjunto convexo = D es convexo.
c) En primer lugar se ve que
f
= 4x
x

f
= 6y 3y 2
y

H=

4
0
0 6 6y

En y = 1, el hessiano es semidefinido positivo, por lo que la funcin es convexa en la regin y 1.

Podemos agregar que en la regin y < 1, la funcin es estrictamente convexa.
d) Para que el problema sea convexo, f(x) debe ser convexa y estar definida sobre un dominio
D convexo. Para que la funcin objetivo sea convexa se requiere que
f (x1 + (1 )x2 ) f(x1 ) + (1 )f(x2 )

x1 , x2 D; [0, 1]

e) El conjunto B A no necesariamente es convexo, por lo que la funcin definida en el dominio

B no necesariamente sera convexa.
f) En primer lugar buscamos los puntos candidatos a solucin ptima utilizando las primeras
derivadas, donde se obbtiene
f
= 2x + z 0,
x
Despejando este sistema, se
hessiano

2 0

H= 0 2
1 1

f
= 2y + z 0,
y

f
= 2z + x + y 0
z

encuentra el punto candidato (x, y, z) = (0, 0, 0). Luego se estudia el

1 1 = 2 > 0, 2 = 4 > 0, 3 = 4 > 0

2

x, y, z

42

CHAPTER 1. INTRODUCCIN

As H es definida positiva en todo el dominio, por lo que la funcin objetivo es estrictamente

convexa. Esto implica que el punto (0,0,0) es un mnimo global.
Problema 24 Encuentre y caracterice las soluciones ptimas del siguiente problema:
f (x, y) = 2x3 + 3x2 12x + 2y 2 8y
Solucin:
Las derivadas parciales son
f
= 6x2 + 6x 12 0,
x

f
= 4y 8 0
y

Resolviendo este sistema, se obtienen los puntos candidatos (1, 2) y (2, 2). Para caracterizar estos
puntos se estudia el hessiano, dado por
H=

12x + 6 0
0
4

As el primer punto ser un mnimo local estricto, y el segundo no es caracterizable. Al observar el

hessiano se puede apreciar que la funcin es convexa en la regin x 1/2.
Problema 25 Encuentre y caracterice las soluciones ptimas de la funcin
f (x, y) = sin x + sin y + sin(x + y)
Solucin:
En primer lugar se buscan los puntos crticos por medio de las primeras derivadas, que son
f
= cos x + cos(x + y) 0,
x

f
= cos y + cos(x + y) 0
y

Se ve que los puntos crticos son tales que cos x = cos y, es decir donde x = y + 2n, n=0,1,2...
Despejando para x, se obtiene 2 cos2 x + cos x 1 = 0 , considerando que cos 2x = 2 cos2 x 1 y
que cos(x 2n) = cos x. As los puntos crticos sern las soluciones de esta ecuacin cuadrtica,
y sern cos x = 1 y cos x = 1/2. Es decir, x = , /3, 5/3 (Y sus respectivos perodos 2m,
m=0,1,2... ). As los puntos crticos sern
( + 2m, + 2n) , (/3 + 2m, /3 + 2n) , (5/3 + 2m, 5/3 + 2n)
Para determinar la naturaleza de estos puntos, se calcula el hessiano resultando
H=

sin x sin(x + y)
sin(x + y)
sin(x + y)
sin y sin(x + y)

Luego ste se evala en los puntos crticos:

1.9. PROBLEMAS RESUELTOS

43

i)
H=

0 0
0 0

Se podra decir que el hessiano es semidefinido positivo y/o negativo. As, no se puede caracterizar
este punto.
ii)



3 2 3

H=

3 < 0, 2 = 3 3/4 = 9/4 > 0

1
3
3
2
As en el segundo punto crtico, el hessiano es definido negativo, por lo que el punto corresponde a
un mximo local estricto, n, m.
iii)



3 23
H = 3
= 1 = 3 > 0, 2 = 3 3/4 = 9/4 > 0
3
2
As en el tercer punto crtico, el hessiano es definido positivo, por lo que el punto corresponde a un
mnimo local estricto, n, m.