Escuela Técnica Superior de Ingenieros IndustrialesUniversidad Politécnica de Madrid

Curso 2013–2014

Definiciones, notacionesy resultados básicosde matemáticas

José Luis de la Fuente O’Connorjldelafuente@etsii.upm.es

joseluis.delafuente@upm.es

1

2

E N ESTA INTRODUCCIÓN a la asignatura Matemáticas de la Especialidad–Ingeniería Eléc-trica se recopilan conceptos, definiciones, relaciones y resultados que puede ser útil recordaro considerar para seguir su desarrollo de manera provechosa. Todos o casi todos se han estu-

diado en otras asignaturas de cursos anteriores a aquél en el que se imparte ésta. En ningún caso esun 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 laslecciones y presentaciones de las clases.

1 Conjuntos

Un conjunto es una colección de objetos: los números naturales, las soluciones de un problemadeterminado, los municipios de una provincia, etc. Se identifica por una letra mayúscula: el conjuntoS , 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 elementoa pertenece a un conjunto se indica a 2 S . Los conjuntos se definen mediante la enumeración entrellaves de sus elementos, S D fa; b; : : : g, o especificando, también entre llaves, la propiedad que loscaracteriza, 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 losnú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 unsubconjunto del conjunto S , o que está contenido en S 0, expresándose S 0 � S o S � S 0.

La unión de dos conjuntos S y T , expresada S [ T , es el conjunto formado por los elementos quepertenecen a S o a T .

La intersección de S y T , expresada S \ T , es el conjunto formado por los elementos que perte-necen 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 elementosde 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 � bse indica Œa; b�. El formado por los x tales que a < x � b, por .a; b�. El de los x que verifican quea < x < b, por .a; b/.

Si S es un conjunto no vacío de números reales acotados superiormente —mayorados—, existe unnúmero real mínimo y tal que x � y para todo x 2 S . Al número y se le denomina cota superiormínima o supremo de S ; se expresa así:

supx2S

.x/ o sup fx W x 2 Sg :

De forma similar se define la cota inferior máxima —o ínfimo— de un conjunto S no vacío denúmeros reales acotados inferiormente o minorados:

Kınfx2S

.x/ o Kınf fx W x 2 Sg :

2 Aplicaciones

Dados dos conjuntos S y T , una aplicación f de S en T , expresada como f W S ! T , es unaasociación o criterio que a cada elemento de S hace corresponder uno de T .

3

La imagen de un elemento x 2 S con la aplicación f W S ! T es el elemento f .x/ 2 T . Elconjunto imagen f .S/ = ff .x/ 2 T; para todo x 2 Sg. La imagen de un subconjunto S 0 � S conla aplicación f sería, por consiguiente, el subconjunto imagen f .S 0/. El conjunto S se conoce comoorigen o dominio de definición y el T como dominio de valores. Una aplicación f W S ! T se diceinyectiva 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 x2, 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 con-juntos 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 Stal que f .x/ D y.

Una aplicación se dice biyectiva si es inyectiva y suprayectiva. Ejemplo, si Jn es el conjunto de losnúmeros enteros de 1 a n, Jn D f1; : : : ; ng, y se define una aplicación � W Jn ! Jn que modifica elorden de disposición de los elementos de Jn —estas aplicaciones se denominan permutaciones—, talaplicación es biyectiva.

Un conjunto S se dice numerable si existe una biyección entre N y S : a cada unos de los n elemen-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 � 1se le hace corresponder un x.n/ 2 T : n 7! x.n/. Tal sucesión se expresa como fx.1/; x.2/; : : : g ofx.n/gn�1.

Los conjuntos dotados de ciertas leyes de composición o asociación interna —adición, multiplica-ción, división o cualquier otra—, se dice que poseen una estructura. Las estructuras fundamentalesson: grupo, anillo (Z por ejemplo), cuerpo (R y C, por ejemplo) y espacio vectorial.

La imagen de un elemento x 2 S con la aplicación f W S ! T es el elemento f .x/ 2 T . Elconjunto imagen f .S/ = ff .x/ 2 T; para todo x 2 Sg. La imagen de un subconjunto S 0 � S conla aplicación f sería, por consiguiente, el subconjunto imagen f .S 0/. El conjunto S se conoce comoorigen o dominio de definición y el T como dominio de valores. Una aplicación f W S ! T se diceinyectiva 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 x2, 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 con-juntos 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 Stal que f .x/ D y.

Una aplicación se dice biyectiva si es inyectiva y suprayectiva. Ejemplo, si Jn es el conjunto de losnúmeros enteros de 1 a n, Jn D f1; : : : ; ng, y se define una aplicación � W Jn ! Jn que modifica elorden de disposición de los elementos de Jn —estas aplicaciones se denominan permutaciones—, talaplicación es biyectiva.

Un conjunto S se dice numerable si existe una biyección entre N y S : a cada unos de los n elemen-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 � 1se le hace corresponder un x.n/ 2 T : n 7! x.n/. Tal sucesión se expresa como fx.1/; x.2/; : : : g ofx.n/gn�1.

Los conjuntos dotados de ciertas leyes de composición o asociación interna —adición, multiplica-ción, división o cualquier otra—, se dice que poseen una estructura. Las estructuras fundamentalesson: grupo, anillo (Z por ejemplo), cuerpo (R y C, por ejemplo) y espacio vectorial.

RCQ

ZN

43 Espacios vectoriales

SeaK un cuerpo, un espacio vectorialE sobreK es un conjunto dotado de una ley de composicióninterna, adición, con la siguientes propiedades —grupo conmutativo—,

x C y D y C x.x C y/C z D x C .y C z/

x C ø D xx C .�x/ D ø;

4

y una ley de composición externa, producto por un escalar, de la que el dominio de operadores es K,con las siguientes propiedades,

1 � x D x˛.ˇ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. Enlas aplicaciones que se estudian en la asignatura los casos más importantes ocurren cuando K D Ro K D C. Con la notación K designaremos a cualquiera de los cuerpos R o C y por x un vectorcualquiera de un espacio vectorial.

Un ejemplo característico de espacio vectorial lo constituye el formado por sucesiones ordenadasde n elementos cualesquiera de K, o n-uplas x D .x1; : : : ; xn/, definiendo la suma de vectoresmediante

.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

PnkD0 akxk, con

coeficientes ak, reales o complejos, n � 0.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 2M H) x C y 2M;8x 2M y 8� 2 K H) �x 2M:

La intersección de una familia cualquiera de subespacios de E es también un subespacio.SiX es un subconjunto cualquiera de E, el subespacio hXi engendrado porX es la intersección se

todos los subespacios que contienen a X . Cuando hXi D E, se dice que X es una parte generadorade E.

Dados vectores x1; : : : ;xn y escalares �1; : : : ; �n, el vector formado según la expresión

x D �1x1 C � � � C �nxnse dice que es combinación lineal de los vectores x1; : : : ;xn de coeficientes �1; : : : ; �n. Un sub-conjunto X de E es un subespacio si y sólo si contiene a cualquier combinación lineal de cualquiersubconjunto finito de vectores de X . También se demuestra que el subespacio hXi es el conjunto detodas 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 que

PkiD1 �ixi D 0 ; linealmente independientes, si

kXiD1

�ixi D 0 H) �i D 0; 0 � i � k :

5

Una parte X de un espacio vectorial E se dice que es una familia libre si los vectores de cualquiersubconjunto finito de X son linealmente independientes.

La dimensión de un subespacio es el máximo número de vectores linealmente independientes en elsubespacio.

Una base de un espacio vectorial E es cualquier subconjunto B de E que sea, simultáneamen-te, una parte libre y generadora de E; dicho de otra forma, una base de un espacio vectorial es unconjunto —normalmente se supone ordenado (numerado)— de vectores linealmente independientesque generan dicho espacio. Se demuestra que cualquier espacio vectorial tiene una base y que todas lasbases de un mismo espacio tienen la misma cardinalidad —se pueden poner en biyección—. Cuandoel 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 Kn,

e1 D

266664

1

0:::

0

377775 ; e2 D

266664

0

1:::

0

377775 ; : : : ; en D

266664

0

0:::

1

377775 ;

forman una base en dicho espacio; éste, por tanto, tiene dimensión n. Esta base se denomina base ca-nónica de Kn. En esta base, cualquier vector xT D Œx1; x2; : : : ; xn� se puede expresar de la siguienteforma: 2

66664

x1

x2:::

xn

377775 D x1

266664

1

0:::

0

377775C x2

266664

0

1:::

0

377775C � � � C xn

266664

0

0:::

1

377775 :

Si A y B son subconjuntos de un espacio vectorial E, el conjunto AC B se define como:

AC B D faC 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 sedenomina directa, escribiéndose A˚ B . Si A˚ B D E, cualquier vector c 2 E se descompone demanera única como c D a C b, con a 2 A y b 2 B; también se dice que A y B son subespaciossuplementarios.

3.1 Espacios normados

Si en un espacio vectorial E sobre K (R o C) se define una norma vectorial como una aplicaciónk � k W E ! R que verifica

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;kuC vk � kuk C kvk 8u; v 2 E;

se dice que E es un espacio vectorial normado.La condición kuCvk � kukCkvk 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 quela suma de los otros dos: ver figura. Una variante de esta regla es la siguiente:

ku � vk � kuk � kvk:6

3.1 Espacios normados

Si en un espacio vectorial E sobre K (R o C) se define una norma vectorial como una aplicaciónk � k W E ! R que verifica

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;kuC vk � kuk C kvk 8u; v 2 E;

se dice que E es un espacio vectorial normado.La condición kuCvk � kukCkvk 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 quela suma de los otros dos: ver figura. Una variante de esta regla es la siguiente:

ku � vk � kuk � kvk:

uC v

u

v

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

kxkp D�jx1jp C � � � C jxnjp

�1=p;

denominadas normas p de Hölder. Casos particulares lo constituyen las correspondientes a p D 1 yp D 2:

kxk1 DnXiD1jxi j

kxk2 Dpjx1j2 C � � � C jxnj2 :

Esta última se denomina en Rn norma euclídea. También en Kn es una norma la dada por

kxk1 D mKax1�i�n

jxi j :

Estas normas cumplen, cualquiera que sea x 2 Kn, que

kxk1 � kxk2 � kxk1 � nkxk1 :

Si la bola cerrada unidad en R2 es el conjunto fx 2 R2 W kxk � 1g, sus formas para las normasvectoriales 1, 2,1, y p son las que representa la figura 3.2.

7

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

kxkp D�jx1jp C � � � C jxnjp

�1=p;

denominadas normas p de Hölder. Casos particulares lo constituyen las correspondientes a p D 1 yp D 2:

kxk1 DnXiD1jxi j

kxk2 Dpjx1j2 C � � � C jxnj2 :

Esta última se denomina en Rn norma euclídea. También en Kn es una norma la dada por

kxk1 D mKax1�i�n

jxi j :

Estas normas cumplen, cualquiera que sea x 2 Kn, que

kxk1 � kxk2 � kxk1 � nkxk1 :

Si la bola cerrada unidad en R2 es el conjunto fx 2 R2 W kxk � 1g, sus formas en espaciosvectoriales normados por la 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

kf kp D"Z 1

0

jf .t/jp dt#1=p

