Tema 5

Optimización

Optimización con
restricciones: Condiciones
necesarias y suficientes
 Índice
Esquema. . . . . . . . . . . . . . . . . . . . . . . 2

Ideas clave . . . . . . . . . . . . . . . . . . . . . . 3

5.1 Introducción y objetivos . . . . . . . . . . . . . 3

5.2 Condiciones necesarias para restricciones no lineales. . 5

5.3 Condiciones suficientes para restricciones no lineales. . 14

Esquema

Optimización
2
Tema 5. Esquema
 Ideas clave

5.1 Introducción y objetivos

Este tema (y el siguiente) está dedicado al desarrollo de técnicas para la resolución

de problemas de optimización con restricciones. Recordamos que estos problemas se
pueden escribir, en forma estándar, de la siguiente manera:

minimizar f (x),

sujeto a G(x) ≤ 0,

H(x) = 0.

Con G : U 7→ Rm , H : U 7→ Rp y U un abierto de Rn . Durante todo el capítulo,

asumiremos que la función objetivo f así como las funciones de restricción H y H
son dos veces diferenciables con continuidad.

Dada la naturaleza no lineal del problema, solo podemos aspirar a encontrar solucio-
nes locales (como pasa en el caso de optimización sin condiciones). Vimos en el tema
1, que si la región de soluciones factibles y la función objetivo son convexas, enton-
ces toda solución local es también global. En este contexto, recordamos el siguiente
resultado:

Optimización
3
Tema 5. Ideas clave
 Teorema 1: Condiciones de Karush-Kuhn-Tucker

Consideramos un problema de optimización en forma estándar con f , G y H fun-

ciones de clase C 1 . Sea

S = {x ∈ U : G(x) ≤ 0, H(x) = 0},

el conjunto de las soluciones factibles y x0 ∈ S. Entonces:

1. Si f es una función convexa, S es un conjunto convexo y x0 es un mínimo local,

entonces x0 es también un mínimo global.

2. Si f , Gi son funciones convexas y Hj = Aj x + bj , j = 1, . . . p con Aj matrices

n × p y bj ∈ Rp . Entonces dado x0 ∈ S, si existen constantes µi ≥ 0, i =
1, . . . , m y λj , j = 1, . . . , p tales que

m p
X X
∇f (x0 ) = µi ∇Gi (x0 ) + λj ∇Hj (x0 ) = 0,
i=1 j=1

µi Gi (x0 ) = 0, i = 1, . . . , m,

entonces x0 es un mínimo global.

En este tema nos preocupamos por explorar más a fondo las condiciones necesarias
y suficientes para los problemas de optimización con restricciones desde un punto
de vista más analítico. Exploraremos las condiciones necesarias, primero, mediante la
regla de los multiplicadores de Lagrange. Luego utilizaremos esa misma técnica para
derivar condiciones necesarias.

Optimización
4
Tema 5. Ideas clave
5.2 Condiciones necesarias para restricciones no
lineales

Nos centraremos primero en problemas donde las restricciones vienen dadas por una
ecuación no lineal. Esto es

minimizar f (x),

sujeto a H(x) = 0.

Notamos que el problema está escrito en forma estándar. Aquí, f es una función de-
finida en un abierto U de Rn y H está definida, también en U , y toma valores en Rp .
Una suposición necesaria para lo que viene es que todas las funciones implicadas son
derivables con continuidad.

Restricciones lineales

Supongamos que H(x) = Ax − b es una función afín, con A una matriz p × n de

rango p y b ∈ Rp . Siempre existe una reordenación de las columnas de A de manera
que A = [B, N ] con B una matriz p × p de determinante no nulo. Dado un vector x,
podemos separarlo como x = (xB , xN ), entonces se cumple que

xB = B −1 b − B −1 N xN . (1)

Podemos substituir esta expresión en la función objetivo:

f (x) = f (xB , xN ) = f (B −1 b − B −1 N xN , xN ) = F (xN ).

Hemos reducido nuestro problema a la minimización sin restricciones de la función

