SEMI_27_7_21

Vista previa del material en texto

Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Convex Analysis for Optimization
Jan Brinkhuis
Villalba Salazar, Raul Moises
Prof. Alex Armando Cruz Huallpara
Seminario I
27 de julio del 2021
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Capítulo 5: Funciones convexas - propiedades básicas
1 Abstract
2 Mapa vial
3 Motivación
4 Descripción de conjuntos convexos
5 ¿Por qué pueden surgir funciones convexas que no son
agradables en las aplicaciones?
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Abstract
¿Por qué?. Un segundo objeto principal del análisis convexo es una
función convexa. Las funciones convexas pueden ayudar a describir
conjuntos convexos: estos son conjuntos infinitos, pero a menudo
pueden describirse mediante una fórmula para una función convexa,
es decir, en términos finitos. Además, en muchas aplicaciones de
optimización, la función que debe minimizarse es la convexa y luego
la convexidad se utiliza para resolver el problema.
¿Qué?. En los capítulos anteriores, hemos invertido mucho tiempo
y esfuerzo en conjuntos convexos y conos convexos, demostrando
todas sus propiedades estándar. Ahora hay buenas noticias. No es
necesario establecer más propiedades esencialmente nuevas en el
resto de este libro. Queda por cosechar las recompensas.
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Abstract
En los Capítulos. 5 y 6, consideramos comenzar con funciones con-
vexas: las propiedades duales en el Cap. 6, y las propiedades que no
requieren dualidad, las propiedades primarias de este capítulo. Es-
to requiere conjuntos convexos: las funciones convexas son funcio-
nes especiales en conjuntos convexos. Aún mejor, pueden expresarse
completamente en términos de conjuntos convexos: las funciones
convexas son funciones para las cuales el epígrafo, es decir, la región
por encima del gráfico, es un conjunto convexo. Algunas propieda-
des de las funciones convexas se derivan inmediatamente de una
propiedad de un conjunto convexo, aplicada al epígrafo.
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Abstract
Un ejemplo es la propiedad de continuidad de las funciones con-
vexas. Para otras propiedades, se requiere una investigación más
profunda: se debe tomar la homogeneización del epígrafo, y luego
se debe aplicar una propiedad de los conos convexos. Un ejemplo es
la construcción unificada de las ocho operaciones binarias estándar
en funciones convexas (suma, máximo, casco convexo del mínimo,
convolución infimal, suma de Kelley) mediante el método de ho-
mogeneización. Las fórmulas que los definen se ven completamente
diferentes entre sí, pero todas pueden generarse exactamente de la
misma manera sistemática mediante una reducción a conos convexos
("homogeneización").
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Abstract
Uno tiene para las funciones convexas el mismo problema técnico
que para los conjuntos convexos: todas las funciones convexas que
ocurren en las aplicaciones tienen las agradables propiedades de ser
cerradas y adecuadas, pero si trabaja con ellas y crea nuevas funcio-
nes a partir de ellas, entonces podrían perder las propiedades. Dos
ejemplos de tal trabajo son: (1) la consideración, en un análisis de
sensibilidad para un problema de optimización, de la función de va-
lor óptimo, y (2) la aplicación de una operación binaria. Finalmente,
dos funciones continuamente diferenciables f (x) son convexas si su
Hessiana f (2) es semidefinida positiva para todo x.
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Mapa vial
1. Definiciones 5.2.1, 5.2.4, 5.2.6, 5.2.9 y 5.2.10 (función convexa,
definida por la desigualdad de Jensen o por la convexidad de un
conjunto: su epígrafo (estricto)).
2. Proposición 5.3.1 (propiedad de continuidad de una función con-
vexa).
3. Proposiciones 5.3.6, 5.3.9 (caracterizaciones de primer y segundo
orden de funciones convexas).
4. Figura 5.7 y Definición 5.4.2 (función convexa de construcción
por homogeneización).
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Mapa vial
5. Definiciones 5.2.12, 5.3.4 (dos buenas propiedades para las fun-
ciones convexas, lo cerrado y lo correcto).
6. Definiciones 5.5.1, 5.5.2 (las dos acciones de funciones lineales
sobre funciones convexas).
7. Figura 5.8, Definición 5.6.1, Proposición 5.6.6 (operaciones bina-
rias en funciones convexas (suma puntual, máxima puntual, casco
convexo de mínimo puntual, convolución infimal, suma de Kelley ,
definidas por fórmulas y construidas por homogeneización).
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Motivación
El objetivo de esta sección es motivar el con-
cepto de función convexa.
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Descripción de conjuntos convexos
El objetivo de esta sección es dar dos ejemplos de cómo un conjunto
convexo, que suele ser un conjunto infinito, puede describirse me-
diante una función, que a menudo se puede describir en términos
finitos: mediante una fórmula.
Ejemplo 5.1.1 (Un conjunto convexo cerrado ilimitado visto
como un epígrafo)
Suponga que A ⊆ X = Rn es un conjunto convexo cerrado ilimitado.
Entonces tiene un vector de recesión v distinto de cero. Suponga que
−v no es un vector de recesión para A. Entonces podemos ver A
como un epígrafo, es decir, como la región sobre la gráfica de una
función. La figura 5.1 ilustra cómo se puede hacer esto.
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Figura: Fig. 5.1 Conjunto convexo cerrado ilimitado visto como un
epígrafo
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
He aquí una descripción precisa. Sea L el hiperplano en X que pasa
por el origen ortogonal a v , es decir,
L = v⊥ = {x ∈ X | x · v = 0}
Sea B ⊆ L la imagen de A bajo la proyección ortogonal de X sobre
L. Luego ponemos f (x) = ḿın {ρ|x + ρv ∈ A} para cada x ∈ B.
Esto está bien definido: según la definición de B, existe un número
ρ ∈ R tal que x +ρv ∈ A; como −v no es una dirección de recesión
de A, el conjunto de talesnúmeros ρ está acotado por debajo; por
la cercanía de A, se deduce que existe un número mínimo ρ. Esto
completa la verificación de que f (x) está bien definida para todo
x ∈ B. Esto da que x + f (x)v ∈ A y que x + ρv ∈ A implica
ρ ≥ f (x).
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Por el contrario, para todo ρ ≥ f (x), tenemos que el punto x +ρv =
(x +f (x)v)+(ρ−f (x))v está en A, ya que x +f (x)v ∈ A y, además,
v es un vector de recesión de A. Entonces obtenemos una función
f : B → R y el conjunto A es el subconjunto de X que consta de
todos los vectores x + ρv donde (x , ρ) corre sobre el epígrafo de f ,
epi f = {(x , ρ) | x ∈ B , ρ ∈ R , ρ ≥ f (x)}
De esta manera, el conjunto convexo A se describe completamente
en términos de la función f : es esencialmente el epígrafo de f . La
función f se llama función convexa ya que su epígrafo es un conjunto
convexo. Además, f se denomina semicontinua inferior o cerrada
ya que su epígrafo es un conjunto cerrado. Hay muchas funciones
definidas por una fórmula, es decir, en términos finitos, que pueden
verificarse como funciones convexas, como veremos. Para tal función
f , se obtiene una descripción finita conveniente del conjunto convexo
epi f , el epígrafo de f , por la fórmula de la función f .
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Ejemplo 5.1.2 (Un conjunto convexo cerrado descrito por su
calibre)
La norma euclidiana sobre Rn se puede describir en térmi-
nos de la bola unitaria cerrada estándar Bn como ||x || =
ı́nf
{
t > 0 | xt ∈ Bn
}
. Ahora generalizamos esta construcción. Su-
pongamos que tenemos un conjunto convexo cerrado A ⊆ X = Rn
que contiene el origen en su interior (recuerde que esta condición
puede asumirse para un conjunto convexo cerrado no vacío dado
trasladándolo a una nueva posición de tal manera que un interior
relativo el punto se lleva al origen, y luego se restringe el espacio
de Rn al lapso de la copia traducida del conjunto dado). Entonces
el cierre de c(A), la homogeneización de A, es el epígrafo de una
función pA : X → R+. Uno tiene
pA(x) = ı́nf
{
t > 0 | xt ∈ A
}
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Esta función se llama función de Minkowski o calibre de A. El con-
junto A se puede expresar en términos de esta función por medio
de
A = {x ∈ X |g(x) ≤ 1}
Si g puede ser dado por una fórmula, entonces esto da nuevamente
una descripción finita conveniente del conjunto convexo A: por la
fórmula para su calibre g , una función convexa como su epígrafo
es un cono convexo y por lo tanto un conjunto convexo. La figura
5.2 ilustra esta descripción para el caso de que A esté acotado.
Se dibuja un subconjunto A del plano R2. Es un conjunto convexo
cerrado acotado que contiene el origen en su interior. Algunas flechas
se dibujan desde el origen hasta el límite de A. En tal flecha, el valor
del calibre g de A crece linealmente de 0 a 1.
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Figura: Fig. 5.2 Un conjunto convexo cerrado descrito por su calibre
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Conclusión:
Hemos visto dos métodos para describir conjuntos convexos por me-
dio de funciones; esto es conveniente, ya que las funciones a menudo
se pueden describir mediante una fórmula. Entonces, un infinito (un
conjunto convexo) se captura en términos finitos. El primer méto-
do consiste en ver un conjunto convexo ilimitado con la ayuda de
una dirección de recesión como epígrafo de una función. El segundo
método consiste en describir un conjunto convexo por su calibre.
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
¿Por qué pueden surgir funciones convexas que no son
agradables en las aplicaciones?
En este capítulo, definiremos dos propiedades interesantes, lo ce-
rrado y lo correcto, que poseen todas las funciones convexas que
ocurren en las aplicaciones. Ahora describimos una operación que
debe realizarse en muchas aplicaciones y que conduce a una función
convexa que podría no tener estas dos buenas propiedades. Ésta es
la razón por la que se admite en la teoría de funciones convexas
también funciones que no tienen estas dos bonitas propiedades.
Ejemplo 5.1.3 (La importancia del análisis de sensibilidad)
A veces, la sensibilidad de una solución óptima se considera más
importante que la solución óptima en sí. Supongamos, por
ejemplo, que una empresa quiere iniciar un nuevo proyecto.
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Para empezar, se podrían crear algunos escenarios posibles sobre
cómo hacerlo. Luego, para ayudar a los gerentes responsables a
tomar una decisión, los ingresos esperados menos el costo se
determina para cada escenario, mediante optimización. Es posible
que se sorprenda al saber que los gerentes a menudo no están muy
interesados en comparar las ganancias óptimas de los escenarios.
Están más interesados en evitar escenarios de riesgo. Algunos de
los datos de un problema de optimización para un escenario dado,
como los precios, son inciertos. En algunos escenarios, la
sensibilidad de los beneficios óptimos en los datos es mucho mayor
que en otros. Sea S(y) la ganancia óptima para un escenario dado
si el vector de datos es y . Entonces, la función S se denomina
función de valor óptimo y, por su definición, determina la
sensibilidad del valor óptimo para los cambios y .
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
Abstract Mapa vial Motivación Descripción de conjuntos convexos ¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?
Por tanto, la función de valor óptimo es de gran interés. La función
S es cóncava (es decir, −S es convexa), si las funciones que
describen el problema de optimización para el escenario son
convexas. De hecho, hacer −S con estas funciones convexas es un
operador que preserva la convexidad. En cada aplicación, las
funciones convexas que describen el problema de optimización para
un escenario dado tienen dos buenas propiedades. Sin embargo,
resulta que la función de valor óptimo S no necesita tener estas
dos buenas propiedades.
Seminario I Prof. Alex Armando Cruz Huallpara
Convex Analysis for Optimization
	Abstract
	Mapa vial
	Motivación
	Descripción de conjuntos convexos
	¿Por qué pueden surgir funciones convexas que no son agradables en las aplicaciones?