y porkf k1 D mKax

t2Œ0;1�jf .t/j :

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 unN 2 N tal que a partir de él, n � N , se cumple que kx.n/�vk < ".Cuando una sucesión fx.n/g admite un vector límite v sólo tiene ese vector como límite —si existe

límite es único—: se escribe lKımn!1 x.n/ D v. Es equivalente decir que lKımn!1 x.n/ D v y quelKımn!1 kx.n/ � vk D 0. En particular, x.n/ ! 0 si y sólo si kx.n/k ! 0.

1Cuando así lo aconseja la dificultad de la notación, una sucesión también se designa por fxng; sus integrantes, x.k/.

7

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

28/63

– Si el conjunto fx 2 R2 W kxk � 1g es la bola cerrada unidad enR2, su forma para las normas vectoriales 1, 2, 1, y p son estas.

‖x‖1 =2∑

i=1

|xi|

‖x‖2 =√

|x1|2 + |x2|2 =√

xT x

‖x‖∞ = max1≤i≤2

|xi|

‖x‖p =[|x1|p + |x2|p

]1/p

, (1 ≤ p < ∞)

kxk1 D2

i

iD1jxi j

kxk2 Dqjx1j2C jx2j2 D

qxTx

kxk1 D mKax1�i�2

jxi j

kxkp D Œjx1jp C jx2jp�1=p ; .1 � p <1/

Figura 3.2: Forma de la bola unidad para diferentes normas en R2

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 quekx.p/ � x.q/k < ". Toda sucesión convergente es una sucesión de Cauchy pero pueden existir es-pacios normados con sucesiones de Cauchy que no son convergentes. Un espacio vectorial normadose 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. Todoespacio vectorial normado de dimensión finita es un espacio de Banach. En un espacio de dimensióninfinita esto no es cierto; por ejemplo, es fácil ver que en C Œ0; 1� la sucesión de funciones cuyasgráficas son las de la figura 3.3 es una sucesión de Cauchy para cualquier norma k � kp, pero no tienelímite en C Œ0; 1�.

-

6

= =

= =

����������

1n

1n

0 1 x

fn.x/

Figura 3.3: Gráfica de una de las funciones de una sucesión de Cauchy

8

3.2 Espacios con producto interior

Sea E un espacio vectorial sobre un cuerpo K (R o C); una forma sesquilineal —vez y medialineal— sobre E es una aplicación, h�j�i W E �E ! K, que verifica2:

1) h˛uC ˇvjwi D ˛hujwi C ˇhvjwi y

2) huj˛vC ˇwi D ˛hujvi C ˇhujwi;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 cumpleque

u ¤ 0 H) hujui > 0 ;se dice que la forma es definida positiva, denominándosela también producto escalar. Una formasesquilineal sobre R es siempre bilineal.

Un espacio prehilbertiano es un espacio vectorial sobre K dotado de una forma hermítica definidapositiva. Todo espacio prehilbertiano es un espacio normado mediante

kvk Dphvjvi :

En la demostración de que esta definición corresponde a la de una norma en E juega un papel impor-tante 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 delproducto escalar k � k D

ph�; �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 su k � k2 es igual a la

unidad, se denominan ortonormales. Para dos vectores ortogonales se tiene la identidad

kuC vk2 D kuk2 C kvk2 ;que es una generalización del teorema de Pitágoras. En un espacio prehilbertiano, el único vectorortogonal a todos los vectores del espacio es el vector nulo; si este espacio es de dimensión finita esposible construir una base ortonormalizada.

En un espacio euclídeo n-dimensional, el ángulo entre dos vectores x e y es

� D arc cos�xTy

kxkkyk�;

donde

� D xTy

kxkkykcumple que �1 � � � 1, para cualesquiera x e y .

2La barra designa complejo conjugado.

9

Dos vectores son ortogonales si xTy D 0 (� D �=2; � D 0); alineados, si xTy D kxkkyk(� D 0; � D 1); opuestos, si xTy D �kxkkyk (� D �; � D �1). Forman un ángulo agudo sixTy > 0 (� < �=2; � > 0) y un ángulo obtuso si xTy < 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 ortogonalde M , M?, es el subespacio formado por todos los vectores ortogonales a los de M , siendo unsubespacio suplementario de M ; es decir M ˚M? D E. Cualquier x 2 E, por consiguiente, sepuede expresar como x D aC b, con a 2M y b 2M?.

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, operador lineal u homomorfismo, f , de E en F , como una aplicación f WE ! 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 particularesinteresantes: el primero cuando E D F , en este caso se dice que f es un operador lineal de E oendomorfismo de E; el segundo cuando F D K —el cuerpo base—, en cuyo caso la aplicación sedenomina forma lineal sobre E.

El conjunto L.E; F / de todas las aplicaciones lineales del espacio E en el espacio F se estructuracomo un espacio vectorial si se definen las siguientes operaciones:

a) adición .f C g/ W .f C g/.x/ D f .x/C g.x/ 8x 2 EIb) producto por un escalar �f W .�f /.x/ D �f .x/ 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 deun subespacio de E forma un subespacio de F . En particular, la imagen de todo E es un subespaciode F que se denomina subespacio imagen de f , representándose mediante Im.f /. Análogamente, elconjunto anti-imagen de un subespacio de F forma un subespacio de E. En particular, la anti-imagendel subespacio nulo de F forma lo que se denomina el núcleo de la aplicación, representándose porker.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 porx0 C ker.f /, donde x0 es una solución particular de la ecuación. En particular, la aplicación esinyectiva si y sólo si ker.f / D ;.

SeanE 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 queE D F : f � se dice entonces que es el operador adjunto de f . Cuando un operador f de E cumpleque 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 esun operador hermítico. Un operador simétrico cumple que

hxjf .y/i D hf .x/jyi;10

mientras que uno hermítico, quehxjf .y/i D hf .x/jyi:

Un operador f deE es unitario cuando es invertible y su inverso coincide con su adjunto. Es decir,si f � D f �1. Para un operador unitario se tiene que

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 denominaoperadores isométricos.

Dada una transformación lineal, u aplicación lineal, f W E ! E, se dice que un subespacio W deE es un subespacio invariante frente a f (o f -invariante) si para todo vector w 2 W se cumple quef .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 basesfe1; e2; : : : ; eng de E y ff1; f2; : : : ;fmg de F por una tabla de coeficientes, matriz asociada, de mfilas y n columnas:

A D

2664a11 � � � a1n:::

: : ::::

am1 � � � amn

3775 2 Km�n :

Los coeficientes aij están definidos por

g.ej / DmXiD1

aijfi ; 1 � j � n :

El vector columna j -ésimo 266664

a1j

a2j:::

amj

377775

representa el vector g.ej / en la base .fi/. A partir de la matrizA se pueden calcular los componentesy1; y2; : : : ; ym del vector y D g.x/ en la base .fi/, conociendo los componentes x1; x2; : : : ; xn enla base .ej /. En efecto:

266664

y1

y2:::

ym

377775 D x1

266664

a11

a21:::

am1

377775C x2

266664

a12

a22:::

am2

377775C � � � C xn

266664

a1n

a2n:::

amn

377775 :

Expresión que también se puede escribir de la siguiente forma:

y DnXiD1

xiai ;

11

donde ai es el vector columna i -ésimo de la matriz A. Así pues, si se fijan dos bases en E y F , cadaaplicación lineal, g W E ! F , queda unívocamente representada por una matriz. Recíprocamente,toda matriz en Km�n define unívocamente una aplicación lineal entre dos espacios E y F de dimen-siones n ym en los que se han fijado dos bases. En particular, se pueden identificar las matricesm�ncon las aplicaciones lineales de Kn en Km.

Las matrices de m filas y n columnas con coeficientes en el cuerpo K forman un espacio vectorial,Km�n, 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 AT , traspuesta de A.

El núcleo y la imagen de una matriz A 2 Km�n, ker.A/ y Im.A/, respectivamente, se definencomo los subespacios de Kn y Km que son el núcleo y la imagen de la aplicación lineal asociada:

ker.A/ D fx 2 Kn W Ax D 0gIm.A/ D fy 2 Km W y D Ax; x 2 Kng

%

A2Km�n

:

Dicho de otra forma, la imagen de una matriz es el subespacio generado por los vectores columna dela matriz; los vectores fila también generan un subespacio que no es otro que la imagen de AT .

Para una matriz A 2 Rm�n se cumple que:

ker�AT

�D .Im.A//?Im�AT

�D .ker.A//?

ker.A/D �Im �AT

��?Im.A/D �ker

�AT

��?:

El Teorema fundamental del algebra lineal establece que si A 2 Rm�n se cumple que

ker .A/˚ Im�AT

� D Rn:

El rango de una matriz es la dimensión3 de su subespacio imagen:

rango.A/ D dim.Im.A//

Una matriz A 2 Km�n se dice de rango completo si rango.A/ D mKın.m; n/. Una matriz cuadradaA 2 Kn�n se denomina singular si rango.A/ < n; regular si rango.A/ D n.

La aplicación asociada a una matriz A 2 Rm�n es suprayectiva si rango.A/ D m. Para una matrizA 2 Km�n 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.

4.1 Normas de matrices

Aun cuando en lo que sigue nos limitaremos a matrices cuadradas, la mayor parte de las definicio-nes y resultados son extensibles a matrices rectangulares; también supondremos que las matrices sonreales.

3Recordemos: máximo número de vectores linealmente independientes.

12

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 sobreRm�n como una aplicación k � k W Rm�n ! R que cumple:

1) kAk D 0 H) A D 0:2) k�Ak D j�j � kAk:3) kA CBk � kAk C kBk:4) kABk � kAk � kBk:

Existen normas sobre el espacio Rm�n que no son normas matriciales pues no cumplen la propiedad4). Así, si se define

kAk D mKax1�i;j�n

jaij j ;

se satisfacen 1), 2) y 3); sin embargo, tomando A D B Dh1

1

1

1

i, es fácil ver que kABk D 2 >

kAk � kBk D 1, por lo que no se cumple 4).Un ejemplo importante de norma matricial es la norma de Frobenius, definida como:

kAk2F DX

1�i;j�na2ij D traza.ATA/;

donde la traza de una matrizA de orden n esPniD1 ai i . Es fácil ver que esta norma deriva del producto

escalar hAjBi D traza.ATB/, que configura al espacio de las matrices cuadradas como un espacioprehilbertiano. La norma de Frobenius cumple que

kABkF � kAkF � kBkF :

Una norma matricial k � k sobre Rm�n se dice consistente con una norma vectorial k � k0 sobre Rncuando 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 consis-tente. Una norma matricial consistente con una cierta norma vectorial k � k se construye mediante ladefinición

kAk D sup0¤x2Rn

kAxkkxk :

Esta norma matricial se dice inducida por la norma vectorial. Ejemplo: la norma matricial inducidapor la norma euclídea de Rn es la norma espectral:

kAk2 D sup0¤x2Rn

"xTATAx

xTx

#1=2Dp�max.ATA/ D �max.A/;

donde � designa un valor propio de A y � un valor singular. Si k � k es la norma inducida por unacierta norma vectorial y k � k0 es una norma matricial cualquiera consistente con esa norma vectorial,

13