F . Una vez encontrado un óptimo xN para el problema reducido, podemos recuperar

Optimización
5
Tema 5. Ideas clave
completar x, recuperando xB vía la ecuación (1).

Ejemplo 1.
Consideramos el siguiente problema de optimización no lineal con restricciones
lineales.

minimizar x2 + y 2 ,

sujeto a x − y = 1.

De la ecuación de la restricción, podemos escribir y en función de x, esto es

y = x − 1 (notamos que no tiene ninguna importancia la elección de la variable).
Substituyendo esta expresión para y en la función objetivo. Luego, el problema
se reduce a
minimizar 2x2 − 2x + 1.

Hemos reducido el problema a encontrar el mínimo de una función unimodal.

Al ser, de hecho, f un polinomio de segundo grado, la minimización es trivial,
x = 3/4. Recuperamos y mediante la ecuación de restricción, en este caso y =
−1/4. Luego, nuestro óptimo es (3/4, 1/4). Dejamos al lector la comprobación
de que, en efecto, hemos obtenido un mínimo local. Observando que se verifican
las condiciones de Karush-Kuhn-Tucker, podemos argumentar que el mínimo es,
de hecho, global.

Restricciones no lineales

Consideramos ahora el caso general, en que H es una función estrictamente no lineal.

Del caso lineal hemos aprendido que podemos reducir el problema con restricciones a
un problema sin restricciones resolviendo una ecuación lineal. Vamos a seguir ese hilo
con el caso no lineal. Nos fijamos ahora en la ecuación H(x) = 0 y nos preguntamos
si podemos encontrar xB = ϕ(xN ) de manera que H(xB , xN ). Para contestar a esa
∂Hi (x)
cuestión, nos fijamos en la matriz diferencial de la función H: DH(x)i,j = ∂xj
,
que es una matriz de medidas p × n. Notamos que si H es una función afín (como en

Optimización
6
Tema 5. Ideas clave
el caso anterior) entonces DH(x) = A. En ese caso, podíamos aislar xB en función
de xN porque habíamos supuesto que el rango era máximo. Vamos a extender esa
hipótesis a DH(x). Diremos que x es un punto regular de H si el rango de DH(x) es
p. Un teorema clásico de análisis vectorial nos dice que, esta condición nos permitirá
resolver la ecuación:

Teorema 2: Función Implícita

Sea U un abierto de Rn y H : U 7→ Rp una función diferenciable con continui-

dad. Supongamos que x0 es un cero regular de H. Consideramos un orden en las
columnas de DH tal que la variable x0 = (x0B , x0N ) con x0B ∈ Rp y la diferencial
reducida
∂Hi (x0B , x0N )
DHB (x0B ) = ,
∂xj
i, j = {1, . . . , p} tiene determinante no nulo. Entonces existe W ⊂ Rn−p de xB
y una función diferenciable ϕ : W 7→ Rp tal que H(ϕ(xN ), xN ) = 0 para todo
xN ∈ W .

El teorema de la función implícita nos dice que, si la función H es regular, podremos

utilizar la misma estrategia, para el caso no lineal, que hemos utilizado en el caso lineal.
El teorema fundamental que resume estas ideas es el siguiente:

Optimización
7
Tema 5. Ideas clave
 Teorema 3: Regla de los multiplicadores de Lagrange

Consideramos el siguiente problema de optimización:

minimizar f (x),

sujeto a H(x) = 0.

Aquí, f y H son funciones diferenciables con continuidad definidas en un abierto

U de R y con valores en R y Rp respectivamente. Supongamos que x∗ es un mi-
nimizador local del problema que cumple las hipótesis del teorema de la función
implícita. Entonces, existen constantes λ∗1 , . . . , λ∗p tal es que

p
X
∇f (x∗ ) − λ∗i ∇Hi (x∗ ) = 0.
i=1

Optimización
8
Tema 5. Ideas clave
 En particular, el punto (x∗ , λ∗ ) es un extremo relativo de la función Lagrangiana

