1. No category

Universidad Politécnica de Madrid
Escuela Técnica Superior de Ingenieros Industriales
Definiciones, notación y
proposiciones básicas
de matemáticas
José Luis de la Fuente O’Connor
[email protected]
[email protected]
Madrid, Curso 2015-2016
E
N ESTA INTRODUCCIÓN a la asignatura Matemáticas de la Especialidad–Ingeniería Eléctrica se recopilan
conceptos, definiciones, relaciones y resultados que puede ser útil recordar o considerar para seguir su desarrollo
de manera provechosa. Todos o casi todos se han estudiado en otras asignaturas de cursos anteriores a aquél en
el que se imparte ésta. En ningún caso es un exhaustivo recordatorio de las matemáticas elementales que debe
conocer un ingeniero industrial. También se introduce una cierta notación que, de forma uniforme, trataremos de usar en
todas las lecciones y presentaciones de las clases.
1 Conjuntos
Un conjunto es una colección de objetos: los números naturales, las soluciones de un problema determinado, los
municipios de una provincia, etc. Se identifica por una letra mayúscula: el conjunto S , el conjunto de los números naturales
N, el de los enteros Z, el de los reales R, complejos C, racionales Q, etc.
Cada uno de los objetos en la colección es un elemento o miembro del conjunto. Si un elemento a pertenece a un conjunto se indica a 2 S . Los conjuntos se definen mediante la enumeración entre llaves de sus elementos, S D fa; b; : : : g,
o especificando, también entre llaves, la propiedad que los caracteriza, S D fx W x 2 R; x 2g: números reales menores
o iguales que dos.
El conjunto sin elementos se denomina vacío, designándose ;. Ejemplo: el conjunto S de los números reales x que
son mayores que 1 y menores que 0: esto es, S D fx 2 R W x > 1; x < 0g.
Si S y S 0 son dos conjuntos y todos los elementos del conjunto S 0 lo son de S , se dice que S 0 es un subconjunto del
conjunto S , o que está contenido en S 0 , expresándose S 0 S o S S 0 .
T.
La unión de dos conjuntos S y T , expresada S [ T , es el conjunto formado por los elementos que pertenecen a S o a
La intersección de S y T , expresada S \ T , es el conjunto formado por los elementos que pertenecen a S y a T .
Si S 0 es un subconjunto de S , el complemento de S 0 en S es el conjunto formado por los elementos de S que no
pertenecen a S 0 .
Si a y b son números reales, y a b, el conjunto de números x de la recta real tales que a x b se indica Œa; b.
El formado por los x tales que a < x b, por .a; b. El de los x que verifican que a < x < b, por .a; b/.
Si S es un conjunto no vacío de números reales acotados superiormente —mayorados—, existe un número real mínimo
y tal que x y para todo x 2 S . Al número y se le denomina cota superior mínima o supremo de S ; se expresa así:
sup .x/
x2S
o
sup fx W x 2 S g :
De forma similar se define la cota inferior máxima —o ínfimo— de un conjunto S no vacío de números reales acotados
inferiormente o minorados:
Kınf .x/ o Kınf fx W x 2 S g :
x2S
2 Aplicaciones
Dados dos conjuntos S y T , una aplicación, transformación o mapeo f de S en T , expresada como f W S ! T , es
una asociación o criterio que a cada elemento de S hace corresponder uno de T .
La imagen de un elemento x 2 S con la aplicación f W S ! T es el elemento f .x/ 2 T . El conjunto imagen
f .S / = ff .x/ 2 T; para todo x 2 S g. La imagen de un subconjunto S 0 S con la aplicación f sería, por consiguiente,
el subconjunto imagen f .S 0 /. El conjunto S se conoce como origen o dominio de definición y el T como dominio de
valores. Una aplicación f W S ! T se dice inyectiva si para cualquier par de elementos x; y 2 S , x ¤ y, se cumple que
f .x/ ¤ f .y/. Ejemplo, la aplicación f W R ! R, definida por f .x/ D x 2 , no es inyectiva, pues f .1/ D f . 1/ D 1.
Una función es un caso particular de aplicación en donde los conjuntos origen e imagen son conjuntos de números: R,
C, Z, N, etc.
Una aplicación f W S ! T se dice suprayectiva —sobreyectiva, epiyectiva, suryectiva o exhaustiva— si el conjunto
imagen f .S / es igual a todo el conjunto T ; es decir, para todo y 2 T existe un x 2 S tal que f .x/ D y.
Una aplicación se dice biyectiva si es inyectiva y suprayectiva. Ejemplo, si Jn es el conjunto de los números enteros
de 1 a n, Jn D f1; : : : ; ng, y se define una aplicación W Jn ! Jn que modifica el orden de disposición de los elementos
de Jn —estas aplicaciones se denominan permutaciones—, tal aplicación es biyectiva.
1
Una función es un caso particular de aplicación en donde los conjuntos origen e imagen son conjuntos de números: R, C, Z, N, etc.
Una aplicación f W S ! T se dice suprayectiva —sobreyectiva, epiyectiva, suryectiva o exhaustiva—
si el conjunto imagen f .S/ es igual a todo el conjunto T ; es decir, para todo y 2 T existe un x 2 S
tal que f .x/ D y.
Una aplicación se dice biyectiva si es inyectiva y suprayectiva. Ejemplo, si Jn es el conjunto de los
números enteros de 1 a n, Jn D f1; : : : ; ng, y se define una aplicación W Jn ! Jn que modifica el
orden de disposición de los elementos de Jn —estas aplicaciones se denominan permutaciones—, tal
Un conjunto S se dice
numerable si existe una biyección entre N y S : a cada unos de los n elementos k, 1 k n,
aplicación es biyectiva.
se le asocia un elemento aUn
S , esto
7! ak . si existe una biyección entre N y S : a cada unos de los n elemenk 2
conjunto
S sees:
diceknumerable
tos k, 1 k n, se le asocia un elemento ak 2 S, esto es: k 7! ak .
Una sucesión de elementos de un conjunto T es una aplicación de N en T : a cada elemento n 1 se le hace corresUna
sucesión de elementos de un conjunto T es una aplicación
de N en T : a cada
elemento n 1
.1/
ponder un x .n/ 2 T : n 7!
x .n/
. Tal
sucesión
fxsucesión
; x .2/se; expresa
: : : g ocomo
fx .n/fxg.1/n1
. ;:::g o
.n/ expresa como
se le
hace
corresponder
un xse
2 T : n 7! x .n/ . Tal
; x .2/
fx .n/ gn1 .
Los conjuntos dotados de ciertas leyes de composición o asociación interna —adición, multiplicación, división o
Los conjuntos dotados de ciertas leyes de composición o asociación interna —adición, multiplicacualquier otra—, se dice
que
poseen
una otra—,
estructura.
Las
estructuras
algebraicas
fundamentales
son grupo, anillo (Z
ción,
división
o cualquier
se dice que
poseen
una estructura.
Las estructuras
fundamentales
grupo,
(Z por ejemplo),
cuerpovectorial.
(R y C, por ejemplo) y espacio vectorial.
por ejemplo), cuerpo (Rson:
y C,
poranillo
ejemplo)
y espacio
R
C
3 Espacios vectoriales
Z
Q
N
4
Un espacio vectorial E es una estructura algebraica creada a partir de un conjunto no vacío, una ley de composición
interna definida para los elementos del conjunto, adición, con la siguientes propiedades —grupo conmutativo—,
xCy DyCx
.x C y/ C z D x C .y C z/
xCøDx
x C . x/ D ø;
y una ley de composición externa, producto por un escalar, definida entre dicho conjunto y otro conjunto, K, con estructura de cuerpo, con las siguientes propiedades,
1x Dx
˛.ˇx/ D .˛ˇ/x
.˛ C ˇ/x D ˛x C ˇx
˛.x C y/ D ˛x C ˛y;
válidas cualesquiera que sean x; y; z en E y ˛; ˇ en K. A ø se le denomina elemento neutro y a x el opuesto de x. Es
usual denominar vectores a los elementos de E y escalares a los de K. En las aplicaciones que se estudian en la asignatura
los casos más importantes ocurren cuando K D R o K D C. Con la notación K designaremos a cualquiera de los cuerpos
R o C y por x un vector cualquiera de un espacio vectorial.
Un ejemplo característico de espacio vectorial lo constituye el formado por sucesiones ordenadas de n elementos
cualesquiera de K, o n-uplas x D Œx1 ; : : : ; xn , definiendo la suma de vectores mediante
Œx1 ; : : : ; xn  C Œy1 ; : : : ; yn  D Œx1 C y1 ; : : : ; xn C yn 
y el producto por un escalar mediante
˛Œx1 ; : : : ; xn  D Œ˛x1 ; : : : ; ˛xn  :
Otro espacio vectorial muy conocido es Pn , de polinomios de grado n, pn .x/ D
reales o complejos, n 0.
2
Pn
kD0
ak x k , con coeficientes ak ,
Si X es un conjunto arbitrario, el conjunto de aplicaciones ' W X ! K se estructura también como un espacio vectorial
definiendo las operaciones
.' C
/ W x 7 ! '.x/ C
.x/
.'/ W x 7 ! '.x/ :
El ejemplo anterior es un caso particular de este espacio vectorial tomando X D f1; 2; : : : ; ng.
Un subespacio M , de un espacio vectorial E sobre un cuerpo K, es un subconjunto no vacío cerrado respecto de las
operaciones de adición y producto por un escalar; es decir, se cumple que:
8x; y 2 M H) x C y 2 M;
8x 2 M y 8 2 K H) x 2 M:
La intersección de una familia cualquiera de subespacios de E es también un subespacio.
Si X es un subconjunto cualquiera de E, el subespacio engfXg engendrado o generado por X es la intersección se
todos los subespacios que contienen a X . Cuando engfXg D E, se dice que X es una parte generadora de E.
Dados vectores x1 ; : : : ; xn y escalares 1 ; : : : ; n , el vector formado según la expresión
x D 1 x1 C C n xn
se dice que es combinación lineal de los vectores x1 ; : : : ; xn de coeficientes 1 ; : : : ; n . Un subconjunto X de E es un
subespacio si y sólo si contiene a cualquier combinación lineal de cualquier subconjunto finito de vectores de X. También
se demuestra que el subespacio engfXg es el conjunto de todas las combinaciones lineales de vectores de X.
Un conjunto de vectores x1 ; x2 ; : : : ; xk se dicen linealmente dependientes si existen escalares i , no todos cero, tales
P
que kiD1 i xi D 0 ; linealmente independientes, si
k
X
i D1
i xi D 0 H) i D 0;
0i k:
Una parte X de un espacio vectorial E se dice que es una familia libre si los vectores de cualquier subconjunto finito de
X son linealmente independientes.
La dimensión de un subespacio es el máximo número de vectores linealmente independientes en el subespacio.
Una base de un espacio vectorial E es cualquier subconjunto B de E que sea, simultáneamente, una parte libre
y generadora de E; dicho de otra forma, una base de un espacio vectorial es un conjunto —normalmente se supone
ordenado (numerado)— de vectores linealmente independientes que engendran (o generan) dicho espacio. Se demuestra
que cualquier espacio vectorial tiene una base y que todas las bases de un mismo espacio tienen la misma cardinalidad
—se pueden poner en biyección—. Cuando el cardinal de las bases es un número natural, n 2 N, se dice que el espacio
es de dimensión finita n. En un espacio vectorial K n ,
2 3
2
3
2
3
1
0
0
6 7
6
7
6
7
6 0 7
6 1 7
6 0 7
6 7
6
7
6
7
e1 D 6 : 7 ; e2 D 6 : 7 ; : : : ; en D 6 : 7 ;
6 :: 7
6 :: 7
6 :: 7
4 5
4
5
4
5
0
0
1
forman una base en dicho espacio; éste, por tanto, tiene dimensión n. Esta base se denomina base canónica de K n . En
esta base, cualquier vector x T D Œx1 ; x2 ; : : : ; xn  se puede expresar de la siguiente forma:
2
3
2
3
2 3
2
3
x1
1
0
0
6
7
6
7
6 7
6
7
6 x2 7
6 0 7
6 1 7
6 0 7
6
7
6
7
6 7
6
7
6 : 7 D x1 6 : 7 C x2 6 : 7 C C xn 6 : 7 :
6 :: 7
6 :: 7
6 :: 7
6 :: 7
4
5
4
5
4 5
4
5
xn
0
0
1
Si A y B son subconjuntos de un espacio vectorial E, el conjunto A C B se define como:
A C B D fa C b W a 2 A; b 2 Bg :
Cuando A y B son subespacios, también lo es la suma A C B. Si además A \ B D ;, la suma se denomina directa,
escribiéndose A ˚ B. Si A ˚ B D E, cualquier vector c 2 E se descompone de manera única como c D a C b, con
a 2 A y b 2 B; también se dice que A y B son subespacios suplementarios.
3
3.1 Espacios normados
Si en un espacio vectorial E sobre K (R o C) se define una norma vectorial como
k k W E ! R que verifica
3.1 Espacios normados
kvk D 0 H) v D 0 y x ¤ 0 H) kxk > 0;
k˛vk D j˛jkvk para ˛ 2 K y v 2 E;
Si en un espacio vectorial E sobre K (R o C) se define una norma vectorial como una aplicación k k W E ! R que
ku C vk kuk C kvk 8u; v 2 E;
verifica
kvk D 0 H) v D 0 y x ¤ 0 H) kxk > 0;
se dice que E es un espacio vectorial normado.
k˛vk D j˛jkvkLa condición
para ˛ 2 kuCvk
K y v
2 kukCkvk
E;
es la desigualdad de Minkowski; se conoce tambi
del triángulo. Es una generalización del hecho de que un lado de un triángulo no puede
ku C vk lakuk
kvk
8u; vdos:
2 E;
sumaCde
los otros
ver figura. Una variante de esta regla es la siguiente:
se dice que E es un espacio vectorial normado.
ku vk kuk kvk:
La condición ku C vk kuk C kvk es la desigualdad de Minkowski; se conoce también como regla del triángulo.
Es una generalización del hecho de que un lado de un triángulo no puede ser mayor que la suma de los otros dos: ver
figura 3.1. Una variante de esta regla es la siguiente: ku vk kuk kvk.
v
uCv
u
Figura 3.1: Representación gráfica de la regla del triángulo
Figura 3.1: Representación gráfica de la regla del triángulo
En el espacio vectorial Kn , para 1 p < 1, se tiene la familia de normas
En el espacio vectorial Kn , para 1 p < 1, se tiene la familia de normas
1=p
p
p
p
p
p
p
kxk
D
jx
j
C
C
jx
j
;
p
1
n
kxkp D
jx1 j C C jxn j
denominadas normas p de Hölder. Casos particulares
lo constituyen
las correspondientes
a pparticulares
D 1 y p Dlo2:constituyen las correspondien
denominadas
normas
p de Hölder. Casos
p Dn2:
X
n
kxk1 D
jxi j
X
jxi j
kxk1 D
i D1
p
i D1
2
2
jx1 j C C jxn j :
kxk2 D
p
kxk2 D jx1 j2 C C jxn j2 :
Esta última se denomina en Rn norma euclídea. También en Kn es una norma la ndada por
Esta última se denomina en R norma euclídea. También en Kn es una norma la dada
kxk1 D mKax jxi j :
kxk1 D mKax jxi j :
1in
1in
Estas normas cumplen, cualquiera que sea x 2 Kn , que
Estas normas cumplen, cualquiera que sea x 2 Kn , que
kxk1 kxk2 kxk1 nkxk1 :
kxk1 kxk2 kxk1 nkxk1 :
2
2 espacios vectoriales normados
Si la bola cerrada unidad en R2 es el conjunto fx 2SiRla
Wbola
kxkcerrada
1g, sus
formas
unidad
en Ren
es el conjunto fx 2 R2 W kxk por
1g, sus formas pa
la 1, 2, 1 y p son las que representa la figura 3.2. vectoriales 1, 2, 1, y p son las que representa la figura 3.2.
En el espacio C Œ0; 1 de funciones continuas del intervalo Œ0; 1 en C, son normas las dadas por
7
"Z
#1=p
1
kf kp D
0
jf .t /jp dt
y por
kf k1 D mKax jf .t /j :
t 2Œ0;1
En un espacio vectorial normado se define la distancia entre dos elementos u y v mediante
d.u; v/ D ku
vk :
Esta definición convierte a cualquier espacio vectorial normado en un espacio métrico.
Sea E un espacio vectorial normado; se dice que una sucesión1 fx .n/ g en E converge a un límite v 2 E, si para todo
" > 0, existe un N 2 N tal que a partir de él, n N , se cumple que kx .n/ vk < ".
1 Cuando
así lo aconseja la dificultad de la notación, una sucesión también se designa por fxn g; sus integrantes, x .k/ .
4
– Si el conjunto fx 2 R2 W kxk 1g es la bola cerrada unidad en
R2, su forma para las normas vectoriales 1, 2, 1, y p son estas.
x11 D
=
kxk
2
i
2
i=1
|xijx
| ij
iD1
D1
√ q
q
2 2
x22 D
= jx
|x11|j22+C|xjx
2 | 2=
kxk
j DxT xx T x D 1
x1
max
kxk
D1≤i≤2
mKax|xjx
∞ =
i| i j D 1
1i2
1/p
p p 1=p
xpp D
= Œjx
|x11|jpp+C|xjx
p
< p∞)
kxk
< 1/
2 | 2 j , (1 ;≤.1
D1
28/63
Figura 3.2: Forma de la bola unidad para diferentes normas en R2
a
b
c
d
e
f
i
j
1
2
3
9
4
6
10
8
7
g
5
Cuando una sucesión fx g admite un vector límite v sólo tiene ese vector como límite.2 Se escribe lKımn!1 x .n/ D v.
Es equivalente decir que lKımn!1 x .n/ D v y que lKımn!1 kx .n/ vk D 0. En particular, x .n/ ! 0 si y sólo si kx .n/ k ! 0.
h
.n/
Una sucesión fx .n/ g en un espacio vectorial normado por k k se denomina sucesión de Cauchy si para cada " > 0
existe un n 2 N tal que cualesquiera que sean p; q n, se cumple que kx .p/ x .q/ k < ". Toda sucesión convergente es
una sucesión de Cauchy pero pueden existir espacios normados con sucesiones de Cauchy que no son convergentes. Un
espacio vectorial normado se dice completo si toda sucesión de Cauchy en él tiene límite.
Un espacio de Banach es un espacio vectorial completo respecto de la norma a él asociada. Todo espacio vectorial
normado de dimensión finita es un espacio de Banach. En un espacio de dimensión infinita esto no es cierto; por ejemplo,
es fácil ver que en C Œ0; 1 la sucesión de funciones cuyas gráficas son las de la figura 3.3 es una sucesión de Cauchy para
cualquier norma k kp , pero no tiene límite en C Œ0; 1.
1
n
fn .x/ 6
=
=
0
1
x
=
1
n
=
Figura 3.3: Gráfica de una de las funciones de una sucesión de Cauchy
3.2 Espacios con producto interior
Sea E un espacio vectorial sobre un cuerpo K (R o C); una forma sesquilineal —vez y media lineal— sobre E es una
aplicación hji W E E ! K que verifica3 :
1)
h˛u C ˇvjwi D ˛hujwi C ˇhvjwi y
2) huj˛v C ˇwi D ˛hujvi C ˇhujwi;
2 Si
3 La
existe límite es único.
barra designa complejo conjugado.
5
cualesquiera que sean u, v, w en E y ˛; ˇ en K. Si además se cumple que
hujvi D hvjui ;
la forma se denomina hermítica. Es claro que hujui es siempre un número real. Cuando se cumple que
u ¤ 0 H) hujui > 0 ;
se dice que la forma es definida positiva, denominándosela también producto escalar. Una forma sesquilineal sobre R es
siempre bilineal.
Un espacio prehilbertiano es un espacio vectorial sobre K dotado de una forma hermítica definida positiva. Todo
espacio prehilbertiano es un espacio normado mediante
p
kvk D hvjvi :
En la demostración de que esta definición corresponde a la de una norma en E juega un papel importante la desigualdad
de Cauchy-Schwarz: a saber,
ˇ
ˇ
ˇ
ˇ
ˇhujviˇ kuk kvk :
Un espacio
de Hilbert es un espacio prehilbertiano completo respecto de la norma que deriva del producto escalar
p
k k D h; i . Dicho de otra forma, un espacio prehilbertiano que con esta norma da un espacio de Banach.
El espacio euclídeo n-dimensional, expresado Rn o En , es un espacio de Hilbert de dimensión finita.
Dos vectores cuyo producto escalar es cero se denominan ortogonales; si sus k k2 son la unidad se denominan
ortonormales. Para dos vectores ortogonales se tiene la identidad
ku C vk2 D kuk2 C kvk2 ;
que es una generalización del teorema de Pitágoras. En un espacio prehilbertiano el único vector ortogonal a todos los
vectores del espacio es el vector nulo; si este espacio es de dimensión finita es posible construir una base ortonormalizada.
En un espacio euclídeo n-dimensional el ángulo entre dos vectores x e y es
T
x y
;
D arc cos
kxkkyk
donde
D
cumple que 1 1, para cualesquiera x e y.
xT y
kxkkyk
Dos vectores son ortogonales si x T y D 0 ( D =2; D 0); alineados, si x T y D kxkkyk ( D 0; D 1); opuestos,
si x T y D kxkkyk ( D ; D 1). Forman un ángulo agudo si x T y > 0 ( < =2; > 0) y un ángulo obtuso si
x T y < 0 ( > =2; < 0).
Una familia cualquiera de vectores distintos del nulo y ortogonales dos a dos es una familia libre. Si M es un subespacio
de un espacio prehilbertiano E de dimensión finita, el subespacio ortogonal de M , M ? , es el subespacio formado por
todos los vectores ortogonales a los de M , siendo un subespacio suplementario de M ; es decir M ˚ M ? D E. Cualquier
x 2 E, por consiguiente, se puede expresar como x D a C b, con a 2 M y b 2 M ? .
3.3 Aplicaciones lineales
Dados dos espacios vectoriales E y F sobre el mismo cuerpo K se define una aplicación lineal, transformación lineal,
mapeo, operador lineal u homomorfismo, f , de E en F , como una aplicación f W E ! F que verifica
f .x C y/ D f .x/ C f .y/ ;
cualesquiera que sean los vectores x, y de E y los escalares y . Existen dos casos particulares interesantes: el primero
cuando E D F , en este caso se dice que f es un operador lineal de E o endomorfismo de E; el segundo cuando F D K
—el cuerpo base—, en cuyo caso la aplicación se denomina forma lineal sobre E.
El conjunto L.E; F / de todas las aplicaciones lineales del espacio E en el espacio F se estructura como un espacio
vectorial si se definen las siguientes operaciones:
a) adición .f C g/ W
b) producto por un escalar f W
.f C g/.x/ D f .x/ C g.x/
.f /.x/ D f .x/
6
8x 2 EI
8x 2 E y 8 2 K:
En particular, el conjunto L.E; K/ de formas lineales es un espacio vectorial denominado dual de E, representándose con
E .
Para una aplicación lineal f W E ! F , el conjunto de vectores de F que son la imagen de los de un subespacio de
E forma un subespacio de F . En particular, la imagen de todo E es un subespacio de F que se denomina subespacio
imagen de f , representándose mediante Im.f /. Análogamente, el conjunto anti-imagen de un subespacio de F forma
un subespacio de E. En particular, la anti-imagen del subespacio nulo de F forma lo que se denomina el núcleo de la
aplicación, representándose por ker.f /. Así pues
ker.f / D fx 2 E W f .x/ D 0g :
Si b 2 F , la ecuación lineal f .x/ D b tiene solución si y sólo si b 2 Im.f /. En ese caso el conjunto de todas
las soluciones es la variedad lineal —traslación de un subespacio— dada por x0 C ker.f /, donde x0 es una solución
particular de la ecuación. En particular, la aplicación es inyectiva si y sólo si ker.f / D ;.
Sean E y F dos espacios prehilbertianos sobre el cuerpo K; si f W E ! F es una aplicación lineal, la aplicación
traspuesta de f es la aplicación f W F ! E que cumple
hxjf .y/i D hf .x/jyi ;
cualesquiera que sean los vectores x 2 E e y 2 F . Particularmente importante es el caso en que E D F : f se dice
entonces que es el operador adjunto de f . Cuando un operador f de E cumple que f D f se denomina operador
autoadjunto. En el caso de que E sea un espacio vectorial real, también se dice que f es un operador simétrico y cuando
es un espacio vectorial complejo, que f es un operador hermítico. Un operador simétrico cumple que
hxjf .y/i D hf .x/jyi;
mientras que uno hermítico, que
hxjf .y/i D hf .x/jyi:
Un operador f de E es unitario cuando es invertible y su inverso coincide con su adjunto. Es decir, si f D f
Para un operador unitario se tiene que
1
.
hf .x/jf .y/i D hf .f .x//jyi D hxjyi ;
de manera que kf .x/k D kxk. Por este motivo a los operadores unitarios también se les denomina operadores isométricos.
Dada una transformación lineal, aplicación lineal, o mapeo, f W E ! E, se dice que un subespacio W de E es un
subespacio invariante frente a f (o f -invariante) si para todo vector w 2 W se cumple que f .w/ 2 W . Dicho de otra
manera, W es un subespacio invariante si f .W / W .
4 Matrices
Sean dos espacios vectoriales E y F de dimensiones finitas n y m sobre el mismo cuerpo K. Una aplicación lineal
g W E ! F , g 2 L.E; F /, está caracterizada o representada en dos bases fe1 ; e2 ; : : : ; en g de E y ff1 ; f2 ; : : : ; fm g de
F por una tabla de coeficientes, matriz asociada, de m filas y n columnas:
2
3
a11 a1n
6 : :
7
: : : ::: 7 2 K mn :
AD6
4 :
5
am1 amn
Los coeficientes aij están definidos por
g.ej / D
El vector columna j -ésimo
m
X
1 j n:
aij fi ;
i D1
2
6
6
6
4
a1j
a2j
::
:
amj
7
3
7
7
7
5
representa el vector g.ej / en la base .fi /. A partir de la matriz A se pueden calcular los coeficientes y1 ; y2 ; : : : ; ym del
vector y D g.x/ en la base .fi /, conociendo los coeficiente x1 ; x2 ; : : : ; xn en la base .ej /. En efecto:
2
3
2
3
3
2
2 3
a11
y1
a12
a1n
6 a 7
6 a 7
6y 7
6 a
7
6 22 7
6 2n 7
6 21 7
6 27
6 :: 7 D x1 6 :: 7 C x2 6 :: 7 C C xn 6 :: 7 :
4 : 5
4 : 5
4 : 5
4 : 5
am2
amn
am1
ym
Expresión que también se puede escribir de la siguiente forma:
yD
n
X
xi ai ;
i D1
donde ai es el vector columna i-ésimo de la matriz A. Así pues, si se fijan dos bases en E y F , cada aplicación lineal, g W
E ! F , queda unívocamente representada por una matriz. Recíprocamente, toda matriz en K mn define unívocamente
una aplicación lineal entre dos espacios E y F de dimensiones n y m en los que se han fijado dos bases. En particular, se
pueden identificar las matrices m n con las aplicaciones lineales de K n en K m .
Las matrices de m filas y n columnas con coeficientes en el cuerpo K forman un espacio vectorial, K mn , sobre dicho
cuerpo K.
Si E y F son dos espacios de dimensión finita dotados de un producto escalar y la aplicación ˛ 2 L.E; F / se representa
en dos bases ortonormalizadas mediante una matriz A, la aplicación ˛ T 2 L.F; E/, traspuesta de ˛, viene representada
por la matriz A T , traspuesta de A.
El núcleo y la imagen de una matriz A 2 K mn , ker.A/ y Im.A/, respectivamente, se definen como los subespacios
de K n y K m que son el núcleo y la imagen de la aplicación lineal asociada:
7
7
ker.A/ D fx 2 K n W Ax D 0g
7
5
:
Im.A/ D fy 2 K m W y D Ax; x 2 K n g
mn
A2K
Dicho de otra forma, la imagen de una matriz es el subespacio generado por los vectores columna de la matriz; los vectores
fila también generan un subespacio que no es otro que la imagen de A T .
Para una matriz A 2 Rmn se cumple que:
ker A T D .Im.A//?
Im A T D .ker.A//?
?
ker.A/ D Im A T
?
:
Im.A/ D ker A T
El Teorema fundamental del algebra lineal establece que si A 2 Rmn se cumple que
ker .A/ ˚ Im A T D Rn :
El rango de una matriz es la dimensión4 de su subespacio imagen:
rango.A/ D dim.Im.A//
Una matriz A 2 K
se dice de rango completo si rango.A/ D mKın.m; n/. Una matriz cuadrada A 2 K nn se
denomina singular si rango.A/ < n; regular si rango.A/ D n. También se cumple que rango.A/ D rango.A T /.
mn
La aplicación asociada a una matriz A 2 Rmn es suprayectiva si rango.A/ D m. Para una matriz A 2 K mn se
cumple que
dim.ker.A// C rango.A/ D n ;
o, alternativamente, dim.ker.A// D n rango.A/. La aplicación lineal asociada a A es, por tanto, inyectiva, si y sólo si
rango.A/ D n. Por otro lado dim.ker.A T // C rango.A T / D m.
El producto exterior uvT de un vector columna n 1 por un vector fila 1 n es una matriz A nn de rango 1.
2
3
u1 v1 u1 v2 u1 vn
6 u v u v u v 7
2 n7
6 2 1 2 2
A D uvT D 6 :
:: 7
4 ::
: 5
un v1 un v2 un vn
4 Recordemos:
máximo número de vectores linealmente independientes.
8
4.1 Normas de matrices
Aun cuando en lo que sigue nos limitaremos a matrices cuadradas, la mayor parte de las definiciones y resultados son
extensibles a matrices rectangulares; también supondremos que las matrices son reales.
Las matrices cuadradas de orden n forman un espacio vectorial con un producto, esto es, un álgebra. Una norma
matricial es una norma vectorial compatible con el producto. Se define formalmente sobre Rmn como una aplicación
k k W Rmn ! R que cumple:
1) kAk D 0 H) A D 0:
2) kAk D jj kAk:
3) kA C Bk kAk C kBk:
4) kABk kAk kBk:
Existen normas sobre el espacio Rmn que no son normas matriciales pues no cumplen la propiedad 4). Así, si se
define
kAk D mKax jaij j ;
1i;j n
se satisfacen 1), 2) y 3); sin embargo, tomando A D B D
que no se cumple 4).
h
11
11
i
, es fácil ver que kABk D 2 > kAk kBk D 1, por lo
Un ejemplo importante de norma matricial es la norma de Frobenius, definida como:
X
2
kAk2F D
aij
D traza.A T A/;
1i;j n
P
donde la traza de una matriz A de orden n es niD1 ai i . Es fácil ver que esta norma deriva del producto escalar hAjBi D
traza.A T B/, que configura al espacio de las matrices cuadradas como un espacio prehilbertiano. La norma de Frobenius
cumple que
kABkF kAkF kBkF :
Una norma matricial k k sobre Rmn se dice consistente con una norma vectorial k k0 sobre Rn cuando para cada
matriz A y cada vector x se cumple que
kAxk0 kAk kxk0 :
Por ejemplo, la norma de Frobenius y la norma euclídea de Rn son consistentes pues
kAxk2 kAkF kxk2 :
Se demuestra que para toda norma matricial es posible construir una norma vectorial consistente. Recíprocamente, a toda
norma vectorial sobre Rn se le puede asociar una norma matricial consistente. Una norma matricial consistente con una
cierta norma vectorial k k se construye mediante la definición
kAk D
sup
0¤x2Rn
kAxk
:
kxk
Esta norma matricial se dice inducida por la norma vectorial. Ejemplo: la norma matricial inducida por la norma euclídea
de Rn es la norma espectral:
kAk2 D
sup
0¤x2Rn
"
x T A T Ax
xT x
#1=2
D
q
max .A T A/ D max .A/;
donde designa un valor propio de A y un valor singular. Si k k es la norma inducida por una cierta norma vectorial
y k k0 es una norma matricial cualquiera consistente con esa norma vectorial, se cumple, para toda matriz A, que
kAk kAk0 . En particular, para la norma espectral y la norma de Frobenius, se cumple que
p
kAk2 kAkF nkAk2 :
También, que kABkF kAkF kBk2 y kABkF kAk2 kBkF 2. Como casos particulares, kIk2 D 1 y kDk2 D
mKaxi jdi j.
9
Las normas matriciales inducidas más usadas son
kAk1
D
kAk1
D
mKax
1j n
mKax
1im
m
X
i D1
n
X
j D1
jaij j
y
jaij j :
Ejemplo 4.1 El efecto que produce aplicar la transformación lineal basada en la matriz
"
#
12
AD
02
sobre la bola unidad definida a partir de las normas k k1 , k k2 y k k1 en R2 , se representa en la figura 4.4. La aplicación
[2, 2]T
[0, 1]T
A1 = 4
[1, 0]T
norma11
norma
[1, 0]T
A2 ≈ 2,9208
norma22
norma
A∞ = 3
norma1
∞
norma
– LaFigura
aplicación
transforma el vector e 1 D Œ1; 0T en sí mismo y
4.4: Efecto de una aplicación lineal sobre la bola unidad para diferentes normas
e 2 D Œ0; 1T en Œ2; 2T .
39/63
transforma el vector e1 D Œ1; 0T en sí mismo y e2 D Œ0; 1T en Œ2; 2T . Con la norma 1, el vector unitario que más
se amplifica al aplicarle la transformación es Œ0; 1T (o Œ0; 1T ), que pasa a ser Œ2; 2T . Su factor de amplificación, en
términos de la norma 1, es 4.
a
b
c
1
2
3
h
i
j
10
8
7
Con la norma 2, el vector unitario que más se amplifica es el que se representa en la figura con una recta discontinua.
g
e
f
9
4
6
5
d
El factor de amplificación
es
2,9208.
Para la norma 1, igualmente, el vector unitario que más se amplifica es el que se representa también con la recta
discontinua: Œ1; 1T , que pasa a transformarse en Œ3; 2T . El factor de amplificación correspondiente es en este caso 3 ya
que
Œ1; 1T D 1
1
u
Œ3; 2T D 3:
1
4.2 Matrices ortogonales, unitarias, simétricas, Hessenberg, de permutación y de proyección
Una matriz Q 2 Rmn se dice ortogonal si verifica que QT Q D I; es decir, cuando sus vectores columna son
ortogonales dos a dos y de norma euclídea unitaria (ortonormales). Si Q 2 Rnn es ortogonal, se cumple que QQT D
QT Q D I.
10
Las matrices ortogonales Q 2 Rmn verifican:
y
kQk2
kQkF
kQAk2
kQAkF
D1
D n1=2
D kAk2
D kAkF
kQk2
kQkF
kAQk2
kAQkF
D
D
D
D
1
m1=2
kAk2
kAkF
9
>
>
>
=
>
>
>
;
si m n
>
>
>
;
si m n
9
>
>
>
=
Una matriz ortogonal no modifica ni los ángulos ni las normas, .Qx/H .Qy/ D x H QH Qy D x H y. Si y D x,
jjQxjj2 D jjxjj2 .
La extensión de las matrices ortogonales al campo complejo son las matrices unitarias. Son matrices, U 2 C nn ,
cuya inversa es su compleja conjugada: U H U D U U H D I: Todos los valores propios de las matrices unitarias tienen
módulo unidad. Como las ortogonales, una matriz unitaria no modifica ni los ángulos ni las normas, .U x/H .U y/ D
x H U H U y D x H y. Si y D x, jjU xjj2 D jjxjj2 .
Una matriz de permutación es una matriz cuadrada cuyas columnas están formadas por las de la matriz unidad permutadas. Una matriz de permutación es una matriz ortogonal.
Una matriz se dice simétrica si se verifica que A D A T . Para una matriz cualquiera A 2 Rmn , la matriz A T A es
simétrica. Si A 2 C nn es igual a su traspuesta conjugada, A D B D A H , bij D aNj i , se dice hermítica.
Una matriz A se dice definida positiva si x T Ax > 0 para todo vector x ¤ 0. De forma similar se definen matrices
semidefinida positiva, definida negativa y semidefinida negativa, si x T Ax 0, < 0 y 0, respectivamente, para todo
vector x ¤ 0. La matriz A se dice indefinida si x T Ax es positivo para algún x y negativo para otros. También A 2 C nn
se dice definida positiva si para todo x 2 C n ; x ¤ 0, se cumple que x H Ax > 0.
Si A 2 Rnn es simétrica y definida positiva se puede descomponer de la formaA D QDQT donde Q es una
1
1
matriz ortogonal y D, diagonal, tiene todos sus coeficientes positivos por lo que A 2 D QD 2 QT satisfaciéndose que
1
1
A 2 A 2 D A.
Una matriz de Hessenberg es una matriz triangular excepto por una subdiagonal adyacente a la diagonal principal.
@
@
@
0
@
@
Cualquier matriz se puede reducir a la forma de Hessenberg mediante transformaciones ortogonales de Householder o
Givens. Si la matriz original es simétrica, al reducirla a la forma de Hessenberg se obtendrá una tridiagonal.
Se denomina proyector o matriz de proyección a una matriz P 2 Rnn que verifica que P 2 D P. Si P además es
simétrica, se denomina proyector ortogonal o matriz de proyección ortogonal. Si, en este último caso, F es el subespacio
imagen de la matriz P (el mismo que el de la matriz P T ), Px define la proyección ortogonal del vector x sobre F .
Se denomina proyector suplementario de P al proyector S D I
F D ker.S / y G D Im.S /.
P. Si F D Im.P/ y G D ker.P/, entonces
En el caso de un proyector ortogonal P en el que F D Im.P/, se tiene que Rn D F ˚ F ? , verificándose que
kPxk2 kxk2 y que
kx Pxk2 D
mKın
kx yk2 :
y2Im.P /DF
5 Valores propios, valores singulares y formas cuadráticas
5.1 Valores propios
Si A es una matriz cuadrada de orden n y coeficientes en K (R o C), un vector no nulo u 2 Kn se denomina vector
propio de A si para algún 2 K se cumple que
Au D u :
11
A este se le denomina valor propio o autovalor de la matriz A. El conjunto de los valores propios de una matriz A se
denomina espectro de A, designándose por ƒ.A/. El radio espectral, .A/, se define de la siguiente manera:
.A/ D mKax ji j:
1in
Para que un número sea valor propio de A, el sistema lineal y homogéneo de ecuaciones dado por .I
debe tener soluciones distintas de la trivial x D 0. Esto equivale a que
det.A
A/x D 0
I/ D 0 :
Esta es una ecuación polinómica de grado n en que se denomina ecuación característica, o polinomio característico, de
la matriz A. La ecuación característica admite la raíz D 0 si y sólo si det.A/ D 0. Una matriz es invertible, por tanto,
si y sólo si no admite al cero como vector propio.
Para que exista una solución distinta de la trivial x D 0, el valor propio deberá ser raíz del polinomio característico
de grado n asociado a A, esto es det.A I/ D 0. Lo que es igual a n C g1 n 1 C g2 n 2 C C gn D 0:
La multiplicidad algebraica del valor propio de A es la multiplicidad de la raíz correspondiente del polinomio característico asociado a A. La multiplicidad geométrica de es el número de vectores propios linealmente independientes que
se corresponden con . La multiplicidad geométrica de un valor propio es menor o igual que su multiplicidad algebraica.
Por ejemplo, si A D I, D 1 es un valor propio con multiplicidad algebraica y geométrica n. El polinomio característico de A es p.z/ D .z 1/n y ei 2 C n , i D 1; : : : ; n, sus vectores propios. Si el valor propio tiene una multiplicidad
geométrica menor que la algebraica, se dice defectuoso. Se dice que una matriz es defectuosa si tiene al menos un valor
propio defectuoso. La matriz
2
3
210
40 2 15
002
tiene un valor propio, 2, de multiplicidad algebraica 3 y multiplicidad geométrica 1; u D Œ100T . Si una matriz A 2 C nn
no es defectuosa, dispone de un conjunto de n vectores propios linealmente independientes.
Un resultado interesante debido a dos matemáticos del siglo XIX, Cayley, británico y Hamilton, irlandés, dice que
cualquier matriz A 2 C nn satisface su propia ecuación característica. Es decir,
A n C g1 A n
1
C g2 A n
2
C C gn I D 0:
Si A es invertible, como consecuencia de ello,
A
1
D
1 n
A
gn
g1 n
A
gn
1
2
gn 1
I:
gn
A partir del teorema de Cayley-Hamilton también es fácil comprobar que existe un polinomio p de grado máximo n
tal que A 1 D p.A/. Como ejemplo, la matriz
12
34
1
tiene como polinomio característico x 2 5x 2. El teorema de Cayley-Hamilton dice que A 2 5A 2I D 0, lo cual se
puede comprobar inmediatamente. La inversa de A se puede obtener de esta ecuación a partir de A .A 5I/ D 2I. En
efecto, A 1 D 21 .A 5I/.
Para A 2 C nn y 0 ¤ b 2 C n1 , al subespacio Kj .A; b/ D engfb Ab : : : A j
Krylov.
1
bg se le denomina subespacio de
Igual que cualquier matriz tiene asociado un polinomio característico, cualquier polinomio tiene asociado una matriz
compañera. La matriz compañera de un polinomio mónico5 p.t / D c0 C c1 t C C cn 1 t n 1 C t n es
2
0
61
6
C .p/ D 6
6 0:
4 ::
0
0
1
::
:
:::
:::
:::
::
:
0 0 :::
0
0
0
::
:
1
3
c0
c1
c2
::
:
cn
1
7
7
7
7
5
El polinomio mínimo q.t / de la matriz A es el polinomio mónico único de grado mínimo tal que q.A/ D 0.
5 Un
polinomio a0 C a1 x C a2 x 2 C : : : C an x n se dice que es mónico si an D 1.
12
Una matriz real de orden n no tiene necesariamente valores propios reales pero, como consecuencia del teorema
fundamental del álgebra, cualquier matriz compleja tiene al menos un valor propio complejo. El número máximo de
valores propios es n.
Al aplicársele a cualquier vector la transformación que representa A ese vector tiende a orientarse hacia la dirección
del vector propio dominante de A. Si aquel vector está en la dirección de alguno de los vectores propios de A, se expande
o contrae por un factor que determina el correspondiente valor propio. Por ejemplo, la matriz
21
12
tiene como valores propios 3 y 1. Los vectores propios asociados son Œ1 1T y Œ 1 1T . El efecto de aplicarla sobre distintos
vectores se puede ver en la figura (en magenta y azul los vectores propios; otros en rojo).
Siendo un valor propio de la matriz A, el conjunto de soluciones del sistema de ecuaciones
.I
A/x D 0
es un subespacio de Kn que se denomina subespacio propio asociado al valor propio , designándose con E . Si n es la
multiplicidad de como raíz de la ecuación característica de A, se cumple que
dim.E / n :
La intersección de subespacios propios correspondientes a valores propios distintos se reduce al subespacio nulo; esto es,
¤ H) E \ E D ; :
De este modo, la suma de subespacios propios es directa. Se cumple que
M
E D Kn
2ƒ.A/
si y sólo si para cada 2 ƒ.A/, dim.E / D n ; en ese caso existe una base de Kn formada toda ella por vectores propios
de A.
El teorema central en el estudio de los métodos y algoritmos numéricos para el cálculo y análisis de valores y vectores
propios es el de la descomposición de Schur.
Teorema 5.1 Descomposición o triangularización de Schur. Para cualquier A 2 C nn existe una matriz unitaria U y
una matriz triangular superior, T , tal que
AU D U T o U H AU D T .
Los valores propios de A son entonces los coeficientes de la diagonal principal de R.
Teorema 5.2 Para cualquier matriz hermítica A 2 C nn existe una matriz unitaria U tal que
U H AU D D,
donde D es una matriz diagonal.
1. Los valores propios de A son números reales.
2. Se pueden obtener vectores propios de A que sean ortonormales.
13
En este caso se dice que la matriz A es semejante a una matriz diagonal: la matriz A es diagonalizable por semejanza.
Una matriz A 2 C nn es normal, es decir AA H D A H A, si y sólo si A D U ƒU H , donde U es una matriz unitaria y
ƒ una diagonal cuyos coeficientes son los valores propios de A. Los vectores propios son los vectores columna de U .
Toda matriz real y simétrica tiene todos sus valores propios reales y es diagonalizable por semejanza. Se demuestra
además que los subespacios propios correspondientes a valores propios distintos son ortogonales. De aquí se sigue que es
siempre posible formar una base ortonormalizada de vectores propios para una matriz real y simétrica A. Existe entonces
una matriz ortogonal Q tal que se verifica que
QT AQ D D;
con QT D Q
1
;
y, de aquí que, toda matriz real y simétrica es congruente ortogonal con su reducida diagonal. Este resultado fundamental
de la teoría de matrices es la versión elemental del denominado teorema espectral.
Si A es hermítica, el producto x H Ax es un número real. Los valores propios de una matriz hermítica, en consecuencia,
son números reales. En una matriz hermítica los vectores propios correspondientes a dos valores propios distintos son
ortogonales entre sí.
Teorema 5.3 Descomposición de Jordan Para una matriz A 2 C nn existe una matriz regular X 2 C nn tal que
X 1 AX D diag.J 1 ; : : : ; J k / donde
2
3
i 1
6 1 0 7
i
6
7
ni ni
Ji D 6
7
6
72C
4 0
5
1
i
y n1 C nk D n. Las J i son las matrices o bloques de Jordan y los i los valores propios de A.
5.2 Valores singulares
La noción de valor propio, o autovalor, no tiene significado para matrices rectangulares. En éstas, por el contrario,
se introduce el concepto de valor singular. Si A es una matriz rectangular m n con coeficientes en R, se definen sus
valores singulares i ; i D 1; : : : ; mKınfm; ng, como las raíces cuadradas positivas de los valores propios de la matriz
cuadrada A TA 2 Rnn .
Se demuestra que si A 2 Rmn , existen dos matrices ortogonales,
U D Œu1 ; : : : ; um  2 Rmm
y
V D Œv1 ; : : : ; vn  2 Rnn ;
tales que
y donde
U T AV D diag.1 ; : : : ; p /;
p D mKınfm; ng ;
1 2 p 0 :
Los vectores ui se denominan vectores singulares izquierdos; los vi , vectores singulares derechos.
Los valores singulares de A son las longitudes de los semiejes del hiperelipsoide E definido por
E D fy W y D Ax; kxk2 D 1g :
Es decir, las longitudes de los semiejes del hiperelipsoide imagen de la esfera unidad resultante de la aplicación que
caracteriza la matriz A. En la figura ?? se describe gráficamente el caso en que m D n D 2.
Para una matriz A 2 Rmn cuya descomposición en valores singulares es A D U †V T , se define su matriz pseudoinversa, A Ž , como
AŽ D V †ŽU T ;
donde
† Ž D diag.1 1 ; : : : ; r 1 ; 0; : : : ; 0/ 2 Rnm :
14
σ1
σ2
x
Ax
Ax
Figura 5.5: Representación en dos dimensiones de una transformación lineal de la esfera unidad
Si A 2 Rmn es de rango completo y m > n,
AŽ D AT A
si m < n
1
A Ž D A T AA T
AT I
1
:
Para cualquier matriz A 2 Rmn , la matriz A Ž A es la matriz n n de proyección ortogonal sobre el subespacio de los
vectores fila de A, AA Ž la m m de proyección ortogonal sobre la imagen de la matriz A (subespacio de sus vectores
columna) y .I A Ž A/ la de proyección ortogonal sobre el núcleo de A, ker.A/.
5.3 Formas cuadráticas
Una forma cuadrática en n variables es un polinomio de segundo grado en esas variables. La expresión más general
de una forma cuadrática es
q.x/ D x T Qx ;
donde Q D QT es una matriz simétrica de orden n. Nos limitaremos al análisis de formas cuadráticas con coeficientes
reales.
Mediante una transformación lineal de variables, x D T y, una forma cuadrática se puede reducir a la forma canónica
de suma de cuadrados siguiente:
p
pCq
X
X
q.x/ D
yi2
yi2 :
i DpC1
iD1
El rango de la forma es p C q y la signatura p
q (p números positivos y q negativos).
Una forma cuadrática real es definida positiva si para todo vector x ¤ 0, q.x/ > 0. El rango y signatura de una forma
cuadrática definida positiva valen n. Si Q la forman los coeficientes qij y se introducen los números menores como
2
3
q11 q12 q1i
6q q q 7
2i 7
6 21 22
i D det 6 :: :: : : :: 7 ;
4 : :
: : 5
qi1 qi 2 qi i
la forma cuadrática asociada a Q es definida positiva si y sólo si todos los menores i son positivos.
Sean 1 ; : : : ; n los valores propios —que sabemos son reales— de la matriz Q; por el teorema espectral, existe una
matriz ortogonal P tal que
P T QP D diag.1 ; : : : ; n /:
Haciendo en la forma cuadrática q.x/ D x T Qx el cambio de variables x D Py, se tiene que
q.x/ D y T P T QPy D 1 y12 C C n yn2 ;
lo que hace ver que el rango de la forma cuadrática es el número total —teniendo en cuenta las multiplicidades— de
valores propios no nulos de Q, mientras que la signatura coincide con la diferencia entre los números de valores propios
15
positivos y negativos. En particular, la forma cuadrática asociada a Q es definida positiva si y sólo si todos los valores
propios de Q son positivos.
En ciertos casos es importante acotar el cociente de una forma cuadrática al cuadrado de la norma euclídea, es decir, el
cociente
x T Qx
;
x ¤ 0:
r.x/ D T
x x
Mediante una transformación ortogonal x D Py, este cociente se escribe como
r.x/ D
de manera que se deducen las acotaciones
1 y12 C C n yn2
;
y12 C C yn2
x T Qx
max .Q/ :
xT x
Estas acotaciones no se pueden mejorar ya que si Qv D v,
mi n .Q/ vT Qv
D :
vT v
Como ya se ha visto, una matriz simétrica definida positiva tiene todos sus valores propios reales y positivos; si es
semidefinida, alguno es cero. Si la matriz es negativa definida, todos sus valores propios son negativos.
Un resultado muy interesante para averiguar el orden de magnitud de los valores propios de una matriz es el del teorema
de Gerschgorin, que dice que si A 2 Rnn es una matriz simétrica con valores propios 1 ; 2 ; : : : ; n , entonces
9
8̂
>
>
ˆ
n
=
<
X
jaij j ;
mKın i mKın ai i
>
1i n
1i n ˆ
>
j D1
;
:̂
j ¤i
9
8̂
>
>
ˆ
n
=
<
X
jakj j :
mKax i mKax akk C
>
1kn
1kn ˆ
>
j D1
;
:̂
j ¤k
Se dice que una matriz A 2 C
nn
, de coeficientes aij , es de diagonal dominante por filas cuando cumple que
jai i j n
X
jaij j;
n
X
jaj i j;
j D1;j ¤i
i D 1; : : : ; n:
Análogamente, se dice diagonal dominante por columnas si
jai i j j D1;j ¤i
i D 1; : : : ; n:
Si las desigualdades se verifican estrictamente la matriz A se denomina diagonal estrictamente dominante.
Lema 5.4 Para que una matriz simétrica sea definida positiva es necesario que todos los coeficientes de la diagonal
principal sean positivos.
Lema 5.5 Para que una matriz simétrica A sea definida positiva es necesario que el coeficiente de mayor valor absoluto
esté en la diagonal principal. Más concretamente,
mKax jaij j < mKax akk :
i ¤j
k
Lema 5.6 Si en cada fila de una matriz simétrica A el coeficiente de la diagonal principal es mayor que la suma de los
valores absolutos de todos los demás coeficientes de la fila, es decir, si
akk >
n
X
j D1
jakj j
k D 1; : : : ; n;
j ¤k
A es definida positiva.
16
Es importante destacar que este último criterio define una condición suficiente, no necesaria. En efecto, la matriz
2
3
322
Q D 42 3 25
223
es definida positiva pues la forma cuadrática
q.x/ D x T Qx D x12 C x22 C x32 C 2.x1 C x2 C x3 /2
cualquiera que sea x ¤ 0, es siempre positiva: q.x/ > 0. Esta matriz, sin embargo, no satisface el lema ??.
Además de las normas vectoriales y matriciales ya presentadas, otra norma vectorial que se utiliza en el curso es
p
p
kxkA D A 1=2 x D hAxjxi D x T Ax;
2
6
denominada norma A o norma de energía del vector x, para una matriz A simétrica y definida positiva. A hxjyiA D
hAxjyi se le denomina producto interior de A o producto escalar de energía. La matriz A 1=2 es la única matriz definida
positiva solución de la ecuación matricial X 2 D X X D A.
6 Topología
En un espacio vectorial normado se define una bola abierta, S.x0 ; r/, de centro x0 y radio r, como el conjunto de
puntos x que verifican kx x0 k < r. Es decir:
S.x0 ; r/ D fx 2 Rn W kx
x0 k < rg:
Una bola cerrada, SN .x0 ; r/, se define, por el contrario, como el conjunto de puntos x que verifican kx
decir:
SN .x0 ; r/ D fx 2 Rn W kx x0 k rg:
x0 k r. Es
Consideraremos en lo que sigue de este apartado un subconjunto S del espacio vectorial métrico hasta ahora estudiado
(puede ser, por ejemplo, Rn ).
Un punto y 2 S es un punto interior del conjunto S si existe un " tal que
kx
yk < " ) x 2 S :
En otras palabras, existe una bola abierta S.y; "/ de centro y y radio " contenida íntegramente en S .
El conjunto de todos los puntos interiores del conjunto S se denomina interior de S . Este conjunto puede, evidentemente, ser vacío. Ejemplo: un plano del espacio R3 .
Un subconjunto de S se dice abierto si coincide con su interior; es decir, si alrededor de todo punto de S existe una
bola abierta contenida íntegramente en S . Dos ejemplos: la bola abierta unidad, S.x; 1/ D fx W kxk < 1g y el espacio
Rn en su totalidad. En general los subconjuntos o conjuntos abiertos se caracterizan por no tener límites definidos o ser
disjuntos de su frontera (ver más adelante la definición del concepto frontera).
Un entorno de un punto x, E.x/, es un conjunto abierto que contiene a x. En otras palabras, E.x/ es un entorno de x
si contiene una bola abierta de centro x.
Se dice que un punto x es un punto de acumulación del subconjunto S si en todo entorno de x existen un número
infinito de puntos de S .
Un punto x se denomina punto de adherencia del subconjunto S cuando todo entorno de dicho punto x contiene al
menos un punto de S ; es decir, para todo " existe un y 2 S tal que kx yk < ". El conjunto de todos los puntos de
adherencia se denomina adherencia —en la literatura anglosajona y latinoamericana, clausura cl.S /—. La adherencia de
la bola abierta S.x; 1/ D fx W kxk < 1g es la cerrada SN .x; 1/ D fx W kxk 1g.
Se denomina frontera de un conjunto a la parte de la adherencia que no está en el interior.
Un conjunto, o subconjunto, se dice cerrado si coincide con su adherencia. La adherencia de cualquier conjunto S es el
conjunto cerrado más pequeño que contiene a S . Se puede demostrar que un conjunto es cerrado si y sólo si toda sucesión
convergente de elementos de S tiene un límite en ese conjunto.
6 Pues
suele corresponder con la energía física de ciertos sistemas.
17
Un conjunto, o subconjunto, se dice compacto si es cerrado y acotado (contenido en una bola de radio r < 1). Un
importante resultado, debido a Weierstrass, dice que si S es un conjunto compacto, de cada sucesión o sucesión infinita
fx .n/ gn2N de elementos de dicho conjunto es posible extraer una subsucesión
n
o
x .`/
LN
`2L
que converge a un elemento del propio conjunto S .
Si fr .k/ g es una sucesión de números reales y s .k/ D sup fr .i / W i kg, entonces fs .k/ g converge a un número real s0 ;
a este número se le denomina límite superior de fr .k/ g y se expresa como
lKım sup r .k/
o lKım r .k/ :
k!1
El límite superior de una sucesión de números reales es el mayor punto de acumulación de la sucesión. De forma similar
se define el límite inferior.
7 Teorema de la proyección
Gran parte de las teorías de sistemas de ecuaciones y de optimización que se estudian en la asignatura están basadas en
unos pocos resultados simples e intuitivos. Entre estos, quizás el más sencillo y usado sea el teorema de la proyección. Su
aplicación en la teoría de mínimos cuadrados lineales es fundamental. En un espacio Euclídeo ordinario de tres dimensiones determina que la distancia más corta de un punto exterior a un plano a ese plano la proporciona la perpendicular al
plano desde dicho punto. La expresión formal de este teorema en espacios de Hilbert es la que sigue.
Teorema 7.1 Sea H un espacio de Hilbert y M un subespacio cerrado de H . Para todo vector x 2 H existe un único
vector m0 2 M tal que kx m0 k2 kx mk2 , para todo m 2 M . La condición necesaria y suficiente además para
que m0 2 M sea el vector mínimo único es que x m0 sea ortogonal a M .
D EMOSTRACIÓN . Primero probaremos que si m0 es un vector que minimiza kx mk, x m0 es ortogonal a M .
Supongamos para ello, por el contrario, que existe un m que no es ortogonal a x m0 ; sin pérdida de generalidad
podemos suponer que kmk D 1 y que hx m0 jmi D ı ¤ 0. Definamos el vector m1 2 M como m1 D m0 C ım.
Tendremos que
kx
De esta manera, si x
m1 k22 D kx
m0
m0 k22
D kx
ımk22 D kx
jıj2 < kx
m0 k22
m0 k22 :
hx
m0 jımi
hımjx
m0 i C jıj2
m0 no es ortogonal a M , m0 no es el mínimo que decíamos.
Veamos ahora cómo, si x m0 es ortogonal al subespacio M , m0 es el único vector de M que minimiza kx
En efecto, para todo m 2 M , el teorema de Pitágoras dice que
mk22 D kx
kx
Por lo tanto kx
m0 C m0
mk22 D kx
m0 k22 C km0
mk2 .
mk22 :
m0 k2 para m ¤ m0 .
mk2 > kx
Demostraremos ahora la existencia de un m0 que minimiza kx mk2 . Si x 2 M , entonces m0 D x y todo estaría
probado como es obvio. Si x … M , definamos un ı D Kınfm2M kx mk2 ; lo que queremos es obtener un m0 2 M tal que
kx m0 k2 D ı.
A tal fin, sea fm.i / g una sucesión de vectores en M tal que kx m.i / k2 ! ı. Por la ley del paralelogramo7 se tiene
que
2
2
.j /
2 .m
x/ C .x m.i / /2 C .m.j / x/ .x m.i / /2 D 2 m.j / x 2 C
2
C2 x m.i / :
2
Reordenando, se obtiene
7 Para
u, w 2 M ,
.j /
m
ju C wj2
m D 2 m.j /
C ju
2
.i / 2
wj2
D
2juj2
2
x C 2 x
2
C 2jwj2 .
18
2
.i / m 2
4 x
2
m.i / C m.j / :
2
2
Proposición 8.3 (Condiciones necesarias de segundo orden) Sea  un subconjunto de Rn y una
función f W  ! R, f 2 C 2 . Si x en un mínimo relativo de f en , para toda dirección d 2 Rn ,
factible desde x , se cumple que:
.j /
.i / 2
.i /
Como km.i / xk22 ! ı 2 cuando i ! 1,rf
km.x
m k2 ! 0 cuando i; j ! 1. Es decir, fm g es
/d 0:
.i
/
.j
/
Exercise
.i /
Cauchy;
como
es un
subespacio
cerrado, la
sucesión fm
g tiene
m0 en de ı se
Para todo i; j , el vector .muna sucesión
C m de
/=2
está en
MM
pues
éste
es un espacio
vectorial
(lineal).
Deunlalímite
definición
rf .x
D 0; entonces d T r 2 f .x /d 0:
M.jy,/ /=2k
debido
a la continuidad de la norma,Sikx
m0 k/d
2 ! ı.
deduce que kx .m.i / C m
2 ı, por lo que
2del problema
2
la solución
6=2 0, y pone en evidencia
given two
n-vectors
El
de laxproyección
que
(Condiciones
teorema
.i / segundo2orden) Sea x un punto interior de  y su4ı :
2 x mde
m.i / 28.4
m.j / x Cnecesarias
m.j / Proposición
2
2
póngase2que también unminimizar
mínimo
relativo
de f 2W  ! R, f 2 C . Entonces:
ktx yk
minimize
(over t) t ktx − yk
.j /
j ! 1. Es decir, fm.i / g es una sucesión de
Como km.i/ xk22 ! ı 2 cuando
i !
1, kmortogonal
m.ide/ ky22 sobre
! 0x:cuando
/ D 0:
es el vector
proyección
txrf
en.x
lai;figura.
.i /
Cauchy; como M es un subespacio cerrado, la sucesión fm g tienePara
un límite
m TenrM
y,debido
2
todo
f .x
/d
0:xa la continuidad de la
geometrically, tx is the projection of a vector y on thed;
line0d through
0 and
norma, kx m0 k2 ! ı.
Proposición 8.5 (Condiciones suficientes de segundo orden) Sea f 2 C 2 una función definida en
x interior. Supóngase además que:
una región en la cual x es un punto
tx .x / D 0:
rf
La matriz Hessiana r 2 f .x / es definida positiva:
y
x es entonces un mínimo relativo estricto de f .
0
9 Conjuntos convexos
Figuraconvexos
7.6: Solución de minimizar t kt x
8 Conjuntos
yk
convexo
y sólo
para todo
de puntos x1 ; x2 2 C todas las
C laconvexo
solución
Rn sesi dice
Unpone
conjunto
C conjunto
Rn seque
dice
y del
sólo
si para si
todo
par desi puntos
x1 ; xpar
El teorema de la proyección
en Un
evidencia
problema
2 2 C todas las
Vectors
1-20están
combinaciones
la 1forma
D x
/x
, conen
0
1,
en C
. Es decir, cuando para
1 C0.1
combinaciones
de la forma x de
D x
C .1 x /x
1,2están
C .Esdecir,
cuando
para
2 , con
cada par
puntosconvexo,
del conjunto
convexo,
todos
los puntos
de laestán
recta
que
los une están en el conjunto.
cada par de puntos
del de
conjunto
todos
los
puntos
de
la
recta
que
los
une
en
el
conjunto.
minimizar ktx yk
t
es el vector proyección ortogonal de y sobre x: t x en la figura ??.
8 Conjuntos convexos
Conjunto convexo
Conjunto no convexo
Un conjunto
C Rn se of
diceconvex
convexo si y sólo si para todo
par de puntos x1 ;non-convex
x2 2 C todas las combinaciones de la
Examples
La expresión x sets
D x1 C .1 /x2Examples
, 0 1, defineof
la combinación convexa de sets
x1 y x2 . Si
•
A
segment
isa
convex
set.
forma x D x1 Cline
.1 /x
,
con
0
1,
están
en
C
.
Es
cuando
para
cada
par de
puntos del conjunto
convexo,
•decir,
The
union
of
two
non-overlapping
line segmen
2
0 < < 1, es decir
2
.0;
1/,
la
combinación
se
denomina
estrictamente
convexa.
•
Non-convex
sets
can
have
“indentations.
La expresión x D x1 C .1 /x2 , 0 1, define la combinación
convexa de x1 y x”
2 . Si
todos los puntos de la recta que
los
une
están
en
el
conjunto.
El concepto de combinación convexa se puede generalizar a cualquier número finito de puntos de
0 < < 1, es decir 2 .0; 1/, la combinación se denomina estrictamente convexa.
la siguiente manera:
xD
donde
p
X
i D1
i D 1;
p
X
i xi ;
25
i D1
i 0;
i D 1; : : : ; p:
Fig. 4.9. Convex
sets
with
pairs
of
points
joined by line segments.
El conjunto intersección de todos los conjuntos convexos que contienen a un subconjunto S Rn
Title Page
Figura
8.7:
Conjuntos
convexos
–izquierda–;
no convexos
–derecha–
se
llama
envoltura
convexa
de S y se designa
por conv.S/.
38
of
156
Title Page
Go Back
Full Screen
Close
39
of 156
Quit
23
La expresión x D x1 C .1 /x2 , 0 1, define la combinación
convexa de x1 y x2 . Si 0 < < 1, es decir
2 .0; 1/, la combinación se denomina estrictamente convexa.
El concepto de combinación convexa se puede generalizar a cualquier número finito de puntos de la siguiente manera:
xD
donde
p
X
iD1
i D 1;
p
X
i xi ;
iD1
i 0;
i D 1; : : : ; p:
El conjunto intersección de todos los conjuntos convexos que contienen a un subconjunto S Rn se llama envoltura
convexa de S (figura ??) y se designa por conv.S /.
Un conjunto C Rn se dice que es afín (también se dice que C es una variedad afín o una variedad lineal) si para
cualesquiera x; y 2 C y cualquier 2 R se tiene que .1 /x C y 2 C . El conjunto vacío es afín.
Un conjunto C Rn es afín si y sólo si es de la forma C D fa C l W a 2 Rn ; l 2 Lg, donde L es un subespacio
vectorial de Rn asociado a C . Es decir, un conjunto afín es un subespacio desplazado del origen. La dimensión de un
19
Go Back
Figure 2.2 Some simple convex and nonconvex sets. Left. The hexagon,
516 which
Appendix
Sets
includesBitsConvex
boundary
(shown darker), is convex. Middle. The kidney
shaped set is not convex, since the line segment between the two points in
the set shown as dots is not contained in the set. Right. The square contains
some boundary points but not others, and is not convex.
x2
x2
x1
x1
convex
nonconvex
Fig. B.1 Convexity2
Figure 2.3
Theconjuntos
convex hulls
of2two
R . Left.deThe
of la
a derecha de un conjunto
Figura 8.8: Envoltura convexa
de dos
de R
. Lasets
de lainizquierda
15 convex
puntos;hull
la de
set of fifteen points (shown as dots) is the pentagon (shown shaded). Right.
no convexo
The convex hull of the kidney shaped set in figure 2.2 is the shaded set.
C+D
conjunto afín x C L es la de su correspondiente subespacio L. Es evidente que cualquier conjunto afín es convexo aunque
el recíproco no es cierto en general.
D
2.C
Roughly speaking, a set is convex if every point in the set can be seen by every other
along de
ansoluciones
unobstructed
path
between lineales,
them, where
unobstructed
Proposición 8.1 point,
El conjunto
de unstraight
sistema de
ecuaciones
C D fx
W Ax D b; A 2 Rmn ; b 2
C
means
lying
in
the
set.
Every
affine
set
is
also
convex,
since
it
contains
the entire
m
R g, es un conjunto afín.
line between any two distinct points inDit, and therefore also the line segment
C
C and nonconvex sets
between the points. Figure 2.2 illustrates some simple convex
2
D EMOSTRACIÓN .inEnRefecto,
supongamos
que
x
;
x
2
C
,
es
decir,
Ax
D
b,
Ax
1
2
1
2 D b. Entonces, para cualquier ,
.
We
of the form θ1 x1 + · · · + θk xk , where θ1 + · · · + θk = 1 and
0 call a point
A . x1 C .1 combination
/0 x2 / D of Ax
Ax2
1 C .1 x ,/
θi ≥ 0, i = 1, . . . , k, a convex
the points
1 . . . , xk . As with affine
.1sets /
D ofifb
C only
b contains every convex
sets, it can be shown thatFig.
a set
convex
and
if it
B.2 is
Properties
convex
combination of its points. A convex combination
of
points
can be thought of as a
D b;
mixture or weighted average of the points, with θi the fraction of xi in the mixture.
n
Definition. afín
Let Sx1beCa.1
subset
of2Eestá
. The
convexenhull
of S, denoted
co(S),
is
lo que prueba que la combinación
/x
también
el conjunto
C . El
subespacio
asociado con el
theconvex
set
is athe
ofconv
all convex
sets
S. The
closed
The
of
setintersection
C,dedenoted
C, is the
setcontaining
of all convex
combinations
conjunto afín C en este
caso
es which
elhull
espacio
nulo
A, ker.A/.
convex
hull of S is defined as the closure of co(S).
of points
in C:
26
2 Convex sets
n
Si S R , la envoltura
afín de Sconclude
, aff.S /, es
intersección
de todos
los conjuntos
afinescone.
que contienen
a S . Como se
thislasection
by defining
a cone
and a convex
A
convFinally,
C = {θwe
1 x1 + · · · + θk xk | xi ∈ C, θi ≥ 0, i = 1, . . . , k, θ1 + · · · + θk = 1}.
puede comprobar, aff.S
/ Dcone
aff.conv.S
//. kind of convex set that arises quite frequently.
convex
is a special
suggests,
hullx conv
is always
convex.
is thesmallest
Un conjunto CAsthe
Rnname
se dice
un conothe
si convex
para todo
2 C ,Cx
2 C , para
todo It
escalar
2 R tal que 0. Un
convex set that contains C: If B is any convex set that contains C, then conv C ⊆
B. Figure 2.3 illustrates the definition of convex hull.
The idea of a convex combination can be generalized to include infinite sums, integrals, and, in the most general form, probability distributions. Suppose θ1 , θ2 , . . .
x1
0
x2
0
Not convex
Figure 2.4 The0pie slice shows all points of the form θ1 x1 + θ2 x2 , where
0 0) is at
θ1 , θ2 ≥ 0. The apex of the slice (which corresponds to θ1 = θ2 =
0; its edgesNot
(which
correspond to θ1 = 0 or θ2 = 0) pass through
the points
convex
Convex
x1 and x2 .
Figura 8.9: Tres conos: el primero y el segundo no son convexos; el tercero si
Fig. B.3 Cones
cono que también es convexo se denomina cono convexo (figura ??). En este caso, para todo x1 ; x2 2 C y 1 ; 2 0,
1 x1 C 2 x2 2 C .
El conjunto fx 2 Rm W x D A˛; A 2 Rmn ; ˛ 2 Rn ; ˛ 0g es un cono convexo generado por los vectores columna
de la matriz A.
0
0
Figure 2.5 The conic hulls (shown shaded) of the two sets of figure 2.3.
Figura 8.10: Envoltura cónica de los dos conjuntos de la figura ??
El conjunto de todas las combinaciones cónicas, 1 x1 C C k xk , 1 ; : : : ; k 0, de los puntos de un conjunto C
es la envoltura cónica de C , cone.C /..
20


X



X i
i
λ
x
:
k
∈
N,
x
∈
X,
λ
∈
R,
i
=
1,
2,
.
.
.
,
k
;
λ
=
1
a f f (X) = 

i
i
i




Figura 8.8: Envoltura cónica de los dos conjuntos de la figura 8.6
0
0
Figure 2.5 The conic hulls (shown shaded) of the two sets of figure 2.3.
i=1
i=1
Teorema de Carathéodory para convexos
Un punto x es un punto extremo de un conjunto convexo C si y sólo si no es interior a un segmento de recta contenido
Teorema de Carathéodory
para conos
en C . Es decir, si y sólo si
Teorema 2.2. Si X ⊂ Rn y x ∈ conv (X), existen xi ∈ X y λ ≥ 0, i = 1, . . . , n + 1,
Un punto
deDun
conjunto
convexo
C
sixno
interior
a ·un
x
.1 (X),
ˇ/y Cexisten
ˇz con
0<ˇ
1 y si
y; zyy
2sólo
C
D yes
z: 1, 2,
Teorema
2.1. xSiesXun⊂punto
Rn yextremo
x ∈ cone
xi< ∈
X
λi)≥
0,
iD=
· ·segmento
, n, i de recta contenido
n+1
n+1
P
P
n si y sólo si
en C . Es decir,
P
Dos
debido
a Carathéodory
R iy xEs
2 cone.X
/, existen
x y , i D 1; : :elemento
: ; n,
i resultados
λi . Es
=decir,
1, cualquier
tales
que dicen
x =quedesi Xlaλcónica
decir,
cualquier
de la envoltura
P importantes
i x . de
tales que x = tales
λi xque
.con
Es
elemento
envoltura
cónica
dede,X
essumo,
x D decir,
x cualquier
elemento de la envoltura
X es combinación
cónica
a lo
P
n
n
iD1
i
i
i=1D .1 si ˇ/y
i=1
n ˇz con 0 < ˇ <
x
Dque
y xDDz:
i=1 n puntos de X. Igualmente,
X RC
y x 2 conv.X /, existen x1 yy y;
, i zD21; C
: : : ; n)
C 1,xtales
i
i
nC1
i
i
iD1 i xi .
Es decir, cualquier elemento de la envoltura convexa de X es combinación convexa de, a lo sumo, n C 1 puntos de X. La
figura 8.9 ilustra estos resultados.
convexa
de X neselementos
combinación
combinación cónica de,
a lo sumo,
de X.convexa de, a lo sumo, n + 1 puntos de X.
Figura 8.9: El teorema de Carathéodory
Teorema de Carathéodory para convexos
Figura 8.11: El teorema de Carathéodory
Llamaremos hiperplano H de vector característico a 2 Rn ; a ¤ 0, al conjunto H D fx 2 Rn W aT x D cg, con
n
i
(X),
Teorema
2.2. Si cX2importantes
⊂UnRhiperplano
y xdebido
∈
existen
∈
i=
1, . . . ,/,nexisten
+ 1, xi y i , i D 1; : : : ; n,
R.
es elconv
conjunto
de soluciones
de dicen
unax
ecuación
i R≥
Dos resultados
a Carathéodory
queXlineal
siyXλen
R. n0,y x
2 cone.X
P
n+1
n+1
n
Un
hiperplano
en
R
es
un
espacio
afín
o
una
variedad
lineal
.n
1/-dimensional.
P
P
x D iD1 i xi . Es decir,
elemento de la envoltura cónica de X es combinación
cónica
i
˚
de, a lo sumo,
que
x = H , aλcualquier
. Es decir,
cualquier elemento de la envoltura
contales λque
PnC1
Dado
un hiperplano
xi x
D
i = 1, tales
n c, llamaremos semiespacios cerrados de borde H a los conjuntos H D x 2 R W a x c
n
n
T
C
n
T
˚
ni=1
puntos de X. Igualmente,
si X R y x 2 conv.X /, existen ıxi y˚ i , in DT 1; : :: ; nı C ˚1, tales
que x D iD1 i xi .
y H D x 2 Rn W aTi=1
x c , y semiespacios abiertos de borde H a H C D x 2 R W a x > c y H D x 2 Rn W aT x < c .
Es decir,
elemento
laconvexa
envoltura
convexa
X
de, a lo sumo, n C 1 puntos de X. La
convexa
decualquier
X es Los
combinación
de,laaunión
lodedesumo,
nes+el espacio
1 puntos
de X.
semiespacios de
de borde
H son convexos;
HCes
y Hcombinación
Rnconvexa
.
figura ?? ilustra estos
En laresultados.
figura 8.10 se representa el hiperplano x1 C 4x2 D 11, su vector característico a D Œ 1; 4T y los semiespacios
HC y H .
Llamaremos hiperplano
H de vector característico a 2 Rn ; a ¤ 0, al conjunto H D fx 2 Rn W aT x D cg, con
En un hiperplano aT x D c, la constante c determina el desplazamiento del hiperplano del origen. Un hiperplano se
T
c 2 R. Un hiperplano
es el de
conjunto
dedonde
unaxecuación
enhiperplano
Rn . (aT x0 D c). Esa última
puede expresar
la forma fxde
W asoluciones
.x x0 / D 0g,
punto del
0 es cualquierlineal
expresión se puede trabajar un poco más pues fx W aT .x
x0 / D 0g D x0 C a? , donde a? es el complemento ortogonal
n
Un hiperplanodeen
esfvun
o una
variedad
lineal
.n en un1/-dimensional.
a, esRdecir
W aTespacio
v D 0g. Loafín
que lleva
a que
un hiperplano
consiste
desplazamiento x0 más todos los vectores
˚
ortogonales al vector característico a: el conjunto de soluciones de aT x D c: x C ker.a/, recordemos.
Dado un hiperplano H , aT x D c, llamaremos semiespacios cerrados 0de borde H a los conjuntos HC D x 2 Rn W aT x c
Un politopo esun conjunto formado por la intersección de un número finito
de semiespacios
cerrados. Un politopo
˚
˚
ı
˚
ı
T por un punto.
n
conjunto
por la intersección
de unde
número
finito
2 Rnque
W apasan
x > c y H D x 2 Rn W aT x < c .
y H D x 2 Rcónico
W aTesxun
c , yformado
semiespacios
abiertos
borde
Hdeasemiespacios
H C D xcerrados
Un poliedro es un politopo acotado y no vacío. Es fácil comprobar que la intersección de conjuntos
convexos es convexa
Los semiespacios
de
borde H son convexos; la unión de H convexos.
y H Sies
el espacio Rn . En
la figura ?? se representa el hiy que, por lo tanto, los politopos y los poliedros son conjuntos C
un politopo P es un poliedro, cualquier punto
se puede expresar como combinación convexa de sus puntos extremos.
a
Teorema 8.1 Sea C un conjunto convexo e y un punto exterior a la adherencia de C . Existe un vector a tal que
aT y < Kınfx2C aT x.
H+
21
x
x̄0
a
y
H−
H
Figura 8.10: Hiperplano x1 C 4x2 D 11 y los semiespacios en los que divide R2
Figura 8.12: Hiperplano x1 C 4x2 D 11 y los semiespacios en los que divide R2
En un hiperplano aT x D c, la constante c determina el desplazamiento del hiperplano del origen.
Un
se puede
expresar de la
aTT.xy los
x0 / D
0g, donde x0 es H
cualquier
punto del
perplano x1 C 4x2 D 11,hiperplano
su vector
característico
a forma
D Œ fx1;W 4
semiespacios
C yH .
hiperplano (aT x0 D c). Esa última expresión se puede trabajar un poco más pues fx W aT .x x0 / D
0g D
a?constante
, donde a? esc eldetermina
complementoelortogonal
de a, es decirdel
fv W hiperplano
aT v D 0g. Lodel
que lleva
En un hiperplano aT x
Dxc,
desplazamiento
origen. Un hiperplano se
0 Cla
a que un hiperplano
consiste en un desplazamiento x0 más todos los vectores ortogonales al vectorT
T
puede expresar de la forma
fx
W
a
.x
x
/
D
0g,
donde
x
0
T 0 es cualquier punto del hiperplano (a x0 D c). Esa última
característico a: el conjunto de soluciones de a x D c: x0 C ker.a/, recordemos.
?
expresión se puede trabajarUnun
pocoesmás
pues fx
W aT por
.x la intersección
x0 / D 0gdeD
, donde
a? es el
complemento ortogonal
0 C afinito
politopo
un conjunto
formado
un x
número
de semiespacios
cerraT
dos.0g.
Un Lo
politopo
conjunto
formado por la
intersección
número finito de semiespade a, es decir fv W a v D
quecónico
llevaesa un
que
un hiperplano
consiste
endeunundesplazamiento
x0 más todos los vectores
cios cerrados que
por un punto.
ortogonales al vector característico
a: pasan
el conjunto
de soluciones de aT x D c: x0 C ker.a/, recordemos.
B.3y no
Separating
Supporting
Hyperplanes
Un poliedro es un politopo acotado
vacío. Es fáciland
comprobar
que la intersección
de conjuntos 519
Un politopo es un conjunto
formado
la intersección
de un
finito
de semiespacios
convexos es
convexa ypor
que por
lo tanto los politopos
y losnúmero
poliedros son
conjuntos
convexos. En estacerrados. Un politopo
figura se muestran
varios politopos;de
el del
es un finito
poliedro.
cónico es un conjunto formado
por la intersección
uncentro
número
de semiespacios cerrados que pasan por un punto.
Un poliedro es un politopo acotado y no vacío: ver figura ??. Es fácil comprobar que la intersección de conjuntos
convexos es convexa y que, por lo tanto, los politopos y los poliedros son conjuntos convexos. Si un politopo P es un
poliedro, cualquier punto se puede expresar como combinación convexa de sus puntos extremos.
Teorema 8.2 Sea C un conjunto convexo e y un punto exterior a la adherencia de C . Existe un vector a tal que
aT y < Kınfx2C aT x.
Si un politopo P es un poliedro, cualquier
punto
se puede expresar como combinación convexa de
Fig. B.5
21Polytopes
sus puntos extremos.
Teorema 8.1 Sea C un conjunto convexo e y un punto exterior a la adherencia de C . Existe un
vector a tal que aT y < Kınfx2C aT x.
It is easy to see that half spaces are convex sets and that the union of H+ and
B.3 Separating and Supporting Hyperplanes
519
Fig.politopos:
B.5 Polytopes
Figura 8.13: Diversos
el del centro, un poliedro
D EMOSTRACIÓN
Sea
2.5 .Separating
and supporting hyperplanes
It is easy to see that half spaces
ı D Kınfare
kxconvex
yk2 >sets
0: and that the union of H+ and
47
x2C
H− is the whole space.
Existe un x0 en la frontera de C tal que kx0 yk2 D ı. Esto es así pues la función continua f .x/ D kx yk2 alcanza
Definition.
set which
can bepor
expressed
as the
intersection
of a finite
su mínimo en cualquier
conjunto A
cerrado
y acotado
lo que sólo
es necesario
considerar
x ennumber
la intersección de la
ofbola
closed
halfdespaces
to 2ı.
be a convex polytope.
adherencia de C y la
abierta
centro is
y ysaid
radio
A continuación We
probaremos
a D polytopes
x0 y satisface
condiciones
see thatque
convex
are thelassets
obtaineddel
as enunciado
the familydel
ofteorema.
solutionsEn efecto, para
E
cualquier ˛, 0 to
˛
1,
al
ser
C
un
conjunto
convexo,
el
punto
x
C
˛.x
x
/
2
C
,
por
lo
que
20
0
a set of linear inequalities of the form
kx0 C ˛.x
x0T/
yk2 kx
yk2 :
0
2
a1 x b21
T
a2 x b 2
E1
Desarrollando,
T
·E3˛ 2 kx x0 k22 0:
2˛.x0 y/ .x x·0 / C
· ·
Considerando esta expresión cuando ˛ ! 0C, se tiene que
· ·
TT
bmx0 / 0
.x0 ay/
m x .x
o que
since each individual inequality defines
a half space and the solution family is
Figure 2.18 Three ellipsoids in R2 , centered at the origin (shown as the
the lower
intersection
of contain
these half spaces.
(If some
a = 0, the
set can still, as
T ellipsoid
dot),
points
dots.resulting
The
.x0 that
y/T x .xthe
y/T x0shown
D .x as the
y/iTupper
y C .x
y/
.x0 y/
0
0
the Ereader
may
verify,
be there
expressed
as the0 intersection
of
a
finite
number
of half
minimal,
since
exist ellipsoids
that
contain
the
points,
and
1 is not
T
D .x
y/same
y Creason.
ı2:
0 the
are smaller (e.g., E3 ). E3 is not minimal
for
The ellipsoid
spaces.)
E2 is minimal, since no other ellipsoid (centered at the origin) contains the
Several
in Fig. B.5. We note that a polytope may be
Haciendo a D x0 points
y queda
probado
elare
teorema.
andpolytopes
is contained
inillustrated
E2 .
empty, bounded, or unbounded. The case of a nonempty bounded polytope is of
specialgeométrica
interest and
weteorema
distinguish
this
case
by the following.
La interpretación
de este
es que,
dado
un conjunto
convexo C y un punto y exterior a la adherencia
de C , existe un hiperplano que contiene a y, sin tocar a C , estando C en uno de sus semiespacios abiertos. Este hiperplano
Definition. A nonempty bounded polytope is called a polyhedron.
(de vector característico a en el teorema) se denomina hiperplano separador de C e y.
Si C y D son dos conjuntos convexos disjuntos, C \ D D ;, existe entonces un a ¤ 0 y un b tales que aT x b, para
todo x 2 C , y aT x todox 2 D. Dicho de otra manera, la función aT x b es no positiva en C y no negativa
˚ b, para
T
B.3
SEPARATING
AND
SUPPORTING
en D. El hiperplano x W a x D b es un hiperplano
separador
de los conjuntos C y D como se ve en la figura ??.
HYPERPLANES
aT x ≥ bthe most
aTimportant
x≤b
The two theorems in this section are perhaps
results related to
convexity. Geometrically, the first states that given a point outside a convex set, a
hyperplane can be passed through the point that does not touch the convex set. The
second, which is a limiting case of the first, states that given a boundary point of a
D
convex set, there is a hyperplane
that contains the boundary point and contains the
convex set on one side of it.
C
a
Figure 2.19 The hyperplane
{x Hiperplano
| aT x = b} separates
disjoint
Figura 8.14:
separadorthe
entre
C y Dconvex sets
C and D. The affine function aT x − b is nonpositive on C and nonnegative
on D.
Existen bastantes principios de dualidad que se usan en la asignatura, en especial en la teoría y técnicas de optimización,
que relacionan un problema en términos de vectores en un espacio vectorial con otro expresado en términos de subespacios
22
a
Figure 2.19 The hyperplane
{x Hiperplano
| aT x = b} separates
disjoint
Figura 8.14:
separadorthe
entre
C y Dconvex sets
C and D. The affine function aT x − b is nonpositive on C and nonnegative
on D.
Figura 8.15: Distancia más corta de un punto a un conjunto convexo en términos de la de a hiperplanos separadores
Figura 8.15: Distancia más corta de un punto a un conjunto convexo en términos de la de a hiperplanos separadores
en ese espacio. En gran cantidad de esos principios está presente la relación que se ilustra en la figura 8.15. La distancia
más corta de un punto a un conjunto convexo es igual al máximo de las distancias desde el punto a los hiperplanos que
en ese espacio. En gran
cantidad
esos principios
está presente
la minimización
relación que
ilustraseen
la figura
??.
separan
el conjuntode
convexo
del punto. El problema
original de
sobresevectores
convierte
en otro
de La distancia más
sobre
hiperplanos.
corta de un punto a maximización
un conjunto
convexo
es igual al máximo de las distancias desde el punto a los hiperplanos que separan
el conjunto convexo Teorema
del punto.
ElCproblema
vectores
8.3 Sea
un conjunto original
convexo e yde
un minimización
punto frontera de C .sobre
Existe un
hiperplanose
queconvierte
contiene a yen
y a otro
C en de maximización
sobre hiperplanos. uno de sus semiespacios cerrados.
D EMOSTRACIÓN . Sea fy .k/ g una sucesión de puntos exteriores a la adherencia de C . Sea fa.k/ g la sucesión de puntos
Teorema 8.3 Sea normalizados,
C un conjunto
e yde un
punto
frontera
. Existe
un hiperplano
que contiene a y y a C en
ka.k/ k2convexo
D 1, obtenida
aplicar
el teorema
anteriorde
a laCsucesión
anterior,
tales que,
uno de sus semiespacios cerrados.
T
T
a.k/
y .k/ < Kınf a.k/
x2C
x:
.k/
Comofy
fa.k/
g es
una sucesión
acotada,
subsucesión
fa.k/ g, k 2a H,
a un límite
se tiene
D EMOSTRACIÓN . Sea
g una
sucesión
deuna
puntos
exteriores
laconvergerá
adherencia
de Ca..Para
Seaestefaa.k/
g laque,
sucesión de puntos
x 2 C,
normalizados, ka.k/para
k2 cualquier
D 1, obtenida
de aplicar el teorema
anterior
a
la
sucesión
anterior,
tales
que,
T
T
aT y D lKım a.k/ y .k/ lKım a.k/ x D aT x:
k2H
k2H
T
T
.k/
.k/
.k/
K
a
y
<
ı
nf
a
x: cerrados y que contiene algún punto
Un hiperplano que contiene un conjunto convexo C en uno de sus semiespacios
x2C
frontera de C se denomina hiperplano de apoyo de C .
De acuerdo con esta definición, el teorema anterior dice que, dado un conjunto convexo C y un punto frontera y de C ,
.k/
Como fa.k/ g es unaexiste
sucesión
acotada,
una
subsucesión
g, k 2 H, convergerá a un límite a. Para este a se tiene que,
un hiperplano
de apoyo
de C
que contiene y.fa
˚
para cualquier x 2 C En
, la figura 8.16 x W aT x˚ D aT x0 es el hiperplano
de apoyo de C en el punto x0 : el punto x0 y el conjunto C están
˚
x .TGeométricamente quiere
decir
T
separados por el hiperplano
x W aT x D aT.k/
x W aT x D aT x0 es
0
T
.k/ que el hiperplano
T
˚ yT.k/ T lKım
a
y
D
lK
ı
m
a
a
x
D
a
x:
tangente al conjunto C en x0 y el semiespacio x W a x a x0 contiene a C .
k2H
k2H
Un hiperplano que contiene un conjunto convexo C en uno
24 de sus semiespacios cerrados y que contiene algún punto
frontera de C se denomina hiperplano de apoyo de C .
De acuerdo con esta definición, el teorema anterior dice que, dado un conjunto convexo C y un punto frontera y de C ,
Dual de
cones
andcontiene
generalized
51
existe un hiperplano2.6
de apoyo
C que
y. inequalities
a
x0
C
Figure 2.21 The hyperplane {x | aT x = aT x0 } supports C at x0 .
Figura 8.16: Hiperplano de apoyo de C en x0
˚
En la figura ?? x W aT x D aT x0 es el hiperplano de apoyo de C en el punto x0 : elT puntoTx0 y el conjunto C están
that the ˚point xT0 and the
set C are separated by the hyperplane {x | a x = a x0˚}.
T
T
separados por el hiperplano
x W a interpretation
x D aT x0 . Geométricamente
quiere
T hiperplano x W a x D a x0 es
The geometric
is that the hyperplane
{xdecir
| aT xque
= ael
x } is tangent
0
to C at x0 , and the halfspace {x | aT x ≤ aT x0 } contains C. This is illustrated in
figure 2.21.
A basic result, called the supporting hyperplane theorem, states that for any
nonempty convex set C, and any x0 ∈ bd C, there exists a supporting hyperplane to
C at x0 . The supporting hyperplane theorem is readily proved from the separating
hyperplane theorem. We distinguish two cases. If the interior of C is nonempty,
the result follows immediately by applying the separating hyperplane theorem to
the sets {x0 } and int C. If the interior of C is empty, then C must lie in an affine
set of dimension less than n, and any hyperplane
containing that affine set contains
23
C and x0 , and is a (trivial) supporting hyperplane.
There is also a partial converse of the supporting hyperplane theorem: If a set
is closed, has nonempty interior, and has a supporting hyperplane at every point
in its boundary, then it is convex. (See exercise 2.27.)
˚
tangente al conjunto C en x0 y el semiespacio x W aT x aT x0 contiene a C .
Lema 8.4 (Farkas) El sistema de ecuaciones
Ax D b;
.I /
x 0;
no tiene solución si y sólo si la tiene el sistema
y T A 0T ;
.II /
bT y > 0;
donde A 2 Rmn .
D EMOSTRACIÓN . El lema se puede reformular de la siguiente manera. Si existe un x 0 tal que Ax D b, no existe
ningún y tal que y T A 0T y bT y > 0. Recíprocamente, si no existe ningún x 0 tal que Ax D b, existe un y tal que
y T A 0T y bT y > 0.
Supongamos que el sistema (I) tiene una solución x tal que Ax D b y x 0. Sea y un punto tal que y T A 0T . En
este caso bT y D x T A T y 0 pues x 0 y y T A 0T . Esto demuestra que bT y no puede ser positivo y, por lo tanto,
el sistema (II) no tiene solución.
Supongamos ahora que el sistema (I) no tiene solución. Esto quiere
que by…condiciones
S D fv D Ax
W x 0g;473
es decir
8.1 decir
Dualidad
de óptimo
que b no pertenece al politopo cónico S . Observando la figura ??, está claro que si b … S , existe un hiperplano separador
Politopo cónico S
a3
a2
a1
a4
a5
Hiperplano
b∈
/S
y
Figura 8.2
Figura 8.17: Demostración
del lema de Farkas
Descripción geométrica de la existencia de un hiperplano separador
definido por un y, que separa S y b, y para el cual y T ai 0, i D 1; : : : ; n y y T b > 0, es decir, y forma un ángulo
de más de
grados
con cada
uno de los habitualmente,
vectores columna de
de menos de
90 grados con8forma
b. Estosimétrica
verifica que el
El 90
par
(P)-(D)
se denomina
en Alayliteratura
especializada,
sistema
(II)
tiene
solución.
de la dualidad.
A continuación exponemos dos teoremas que caracterizan las soluciones óptimas del par de
Elproblemas
lema de Farkas
es un resultado importante para el estudio de sistemas lineales de inecuaciones. Su interpretación
primal-dual.
geométrica es la siguiente:
de de
Holguras)
x se
ey
soluciones
factibles
de decir
1. Si Teorema
ai ; i D 1; : :8.3
: ;P
n, (Complementariedad
son los n vectores columna
la matriz Sean
A, que
cumpla
que b D
Ax, x del
0,par
quiere
n
primal-dual
en
forma
simétrica
(P)-(D)
de
(8.8).
Las
condiciones
necesarias
y
queprogramas
el vector b D
a
x
,
x
0;
en
otras
palabras,
que
b
pertenece
al
politopo
cónico
generado
por
los
vectores
i
i D1 i i
suficientes
para
que sean
deejemplo
sus respectivos
problemas
columna
de A. En
la figura
?? seóptimos
muestra un
donde el sistema
(I) no son:
tiene solución: el vector b no pertenece
8 El hiperplano separador del politopo cónico S de la figura debería
T tocar a éste a lo largo de a . El hiperplano de apoyo correspondiente, sí
“casi”
5
A)x = 0
(8.9)
(cT − y
tocaría a a5 .
y
y T (Ax 24
− b) = 0.
(8.10)
Demostración. Como x e y son soluciones factibles de (P) y (D), respectivamente, se tiene
que
474
Capı́tulo 8. Dualidad y análisis de sensibilidad
Semiespacio abierto {y : bT y > 0}
a2
an
474
Capı́tulo 8. Dualidad y análisis de sensibilidad
a1
a3
b
Semiespacio abierto {y : bT y > 0}
a2
an
a1
a3
Cono {y : y T A ≤ 0 T }
b
Figura
8.3 no tiene solución; si (II)
Figura 8.18: El sistema (I) del lema
de Farkas
El sistema (I) del lema de Farkas no tiene solución. La tiene (II)
al cono generado por a1 , a2 , a3 y aTn . La intersección
del cono fy W y T A 0T g (conjunto formado por los vectores
T
{y
:
y
A
≤
0
}
Cono
ı
y que forman un ángulo mayor o igual dea90
con los vectores columna de la matriz A) y el semiespacio abierto
2
fy W bT y > 0g, no es el conjunto vacío: el sistema (II) tiene solución, pues b y cualquier y en el cono que define la
zona sombreada forma un ángulo menor de 90ı y, por lo tanto, bT y > 0.
an
2. El sistema (II) no tiene solución si la intersección del cono fy W y T A 0T g y el semiespacio abierto fy W bT y > 0g
es el conjunto vacío. En la figura ??ase
muestra unFigura
ejemplo
donde
8.3 el sistema (II) no tiene solución. Todo vector y en
b
1
ı
la zona que define el
indicado
un ángulo
mayor no
de 90
consolución.
b. La tieneLa
sintiene
embargo
Elcono
sistema
(I) forma
del lema
de Farkas
tiene
(II)(I) pues b pertenece al
cono generado por a1 , a2 y an .
Semiespacio abierto {y : bT y > 0}
a2
an
a1
b
Cono {y : y T A ≤ 0T }
Semiespacio abierto {y : bT y > 0}
Figura 8.4
El sistema (II) del lema de Farkas no tiene solución. La tiene (I)
Cono {y : y T A ≤ 0T }
Figura 8.19: El sistema
(II) no tiene
Figura
8.4 solución. La tiene (I)
El sistema (II) del lema de Farkas no tiene solución. La tiene (I)
9 Funciones
Recordemos que una función es un caso particular de aplicación donde los conjuntos origen e imagen son conjuntos
de números.
25
Una función f W Rn ! R se dice continua en x si para toda sucesión fx .k/ g que converge a x (expresado x .k/ ! x),
se cumple que f .x .k/ / ! f .x/. De forma equivalente, f se dice continua en x si dado un " > 0, existe un ı > 0 tal que
ky
xk < ı H) kf .y/
f .x/k < " :
Una función f W R ! R se dice satisface la condición de Lipschitz con constante en un conjunto X, si para todo x
e y pertenecientes a X se cumple que
jf .x/ f .y/j jx yj:
Una función que satisface la condición de Lipschitz en un conjunto X se dice continua -Lipschitz en ese X, designándose
f 2 Lip .X /.
Dada una norma vectorial k k en Rn y otra matricial k k en Rmn , m; n > 0, una función g W Rn ! Rmn se
dice satisface la condición de Lipschitz con constante en un abierto D Rn , si para todo x e y pertenecientes a D se
cumple que
kg.x/ g.y/k kx yk:
Una función g que satisface la condición de Lipschitz en D se dice continua -Lipschitz en ese D, designándose g 2
Lip .D/.
Un resultado muy interesante referido a funciones continuas es el teorema de Weierstrass, que dice que una función
continua definida en un conjunto compacto S tiene un punto donde alcanza un mínimo en S . Es decir, existe un x 2 S
tal que para todo x 2 S , f .x/ f .x /.
Un conjunto de funciones f1 ; f2 ; : : : ; fm de Rn en R se puede considerar como una función vectorial
f D Œf1 ; f2 ; : : : ; fm T :
Esta función asigna a todo vector x 2 Rn otro vector f .x/ D Œf1 .x/; f2 .x/; : : : ; fm .x/T de Rm . Tal función vectorial
se dice continua si lo es cada uno de sus componentes f1 ; f2 ; : : : ; fm .
Si cada una de las funciones de f D Œf1 ; f2 ; : : : ; fm T es continua en algún conjunto abierto de Rn , se dice f 2 C . Si
además cada función componente tiene derivadas parciales de primer orden continuas en ese abierto, se dice que f 2 C 1 .
En general, si las funciones componentes tienen derivadas parciales de orden p continuas, se indica f 2 C p .
Si f W Rn ! R y f 2 C 1 , se define el vector gradiente de f como el vector
rf .x/ D
@f .x/
@f .x/ @f .x/
;
;:::;
@x1
@x2
@xn
T
:
También se puede ver expresado alguna vez como fx .x/.
Si f 2 C 2 , se define la matriz Hessiana de f en x como la matriz n n
2 2
3
@ f .x/ @2 f .x/
@2 f .x/
6 @2 x
@x1 @x2
@x1 @xn 7
6
7
1
6 2
7
2
6 @ f .x/ @ f .x/
@2 f .x/ 7
6
7
2
r 2 f .x/ D 6
@x2 @xn 7
6 @x2 @x1 @ x2
7:
::
::
::
6
7
::
6
7
:
:
:
6 2 :
7
4 @ f .x/ @2 f .x/
@2 f .x/ 5
@xn @x1 @xn @x2
@2 xn
A esta matriz también se la puede ver designada como F .x/.
Para la función vectorial f D Œf1 ; f2 ; : : : ; fm T , f 2 C 1 , se define la matriz Jacobiana como la matriz m n
2
3
@f1 .x/ @f1 .x/
@f1 .x/
6 @x1
@x2
@xn 7
6
7
6 @f2 .x/ @f2 .x/
@f2 .x/ 7
6
7
6
7
@x2
@xn 7 :
rf .x/ D J .x/ D 6 @x1
6
7
::
::
::
::
6
7
:
:
:
:
6
7
4 @fm .x/ @fm .x/
@fm .x/ 5
@x1
@x2
@xn
Si f 2 C 2 , es posible definir m Hessianas F1 .x/; F2 .x/; : : : ; Fm .x/ para cada una de las f1 ; : : : ; fm .
26
Una función f W Rn ! Rm es afín si es la suma de una función lineal y una constante; es decir, tiene la forma
f .x/ D Ax C b, donde A 2 Rmn y b 2 Rm .
Teorema 9.1 Teorema de Taylor. Si f W Rn ! R y f 2 C 1 en una región que contiene el segmento Œx1 ; x2 , es decir
puntos ˛x1 C .1 ˛/x2 ; 0 ˛ 1, existe un , 0 1, tal que
f .x2 / D f .x1 / C r T f x1 C .1 /x2 .x2 x1 / :
Además, si f 2 C 2 , existe un ; 0 1, tal que
f .x2 / D f .x1 / C r T f .x1 /.x2
1
x1 / C .x2
2
x1 /T F x1 C .1
/x2 .x2
x1 / ;
donde F denota la matriz Hessiana de f .
Si la función f W R ! R es continua y derivable k C 1 veces en un intervalo, o segmento, Œx; x0 , existe un b entre x
y x0 tal que
f .x/ D
f 00 .x0 /
x0 C
x
2Š
k f .kC1/ .b/
x0 C
x
.k C 1/Š
2
f .x0 / C f 0 .x0 / x
x0
f .k/ .x0 /
x
kŠ
x0
C
C
kC1
f 000 .x0 /
x
3Š
:
x0
3
C Las aproximaciones por este teorema para una función concreta, sen.x/, se pueden ver en la figura ??.
Figura 9.20: Función sen.x/ y, en x D 0, las aproximaciones por Taylor de primer orden, de orden 3, 5, 7, 9, 11 y 13
Una función f W Rn ! R se dice convexa (figura ??) si cumple que f .˛x C ˇy/ ˛f .x/ C ˇf .y/ para todo
x; y 2 Rn y todo ˛; ˇ 2 R, con ˛ C ˇ D 1, ˛ 0, ˇ 0. Si S Rn es un conjunto convexo y f W Rn ! Rm es una
función afín, la imagen de f .S / D ff .x/ W x 2 S g es un conjunto convexo. De forma similar, si f W Rk ! Rn es una
función afín, la imagen inversa f 1 .S / D fx W f .x/ 2 S g también es convexa.
Teorema 9.2 Teorema del valor intermedio. Si f W R ! R es una función continua en el intervalo Œa; b, toma todos
los valores entre f .a/ y f .b/. Más concretamente, si y es un número entre f .a/ y f .b/, existe un número c dentro de
Œa; b, es decir, tal que a c b, en el que f .c/ D y.
27
y = f(x)
y
20 |
convex
CHAPTER
0
Fundamentals
(a)
Figura 9.21: Función
convexa
x
f
f (c)
f (c)
y
a c
a
b
(a)
x
convex
Figura 9.22: Teorema
del valor intermedio
(b)
c
b
(b)
Figure 0.1 Three important theorems from calculus. There
a and b such that: (a) f (c) = y, for any given y between f (a
0.4, the Intermediate Value Theorem (b) the instantaneous sl
(f
(b) − f (a))/(b
− a)enbyel Theorem
0.6,b,
the
Mean Value Theor
Teorema 9.3 Teorema del valor medio. Si f W R ! R es una función continua
y derivable
intervalo Œa;
existe
0
region is equal in area to the horizontally shaded region, by
un número c entre a y b tal que f .c/ D f .b/ f .a/ =.b a/.
Value Theorem for Integrals, shown in the special case g(x) =
Teorema 9.4 Teorema de Rolle. Si f W R ! R es una función continua y derivable en el intervalo Œa; b y suponemos
que f .a/ D f .b/, existe entonces un número c, entre a y b, tal que f 0 .c/ D 0. G ENERALIZACIÓN Si f W R ! R
THEOREM
0.4de orden
(Intermediate
Value
Theorem)
Let fnbe
a continuous funct
es continua y derivable n 1 veces en Œa; b
y la derivada
n existe en el
abierto
.a; b/, y existen
intervalos
a1 < b1 a2 < b2 : : : an < bn en Œa; b, tales que f .ak/
D f .bk/ every
para todo
k Dbetween
1 : : : n, existe
un and
número
c More preci
f realizes
value
f (a)
f (b).
en .a; b/ tal que la derivada de orden n de f en c es cero.
f (a) and f (b), then there exists a number c with a ≤ c ≤ b
f
| CHAPTER 0 Fundamentals
x
EXAMPLE nonconvex
0.7 Show that f (x) = x 2 − 3 on the interval [1, 3] must take o
(c)
f (c)
Because ff (c)
(1) = −2 and f (3) = 6, all values
√ betw
Fig. 7.3 Convex and nonconvex
1, mustfunctions
be taken on by f . For example, setting c = 3, not
y
secondly, f (2) = 1.
THEOREM 0.5
a c
b
(a)
a
c
n→∞ (c)
n→∞
(b)
Figura 9.23: Teorema del valor medio
othercalculus.
words, There
limitsexist
maynumbers
be brought
inside continuou
Figure 0.1 Three important theoremsInfrom
c between
a and b such that: (a) f (c) = y, for any given y between f (a) and f (b), by Theorem
THEOREM 0.6 (Mean Value Theorem) Let f be a continuously differen
0.4, the Intermediate Value Theorem (b) the instantaneous slope of f at c equals
[a, b]. Then there exists a number c between a and b such
(f (b) − f (a))/(b − a) by Theorem 0.6, the Mean Value Theorem (c) the vertically shaded
(b − a).
region is equal in area to the horizontally shaded region, by Theorem 0.9, the Mean
Value Theorem for Integrals, shown
in the special case g(x) = 1.
28
EXAMPLE 0.8
THEOREM 0.4
(Continuous Limits) Let f be a continuous function in a ne
limn→∞ xn = x0 . Then
b
b
c
a
lim f (xn ) = f lim xn = f (
Apply the Mean Value Theorem to f (x) = x 2 − 3 on the in
(Intermediate Value Theorem) Let f be a continuous
function
on the interval
[a, b]. Then
The content
of the theorem
is that because
f (1) =
f realizes every value between f (a)
and
f
(b).
More
precisely,
if
y
is
a
number
between
exist a number c in the interval (1, 3) satisfying f (c) = (6 −
Figura 9.24: Teorema de Rolle
Teorema 9.5 Teorema del valor medio de las integrales. Si f W R ! R es una función continua en el intervalo Œa; b y
g W R ! R una función integrable que no cambia de signo en Œa; b, existe entonces un número c entre a y b tal que
Z
f(c)
b
a
f .x/g.x/ dx D f .c/
Z
b
g.x/ dx:
a
f (c)
a
c
b
(b)
a
c
b
(c)
Figura 9.25: Teorema del valor medio de las integrales
0.1 Three important theorems from calculus. There exist numbers c between
b such that: (a) f (c) = y, for any given y between f (a) and f (b), by Theorem
9.1 Condiciones necesarias y suficientes de primer y segundo orden que ha de cumplir un
e Intermediate Value
Theorem
(b) the instantaneous slope of f at c equals
punto
mínimo
− f (a))/(b − a) by Theorem 0.6, the Mean Value Theorem (c) the vertically shaded
n
definir condiciones
y suficientes
determinar
is equal in areaSetotrata
thedehorizontally
shadednecesarias
region, by
Theorem para
0.9, the
Mean si dada f W  ! R,  2 R , un punto x
cumple
Theorem for Integrals, shown in the special case g(x) = 1. minimizar f .x/:
x
Un punto x 2  se dice que es un mínimo local de la función f W  ! R si existe un > 0 tal que f .x/ f .x /
te Value Theorem)
Let f be a continuous function on the interval [a, b]. Then
para todo x 2  a una distancia menor que de x . Es decir, para todo x 2  tal que jx x j < . Si f .x/ > f .x /
a number between
very value between
para todo x f2(a)
, xand
¤ x f, (b).
a una More
distanciaprecisely,
menor que ifdey xis
, se dice que x es un mínimo local estricto de f en .
(b), then there exists a number c with a ≤ c ≤ b such that f (c) = y.
Teorema 9.6 Condiciones necesarias de primer orden Sea  un subconjunto de Rn y una función f W  ! R,
f 2 C 1 . Si x en un mínimo local de f en , se cumple que rf .x / D 0.
en the
x seinterval
cumple que
/ D take
0, al punto
x values
se le denomina
(x) = x 2 − 3Sion
[1,rf
3].x
must
on the
0 andestacionario.
1.
Teorema 9.7 Condiciones necesarias de segundo orden Sea  un subconjunto de Rn y una función f W  ! R,
cause f (1) =
6, alllocal
values
−2 and
f −2
2 C 2and
. Si xf (3)
en un=mínimo
de
en , se cumple
que 6,
rfincluding
.x√
/ D 0 y r02and
f .x / es semidefinida positiva.
√f between
aken on by f . For example, setting c = 3, note that f (c) = f ( 3) = 0, and
Teorema 9.8 Condiciones suficientes de segundo orden Sea  un subconjunto deRn y una función f W  !
(2) = 1.
2
2
R,
f 2 C . Si se cumple que rf .x / D 0 y r f .x / es definida positiva, x en un mínimo local estricto de f en .
Teorema 9.9 Si f es convexa, cualquier mínimo local x es un mínimo global de f . Si además f es derivable,
local x function
es un mínimo
de f .
Letcualquier
f be amínimo
continuous
in aglobal
neighborhood
of x0 , and assume
s Limits)
= x0 . Then
lim f (xn ) = f
n→∞
lim xn = f (x0 ).
29
n→∞
r words, limits may be brought inside continuous functions.
9.2 Teorema de la función implícita
Teorema 9.10 Sea x0 D Œx01 ; x02 ; : : : ; x0n T un punto de Rn que satisface estas condiciones:
(a) Las m funciones fi 2 C p , i D 1; 2; : : : ; m, en algún entorno de x0 , para alguna p 1.
(b) fi .x0 / D 0; i D 1; 2; : : : ; m:
2
@f1 .x0 /
6 @x1
6
::
(c) La matriz Jacobiana de la función vectorial, rf .x0 / D 6
4 @fm:.x0 /
@x1
Entonces existe un entorno de xO 0 D Œx0mC1 ; x0mC2 ; : : : ; x0n T 2 Rn
O i D 1; 2; : : : ; m tales que:
ese entorno existen funciones i .x/,
m
3
@f1 .x0 /
@x: m 7
7
::
7, es regular.
@fm .x0 / 5
@xm
::
:
tal que para xO D ŒxmC1 ; xmC2 ; : : : ; xn T en
(i) i 2 C p .
(ii) x0i D i .xO 0 /; i D 1; 2; : : : ; m.
O 2 .x/;
O : : : ; m .x/;
O x/
O D 0; i D 1; 2; : : : ; m.
(iii) fi .1 .x/;
Este teorema 9 es muy útil para respaldar la caracterización de puntos óptimos en programación matemática con y sin
condiciones, solución de ecuaciones lineales y no lineales y muchos otros aspectos que analizamos en la asignatura.
Supóngase que se tiene una función vectorial f W Rn ! Rm que cumple
fi .x/ D 0;
i D 1; 2; : : : ; m:
El teorema de la función implícita estudia, si n m de las variables son fijas, si el problema se puede resolver en m
incógnitas. Es decir, si x1 , x2 ; : : : ; xm se pueden expresar en función de las restantes n m de la forma
xi D i .xmC1 ; xmC2 ; : : : ; xn / ;
A las funciones i W Rn
m
i D 1; 2; : : : ; m:
! R, si existen, se las denomina funciones implícitas.
Ejemplo 9.1 Consideremos la ecuación x12 C x2 D 0. Una solución de la misma es x1 D, x2 D 0. En un entorno de esta
solución, sin embargo, no hay función tal que x1 D .x2 /. En esta solución no se cumple la condición .c/ del teorema
u
de la función implícita. En cualquier otra solución si existe dicha .
Ejemplo 9.2 Sea A una matriz m n y considérese el sistema de ecuaciones lineales Ax D b. Si A se estructura así,
A D ŒB; C , donde B es m m, entonces se satisface la condición .c/ del teorema de la función implícita si, y sólo si, B
es regular. Esta condición se corresponde con los requisitos y enunciados de la teoría de ecuaciones lineales. La función
u
implícita se puede considerar como una generalización no lineal de la teoría lineal.
10 Dualidad en Programación Matemática y Optimización
La Dualidad y su teoría juega un papel muy destacado en Programación y Optimización lineal y no lienal, donde se
trata de resolver el problema general
minimizar
f .x/
n
x2R
sujeta a
ci .x/ D 0;
cj .x/ 0;
i 2 E;
j 2 I:
Las función objetivo, f , y las condiciones, ci y cj , son, en general, no lineales, continuas y tienen derivadas parciales
continuas hasta al menos primer orden. Los conjuntos E y I contienen los índices de las condiciones de igualdad y de
desigualdad, o inecuaciones.
Desde el punto de vista práctico, en los algoritmos de resolución de este problema, la dualidad sirve para verificar
la optimalidad de un proceso iterativo o las condiciones de óptimo, para analizar la sensibilidad de una solución a la
9 Sus
orígenes están asociados a Newton, Leibnitz y Lagrange, pero fue formulado por Cauchy
30
variación de los parámetros del problema, para estudiar la velocidad de convergencia de determinados algoritmos de
optimización que usan su formulación y contemplar diversos aspectos geométricos que permiten interpretar mejor lo que
se está haciendo en la búsqueda de una solución.
436
Chapter 14 Dual and Cutting Plane Methods
Las ideas y formulación que exponemos a continuación siguen enteramente lo que expone al respecto el libro de
Luenberger citado en el apartado de bibliografía. Se basa en una forma elegante y global de contemplar la dualidad en
términos de conjuntos e hiperplanos que tocan esos conjuntos. Evidencia el papel de los multiplicadores de Lagrange como
considered
to ser
points
in a vector
space.
The theory
provides
a symmetry
definidores de
hiperplanosas
quedual
pueden
considerados
los duales
de puntos
en un espacio
vectorial.
Esta forma teórica de
primal
and dual
problems
and
symmetry
be considered
as perfect perfecta si
enfrentarse abetween
la dualidad
proporciona
una simetría
entre
losthis
problemas
primalcan
y dual,
la cual pude considerarse
forsonconvex
problems.
Forlanon-convex
the “imperfection”
is gap
made
clear o brecha
los problemas
convexos.
Si no lo son,
imperfección problems
la plasma claramente
el denominado
de dualidad
dual, que tiene
geométrica
sencilla
en este contexto,
y mucha The
importancia
los algoritmos de
by una
the interpretación
duality gap which
has muy
a simple
geometric
interpretation.
global en
theory,
programación
lineal is
y nopresented
lineal que se
en el curso
en la as
asignatura.
which
in estudian
this section,
serves
useful background when later we
specialize
toincógnitas
a local duality
theory
that
can be useddeeven
without
convexity
and
En el problema
dual las
por resolver
son los
multiplicadores
Lagrange
del problema
primal,
que miden las
sensibilidades
del
primal
a
variaciones
en
los
coeficientes
que
determinan
las
condiciones
de
este
problema
y determinan
which is central to the understanding of the convergence of dual algorithms.
como unas penalizaciones
que
se
introducen
en
su
función
objetivo
por
no
utilizar
los
recursos
que
fijan
esas
As a counterpoint to Section 11.9 where equality constraints were considered condiciones
adecuadamente. La función de Lagrange a este respecto incorpora toda la información disponible del problema.
before inequality constraints, here we shall first consider a problem with inequality
La teoríaconstraints.
global que seInexpone
en esteconsider
apéndice the
es laproblem
base sobre la que construir dualidades de tipo local para los
particular,
diversos problemas lineales y no lineales como los que se verán en los distintos temas del curso, incluso sin la existencia
de convexidad, o en algoritmos especializados para
problemasfx
de Programación Lineal como los de punto
minimize
(1)interior, dual
del Símplex, etc.
to gx
≤0
De momento vamos a referirnos a problemas subject
de programación
matemática
como este
x ∈ minimizar
f .x/
n
x2R
andg0are defined on . The function g
⊂ E n is a convex set, and the functions
(1)
sujeta a f
g.x/
is p-dimensional. The problem is not necessarily
x 2 ; convex, but we assume that there
is a feasible point. Recall that the primal function associated with (1) is defined for
n
asconjunto convexo y las funciones, la escalar f W Rn ! R y la vectorial g W Rp ! Rn , están
E
donde  2 zR∈
espun
definidas en . Este problema no es necesariamente convexo pero se asume que tiene al menos un punto factible. Esta
z
= que
inf se
fx
gx
≤ zque
x ∈adoptar
la convención de signos
(2)adecuada.
notación es perfectamente compatible con
otras
utilizan
sin más
La función
primal asociada
a (??)
define,hand
para un
z 2 of
Rp ,inequality
como
defined
by letting
these right
side
constraint take on arbitrary
values. It is understood !.z/
that (2)
isffdefined
on thez; x
set2 D
D Kınf
.x/ W g.x/
g:= z gx ≤ z, for some
(2)
x ∈ .
∗
Se llega a ella dejando
que el (1)
término
la derecha
la inecuación
definen
las condiciones
puedaon
tomar valores
If problem
has adesolution
x∗dewith
value f ∗ que
= fx
, then
f ∗ is the point
p+1
arbitrarios. Se
entiende
que
(??)
está
definida
en
el
conjunto
D
D
fz
W
g.x/
z;
para
algunos
x
2
g.
the vertical axis in E
where the primal function passes through the axis. If (1)
∗ valor de la función objetivo igual a f D f .x /, entonces f es el
Si el problema
(??)
tiene
una
solución
confun
does not have a solution, xthen
= inffx gx ≤ 0 x ∈ is the intersection
pC1
punto de ejepoint.
vertical de R
donde la función primal se cruza con ese eje. Si (??) no tiene solución, ese punto de cruce
es f D Kınf ff .x/
W g.x/
0; principle
x 2 g. is derived from consideration of all hyperplanes that lie
The
duality
El principio
de dualidad
se deduce
de la As
consideración
hiperplanos
que quedan
por vertical
debajo de la función
below
the primal
function.
illustrateddeintodos
Fig. los
14.1
the intercept
with the
∗ con el eje vertical por debajo de f , o
primal. Como
ilustra
la
figura
??,
todos
los
hiperplanos
que
se
indican
se
cruzan
axis of such a hyperplanes lies below (or at) the value f .
en f .
w(z)
r
f*
Hiperplano
debajo de w(z)
z
Fig. 14.1 Hyperplane below z
Figura 10.26: Hiperplano por debajo de !.z/.
31
Para expresar esta propiedad se define la función dual en el cono positivo de Rp como
./ D Kınf ff .x/ C Tg.x/ W x 2 g:
(3)
p
En general, puede que no sea finita dentro del ortante positivo, RC
, pero la región donde está definida es convexa.
Proposición 10.1 La función dual es cóncava en la región donde es finita.
D EMOSTRACIÓN . Supóngase que 1 y 2 están en la región finita y sea 0 ˛ 1. Entonces
.˛1 C .1
˛2 // D Kınf ff .x/ C .˛1 C .1
˛/2 /T g.x/ W x 2 g
Kınf f˛f .x1 / C ˛T1 g.1 / W x1 2 g
C Kınf f.1
˛/f .x2 / C .1
D ˛.1 / C .1
˛/.2 /:
˛/T2 g.x2 / W x2 2 g
Se define D sup f./ W 0g, suponiéndose que el supremo se extiende a toda la región donde es finita.
Ahora pasamos a la forma débil de la dualidad.
Proposición 10.2 Forma débil de dualidad. f .
D EMOSTRACIÓN . Para todo 0 se tiene que
./ D Kınf ff .x/ C T g.x/ W x 2 g
Kınf ff .x/ C T g.x/ W g.x/ 0; x 2 g
Kınf ff .x/ W g.žx/ 0; x 2 g D f :
Adoptando e supremos de .x/ se tiene que f .
De acuerdo con este resultado, la función dual proporciona cotas inferiores del valor óptimo de f .
La función dual tiene una interpretación geométrica interesante. Si se considera el vector Œ1 T T 2 RpC1 , con 0
y la constante c, el conjunto de vectores Œr zT T 2 RpC1 tales que el producto interior Œ1 T Œr zT T r C T z D c
define un hiperplano en RpC1 . Para diferentes valores de c se tiene diferentes hiperplanos, todos paralelos entre si.
Para un vector dado Œ1 T T consideremos el hiperplano más bajo posible de esa forma que casi toca —soporta—
la región de encima de la función primal del problema (??). Supongamos que x1 define ese punto de contacto y que
r D f .x1 / y z D g.x1 /. Se tendrá que c D f .x1 / C T b.x1 / D ./.
Ese hiperplano se cruzará con el eje vertical en un punto de la forma Œr0 0T . Este punto también satisfará que
Œ1 T T Œr0 0T D c D ./. Lo que lleva a que c D r0 . Por lo que ese punto dará ./ directamente. La función
Chapter
14 donde
Dualseand
Cutting
Plane Methods
dual pues, en438
, en igual
al punto
cruzan
el hiperplano
definido por que justo toca el epigrafo —el conjunto
de puntos situados por encima del gráfico de una función— de la función primal.
w (z)
f∗
gap de dualidad
ϕ∗
hiperplano más alto
z
Fig. 14.2
TheHiperplano
highest hyperplane
Figura
10.27:
más alto.
Furthermore, this intercept (and dual
function value) is maximized by the
32
Lagrange multiplier which corresponds to the largest possible intercept, at a point
no higher than the optimal value f ∗ . See Fig. 14.2.
By introducing convexity assumptions, the foregoing analysis can be
strengthened to give the strong duality theorem, with no duality gap when the
constraints of the form hx = 0, as in Section 11.9.
Specifically, we consider the problem
maximize
fx
(4)
0 degx
≤ 0 dual) se maximiza con el multiplicador
Además, como indica la figura ??, ese subject
punto deto
crucehx
(y el=
valor
la función
de Lagrange que corresponde al plano más alto posible que intercepta el eje vertical, siendo el punto de esa intercepción
x∈
menor o igual que el valor óptimo f . La diferencia constituye el gap de dualidad.
Si se incorporan suposiciones de convexidad, el análisis que estamos haciendo de completa con el teorema de la
where h is affine of dimension m, g is convex of dimension p, and is a convex
dualidad fuerte, cuando no hay gap de dualidad y la intersección de esos planos con el eje vertical es el propio f . Esto
se puede ver set.
en la figura ??.
r
w (z)
f * = ϕ∗
hiperplano óptimo
z
14.3 The
strong
Therefuerte
is no. duality
Figura 10.28:Fig.
Expresión
gráfica
del duality
teorematheorem.
de la dualidad
No hay gap
gap de dualidad.
El teorema de la dualidad fuerte lo referimos al problema general
minimizar
f .x/
n
x2R
sujeta a
h.x/ D 0
g.x/ 0
x 2 ;
(4)
donde h W Rm ! Rn es afín, g W Rp ! Rn es convexa y  es convexo. La función dual de este problema es
.; / D Kınf ff .x/ C Th.x/ C Tg.x/ W x 2 g;
(5)
y D sup f.; / W 2 Rm ; 2 Rp ; 0g.
Una función h.x/ es regular con respecto a  si el conjunto C D fy W h.x/ D y para algún x 2 g de Rn contiene
una bola abierta en torno a 0; es decir, C contiene un conjunto de la forma fy W jyj < "g para algún " > 0. Esto viene a
decir que h.x/ puede hacerse 0 y variar arbitrariamente en torno a 0 en cualquier dirección.
Teorema 10.3 Teorema de la dualidad fuerte. Supongamos que en el problema (??) h es regular con respecto a  y
que existe un punto x 2  en el que h.x/ D 0 y g.x/ 0.
Supongamos que el problema tiene como solución x con un valor de la función objetivo f .x / D f . Entonces, para
todo y todo 0 se cumple que
f :
Además, existen unos y 0 tales que
.; / D f y por lo tanto D f . Los vectores y son los multiplicadores de Lagrange del problema.
Como conclusión resumida de lo expuesto sobre dualidad para programación no lineal, se pueden enfrentar los problemas primal y dual como sigue:
f D minimizar !.z/
D maximizar ./
Primal
Dual
sujeta a
sujeta a
z0
33
0
10.1 Dualidad Lagrangiana
Es una forma de denominar lo que acabamos de exponer. La función de Lagrange del problema (??) escrito así
minimizar
f .x/
n
x2R
sujeta a
h.x/ D 0
(6)
g.x/ 0
x 2 ;
es
La función de Lagrange dual es
Th.x/
L.x; ; / D f .x/
Tg.x/:
def
q.; / D Kınf L.x; ; /:
x
Si la función objetivo, h.x/ y g.x/ son convexas, con 0 la función de Lagrange es convexa y una cota inferior del
valor óptimo de la función objetivo de (??). El problema dual de éste es
maximizar q.; /
sujeta a
0;
que es siempre convexo.
10.2 Dualidad de Wolfe
Un poco distinta de las anteriores, especialmente indicada para los métodos de punto interior que se ven en el curso.
El problema dual es
max. L.x; ; /
s. a
rx L.x; ; / D 0
0:
10.3 Ejemplo
En el caso de un problema de Programación Lineal en forma estándar
minimizar
cT x
n
x2R
sujeta a
T .Ax
la función de Lagrange es L.x; ; / D c T x
Ax D b
x 0;
T x, o
b/
L.x; ; / D T b C c
AT Su problema dual
T
max. q.; / D Kınf fL.x; ; /g D b C Kınfx
s. a
0:
n
c
T
A T
x:
T o
x D
(
T b
1
si c
si c
AT AT D0
¤0
Si c A T ¤ 0 el ínfimo es claramente 1, por lo que hay que excluir del problema aquellos para los que se
den esos caos. Por ello, el problema dual queda
maximizar T b
s. a
c
AT D 0;
El dual de Wolfe sería exactamente el mismo. El gap de dualidad
cT x
T b D c T x
T Ax D x T c
34
0:
A T D x T :
11 Bibliografía
B ERTSEKAS , D.P. 2003. Convex Analysis and Optimization. Athena Scientific.
B OYD , S. Y VANDENBERGHE , L. 2004. Convex Optimization. Cambridge University Press.
DE LA F UENTE , J.L. 1998. Técnicas de cálculo para sistemas de ecuaciones, programación lineal y programación
entera. Segunda edición. Reverté.
H ALMOS , P.R. 1974. Finite-Dimensional Vector Spaces. Springer Verlag.
K UHN , H.W. Y T UCKER , A.W. 1951. Nonlinear Programming. Proceedings of the Second Berkeley Symposium on
Mathematical Statistics and Probability. University of California Press. Verlag.
L UENBERGER , D.G. 1969. Optimization by Vector Space Methods. John Wiley and Sons.
L UENBERGER , D.G. Y Y E , Y. 2009. Linear and Nonlinear Programming. Springer Verlag.
N OCEDAL , J. Y W RIGHT, S.J. 2006. Numerical Optimization. Springer Verlag.
R IAZA , R. Y Á LVAREZ , M. 1996. Cálculo infinitesimal. Vol. I. Sociedad de Amigos de la Escuela Técnica Superior de
Ingenieros Industriales de Madrid.
R IAZA , R. Y Á LVAREZ , M. 1997. Cálculo infinitesimal. Vol. II. Sociedad de Amigos de la Escuela Técnica Superior de
Ingenieros Industriales de Madrid.
ROCKAFELLAR , R.T. 1970. Convex Analysis. Princeton University Press.
S AUER , T. 2013. Análisis numérico. Segunda edición. Pearson educación.
W OLFE , P. 1961. A Duality Theorem for Non-Linear Programming. Quart. Appl. Math. 19, Nı 3.
35