se cumple, para toda matriz A, que kAk � kAk0. En particular, para la norma espectral y la normade Frobenius, se cumple que

kAk2 � kAkF :Las normas matriciales inducidas más usadas son

kAk1 D mKax1�j�n

mXiD1jaij j y

kAk1 D mKax1�i�m

nXjD1jaij j :

Ejemplo 4.1 El efecto que produce aplicar la transformación lineal basada en la matriz

A D"1 2

0 2

#

sobre la bola unidad definida a partir de las normas k � k1, k � k2 y k � k1 en R2, se representa en lafigura 4.4. La aplicación transforma el vector e1 D Œ1; 0�T en sí mismo y e2 D Œ0; 1�T en Œ2; 2�T .

h i j

d e f g

a b c

10 8 7

9 4 6 5

1 2 3

39/63

[0, 1]T

[1, 0]T

[1, 0]T

[2, 2]T

norma ∞

norma 2

norma 1

‖A‖2 ≈ 2,9208

‖A‖∞ = 3

‖A‖1 = 4

norma 1

norma 2

norma 1

– La aplicación transforma el vector e1 D Œ1; 0�T en sí mismo ye2 D Œ0; 1�T en Œ2; 2�T .

Figura 4.4: Efecto de una aplicación lineal sobre la bola unidad para diferentes normas

Tomando 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.Tomando la norma 2, el vector unitario que más se amplifica es el que se representa en la figura

con una recta discontinua. El factor de amplificación es 2,9208.Para la norma1, igualmente, el vector unitario que más se amplifica es el que se representa tam-

bién con la recta discontinua: Œ1; 1�T , que pasa a transformarse en Œ3; 2�T . El factor de amplificación

14

correspondiente es en este caso 3 ya que Œ1; 1�T 1 D 1

Œ3; 2�T 1 D 3: u4.2 Matrices ortogonales, matrices de permutación y matrices de proyección

Una matriz Q 2 Rm�n se dice ortogonal si verifica que QTQ D I ; es decir, cuando sus vectorescolumna son ortogonales dos a dos y de norma euclídea unitaria (ortonormales). Si Q 2 Rn�n esortogonal, se cumple queQQT D QTQ D I .

Las matrices ortogonalesQ 2 Rm�n verifican:

kQk2 D 1kQkF D n1=2kQAk2 D kAk2kQAkF D kAkF

9>>>>=>>>>;

si m � n

ykQk2 D 1kQkF D m1=2kAQk2 D kAk2kAQkF D kAkF

9>>>>=>>>>;

si m � n

Una matriz de permutación es una matriz cuadrada cuyas columnas están formadas por las de lamatriz unidad permutadas. Una matriz de permutación es una matriz ortogonal.

Una matriz se dice simétrica si se verifica que AT D A. Para una matriz cualquiera A 2 Rm�n, lamatriz ATA es simétrica.

Se denomina proyector o matriz de proyección a una matriz P 2 Rn�n que verifica que

P2 D PSi P además es simétrica, se denomina proyector ortogonal o matriz de proyección ortogonal. Si, eneste último caso, F es el subespacio imagen de la matriz P (el mismo que el de la matriz PT ), Pxdefine la proyección ortogonal del vector x sobre F .

Se denomina proyector suplementario de P al proyector S D I � P . Si F D Im.P/ y G Dker.P/, entonces F D ker.S/ y G D Im.S/.

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ıny2Im.P /DF

kx � yk2:

5 Valores propios, valores singulares y formas cuadráticas

5.1 Valores propios

Sea A una matriz cuadrada de orden n y coeficientes en K (R o C). Un vector no nulo u 2 Kn sedenomina vector propio de A si para algún � 2 K se cumple que

Au D �u :15

A este � se le denomina valor propio o autovalor de la matriz A. El conjunto de los valores propiosde una matriz A se denomina espectro de A, designándose por ƒ.A/. El radio espectral, �.A/, sedefine de la siguiente manera:

�.A/ D mKax1�i�n

j�i j:

Para que un número � sea valor propio de A, el sistema lineal y homogéneo de ecuaciones dadopor

.�I �A/x D 0debe tener soluciones distintas de la trivial x D 0. Esto equivale a que

det.A � �I/ D 0 :Esta es una ecuación polinómica de grado n en � que se denomina ecuación característica, o po-linomio característico, de la matriz A. La ecuación característica admite la raíz � D 0 si y sólo sidet.A/ D 0. Una matriz es invertible, por tanto, si y sólo si no admite al cero como vector propio.

Una matriz real de orden n no tiene necesariamente valores propios reales pero, como consecuen-cia del teorema fundamental del álgebra, cualquier matriz compleja tiene al menos un valor propiocomplejo. El número máximo de valores propios es n.

Siendo � un valor propio de la matriz A, el conjunto de soluciones del sistema de ecuaciones

.�I �A/x D 0es un subespacio de Kn que se denomina subespacio propio asociado al valor propio �, designándosecon 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 alsubespacio nulo; esto es,

� ¤ � H) E� \E� D ; :De este modo, la suma de subespacios propios es directa. Se cumple queM

�2ƒ.A/E� D Kn

si y sólo si para cada � 2 ƒ.A/, dim.E�/ D n�; en ese caso existe una base de Kn formada toda ellapor vectores propios de A. Siendo V una matriz cuadrada invertible de orden n cuyas columnas sonlos vectores de esa base, se tiene que

AV D V D ;

dondeD D diag.�1; : : : ; �n/. Alternativamente, se puede escribir que

V �1AV D D ;

por lo que la matriz A es semejante a una matriz diagonal; se dice entonces que la matriz A esdiagonalizable por semejanza.

Toda matriz real y simétrica tiene todos sus valores propios reales y es diagonalizable por semejan-za. Se demuestra además que los subespacios propios correspondientes a valores propios distintos sonortogonales. De aquí se sigue que es siempre posible formar una base ortonormalizada de vectorespropios para una matriz real y simétricaA. Existe entonces una matriz ortogonalQ tal que se verificaque

QTAQ D D; con QT D Q�1 ;y, de aquí que, toda matriz real y simétrica es congruente ortogonal con su reducida diagonal. Es-te resultado fundamental de la teoría de matrices es la versión elemental del denominado teoremaespectral.

16

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 � ncon coeficientes en R, se definen sus valores singulares �i ; i D 1; : : : ;mKınfm; ng, como las raícescuadradas positivas de los valores propios de la matriz cuadrada ATA 2 Rn�n.

Se demuestra que si A 2 Rm�n, existen dos matrices ortogonales,

U D Œu1; : : : ;um� 2 Rm�m

yV D Œv1; : : : ; vn� 2 Rn�n ;

tales queU TAV D diag.�1; : : : ; �p/; p D mKınfm; ng ;

y donde�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 dela aplicación que caracteriza la matriz A. En la figura 5.5 se describe gráficamente el caso en quem D n D 2.

{x} {Ax}

σ1σ2

Figura 5.5: Representación en dos dimensiones de una transformación lineal de la esfera unidad

Para una matriz A 2 Rm�n cuya descomposición en valores singulares es A D U†V T , se definesu matriz pseudoinversa, A�, como

A� D V †�U T ;

donde†� D diag.��11 ; : : : ; ��1r ; 0; : : : ; 0/ 2 Rn�m :

Si A 2 Rm�n es de rango completo y m > n,

A� D �ATA��1AT Isi m < n

17

A� D AT �AAT ��1 :Para cualquier matriz A 2 Rm�n, 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 dela matriz A (subespacio de sus vectores columna) y .I �A�A/ la de proyección ortogonal sobre elnú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. Laexpresión más general de una forma cuadrática es

q.x/ D xTQx ;dondeQ D QT es una matriz simétrica de orden n. Nos limitaremos al análisis de formas cuadráticascon coeficientes reales.

Mediante una transformación lineal de variables, x D T y , una forma cuadrática se puede reducira la forma canónica de suma de cuadrados siguiente:

q.x/ DpXiD1

y2i �pCqXiDpC1

y2i :

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 seintroducen los números menores como

�i D det

266664

q11 q12 � � � q1iq21 q22 � � � q2i:::

:::: : :

:::

qi1 qi2 � � � qi i

377775 ;

la forma cuadrática asociada aQ 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

PTQP D diag.�1; : : : ; �n/:

Haciendo en la forma cuadrática q.x/ D xTQx el cambio de variables x D Py , se tiene que

q.x/ D yTPTQPy D �1y21 C � � � C �ny2n ;lo que hace ver que el rango de la forma cuadrática es el número total —teniendo en cuenta lasmultiplicidades— de valores propios no nulos de Q, mientras que la signatura coincide con la dife-rencia entre los números de valores propios positivos y negativos. En particular, la forma cuadráticaasociada aQ es definida positiva si y sólo si todos los valores propios deQ son positivos.

En ciertos casos es importante acotar el cociente de una forma cuadrática al cuadrado de la normaeuclídea, es decir, el cociente

r.x/ D xTQx

xTx; x ¤ 0 :

18

Mediante una transformación ortogonal x D Py , este cociente se escribe como

r.x/ D �1y21 C � � � C �ny2ny21 C � � � C y2n

;

de manera que se deducen las acotaciones

�min.Q/ � xTQx

xTx� �max.Q/ :

Estas acotaciones no se pueden mejorar ya que siQv D �v,

vTQv

vT vD � :

Una matriz A se dice definida positiva si la forma cuadrática xTAx es positiva para todo vectorx ¤ 0. De forma similar se definen matrices semidefinida positiva, definida negativa y semidefinidanegativa, si xTAx � 0, < 0 y � 0, respectivamente, para todo vector x ¤ 0. La matriz A se diceindefinida si la forma xTAx es positiva para algún x y negativa para otros.

Lema 5.1 Para que una matriz simétrica sea definida positiva es necesario que todos los coeficientesde la diagonal principal sean positivos.

Lema 5.2 Para que una matriz simétrica A sea definida positiva es necesario que el coeficiente demayor valor absoluto esté en la diagonal principal. Más concretamente,

mKaxi¤jjaij j < mKax

kakk:

Lema 5.3 Si en cada fila de una matriz simétricaA el coeficiente de la diagonal principal es mayorque la suma de los valores absolutos de todos los demás coeficientes de la fila, es decir, si

akk >

nXjD1

j¤k

jakj j k D 1; : : : ; n;

A es definida positiva.

DEMOSTRACIÓN. Para x ¤ 0 se tendrá que

q.x/ DXi

Xj

aijxixj �Xi

ai ix2i �

Xi

Xj¤ijaij jjxi jjxj j

>Xi

0@Xj¤ijaij j

1A jx2i j �

Xi

Xj¤ijaij jjxi jjxj j

DXi

Xj¤ijaij jjxi j

�jxi j � jxj j� DXi

Xj¤ijaij jjxj j

�jxj j � jxi j�

D 1

2

Xi

Xj¤ijaij j

�jxi j � jxj j�2 � 0:

Es importante destacar que este último criterio define una condición suficiente, no necesaria. Enefecto, la matriz 2

643 2 2

2 3 2

2 2 3

375 ;

19

es definida positiva, pues

q.x/ D x21 C x22 C x23 C 2.x1 C x2 C x3/2;lo que atestigüa que, cualquiera que sea x ¤ 0, q.x/ > 0. Esta matriz, sin embargo, no satisface ellema 5.3.