p
X
T
L(x, λ) := f (x) − λ H(x) = f (x) − λi Hi (x).
i=1

A las constantes λi que sirven para completar la función Lagrangiana L se les llama
multiplicadores de Lagrange. Notamos que la condición ∇L = 0 es un sistema de
ecuaciones no lineal de n+p ecuaciones con n+p incógnitas, lo que significa que en las
condiciones del teorema de la función implícita (regularidad del la matriz Jacobiana),
podemos encontrar (x, λ), tal que ∇L(x, λ) = 0.

Para ilustrar la necesidad de las condiciones de regularidad, vamos a ver un ejemplo

en que no podemos aplicar el teorema anterior.

Ejemplo 2.
Consideramos el problema

minimizar x,

sujeto a x2 + (y − 1)2 − 1 = 0,

x2 + (y + 1)2 − 1 = 0.

Es evidente que (0, 0) es un minimizador que cumple las restricciones: Es el único

punto que cumple las dos ecuaciones de restricción, luego, la única solución facti-
ble. Se desprende, pues, que es la única posible solución del problema. Además,
tenemos que  
2x 2(y − 1)
DH(x, y) =  
2x 2(y + 1)

esto es,  
0 −2
DH(0, 0) =  
0 2

En particular, el gradiente de la función Lagrangiana, se escribe

2
X
∇f (0, 0) − λi ∇Hi (0, 0),
i=1

Optimización
9
Tema 5. Ideas clave
 que, substituyendo,
     
1 0 0
  − λ1   − λ2   .
0 −2 2

Igualando, ∇L(0, 0) = 0, obtenemos las ecuaciones

1 + 2λ1 − 2λ2 = 0,

2λ1 − 2λ2 = 0

Dicho sistema no tiene solución.

Vamos con otro ejemplo. En este caso, sí estaremos en las condiciones de aplicar la
regla de los multiplicadores de Lagrange.

Ejemplo 3.
Consideramos el siguiente problema:

minimizar y 2 − x,

sujeto a 2x2 + 2xy + y 2 − 1 = 0,

En primer lugar, comprobamos la matriz Jacobiana de la función H(x, y) = 2x2 +

2xy + y 2 − 1:  
4x + 2y
∇H(x, y) =  .
2x + 2y

En este caso, la matriz es un vector de R2 . La condición de regularidad se cumple

siempre que el vector no sea nulo, cosa que ocurre solamente para x = 0, y = 0.
Podemos buscar los multiplicadores de Lagrange (en este caso será un solo valor
λ) vía la ecuación:
∇f − λ∇H = 0,

Optimización
10
Tema 5. Ideas clave
o, equivalentemente,
   
−1 4x − 2y
  − λ =0
2y 2x + 2y

Obtenemos, pues, sendas expresiones para λ:

−1 y
λ= , λ= .
4x + 2y x+y

Igualando los dos factores podemos, por ejemplo, aislar x en función de y

2y 2 + y
x=− =: ϕ(y).
4y + 1

Ésta es una curva en el plano x − y de puntos de inflexión de f . Eso sí, no todos

ellos son soluciones factibles ya que no hemos impuesto H(x, y) = 0. Las inter-
secciones de la curva (ϕ(y), y) con el conjunto de soluciones factibles, viene dado
por la ecuación H(ϕ(y), y) = 0, o, explícitamente,

(2y 2 + y)2 2y 3 + y 2
2 − 2 + y 2 − 1 = 0.
(4y + 1)2 4y + 1

Esto es una ecuación polinomial de cuarto grado en y. Esto es, tiene, como máxi-
mo cuatro soluciones reales. Aunque, de hecho, existe la posibilidad de resolver
esta ecuación a mano, necesitaríamos expresiones muy complicadas. Así que la
resolveremos numéricamente. En la tabla 1 mostramos la solución numérica del
problema. La segunda columna corresponde a las cuatro soluciones de la ecua-
ción en y. La primera columna corresponde a los valores x que corresponden
a las cuatro soluciones obtenidas como ϕ(y). Las dos primeras columnas de la
tabla son, pues, las cuatro soluciones factibles del problema. La tercera colum-
na corresponde a la evaluación de la función objetivo. Podemos observar que,
de las cuatro soluciones factibles existentes, la que corresponde a la última fila,
(x, y) ≈ (0.805, −0, 212) es la que tiene el valor mínimo de la función f (ya que
es negativo).