Como ya se ha visto, una matriz simétrica definida positiva tiene todos sus valores propios realesy positivos; si es semidefinida, alguno es cero. Si la matriz es negativa definida, todos sus valorespropios son negativos.

Un resultado muy interesante para averiguar el orden de magnitud de los valores propios de unamatriz es el del teorema de Gerschgorin, que dice que si A 2 Rn�n es una matriz simétrica convalores propios �1; �2; : : : ; �n, entonces

mKın1�i�n

�i � mKın1�i�n

8<ˆ:ai i �

nXjD1

j¤i

jaij j

9>>=>>;;

mKax1�k�n

�i � mKax1�k�n

8<ˆ:akk C

nXjD1

j¤k

jakj j

9>>=>>;:

Se dice que una matriz compleja A, de coeficientes aij , cuadrada y de orden n, es de diagonalestrictamente dominante por filas, o simplemente de diagonal dominante por filas, cuando cumpleque

jai i j >Xj¤ijaij j; i D 1; : : : ; n:

Puede darse una definición análoga de matriz de diagonal dominante por columnas.

6 Topología

En un espacio vectorial normado se define una bola abierta, S.x0; r/, de centro x0 y radio r , comoel conjunto de puntos x que verifican kx � x0k < r . Es decir:

S.x0; r/ D fx 2 Rn W kx � x0k < rg:

Una bola cerrada, NS.x0; r/, se define, por el contrario, como el conjunto de puntos x que verificankx � x0k � r . Es decir:

NS.x0; r/ D fx 2 Rn W kx � x0k � rg: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 conjuntopuede, 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 todopunto de S existe una bola abierta contenida íntegramente en S . Dos ejemplos: la bola abierta unidad,

20

S.x; 1/ D fx W kxk < 1g y el espacio Rn en su totalidad. En general los subconjuntos o conjuntosabiertos se caracterizan por no tener límites definidos o ser disjuntos de su frontera (ver más adelantela 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 xexisten un número infinito de puntos de S .

Un punto x se denomina punto de adherencia del subconjunto S cuando todo entorno de dichopunto 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 anglosajonay latinoamericana, clausura cl.S/—. La adherencia de la bola abierta S.x; 1/ D fx W kxk < 1g es lacerrada NS.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 cual-

quier conjunto S es el conjunto cerrado más pequeño que contiene a S . Se puede demostrar que unconjunto es cerrado si y sólo si toda sucesión convergente de elementos de S tiene un límite en eseconjunto.

Un conjunto, o subconjunto, se dice compacto si es cerrado y acotado (contenido en una bola deradio 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 unasubsucesión n

x.`/o`2L

L � N

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

k!1

�r .k/

�:

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 asigna-tura están basadas en unos pocos resultados simples e intuitivos. Entre estos, quizás el más sencilloy usado sea el teorema de la proyección. Su aplicación en la teoría de mínimos cuadrados lineales esfundamental. En un espacio Euclídeo ordinario de tres dimensiones determina que la distancia máscorta de un punto exterior a un plano a ese plano la proporciona la perpendicular al plano desde dichopunto. 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 vectorx 2 H existe un único vector m0 2 M tal que kx � m0k2 � 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 quex �m0 sea ortogonal a M .

DEMOSTRACIÓN. Primero probaremos que si m0 es un vector que minimiza kx � mk, x � m0 esortogonal aM . Supongamos para ello, por el contrario, que existe unm que no es ortogonal a x�m0;

21

sin pérdida de generalidad podemos suponer que kmk D 1 y que hx �m0jmi D ı ¤ 0. Definamosel vectorm1 2M comom1 D m0 C ım. Tendremos que

kx �m1k22 D kx �m0 � ımk22 D kx �m0k22 � hx �m0jımi � hımjx �m0i C jıj2D kx �m0k22 � jıj2 < kx �m0k22:

De esta manera, si x �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 �mk2. En efecto, para todom 2M , el teorema de Pitágoras dice que

kx �mk22 D kx �m0 Cm0 �mk22 D kx �m0k22 C km0 �mk22:Por lo tanto kx �mk2 > kx �m0k2 param ¤ m0.

Demostraremos ahora la existencia de unm0 que minimiza kx�mk2. Si x 2M , entoncesm0 D xy todo estaría probado como es obvio. Si x … M , definamos un ı D Kınfm2M kx � mk2; lo quequeremos es obtener unm0 2M tal que kx �m0k2 D ı.

A tal fin, sea fm.i/g una sucesión de vectores en M tal que kx � m.i/k2 ! ı. Por la ley delparalelogramo4 se tiene que

.m.j / � x/C .x �m.i// 22C .m.j / � x/ � .x �m.i// 2

2D 2

m.j / � x 22C

C2 x �m.i/ 22:

Reordenando, se obtiene

m.j / �m.i/ 22D 2

m.j / � x 22C 2

x �m.i/ 22� 4

x � m.i/ Cm.j /2

2

2

:

Para todo i; j , el vector .m.i/ Cm.j //=2 está en M pues éste es un espacio vectorial (lineal). De ladefinición de ı se deduce que kx � .m.i/ Cm.j //=2k2 � ı, por lo que

m.j / �m.i/ 22� 2

m.j / � x 22C 2

x �m.i/ 22� 4ı2:

Como km.i/�xk22 ! ı2 cuando i !1, km.j /�m.i/k22 ! 0 cuando i; j !1. Es decir, fm.i/g esuna sucesión de Cauchy; como M es un subespacio cerrado, la sucesión fm.i/g tiene un límitem0 enM y, debido a la continuidad de la norma, kx �m0k2 ! ı.

El teorema de la proyección pone en evidencia que la solución del problema

minimizart

ktx � yk

es el vector proyección ortogonal de y sobre x: tx en la figura.

Como km.i/�xk22 ! ı2 cuando i !1, km.j /�m.i/k22 ! 0 cuando i; j !1. Es decir, fm.i/g esuna sucesión de Cauchy; como M es un subespacio cerrado, la sucesión fm.i/g tiene un límitem0 enM y, debido a la continuidad de la norma, kx �m0k2 ! ı.

El teorema de la proyección pone en evidencia que la solución del problema

minimizart

ktx � yk

es el vector proyección ortogonal de y sobre x: tx en la figura.

Exercise

given two n-vectors x 6= 0, y

minimize (over t) ‖tx − y‖

geometrically, tx is the projection of a vector y on the line through 0 and x

0

Vectors 1-20

y

tx

x

8 Conjuntos convexos

Un conjunto C � Rn se dice convexo si y sólo si para todo par de puntos x1;x2 2 C todas lascombinaciones de la forma x D �x1 C .1� �/x2, con 0 � � � 1, están en C . Es decir, cuando paracada par de puntos del conjunto convexo, todos los puntos de la recta que los une están en el conjunto.

tal que jx � x�j < �. Si f .x/ > f .x�/ para todo x 2 �, x ¤ x�, a una distancia menor que � dex�, se dice que x� es un mínimo relativo estricto de f en �.

Proposición 8.1 (Condiciones necesarias de primer orden) Sea � un subconjunto de Rn y unafunción f W �! R, f 2 C 1. Si x� en un mínimo relativo de f en�, para toda dirección d 2 Rn,factible desde x�, se cumple que rf .x�/d � 0.

Corolario 8.2 Sea � un subconjunto de Rn y una función f W � ! R, f 2 C 1. Si x� es unmínimo relativo de f en � y x� es un punto interior de �, se cumple que rf .x�/ D 0.

Proposición 8.3 (Condiciones necesarias de segundo orden) Sea � un subconjunto de Rn y unafunció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:

rf .x�/d � 0:Si rf .x�/d D 0; entonces dTr2f .x�/d � 0:

Proposición 8.4 (Condiciones necesarias de segundo orden) Sea x� un punto interior de � y su-póngase que también un mínimo relativo de f W �! R, f 2 C 2. Entonces:

rf .x�/ D 0:Para todo d ; dTr2f .x�/d � 0:

Proposición 8.5 (Condiciones suficientes de segundo orden) Sea f 2 C 2 una función definida enuna región en la cual x� es un punto interior. Supóngase además que:

rf .x�/ D 0:La matriz Hessiana r2f .x�/ es definida positiva:

x� es entonces un mínimo relativo estricto de f .

9 Conjuntos convexos

Un conjunto C � Rn se dice convexo si y sólo si para todo par de puntos x1;x2 2 C todas lascombinaciones de la forma x D �x1 C .1� �/x2, con 0 � � � 1, están en C . Es decir, cuando paracada par de puntos del conjunto convexo, todos los puntos de la recta que los une están en el conjunto.

La expresión x D �x1 C .1 � �/x2, 0 � � � 1, define la combinación convexa de x1 y x2. Si0 < � < 1, es decir � 2 .0; 1/, la combinación se denomina estrictamente convexa.

25

Conjunto convexo Conjunto no convexo

La expresión x D �x1 C .1 � �/x2, 0 � � � 1, define la combinación convexa de x1 y x2. Si0 < � < 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 dela siguiente manera:

x DpXiD1

�ixi ;

dondepXiD1

�i D 1; �i � 0; i D 1; : : : ; p:

El conjunto intersección de todos los conjuntos convexos que contienen a un subconjunto S � Rnse llama envoltura convexa de S y se designa por conv.S/.

23

4Para u, w 2M , juCwj2 C ju�wj2 D 2juj2 C 2jwj2.

22

8 Conjuntos convexos

Un conjunto C � Rn se dice convexo si y sólo si para todo par de puntos x1;x2 2 C todas lascombinaciones de la forma x D �x1 C .1� �/x2, con 0 � � � 1, están en C . Es decir, cuando paracada par de puntos del conjunto convexo, todos los puntos de la recta que los une están en el conjunto.

tal que jx � x�j < �. Si f .x/ > f .x�/ para todo x 2 �, x ¤ x�, a una distancia menor que � dex�, se dice que x� es un mínimo relativo estricto de f en �.

Proposición 8.1 (Condiciones necesarias de primer orden) Sea � un subconjunto de Rn y unafunción f W �! R, f 2 C 1. Si x� en un mínimo relativo de f en�, para toda dirección d 2 Rn,factible desde x�, se cumple que rf .x�/d � 0.

Corolario 8.2 Sea � un subconjunto de Rn y una función f W � ! R, f 2 C 1. Si x� es unmínimo relativo de f en � y x� es un punto interior de �, se cumple que rf .x�/ D 0.

Proposición 8.3 (Condiciones necesarias de segundo orden) Sea � un subconjunto de Rn y unafunció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:

rf .x�/d � 0:Si rf .x�/d D 0; entonces dTr2f .x�/d � 0:

Proposición 8.4 (Condiciones necesarias de segundo orden) Sea x� un punto interior de � y su-póngase que también un mínimo relativo de f W �! R, f 2 C 2. Entonces:

rf .x�/ D 0:Para todo d ; dTr2f .x�/d � 0:

Proposición 8.5 (Condiciones suficientes de segundo orden) Sea f 2 C 2 una función definida enuna región en la cual x� es un punto interior. Supóngase además que:

rf .x�/ D 0:La matriz Hessiana r2f .x�/ es definida positiva:

x� es entonces un mínimo relativo estricto de f .

9 Conjuntos convexos

Un conjunto C � Rn se dice convexo si y sólo si para todo par de puntos x1;x2 2 C todas lascombinaciones de la forma x D �x1 C .1� �/x2, con 0 � � � 1, están en C . Es decir, cuando paracada par de puntos del conjunto convexo, todos los puntos de la recta que los une están en el conjunto.

La expresión x D �x1 C .1 � �/x2, 0 � � � 1, define la combinación convexa de x1 y x2. Si0 < � < 1, es decir � 2 .0; 1/, la combinación se denomina estrictamente convexa.

25

Conjunto convexo Conjunto no convexo

La expresión x D �x1 C .1 � �/x2, 0 � � � 1, define la combinación convexa de x1 y x2. Si0 < � < 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 dela siguiente manera:

x DpXiD1

�ixi ;

dondepXiD1

�i D 1; �i � 0; i D 1; : : : ; p:

El conjunto intersección de todos los conjuntos convexos que contienen a un subconjunto S � Rnse llama envoltura convexa de S y se designa por conv.S/.

24 2 Convex sets

Figure 2.2 Some simple convex and nonconvex sets. Left. The hexagon,which includes its boundary (shown darker), is convex. Middle. The kidneyshaped set is not convex, since the line segment between the two points inthe set shown as dots is not contained in the set. Right. The square containssome boundary points but not others, and is not convex.

Figure 2.3 The convex hulls of two sets in R2. Left. The convex hull of aset of fifteen points (shown as dots) is the pentagon (shown shaded). Right.The convex hull of the kidney shaped set in figure 2.2 is the shaded set.

Roughly speaking, a set is convex if every point in the set can be seen by every otherpoint, along an unobstructed straight path between them, where unobstructedmeans lying in the set. Every affine set is also convex, since it contains the entireline between any two distinct points in it, and therefore also the line segmentbetween the points. Figure 2.2 illustrates some simple convex and nonconvex setsin R2.

We call a point of the form θ1x1 + · · · + θkxk, where θ1 + · · · + θk = 1 andθi ≥ 0, i = 1, . . . , k, a convex combination of the points x1, . . . , xk. As with affinesets, it can be shown that a set is convex if and only if it contains every convexcombination of its points. A convex combination of points can be thought of as amixture or weighted average of the points, with θi the fraction of xi in the mixture.

The convex hull of a set C, denoted convC, is the set of all convex combinationsof points in C:

convC = {θ1x1 + · · · + θkxk | xi ∈ C, θi ≥ 0, i = 1, . . . , k, θ1 + · · · + θk = 1}.

As the name suggests, the convex hull convC is always convex. It is the smallestconvex set that contains C: If B is any convex set that contains C, then convC ⊆B. Figure 2.3 illustrates the definition of convex hull.

The idea of a convex combination can be generalized to include infinite sums, in-tegrals, and, in the most general form, probability distributions. Suppose θ1, θ2, . . .

Figura 8.6: Envoltura convexa de dos conjuntos de R2. La de la izquierda de 15 puntos; la de la derecha de un conjuntono convexo

Un conjunto C � Rn se dice que es afín (también se dice que C es una variedad afín o una variedadlineal) si para cualesquiera x;y 2 C y cualquier � 2 R se tiene que .1��/xC�y 2 C . El conjuntovacío es afín.

Un conjunto C � Rn es afín si y sólo si es de la forma C D faC l W a 2 Rn; l 2 Lg, donde L esun subespacio vectorial de Rn asociado a C . Es decir, un conjunto afín es un subespacio desplazadodel origen. La dimensión de un 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.

Ejemplo 8.1 El conjunto de soluciones de un sistema de ecuaciones lineales,C D fx W Ax D b;A 2Rm�n;b 2 Rmg, es un conjunto afín. En efecto, supongamos que x1;x2 2 C , es decir, Ax1 D b,

23

Ax2 D b. Entonces, para cualquier � ,

A .�x1 C .1 � �/x2/ D �Ax1 C .1 � �/Ax2D �bC .1 � �/bD b;

lo que prueba que la combinación afín �x1C .1� �/x2 está también en el conjunto C . El subespacioasociado con el conjunto afín C en este caso es el espacio nulo de A, ker.A/. u

Si S � Rn, la envoltura afín de S , aff.S/, es la intersección de todos los conjuntos afines quecontienen a S . Como se puede comprobar, aff.S/ D aff.conv.S//.

Un conjunto C � Rn se dice un cono si para todo x 2 C , �x 2 C , para todo escalar � 2 R

516 Appendix B Convex Sets

convex nonconvex

x1

x2x2

x1

Fig. B.1 Convexity

C

C

CD

D

C + D

2 . C

0 0

Fig. B.2 Properties of convex sets

Definition. Let S be a subset of En. The convex hull of S, denoted co(S), isthe set which is the intersection of all convex sets containing S. The closedconvex hull of S is defined as the closure of co(S).

Finally, we conclude this section by defining a cone and a convex cone. Aconvex cone is a special kind of convex set that arises quite frequently.

0

Not convex

0

Not convex0

Convex

Fig. B.3 Cones

Figura 8.7: Tres conos: el primero y el segundo no son convexos; el tercero si

tal que � � 0. Un cono que también es convexo se denomina cono convexo. En este caso, para todox1;x2 2 C y �1; �2 � 0, �1x1 C �2x2 2 C .

El conjunto fx 2 Rm W x D A˛;A 2 Rm�n;˛ 2 Rn;˛ � 0g es un cono convexo generado por losvectores columna de la matriz A.

El conjunto de todas las combinaciones cónicas, �1x1 C � � � C �kxk, �1; : : : ; �k � 0, de los puntosde un conjunto C es la envoltura cónica de C , cone.C /..

26 2 Convex sets

0

x1

x2

Figure 2.4 The pie slice shows all points of the form θ1x1 + θ2x2, whereθ1, θ2 ≥ 0. The apex of the slice (which corresponds to θ1 = θ2 = 0) is at0; its edges (which correspond to θ1 = 0 or θ2 = 0) pass through the pointsx1 and x2.

00

Figure 2.5 The conic hulls (shown shaded) of the two sets of figure 2.3.Figura 8.8: Envoltura cónica de los dos conjuntos de la figura 8.6

Un punto x es un punto extremo de un conjunto convexo C si y sólo si no es interior a un segmentode recta contenido en C . Es decir, si y sólo si

x D .1 � ˇ/y C ˇz con 0 < ˇ < 1 y y; z 2 C ) x D y D z:

24

Dos resultados importantes debido a Carathéodory dicen que si X � Rn y x 2 cone.X/, existenxi y �i , i D 1; : : : ; n, tales que x DPn

iD1 �ixi . Es decir, cualquier elemento de la envoltura cónicade X es combinación cónica de, a lo sumo, n puntos de X . Igualmente, si X � Rn y x 2 conv.X/,existen xi y �i , i D 1; : : : ; n C 1, tales que x D PnC1

iD1 �ixi . Es decir, cualquier elemento de laenvoltura convexa de X es combinación convexa de, a lo sumo, n C 1 puntos de X . La figura 8.9ilustra estos resultados.

Aspectos geométricos y topológicos en Optimización Lineal 95

donde R+ := [0,+∞[, y supp (λ) := {i ∈ I | λ (i) , 0} , es el soporte de λ. Denota-mos λi := λ (i).

Observación 2.1. Si X := {xi , i ∈ I} ⊂ Rn para cierto conjunto de índices I,entonces un elemento de conv (X) se puede escribir como

∑i∈Iλixi, para λ ∈ R(I)

+ con∑i∈Iλi = 1. Análogamente, un elemento de cone (X) se puede poner como

∑i∈Iλixi,

para cierto λ ∈ R(I)+ .

Definición 2.8. Llamamos envoltura afín de X ⊂ Rn al menor subconjunto afínque contiene a X, es decir,

a f f (X) :=⋂{

A ⊂ Rn : A es afín y X ⊂ A}.

Análogamente a los resultados anteriores tenemos que:

Proposición 2.5. Dado X ⊂ Rn, se tiene que:

a f f (X) =

k∑

i=1

λixi : k ∈ N, xi ∈ X, λi ∈ R, i = 1, 2, . . . , k ;k∑

i=1

λi = 1

Teorema de Carathéodory para conos

Teorema 2.1. Si X ⊂ Rn y x ∈ cone (X), existen xi ∈ X y λi ≥ 0, i = 1, 2, · · · , n,

tales que x =n∑

i=1λixi. Es decir, cualquier elemento de la envoltura cónica de X es

combinación cónica de, a lo sumo, n elementos de X.

Teorema de Carathéodory para convexos

Teorema 2.2. Si X ⊂ Rn y x ∈ conv (X), existen xi ∈ X y λi ≥ 0, i = 1, . . . , n + 1,

conn+1∑i=1λi = 1, tales que x =

n+1∑i=1λixi. Es decir, cualquier elemento de la envoltura

convexa de X es combinación convexa de, a lo sumo, n + 1 puntos de X.

Aspectos geométricos y topológicos en Optimización Lineal 95

donde R+ := [0,+∞[, y supp (λ) := {i ∈ I | λ (i) , 0} , es el soporte de λ. Denota-mos λi := λ (i).

Observación 2.1. Si X := {xi , i ∈ I} ⊂ Rn para cierto conjunto de índices I,entonces un elemento de conv (X) se puede escribir como

∑i∈Iλixi, para λ ∈ R(I)

+ con∑i∈Iλi = 1. Análogamente, un elemento de cone (X) se puede poner como

∑i∈Iλixi,

para cierto λ ∈ R(I)+ .

Definición 2.8. Llamamos envoltura afín de X ⊂ Rn al menor subconjunto afínque contiene a X, es decir,

a f f (X) :=⋂{

A ⊂ Rn : A es afín y X ⊂ A}.

Análogamente a los resultados anteriores tenemos que:

Proposición 2.5. Dado X ⊂ Rn, se tiene que:

a f f (X) =

k∑

i=1

λixi : k ∈ N, xi ∈ X, λi ∈ R, i = 1, 2, . . . , k ;k∑

i=1

λi = 1

Teorema de Carathéodory para conos

Teorema 2.1. Si X ⊂ Rn y x ∈ cone (X), existen xi ∈ X y λi ≥ 0, i = 1, 2, · · · , n,

tales que x =n∑

i=1λixi. Es decir, cualquier elemento de la envoltura cónica de X es

combinación cónica de, a lo sumo, n elementos de X.

Teorema de Carathéodory para convexos

Teorema 2.2. Si X ⊂ Rn y x ∈ conv (X), existen xi ∈ X y λi ≥ 0, i = 1, . . . , n + 1,

conn+1∑i=1λi = 1, tales que x =

n+1∑i=1λixi. Es decir, cualquier elemento de la envoltura

convexa de X es combinación convexa de, a lo sumo, n + 1 puntos de X.

Figura 8.9: El teorema de Carathéodory

Llamaremos hiperplano H de vector característico a 2 Rn; a ¤ 0, al conjunto H D fx 2 Rn WaTx D cg, con c 2 R. Un hiperplano es el conjunto de soluciones de una ecuación lineal en Rn.

Un hiperplano en Rn es un espacio afín o una variedad lineal .n � 1/-dimensional.Dado un hiperplano H , aTx D c, llamaremos semiespacios cerrados de borde H a los conjun-

tos HC D˚x 2 Rn W aTx � c y H� D

˚x 2 Rn W aTx � c, y semiespacios abiertos de borde

H aıHCD

˚x 2 Rn W aTx > c y

ıH�D

˚x 2 Rn W aTx < c. Los semiespacios de borde H son

convexos; la unión de HC y H� es el espacio Rn.

x

H+

H−

H

x0y

a

a

Figura 8.10: Hiperplano �x1 C 4x2 D 11 y los semiespacios en los que divide R2

En un hiperplano aTx D c, la constante c determina el desplazamiento del hiperplano del origen.Un hiperplano se puede expresar de la forma fx W aT .x � x0/ D 0g, donde x0 es cualquier punto delhiperplano (aTx0 D c). Esa última expresión se puede trabajar un poco más pues fx W aT .x�x0/ D0g D x0 C a?, donde a? es el complemento ortogonal de a, es decir fv W aT v D 0g. Lo que llevaa que un hiperplano consiste en un desplazamiento x0 más todos los vectores ortogonales al vectorcaracterístico a: el conjunto de soluciones de aTx D c: x0 C ker.a/, recordemos.

Un politopo es un conjunto formado por la intersección de un número finito de semiespacios cerra-dos. Un politopo cónico es un conjunto formado por la intersección de un número finito de semiespa-cios cerrados que pasan por un punto.

Un poliedro es un politopo acotado y no vacío. Es fácil comprobar que la intersección de conjuntosconvexos es convexa y que por lo tanto los politopos y los poliedros son conjuntos convexos. En estafigura se muestran varios politopos; el del centro es un poliedro.

B.3 Separating and Supporting Hyperplanes 519

Fig. B.5 Polytopes

It is easy to see that half spaces are convex sets and that the union of H+ andH− is the whole space.

Definition. A set which can be expressed as the intersection of a finite numberof closed half spaces is said to be a convex polytope.

We see that convex polytopes are the sets obtained as the family of solutionsto a set of linear inequalities of the form

aT1 x � b1

aT2 x � b2

· ·· ·· ·

aTmx � bm�

since each individual inequality defines a half space and the solution family isthe intersection of these half spaces. (If some ai = 0, the resulting set can still, asthe reader may verify, be expressed as the intersection of a finite number of halfspaces.)

Several polytopes are illustrated in Fig. B.5. We note that a polytope may beempty, bounded, or unbounded. The case of a nonempty bounded polytope is ofspecial interest and we distinguish this case by the following.

Definition. A nonempty bounded polytope is called a polyhedron.

B.3 SEPARATING AND SUPPORTINGHYPERPLANES

The two theorems in this section are perhaps the most important results related toconvexity. Geometrically, the first states that given a point outside a convex set, ahyperplane can be passed through the point that does not touch the convex set. Thesecond, which is a limiting case of the first, states that given a boundary point of aconvex set, there is a hyperplane that contains the boundary point and contains theconvex set on one side of it.

Si un politopo P es un poliedro, cualquier punto se puede expresar como combinación convexa desus puntos extremos.

Teorema 8.1 Sea C un conjunto convexo e y un punto exterior a la adherencia de C . Existe unvector a tal que aTy < Kınfx2C aTx.

DEMOSTRACIÓN. Seaı D Kınf

x2Ckx � yk2 > 0:

26

Figura 8.10: Hiperplano �x1 C 4x2 D 11 y los semiespacios en los que divide R2

En la figura 8.10 se representa el hiperplano�x1C4x2 D 11, su vector característico a D Œ�1; 4�Ty los semiespacios HC y H�.

En un hiperplano aTx D c, la constante c determina el desplazamiento del hiperplano del origen.Un hiperplano se puede expresar de la forma fx W aT .x � x0/ D 0g, donde x0 es cualquier punto delhiperplano (aTx0 D c). Esa última expresión se puede trabajar un poco más pues fx W aT .x�x0/ D0g D x0 C a?, donde a? es el complemento ortogonal de a, es decir fv W aT v D 0g. Lo que lleva

25

a que un hiperplano consiste en un desplazamiento x0 más todos los vectores ortogonales al vectorcaracterístico a: el conjunto de soluciones de aTx D c: x0 C ker.a/, recordemos.

Un politopo es un conjunto formado por la intersección de un número finito de semiespacios cerra-dos. Un politopo cónico es un conjunto formado por la intersección de un número finito de semiespa-cios cerrados que pasan por un punto.

Un poliedro es un politopo acotado y no vacío. Es fácil comprobar que la intersección de conjuntosconvexos es convexa y que por lo tanto los politopos y los poliedros son conjuntos convexos. En estafigura se muestran varios politopos; el del centro es un poliedro.

B.3 Separating and Supporting Hyperplanes 519

Fig. B.5 Polytopes

It is easy to see that half spaces are convex sets and that the union of H+ andH− is the whole space.

Definition. A set which can be expressed as the intersection of a finite numberof closed half spaces is said to be a convex polytope.

We see that convex polytopes are the sets obtained as the family of solutionsto a set of linear inequalities of the form

aT1 x � b1

aT2 x � b2

· ·· ·· ·

aTmx � bm�

since each individual inequality defines a half space and the solution family isthe intersection of these half spaces. (If some ai = 0, the resulting set can still, asthe reader may verify, be expressed as the intersection of a finite number of halfspaces.)

Several polytopes are illustrated in Fig. B.5. We note that a polytope may beempty, bounded, or unbounded. The case of a nonempty bounded polytope is ofspecial interest and we distinguish this case by the following.

Definition. A nonempty bounded polytope is called a polyhedron.

B.3 SEPARATING AND SUPPORTINGHYPERPLANES

The two theorems in this section are perhaps the most important results related toconvexity. Geometrically, the first states that given a point outside a convex set, ahyperplane can be passed through the point that does not touch the convex set. Thesecond, which is a limiting case of the first, states that given a boundary point of aconvex set, there is a hyperplane that contains the boundary point and contains theconvex set on one side of it.

Si un politopo P es un poliedro, cualquier punto se puede expresar como combinación convexa desus puntos extremos.

Teorema 8.1 Sea C un conjunto convexo e y un punto exterior a la adherencia de C . Existe unvector a tal que aTy < Kınfx2C aTx.

DEMOSTRACIÓN. Seaı D Kınf

x2Ckx � yk2 > 0:

Existe un x0 en la frontera de C tal que kx0 � yk2 D ı. Esto es así pues la función continuaf .x/ D kx � yk2 alcanza su mínimo en cualquier conjunto cerrado y acotado por lo que sólo esnecesario considerar x en la intersección de la adherencia de C y la bola abierta de centro y y radio2ı.

A continuación probaremos que a D x0 � y satisface las condiciones del enunciado del teorema.En efecto, para cualquier ˛, 0 � ˛ � 1, al ser C un conjunto convexo, el punto x0C ˛.x�x0/ 2 C ,por lo que

kx0 C ˛.x � x0/ � yk22 � kx0 � yk22:Desarrollando,

2˛.x0 � y/T .x � x0/C ˛2kx � x0k22 � 0:Considerando esta expresión cuando ˛ ! 0C, se tiene que

.x0 � y/T .x � x0/ � 0o que

.x0 � y/Tx � .x0 � y/Tx0 D .x0 � y/Ty C .x0 � y/T .x0 � y/D .x0 � y/Ty C ı2:

Haciendo a D x0 � y queda probado el teorema.

La interpretación geométrica de este teorema es que, dado un conjunto convexo C y un punto yexterior a la adherencia de C , existe un hiperplano que contiene a y , sin tocar a C , estando C en unode sus semiespacios abiertos. Este hiperplano (de vector característico a en el teorema) se denominahiperplano separador de C e y .

26

Si C y D son dos conjuntos convexos disjuntos, C \ D D ;, existe entonces un a ¤ 0 y un btales que aT x � b, para todo x 2 C , y aTx � b, para todo x 2 D. Dicho de otra manera, la funciónaTx � b es no positiva en C y no negativa en D. El hiperplano

˚x W aTx D b es un hiperplano

separador de los conjuntos C y D.

2.5 Separating and supporting hyperplanes 47

E1

E2

E3

Figure 2.18 Three ellipsoids in R2, centered at the origin (shown as thelower dot), that contain the points shown as the upper dots. The ellipsoidE1 is not minimal, since there exist ellipsoids that contain the points, andare smaller (e.g., E3). E3 is not minimal for the same reason. The ellipsoidE2 is minimal, since no other ellipsoid (centered at the origin) contains thepoints and is contained in E2.

D

C

a

aTx ≥ b aTx ≤ b

Figure 2.19 The hyperplane {x | aTx = b} separates the disjoint convex setsC and D. The affine function aTx− b is nonpositive on C and nonnegativeon D.

Existen bastantes principios de dualidad que se usan en la asignatura, en especial en la teoría ytécnicas de optimización, que relacionan un problema en términos de vectores en un espacio vectorialcon otro expresado en términos de subespacios en ese espacio. En gran cantidad de esos principiosestá presente la relación que se ilustra en la figura que sigue. La distancia más corta de un punto a unconjunto convexo es igual al máximo de las distancias desde el punto a los hiperplanos que separanel conjunto convexo del punto. El problema original de minimización sobre vectores se convierte enotro de maximización sobre hiperplanos.

 

    

Figura 8.11: Distancia más corta de un punto a un conjunto convexo en términos de las distancias a hiperplanos separa-dores

Teorema 8.2 Sea C un conjunto convexo e y un punto frontera de C . Existe un hiperplano quecontiene a y y a C en uno de sus semiespacios cerrados.

DEMOSTRACIÓN. Sea fy.k/g una sucesión de puntos exteriores a la adherencia de C . Sea fa.k/g lasucesión de puntos normalizados, ka.k/k2 D 1, obtenida de aplicar el teorema anterior a la sucesiónanterior, tales que, �

a.k/�Ty.k/ < Kınf

x2C

�a.k/

�Tx:

27

Como fa.k/g es una sucesión acotada, una subsucesión fa.k/g, k 2 H, convergerá a un límite a. Paraeste a se tiene que, para cualquier x 2 C ,

aTy D lKımk2H

�a.k/

�Ty.k/ � lKım

k2H

�a.k/

�Tx D aTx:

Un hiperplano que contiene un conjunto convexo C en uno de sus semiespacios cerrados y quecontiene 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 yun punto frontera y de C , existe un hiperplano de apoyo de C que contiene y . En esta figura

2.6 Dual cones and generalized inequalities 51

C

a

x0

Figure 2.21 The hyperplane {x | aTx = aTx0} supports C at x0.

that the point x0 and the set C are separated by the hyperplane {x | aTx = aTx0}.The geometric interpretation is that the hyperplane {x | aTx = aTx0} is tangentto C at x0, and the halfspace {x | aTx ≤ aTx0} contains C. This is illustrated infigure 2.21.

A basic result, called the supporting hyperplane theorem, states that for anynonempty convex set C, and any x0 ∈ bdC, there exists a supporting hyperplane toC at x0. The supporting hyperplane theorem is readily proved from the separatinghyperplane theorem. We distinguish two cases. If the interior of C is nonempty,the result follows immediately by applying the separating hyperplane theorem tothe sets {x0} and intC. If the interior of C is empty, then C must lie in an affineset of dimension less than n, and any hyperplane containing that affine set containsC and x0, and is a (trivial) supporting hyperplane.

There is also a partial converse of the supporting hyperplane theorem: If a setis closed, has nonempty interior, and has a supporting hyperplane at every pointin its boundary, then it is convex. (See exercise 2.27.)

2.6 Dual cones and generalized inequalities

2.6.1 Dual cones

Let K be a cone. The set

K∗ = {y | xT y ≥ 0 for all x ∈ K} (2.19)

is called the dual cone of K. As the name suggests, K∗ is a cone, and is alwaysconvex, even when the original cone K is not (see exercise 2.31).

Geometrically, y ∈ K∗ if and only if −y is the normal of a hyperplane thatsupports K at the origin. This is illustrated in figure 2.22.

Example 2.22 Subspace. The dual cone of a subspace V ⊆ Rn (which is a cone) isits orthogonal complement V ⊥ = {y | yT v = 0 for all v ∈ V }.

˚x W aTx D aTx0

es el hiperplano de apoyo de C en el punto x0: el punto x0 y el conjunto C es-

tán separados por el hiperplano˚x W aTx D aTx0

. Geométricamente quiere decir que el hiperplano˚

x W aTx D aTx0

es tangente al conjunto C en x0 y el semiespacio˚x W aTx � aTx0

contiene a

C .Lema 8.3 (Farkas) El sistema de ecuaciones

.I / Ax D b; x � 0;no tiene solución si y sólo si la tiene el sistema

.II / yTA � 0T ; bTy > 0;

donde A 2 Rm�n.

DEMOSTRACIÓN. El lema se puede reformular de la siguiente manera. Si existe un x � 0 tal queAx D b, no existe ningún y tal que yTA � 0T y bTy > 0. Recíprocamente, si no existe ningúnx � 0 tal que Ax D b, existe un y tal que yTA � 0T y bTy > 0.

Supongamos que el sistema (I) tiene una solución x tal que Ax D b y x � 0. Sea y un punto talque yTA � 0T . En este caso bTy D xTATy � 0 pues x � 0 y yTA � 0T . Esto demuestra quebTy 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 decir que b … S D fv DAx W x � 0g; es decir que b no pertenece al politopo cónico S . Observando la figura 8.12, está claroque si b … S , existe un hiperplano separador definido por un y , que separa S y b, y para el cualyTai � 0, i D 1; : : : ; n y yTb > 0, es decir, y forma un ángulo de más de 90 grados con cada uno

28

8.1 Dualidad y condiciones de optimo 473

a1

a2a3

a4

a5

b /∈ S

y

Hiperplano

Politopo conico S

Figura 8.2

Descripcion geometrica de la existencia de un hiperplano separador

El par (P)-(D) se denomina habitualmente, en la literatura especializada, forma simetricade la dualidad.

A continuacion exponemos dos teoremas que caracterizan las soluciones optimas del par deproblemas primal-dual.

Teorema 8.3 (Complementariedad de Holguras) Sean x e y soluciones factibles del par deprogramas primal-dual en forma simetrica (P)-(D) de (8.8). Las condiciones necesarias ysuficientes para que sean optimos de sus respectivos problemas son:

(cT − yT A)x = 0 (8.9)

yyT (Ax − b) = 0. (8.10)

Demostracion. Como x e y son soluciones factibles de (P) y (D), respectivamente, se tieneque

s = Ax − b ≥ 0, x ≥ 0 (8.11)

ywT = cT − yT A ≥ 0T , y ≥ 0. (8.12)

Figura 8.12: Demostración del lema de Farkas

de los vectores columna de A y de menos de 90 grados con5 b. Esto verifica que el sistema (II) tienesolución.

El lema de Farkas es un resultado importante para el estudio de sistemas lineales de igualdades ydesigualdades. Su interpretación geométrica es la siguiente:1. Si ai ; i D 1; : : : ; n, son los n vectores columna de la matriz A, que se cumpla que b D Ax, x � 0,

quiere decir que el vector b D PniD1 aixi , xi � 0; en otras palabras, que b pertenece al politopo

cónico generado por los vectores columna de A. En la figura 8.13 se muestra un ejemplo dondeel sistema (I) no tiene solución: el vector b no pertenece al cono generado por a1, a2, a3 y an.La intersección del cono fy W yTA � 0T g (conjunto formado por los vectores y que forman unángulo mayor o igual de 90ı con los vectores columna de la matriz A) y el semiespacio abiertofy W bTy > 0g, no es el conjunto vacío: el sistema (II) tiene solución, pues b y cualquier y en elcono que define la zona sombreada forma un ángulo menor de 90ı y, por lo tanto, bTy > 0.

2. El sistema (II) no tiene solución si la intersección del cono fy W yTA � 0T g y el semiespacioabierto fy W bTy > 0g es el conjunto vacío. En la figura 8.14 se muestra un ejemplo donde elsistema (II) no tiene solución. Todo vector y en la zona que define el cono indicado forma unángulo mayor de 90ı con b. La tiene sin embargo (I) pues b pertenece al cono generado por a1, a2y an.

9 Funciones

Recordemos que una función es un caso particular de aplicación donde los conjuntos origen eimagen son conjuntos de números.

5El hiperplano separador del politopo cónico S de la figura debería “casi” tocar a éste a lo largo de a5. El hiperplano de apoyo correspondiente, sítocaría a a5.

29

474 Capıtulo 8. Dualidad y analisis de sensibilidad

a3a1

a2

b

an

Semiespacio abierto {y : bT y > 0}

Cono {y : yT A ≤ 0T }

Figura 8.3

El sistema (I) del lema de Farkas no tiene solucion. La tiene (II)

an

b

a2

a1

Semiespacio abierto {y : bT y > 0}

Cono {y : yT A ≤ 0T }

Figura 8.4

El sistema (II) del lema de Farkas no tiene solucion. La tiene (I)

Figura 8.13: El sistema (I) del lema de Farkas no tiene solución; si (II)

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 enx 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 conjuntoX , 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 -Lipschitzen ese X , designándose f 2 Lip .X/.

Dada una norma vectorial k � k en Rn y otra matricial k � k en Rm�n, m; n > 0, una funcióng W Rn ! Rm�n se dice satisface la condición de Lipschitz con constante en un abierto D � Rn, sipara 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, quedice que una función continua definida en un conjunto compacto S tiene un punto donde alcanza unmí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 vecto-rial

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 uno de los componentes 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

30

474 Capıtulo 8. Dualidad y analisis de sensibilidad

a3a1

a2

b

an

Semiespacio abierto {y : bT y > 0}

Cono {y : yT A ≤ 0T }

Figura 8.3

El sistema (I) del lema de Farkas no tiene solucion. La tiene (II)

an

b

a2

a1

Semiespacio abierto {y : bT y > 0}

Cono {y : yT A ≤ 0T }

Figura 8.4

El sistema (II) del lema de Farkas no tiene solucion. La tiene (I)

Figura 8.14: El sistema (II) no tiene solución. La tiene (I)

orden continuas en ese abierto, se dice que f 2 C 1. En general, si las funciones componentes tienenderivadas 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/

@x1;@f .x/

@x2; : : : ;

@f .x/

@xn

�T:

También se puede ver expresado alguna vez como fx.x/.Si f 2 C 2, se define la Hessiana, o matriz Hessiana, de f en x como la matriz n � n

r2f .x/ D

26666666664

@2f .x/

@2x1

@2f .x/

@x1@x2� � � @2f .x/

@x1@xn@2f .x/

@x2@x1

@2f .x/

@2x2� � � @2f .x/

@x2@xn:::

:::: : :

:::

@2f .x/

@xn@x1

@2f .x/

@xn@x2� � � @2f .x/

@2xn

37777777775:

A esta matriz también se la puede ver designada como F .x/.Para una función vectorial f D Œf1; f2; : : : ; fm�

T , si f 2 C 1, se define la matriz Jacobiana o,simplemente, la Jacobiana, como la matriz m � n

rf .x/ D J .x/ D

26666666664

@f1.x/

@x1

@f1.x/

@x2� � � @f1.x/

@xn@f2.x/

@x1

@f2.x/

@x2� � � @f2.x/

@xn:::

:::: : :

:::

@fm.x/

@x1

@fm.x/

@x2� � � @fm.x/

@xn

37777777775:

Si f 2 C 2, es posible definir m Hessianas F1.x/;F2.x/; : : : ;Fm.x/ correspondientes a cada una

31

de las m funciones componentes.

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 ˛x1C .1 � ˛/x2; 0 � ˛ � 1, existe un � , 0 � � � 1, tal que

f .x2/ D f .x1/CrTf��x1 C .1 � �/x2

�.x2 � x1/ :

Además, si f 2 C 2, existe un �; 0 � � � 1, tal que

f .x2/ D f .x1/CrTf .x1/.x2 � x1/C 1

2.x2 � x1/TF

��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 .x0/C f 0.x0/�x � x0

�C f 00.x0/2Š

�x � x0

�2 C f 000.x0/3Š

�x � x0

�3 C � � �Cf

.k/.x0/

kŠ

�x � x0

�k C f .kC1/.b/.k C 1/Š

�x � x0

�kC1:

Figura 9.15: 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 si cumple que f .˛x C ˇy/ � f .x/ C f .y/ paratodo x;y 2 Rn y todo ˛; ˇ 2 R, con ˛ C ˇ D 1, ˛ � 0, ˇ � 0.

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 Rm�n y b 2 Rm.

Si S � Rn es un conjunto convexo y f W Rn ! Rm es una función afín, la imagen de f .S/ Dff .x/ W x 2 Sg es un conjunto convexo. De forma similar, si f W Rk ! Rn es una función afín, la

32

7.4 Convex and Concave Functions 193

y = f(x)

xconvex

(a)

f

xnonconvex

(c)

f

xconvex

(b)

Fig. 7.3 Convex and nonconvex functions

y

Figura 9.16: Función convexa

imagen inversa f �1.S/ D fx W f .x/ 2 Sg 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.

20 | CHAPTER 0 Fundamentals

a b

y

c

(a)

a bc

f (c)

(b)

a b

f (c)

c

(c)

Figure 0.1 Three important theorems from calculus. There exist numbers c between

a and b such that: (a) f (c) = y, for any given y between f (a) and f (b), by Theorem

0.4, the Intermediate Value Theorem (b) the instantaneous slope of f at c equals

(f (b) − f (a))/(b − a) by Theorem 0.6, the Mean Value Theorem (c) the vertically shaded

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.

THEOREM 0.4 (Intermediate Value Theorem) Let f be a continuous function on the interval [a,b]. Thenf realizes every value between f (a) and f (b). More precisely, if y is a number betweenf (a) and f (b), then there exists a number c with a ≤ c ≤ b such that f (c) = y. �

� EXAMPLE 0.7 Show that f (x) = x2 − 3 on the interval [1,3] must take on the values 0 and 1.

Because f (1) = −2 and f (3) = 6, all values between −2 and 6, including 0 and1, must be taken on by f . For example, setting c = √

3, note that f (c) = f (√

3) = 0, andsecondly, f (2) = 1. �

THEOREM 0.5 (Continuous Limits) Let f be a continuous function in a neighborhood of x0, and assumelimn→∞ xn = x0. Then

limn→∞f (xn) = f

(lim

n→∞xn

)= f (x0). �

In other words, limits may be brought inside continuous functions.

THEOREM 0.6 (Mean Value Theorem) Let f be a continuously differentiable function on the interval[a,b]. Then there exists a number c between a and b such that f ′(c) = (f (b) − f (a))/

(b − a). �

� EXAMPLE 0.8 Apply the Mean Value Theorem to f (x) = x2 − 3 on the interval [1,3].The content of the theorem is that because f (1) = −2 and f (3) = 6, there must

exist a number c in the interval (1,3) satisfying f ′(c) = (6 − (−2))/(3 − 1) = 4. It is easyto find such a c. Since f ′(x) = 2x, the correct c = 2. �

The next statement is a special case of the Mean Value Theorem.

THEOREM 0.7 (Rolle’s Theorem) Let f be a continuously differentiable function on the interval [a,b],and assume that f (a) = f (b). Then there exists a number c between a and b such thatf ′(c) = 0. �

Teorema 9.3 Teorema del valor medio. Si f W R ! R es una función continua y derivable en elintervalo Œa; b�, existe un número c entre a y b tal que f 0.c/ D �f .b/ � f .a/�=.b � a/.20 | CHAPTER 0 Fundamentals

a b

y

c

(a)

a bc

f (c)

(b)

a b

f (c)

c

(c)

Figure 0.1 Three important theorems from calculus. There exist numbers c between

a and b such that: (a) f (c) = y, for any given y between f (a) and f (b), by Theorem

0.4, the Intermediate Value Theorem (b) the instantaneous slope of f at c equals

(f (b) − f (a))/(b − a) by Theorem 0.6, the Mean Value Theorem (c) the vertically shaded

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.

THEOREM 0.4 (Intermediate Value Theorem) Let f be a continuous function on the interval [a,b]. Thenf realizes every value between f (a) and f (b). More precisely, if y is a number betweenf (a) and f (b), then there exists a number c with a ≤ c ≤ b such that f (c) = y. �

� EXAMPLE 0.7 Show that f (x) = x2 − 3 on the interval [1,3] must take on the values 0 and 1.

Because f (1) = −2 and f (3) = 6, all values between −2 and 6, including 0 and1, must be taken on by f . For example, setting c = √

3, note that f (c) = f (√

3) = 0, andsecondly, f (2) = 1. �

THEOREM 0.5 (Continuous Limits) Let f be a continuous function in a neighborhood of x0, and assumelimn→∞ xn = x0. Then

limn→∞f (xn) = f

(lim

n→∞xn

)= f (x0). �

In other words, limits may be brought inside continuous functions.

THEOREM 0.6 (Mean Value Theorem) Let f be a continuously differentiable function on the interval[a,b]. Then there exists a number c between a and b such that f ′(c) = (f (b) − f (a))/

(b − a). �

� EXAMPLE 0.8 Apply the Mean Value Theorem to f (x) = x2 − 3 on the interval [1,3].The content of the theorem is that because f (1) = −2 and f (3) = 6, there must

exist a number c in the interval (1,3) satisfying f ′(c) = (6 − (−2))/(3 − 1) = 4. It is easyto find such a c. Since f ′(x) = 2x, the correct c = 2. �

The next statement is a special case of the Mean Value Theorem.

THEOREM 0.7 (Rolle’s Theorem) Let f be a continuously differentiable function on the interval [a,b],and assume that f (a) = f (b). Then there exists a number c between a and b such thatf ′(c) = 0. �

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.

33

Teorema 9.5 Teorema del valor medio de las integrales. Si f W R ! R es una función continuaen el intervalo Œa; b� y g W R ! R una función integrable que no cambia de signo en Œa; b�, existeentonces un número c entre a y b tal que

Z b

a

f .x/g.x/ dx D f .c/Z b

a

g.x/ dx:20 | CHAPTER 0 Fundamentals

a b

y

c

(a)

a bc

f (c)

(b)

a b

f (c)

c

(c)

Figure 0.1 Three important theorems from calculus. There exist numbers c between

a and b such that: (a) f (c) = y, for any given y between f (a) and f (b), by Theorem

0.4, the Intermediate Value Theorem (b) the instantaneous slope of f at c equals

(f (b) − f (a))/(b − a) by Theorem 0.6, the Mean Value Theorem (c) the vertically shaded

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.

THEOREM 0.4 (Intermediate Value Theorem) Let f be a continuous function on the interval [a,b]. Thenf realizes every value between f (a) and f (b). More precisely, if y is a number betweenf (a) and f (b), then there exists a number c with a ≤ c ≤ b such that f (c) = y. �

� EXAMPLE 0.7 Show that f (x) = x2 − 3 on the interval [1,3] must take on the values 0 and 1.

Because f (1) = −2 and f (3) = 6, all values between −2 and 6, including 0 and1, must be taken on by f . For example, setting c = √

3, note that f (c) = f (√

3) = 0, andsecondly, f (2) = 1. �

THEOREM 0.5 (Continuous Limits) Let f be a continuous function in a neighborhood of x0, and assumelimn→∞ xn = x0. Then

limn→∞f (xn) = f

(lim

n→∞xn

)= f (x0). �

In other words, limits may be brought inside continuous functions.

THEOREM 0.6 (Mean Value Theorem) Let f be a continuously differentiable function on the interval[a,b]. Then there exists a number c between a and b such that f ′(c) = (f (b) − f (a))/

(b − a). �

� EXAMPLE 0.8 Apply the Mean Value Theorem to f (x) = x2 − 3 on the interval [1,3].The content of the theorem is that because f (1) = −2 and f (3) = 6, there must

exist a number c in the interval (1,3) satisfying f ′(c) = (6 − (−2))/(3 − 1) = 4. It is easyto find such a c. Since f ′(x) = 2x, the correct c = 2. �

The next statement is a special case of the Mean Value Theorem.

THEOREM 0.7 (Rolle’s Theorem) Let f be a continuously differentiable function on the interval [a,b],and assume that f (a) = f (b). Then there exists a number c between a and b such thatf ′(c) = 0. �

9.1 Condiciones necesarias y suficientes de primer y segundo orden que ha de cumplir unpunto mínimo

Se trata de definir condiciones necesarias y suficientes para determinar si un punto x� cumple

minimizarx

f .x/;

donde f W �! R y � 2 Rn.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�/ 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�/ para todo x 2 �, x ¤ x�, a una distancia menor que � dex�, se dice que x� es un mínimo local estricto de f en �.

Teorema 9.6 Condiciones necesarias de primer orden Sea � un subconjunto de Rn y una funciónf W �! R, f 2 C 1. Si x� en un mínimo local de f en �, se cumple que rf .x�/ D 0.

Si en x� se cumple que rf .x�/ D 0, al punto x� se le denomina estacionario.

Teorema 9.7 Condiciones necesarias de segundo orden Sea� un subconjunto de Rn y una funciónf W �! R, f 2 C 2. Si x� en un mínimo local de f en�, se cumple querf .x�/ D 0 yr2f .x�/es semidefinida positiva.

Teorema 9.8 Condiciones suficientes de segundo orden Sea� un subconjunto de Rn y una funciónf W � ! R, f 2 C 2. Si se cumple que rf .x�/ D 0 y r2f .x�/ es definida positiva, x� en unmí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 fes derivable, cualquier mínimo local x� es un mínimo global de f .

34

10 Teorema de la función implícita

Teorema 10.1 Sea x0 D .x01; x02

; : : : ; x0n/ 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:

(c) La matriz Jacobiana de la función vectorial, rf .x0/ D

266664

@f1.x0/

@x1� � � @f1.x0/

@xm:::

: : ::::

@fm.x0/

@x1� � � @fm.x0/

@xm

377775, es

regular.Entonces existe un entorno de Ox0 D .x0mC1

; x0mC2; : : : ; x0n

/ 2 Rn�m tal que para Ox D.xmC1; xmC2; : : : ; xn/ en ese entorno existen funciones �i. Ox/, i D 1; 2; : : : ; m tales que:

(i) �i 2 C p.

(ii) x0iD �i. Ox0/; i D 1; 2; : : : ; m.

(iii) fi.�1. Ox/; �2. Ox/; : : : ; �m. Ox/; Ox/ D 0; i D 1; 2; : : : ; m.

Este teorema —cuyos orígenes están asociados a Newton, Leibnitz y Lagrange, pero que fue for-mulado por Cauchy— es muy útil para respaldar la caracterización de puntos óptimos en programa-ción matemática con y sin condiciones, solución de ecuaciones lineales y no lineales y muchos otrosaspectos 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 puederesolver en m incógnitas. Es decir, si x1, x2; : : : ; xm se pueden expresar en función de las restantesn �m de la forma

xi D �i .xmC1; xmC2; : : : ; xn/ ; i D 1; 2; : : : ; m:A las funciones �i W Rn�m ! R, si existen, se las denomina funciones implícitas.

Ejemplo 10.1 Consideremos la ecuación x21 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ónno se cumple la condición .c/ del teorema de la función implícita. En cualquier otra solución si existedicha �. uEjemplo 10.2 SeaA una matrizm�n y considérese el sistema de ecuaciones linealesAx D b. SiAse estructura así, A D ŒB;C �, donde B es m �m, entonces se satisface la condición .c/ del teoremade la función implícita si, y sólo si, B es regular. Esta condición se corresponde con los requisitosy enunciados de la teoría de ecuaciones lineales. La función implícita se puede considerar como unageneralización no lineal de la teoría lineal. u11 Bibliografía

BERTSEKAS, D.P. 2003. Convex Analysis and Optimization. Athena Scientific.

35

BOYD, S. Y VANDENBERGHE, L. 2004. Convex Optimization. Cambridge University Press.

DE LA FUENTE, J.L. 1998. Técnicas de cálculo para sistemas de ecuaciones, programación linealy programación entera. Segunda edición. Reverté.

ROCKAFELLAR, R.T. 1970. Convex Analysis. Princeton University Press.

HALMOS, P.R. 1974. Finite-Dimensional Vector Spaces. Springer Verlag.

KUHN, H.W. Y TUCKER, A.W. 1951. Nonlinear Programming. Proceedings of the Second Berke-ley Symposium on Mathematical Statistics and Probability. University of California Press. Verlag.

LUENBERGER, D.G. 1969. Optimization by Vector Space Methods. John Wiley and Sons.

LUENBERGER, D.G. Y YE, Y. 2009. Linear and Nonlinear Programming. Springer Verlag.

RIAZA, R. Y ÁLVAREZ, M. 1996. Cálculo infinitesimal. Vol. I. Sociedad de Amigos de la EscuelaTécnica Superior de Ingenieros Industriales de Madrid.

RIAZA, R. Y ÁLVAREZ, M. 1997. Cálculo infinitesimal. Vol. II. Sociedad de Amigos de la EscuelaTécnica Superior de Ingenieros Industriales de Madrid.

WOLFE, P. 1961. A Duality Theorem for Non-Linear Programming. Quart. Appl. Math. 19, Nı 3.

36