Optimización
11
Tema 5. Ideas clave
 x y f (x, y)
-5.378033-01 -3.052670e-01 6.309912e-01
5.378033e-01 -1.380873e+00 1.369008e+00
-8.051506e-01 1.398220e+00 2.760172e+00
8.051506e-01 -2.120803e-01 -7.601725e-01

Tabla 1: Soluciones factibles del problema de optimización. La cuarta fila se revela

como la solución óptima ya que toma el valor mínimo.

Restricciones con desigualdad

En esta sección nos vamos a enfrentar con problemas de optimización con restriccio-
nes no lineales dadas por desigualdades. Esto es, consideramos un abierto U de Rn ;
funciones diferenciables f : U 7→ R, G : U 7→ Rm y el problema

minimizar f (x),

sujeto a G(x) ≥ 0.

Notamos que la restricción no viene en la forma estándar planteada en el tema 1 (aquí

damos la restricción G(x) ≥ 0 y en forma estándar es G(x) ≤ 0). Esto es por conve-
niencia en el desarrollo. En cualquier caso, podemos cambiar G por −G para pasar de
una forma a la otra.

Vamos ahora con una definición que nos será de utilidad. Diremos que una restricción
Gi es activa en un punto x, si Gi (x) = 0. Fijado x ∈ S (donde S es el conjunto de las
soluciones factibles), denotamos A(x) = {α1 , . . . , αk } es el conjunto de índices para
los cuales, las restricciones Gαi (x) = 0.

Vamos a estudiar ahora las condiciones de regularidad necesarias. Diremos que un

punto x es regular si los gradientes de las restricciones que son activas en x son lineal-
mente independientes. Esto es, dado x, el conjunto de vectores ∇Gi (x), i ∈ A(x) está
formado por vectores linealmente independientes. En estas condiciones, podemos es-

Optimización
12
Tema 5. Ideas clave
tablecer la regla de los multiplicadores de Lagrange para problemas con restricciones
con desigualdad.

Teorema 4: Regla de los multiplicadores de Lagrange II

Consideramos el siguiente problema de optimización

minimizar f (x),

sujeto a G(x) ≥ 0.

Si x∗ es un minimizador local regular. Entonces existe un vector λ∗ ∈ Rm

+ de cons-

tantes positivas tal que λ∗i Gi (x∗ ) = 0 para todo i = 1, . . . , m y (x∗ , λ∗ ) es un

punto crítico de la función Lagrangiana

m
X
L(x, λ) = f (x) − λi Gi (x).
i=1

La condición de primer orden sobre la función Lagrangiana, se lee:

m
X
∇f (x) − λi ∇Gi (x) = 0.
i=1

Como λi ≥ 0, esto implica que el vector ∇f (x) es una combinación lineal con coefi-
cientes positivos de los gradientes de ∇Gi . Además, tenemos la condición λi Gi (x) =
0. Esto implica que solamente los gradientes de las restricciones activas son necesarios
para la combinación lineal.

A efectos prácticos, podemos reducir un problema con restricciones de desigualdad

a un problema de restricciones de igualdad introduciendo variables de exceso. En el
siguiente ejemplo mostramos cómo.

Ejemplo 4.

Optimización
13
Tema 5. Ideas clave
 Consideramos el siguiente problema

minimizar x2 ,

sujeto a x + 1 ≥ 0.

La solución de este problema es bastante obvia, ya que el valor x = 0 es una

de las soluciones factibles. Aún así a aplicar el método de los multiplicadores de
Lagrange. Antes de nada, substraer una variable de exceso e > 0. Vamos a subs-
traer directamente la cantidad y 2 para asegurarnos que estamos introduciendo
una cantidad positiva. El problema nos queda:

minimizar x2 ,

sujeto a x + 1 − y 2 = 0.

Los gradientes de las funciones vienen dados por ∇f = (2x, 0)t y (1, −2y)t . En
particular, tenemos la siguiente ecuación para el único multiplicador de Lagrange:

(2x, 0)t − λ(1, −2y)t = 0.

De la cual, resultan

2x − λ = 0,

2λy = 0

De las cuales se deduce que la solución es (x, λ)) = (0, 0).

5.3 Condiciones suficientes para restricciones no

lineales

Recordamos que, para un problema de optimización sin restricciones (esto es, el es-
tudio del mínimo (o el máximo) de una función) se consiguen condiciones suficientes

Optimización
14
Tema 5. Ideas clave
para la existencia de un mínimo local cuando se cuenta con la segunda derivada. Va-
mos a terminar este tema dando resultados análogos para problemas de optimización
con restricciones. En el caso sin restricciones, podemos garantizar que un punto x∗ es
un mínimo local de una función f si

I ∇f (x∗ ) = 0,

I ∇2 (x∗ ) es definida positiva.

Recordamos que ∇2 f es la matriz Hessiana1 . La gran diferencia con los problemas

con restricciones es que la geometría del conjunto de soluciones factibles puede ser
complicada. En particular, la segunda derivada de la función objetivo que verificar las
condiciones en un espacio vectorial distinto a Rn .

Para ser más concretos, consideramos primero el problema con restricciones de igual-
dad:

minimizar f (x),

sujeto a H(x) = 0.

Dado x ∈ U , la matriz Jacobiana de DH(x) tendrá medidas p × n. Con p ≤ n. En

particular tendrá un núcleo al que denotaremos por T (x). Esto es:

T (x) = {q ∈ Rn : DH(x)q = 0}.

El resultado de suficiencia de para el problema es:

Teorema 5: Condiciones suficientes para problemas con igualdad

1
Hemos desestimado la notación del Tema 1 porque podría causar confusión.

Optimización
15
Tema 5. Ideas clave
 Consideramos el problema

minimizar f (x),

sujeto a H(x) = 0.

Con f y H funciones diferenciables dos veces con continuidad. Sea x∗ una solu-
ción factible del problema. Suponemos que existe un vector λ∗ tal que

Pp
1. ∇f (x∗ ) − i=1 λ∗i ∇Hi (x∗ ) = 0,

2. y se cumple que

 p 
X
t 2 ∗ 2 ∗
q ∇ f (x ) − λi ∇ Hi (x ) q > 0,
i=1

para todo q ∈ T (x∗ ) no nulo,

Entonces x∗ es un mínimo local de f .

Éste teorema utiliza la formulación Lagrangiana y aplica el resultado para problemas

sin restricciones. Utilizando el mismo argumento, podemos encontrar un teorema pa-
ra el caso general, el que incluye restricciones de igualdad y de desigualdad.

Teorema 6: Condiciones suficientes para el problema general

Consideramos el siguiente problema de optimización.

minimizar f (x),

sujeto a G(x) ≥ 0,

H(x) = 0.

Con f, G y H funciones dos veces diferenciables. Sea x∗ una solución factible. Si

existen vectores constantes µ∗ ∈ Rm ∗ p
+ y λ ∈ R tales que

Optimización
16
Tema 5. Ideas clave
 Pp Pm
1. ∇f (x∗ ) − ∗ ∗
i=1 λi ∇Hi (x ) − i=1 µ∗i ∇Gi (x∗ ) = 0,

2. y se cumple que

 p m 
X X
∗ ∗
t
q ∇ f (x ) − 2 2
λi ∇ Hi (x ) − µ∗i ∇2 Gi (x∗ ) q > 0,
i=1 i=1

para todo q ∈ T (x∗ ) no nulo,

Entonces x∗ es un mínimo local de f .

Optimización
17
Tema 5. Ideas clave