Optimización con restricciones

T aballo Fin de G ao
Op imización con Res icciones
Manuel Vázquez Mou azos
2018/2019
UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
GRAO DE MATEMÁTICAS
T aballo Fin de G ao
Op imización con Res icciones
Manuel Vázquez Mou azos
Julio, 2019
UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
T abajo p opues o
Á ea de Coñecemen o: Ma emá ica aplicada
Tí ulo: Op imización con es icciones
Ti le: Cons ained op imiza ion
Di ec o : Je ónimo Rod íguez Ga cía
B e e desc ición do con ido
Es e abajo consis i á en el es udio de p oblemas de op imización
con es icciones. Se es udia án condiciones necesa ias y condicio-
nes su icien es pa a la exis encia y unicidad de solución del p oblema
dependiendo de las hipó esis sob e el uncional obje i o y las es-
icciones que de inen el conjun o admisible. Se es udia án ambién
algunos mé odos numé icos básicos pa a la esolución de es e ipo de
p oblemas.
Recomendacións
Habe cu sado la asigna u a “Mé odos Numé icos en Op imización y
Ecuaciones Di e enciales”
iii

i
“Pues o que el Uni e so es pe ec o y ue c ea-
do po el C eado más sabio, nada ocu e en
él sin que es é p esen e alguna ley de máximo
o mínimo”.
L. Eule (s. XVIII)
Índice gene al
Índice de igu as ix
Índice de ablas xi
Resumen xiii
xiii
No ación x
In oducción x ii
1. Op imización sin es icciones 1
1.1. Concep osgene ales ............................... 1
1.2. Condiciones de op imalidad con de i adas . . . . . . . . . . . . . . . . . . . 2
1.3. Exis encia y unicidad de solución . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1. Funcionales coe ci i os . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2. Funcionales con exos . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Funcionales cuad á icos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5. Mé odos pa a la ob ención del mínimo . . . . . . . . . . . . . . . . . . . . . 8
1.5.1. Cálculodelpaso ............................. 9
1.5.2. Mé odo del g adien e . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.3. Mé odo del g adien e conjugado . . . . . . . . . . . . . . . . . . . . . 11
1.5.4. Mé ododeNew on............................ 12
1.5.5. Mé odos Cuasi-New on . . . . . . . . . . . . . . . . . . . . . . . . . 13
2. Op imización con es icciones, eo ía 15
2.1. P esen ación del p oblema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2. Ca ac e ización de óp imos . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3. Mul iplicado es de Lag ange . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
ii
xi
In addi ion, hese knowledge will be applied o quad a ic op imiza ion. This is a special
case ha usually causes special in e es because o i s simplici y in many cases, and wha
is no less impo an , i s use o sol e mo e complex p oblems.
Finally, he op imiza ion p oblem will be add essed om a p ac ical poin o iew. In
his case, di e en me hods ha show di e en ways o app oaching he p oblem will be
s udied. Thus, he algo i hms ha can be implemen ed in any p og amming language (such
as MATLAB o o he s) will be explici ly p o ided o inally ob ain he desi ed solu ion.

No ación
Con el mo i o de acla a las posibles dudas que puedan su gi en la lec u a del p esen e
abajo. A con inuación se ha án algunas acla aciones con el in de explica la no ación
que se usa á a lo la go del mismo:
1. Como se usa á con g an ecuencia ope aciones que in oluc an escala es, ec o es
y ma ices, los ec o es se esc ibi án con le a minúscula en neg i a, mien as que
pa a deno a a una ma iz, se u iliza án le as mayúsculas en neg i a. Po ejemplo,
se á un ec o (y 0se ía el ec o idén icamen e nulo), Muna ma iz, mien as
que cualquie escala se ep esen a á con le a no mal.
2. Cuando se compa en dos ec o es, se en iende que se compa an componen e a com-
ponen e. Es deci , ≥0signi ica ía que odas las componen es del ec o son
posi i as.
3. Como ambién se usa án sucesiones de ec o es, pa a e e i se al ec o k-ésimo de
una sucesión, se u iliza á el supe índice (k). Es deci , (k), deno a el elemen o k-ésimo
de la sucesión  (k)k∈N. Po o a pa e, la componen e i-ésima de un ec o , se
deno a á po el escala i(así mismo, (k)
ideno a á el escala co espondien e a la
componen e i-ésima del ec o k-ésimo). Además, el escala co espondien e a una
posición (i, j)de una ma iz cualquie a M, se deno a á po mij.
4. Los ec o es que se conside a án en el abajo se án columna, es deci , dado ∈Rn
se iene que ∈ Mn×1.
5. Dada una ma iz M∈ Mn× , se deno a á po miel ec o co espondien e a la ila
i-ésima de la ma iz M. És e se á el único caso excepcional donde se conside a án
ec o es ila, dado que al co esponde se con la ila i-ésima, se en ende á que mies
un ec o ila.
6. En los capí ulos 2 y 3, se conside a un p oblema gené ico de op imización con es ic-
ciones al que se deno a á po (Q). En el caso de que sólo se conside en es icciones
x
de igualdad, el p oblema gené ico se deno a po (Qig), mien as que, si sólo se con-
side an las es icciones de desigualdad, se deno a án po (Qdes). Con es a misma
iloso ía, siemp e que se esc iba el subíndice ig ( esp. des) sólo se es a án a conside a
es icciones de igualdad ( esp. desigualdad).
7. En las es icciones que se u iliza án en los capí ulos 2 y 3, se deno a á po ϕ( )a las
es icciones de desigualdad, y po φ( )a las es icciones de igualdad. Así, ambién
se deno a á po Ψ( ) = (ϕ1( ), . . . , ϕm( ))Tal ec o que con iene el alo de las
es icciones de desigualdad (de o ma análoga, Φ( ) = (φ1( ), . . . , φp( ))T).
8. Teniendo en cuen a las unciones Ψ( )yΦ( )de las que se ha hablado. Se deno a á
po Ψ0( )a la ma iz que iene po ilas los g adien es de cada una de las es icciones
de desigualdad ( espec i amen e Φ0( )con las es icciones de igualdad).
De odas o mas, a lo la go del abajo se eco da á la no ación. Pe o se ha conside ado
pe inen e es ablece es as bases pa a ene un pun o de e e encia en el caso de que su ja
alguna duda al espec o.
In oducción
De inida po la RAE como “la acción o e ec o de busca la mejo mane a de ealiza
una ac i idad”, la op imización es una ama de la ma emá ica aplicada que p e ende halla
el elemen o del domino de una unción (a la que comúnmen e se denomina como uncional
obje i o) que lo minimice o maximice. És e, es un p oblema que ha sido a ado desde hace
siglos, pe o no ha sido has a el siglo pasado, cuando más se ha es udiado y p o undizado
en su esolución.
His ó icamen e, su en oque ha sido di e so a lo la go de la his o ia. En iempos de an a-
ño, impo an es ma emá icos como Pie e de Fe ma (1601-1665) en su memo ia Me hodus
ad disqui endam maximan e minimam (esc i a sob e 1629 pe o publicada en 1679 después
de su mue e po su hijo Samuel), ya es ableció eglas pa a el cálculo de máximos y míni-
mos. También Joseph Louis Lag ange (1736-1813) en su publicación Mécanique Analy ique
(1788-89), ue capaz de halla ó mulas basadas en el cálculo que pe mi ie on ca ac e iza
los alo es óp imos que op imizaban cie os p oblemas de op imización. O os, die on so-
lución a p oblemas clásicos que ya se enma caban den o de es e mismo con ex o, como
Leonha d Eule (1707-1783), con su amoso p oblema de los sie e puen es de Königsbe g.
Desde o o pun o de is a, cabe esal a las apo aciones de Isaac New on (1642-1727)
yJohann Ca l F ied ich Gauss (1777-1855), los cuales p opusie on mé odos i e a i os que
con e giesen a un óp imo.
Sin emba go, el máximo desa ollo de la op imización comenzó a p oduci se en el siglo
pasado. P incipalmen e, a causa de las gue as acaecidas, los p oblemas de op imización
empeza on a ene una g an ele ancia pa a minimiza cos es (en el anspo e de soldados
o í e es) o maximizando bene icios (p ocu ando abo da el mayo obje i o posible que
uese menes e conquis a ). Además, ue en onces cuando se pasó a conoce la disciplina de
la op imización con el nomb e de p og amación, el cuál, se comenzó a u iliza debido al uso
de es e é mino po el ejé ci o es adounidense pa a e e i se a los p oblemas de logís ica
que se deseaban abo da median e el uso de es a disciplina.
Fue p ecisamen e en ese momen o, cuando se p odujo el mayo desa ollamien o de
la ma emá ica aplicada, y en pa icula , de la op imización. Fundada en 1941, la O icina
x ii
x iii INTRODUCCIÓN
de In es igación Cien í ica y Desa ollo (IOCD), ue el p ime ó gano o ganizado de los
ma emá icos con a ados po las Fue zas A madas de los E.E.U.U pa a el desa ollo de las
ma emá icas eque idas po la II Gue a Mundial. Sin emba go, ue en 1943 cuando se c eó
el Comi é de Ma emá ica Aplicada (CMA), que siendo un ó gano den o de la IOCD, si ió
pa a ap o echa el inanciamien o del gobie no (a causa del momen o) pa a el desa ollo
de la ma emá ica aplicada.
En es e con ex o, en un p ime luga se desa olló la p og amación lineal, que com-
p endía la esolución de p oblemas de op imización de una unción lineal en un conjun o
de inido po es icciones a ines. En es e ma co, el algo i mo más amoso es el Símplex, que
ue desa ollado en 1947 po Geo ge Be na d Dan zig (1914-2005). El cual, ya lle aba es u-
diado el ema al menos desde 1941, echa en la que ue con a ado po las Fue zas A madas
pa a lle a a cabo eno mes plan eamien os logís icos. Además, ambién cabe des aca la
eo ía de la dualidad que ue publicada en el mismo año (1947) po John on Neumann
(1903-1957).
Figu a 1: Impo an es exponen es de la p og amación lineal en el siglo XX
De o ma pa alela, y ambién pos e io a la II Gue a Mundial, a pa e de con inua
es udiando los p oblemas de p og amación lineal, ambién se amplió el es udio a la p o-
g amación no lineal. La cual, p ocu aba da solución a aquellos p oblemas donde no había
linealidad en las unciones a op imiza ni en las es icciones que de inían los conjun os
donde se op imizaban dichas unciones. Pa a ello, ue necesa io gene aliza concep os ya
conocidos a un caso más gené ico.
En es e ma co, una de las apo aciones más impo an es ue on las conocidas con-
INTRODUCCIÓN xix
diciones de Ka ush-Kuhn-Tucke (conocidas comúnmen e como condiciones KKT), que
gene alizan las condiciones que había dado Lag ange en su día. És as, ue on publicadas
po p ime a ez en el e ano de 1950 de o ma conjun a po Ha old William Kuhn (1925-
2014) y Albe William Tucke (1905-1995). Los cuales, u iliza on ambién en dicho año
po p ime a ez el é mino de p og amación no lineal pa a e e i se a es a disciplina. Sin
emba go, se descub ió con pos e io idad que William Ka ush (1917-1997) había demos a-
do el mismo esul ado en su abajo de in de más e del año 1939. Po consiguien e, hoy
en día se a ibuye dicho descub imien o a los es en conjun o.
Además, ín imamen e ligadas con las condiciones KKT, el ma emá ico F i z John (1910-
1994) publicó en un a ículo en 1948 un esul ado simila al de las condiciones KKT. El
cual, las gene aliza a un ma co más amplio y se conocen en hono a él, como las condiciones
de F i z-John.
Figu a 2: Impo an es exponen es de la p og amación no lineal en el siglo XX
Desde que ue on publicadas, las condiciones KKT adqui ie on g an ama y p es igio.
Se pod ía deci , que ue on el p ime paso hacia es a nue a ama del sabe . G acias a su
econocimien o, den o del mundo ma emá ico, se c eó o icialmen e en 1971 la p ime a
e is a que a ó a la op imización como ema undamen al, Ma hema ical P og amming.
La cuál, p ecedió a una segunda bau izada con el nomb e de Ma hema ical P og amming
Socie y.
Finalmen e, con el eno me desa ollo de la in o má ica y de las máquinas de cálculo en
la úl ima mi ad del siglo pasado, se diseña on muy di e sos algo i mos que pe mi ie on da
solución a los p oblemas de p og amación. La a iedad en dichos algo i mos es muy di e sa
en unción del en oque que se le da al p oblema pa a halla la solución. En una mayo ía,
muchos de ellos buscan calcula pun os cumpliendo las condiciones KKT y hace un es udio

xx INTRODUCCIÓN
pos e io pa a comp oba si son ealmen e solución. Po o o lado, o os in en an busca el
mínimo di ec amen e eniendo en cuen a las ca ac e ís icas del conjun o donde se quie e
minimiza , mien as que, ambién los hay que ecu en a la esolución de subp oblemas
más sencillos que pe mi an c ea un p oceso i e a i o que llegue a la solución.
Hogaño, la op imización es a p esen e en mul i ud de ace as de nues a ida co idia-
na. Las compañías aé eas, diseñan los uelos con la in ención de minimiza los cos es y
maximiza su bene icio. En la medicina, los a amien os con a el cánce , pasan po un
p oceso de op imización pa a minimiza su impac o noci o en la salud de los pacien es.
Los in e so es p ocu an minimiza los iesgos en sus decisiones a la ez que ga an iza una
en abilidad sa is ac o ia. Pe o más allá, incluso la p opia na u aleza es á op imizando
con inuamen e p ocu ando un es ado de mínima ene gía. Es el caso de los ayos de luz que
siguen las ayec o ias que minimizan la du ación de su eco ido.
Todos es os p oblemas ac uales, se isionan en una o mulación ma emá ica como p o-
blemas de op imización, de hecho, en [5, Cap. 12] se modelizan mul i ud de p oblemas en
una o mulación adap ada a la p og amación ma emá ica. Pe o calcula su solución, puede
llega a se bas an e complejo en ocasiones. Es e abajo, p e ende da espues a a es os
p oblemas a ando el caso en el que las unciones a minimiza y las es icciones, sean
di e enciables.
Pa a empeza , el p ime capí ulo se dedica a la op imización sin es icciones. És e es el
caso más sencillo den o de es a disciplina, la cuál desea halla el alo óp imo del uncional
obje i o en odo su dominio.
Pa a ello, se comienza p esen ando el p oblema y ca ac e izando sus óp imos. Como
se ha dicho, en es e abajo se a a el caso donde odas las unciones que in e ienen en
el p oblema son di e enciables, y és e, se á un hecho c ucial pa a pode ca ac e iza los
óp imos. Pos e io men e, se aumen a án las hipó esis sob e los p oblemas a a a pa a
pode demos a cuando és os ienen solución y és a es única. Pa a ello, se in oduci á la
de inición de coe ci i idad y con exidad.
Una ez explicados es os concep os, se in oduci án los uncionales cuad á icos, los
cuales son in e esan es desde el pun o de is a eó ico, debido a que pe mi en aplica les
con sencillez las condiciones de op imalidad que se hayan is o con an e io idad.
Y pa a inaliza el capí ulo, se p esen a án di e sos mé odos, a a és de los cuales,
se pod á calcula el óp imo de o ma exac a o numé ica (ap oximada). En es e con ex o,
odos es os mé odos es án basados en un mismo algo i mo, y lo que se p esen a á son
di e en es o mas de abo da cada paso de dicho algo i mo. De es a o ma, combinando las
di e en es mane as de abo da los pasos, se end á una eno me amilia de mé odos.
El in e és que subyace de ás de es e capí ulo inicial, son a ios. Po un lado, el de
INTRODUCCIÓN xxi
comenza a maneja los concep os básicos de la op imización, así como, esul ados básicos
que se u iliza án a lo la go de odo el abajo. Y po o a pa e, el de conoce di e en es o -
mas de esol e los p oblemas de op imización sin es icciones, ya que se á imp escindible
pa a esol e los p oblemas de op imización con es icciones.
Pos e io men e, el segundo capí ulo ya se in oduci á de pleno en el mundo de la op i-
mización con es icciones. En es e caso, el obje i o sigue siendo el mismo, halla el óp imo
de un uncional obje i o. Sin emba go, se añade la peculia idad de que no odos los alo es
de su dominio son admisibles. Es o quie e deci que sólo se desea op imiza dicho uncional
en un subconjun o de su dominio. Es e subconjun o, queda á de e minado po una se ie
de unciones que se denominan es icciones, y nue amen e, sólo se a a á en es e abajo
el caso en el que dichas es icciones sean di e enciables.
El hecho de la di e enciabilidad, uel e a se muy in e esan e en es e capí ulo, ya que
pe mi e da una a iedad de condiciones necesa ias y/o su icien es que pe mi en ca ac e-
iza los óp imos del p oblema. Y p ecisamen e, se á ese el p ime obje i o del capí ulo.
Luego, se in oduci án los mul iplicado es de Lag ange, que ol e án a da condiciones
necesa ias pa a óp imos en un caso especial de es icciones. De es a o ma, se amplia án
dichas condiciones a un caso gené ico incluyendo más ipos de es icciones al in oduci
los mul iplicado es de Ka ush-Kuhn-Tucke y F i z-John.
Todos esos mul iplicado es, pe mi i án apo a impo an es esul ados pa a segui ca-
ac e izando los óp imos de los p oblemas que se a an. Es os esul ados, se án de i al
impo ancia con pos e io idad debido a que muchos mé odos que se e án con pos e io-
idad, se basa án en consegui pun os que cumplan dichas condiciones (los cuales son
candida os a óp imo) y haciendo un es udio pos e io , se de e mina ía si ealmen e son óp-
imos o no. En es e sen ido, ambién se apo a án condiciones su icien es bajo las cuales,
las condiciones is as apo en exac amen e el óp imo del p oblema.
Finalmen e y pa a e mina es e segundo capí ulo, se in oduci án algunas nociones
básicas sob e la eo ía de la dualidad. Su in e és e adica en la c eación de un nue o
p oblema (al que se denomina á como p oblema dual) con el obje i o de que és e sea más
sencillo que el p oblema inicial (al que se conoce á como p oblema p imal). De es a o ma,
se pod á es ablece una elación en e las soluciones de ambos p oblemas pa a que en
ocasiones uese con enien e esol e el p oblema dual en ez del p imal.
Todo es o, se aplica á ambién a la p og amación cuad á ica. Es e ipo especial de
op imización, se basa en un uncional cuad á ico (se de ini á en los capí ulos uno y dos) y
un conjun o de inido po es icciones a ines. La pa icula idad de es e ipo de p oblemas,
pe mi i á aplica los concep os in oducidos en el capí ulo dos de o ma sencilla y simple.
Sin emba go, es di ícil que en la ealidad, los p oblemas de op imización que se plan ean,
xxii INTRODUCCIÓN
se enma quen den o de es e ma co de p oblemas. Pe o el in e és mayo i a io de es os, es
debido a su u ilización en algunos mé odos de esolución de p oblemas gené icos, y es po
ello, que se le hace un hueco en el abajo.
Finalmen e, odo concluye en el e ce y úl imo capí ulo dedicado en exclusi idad a
los mé odos de esolución. Aquí se á donde se empleen los conocimien os adqui idos en los
capí ulos an e io es pa a pode deduci odos los algo i mos que se plan een.
La p ime a sección se dedica á a los mé odos de penalización. Se comenza á po la
penalización ex e io seguida de la penalización in e io . És os, son los más in ui i os y
abo dan di ec amen e el p oblemas penalizando aquellos pun os que no se encuen en den-
o del conjun o admisible donde se desea op imiza el uncional obje i o. Así pues, es os
mé odos apo an como solución un óp imo calculado de o ma numé ica esol iendo una
secuencia de p oblemas sin es icciones.
Sin emba go, en la p ác ica a eces esul a p oblemá ica la esolución de es os ipos de
p oblemas, po lo que se in oduce un nue o mé odo. És e es el conocido como Lag angiano
aumen ado, y se basa en las condiciones de op imalidad que apo an los mul iplicado es
de Lag ange y KKT. En es e caso, el mé odo es muy in e esan e debido a su buen un-
cionamien o en la p ác ica, pe o en ez de con e ge a un óp imo, lo hace a un pun o
cumpliendo las condiciones KKT. Es po ello, que es necesa io ecu i a los concep os
eó icos explicados en el capí ulo dos pa a es udia si el pun o ob enido es ealmen e un
óp imo.
A con inuación, se da á o a isión de esolución hablando de mé odos basados en di ec-
ciones ac ibles. En es e caso, es e ipo de mé odos, buscan el óp imo median e un p oceso
i e a i o que p oduzca una sucesión de pun os del conjun o donde se desea op imiza el
uncional.
Pa a ello, un p ime mé odo se á el desa ollado po Zou endijk, que debe ecu i a la
p og amación lineal. Nó ese, que no es ex año ecu i a la p og amación lineal, debido a
la exis encia de mé odos que uncionan muy bien en la p ác ica como el mé odo Símplex.
En es e abajo, no se a a la p og amación lineal (dado que el obje i o es a a la
p og amación no lineal di e enciable), pe o se apo a án e e encias que se pueden consul a
en las que se explica con de alle el mé odo Símplex, así como, su deducción. Además,
ambién se apo a á o o mé odo basado en di ecciones ac ibles u ilizado en la esolución
de la p og amación cuad á ica.
Finalmen e, se dedica á la úl ima sección a los mé odos de ipo SQP (sequen ial quad a-
ic p og amming) que como bien indica su nomb e, se basan en la p og amación cuad á ica.
Y es que su me odología se basa en la esolución sucesi a de p oblemas de ipo cuad á ico.
Po es e hecho, se u iliza los conocimien os que se hayan in oducido a lo la go del
INTRODUCCIÓN xxiii
abajo sob e los p oblemas cuad á icos. Nue amen e, su con e gencia apo a á pun os
cumpliendo las condiciones que de i an de los mul iplicado es de Lag ange y KKT. Es po
ello, que se debe ía hace una e lexión pos e io al igual que sucedía ya con o o ipo de
mé odos que con e gían a es os ipos de pun os.
Po o a pa e, ambién se han añadido dos Anexos que con ienen pseudocódigos ela i-
os a los algo i mos y mé odos in oducidos a lo la go del abajo. Su in e és es comple a
la in o mación o acla a dudas que pod ían su gi en la lec u a de los algo i mos. Sin em-
ba go, si se desea consul a los códigos comple os de los mé odos in oducidos, ambién se
puede hace en el a chi o .zip que se adjun a con la en aga del abajo. En él, se ienen
los a chi os .m que se hicie on con la p og amación en Ma lab de odos los mé odos que
se in oduje on en el abajo, y ambién, algunas ejecuciones de p ueba que mues a su
uncionalidad.
De es a o ma, se pond ía pun o y inal a es e abajo. Lo cie o, es que hay muchos
más mé odos de los que se pod ía habla y basados en muchos más en oques. Pues bien,
el ema es eno me y la di e sidad inmensa, po lo que se ha que ido cen a el abajo en
aquellos algo i mos y écnicas que se suelen usa con mayo ecuencia dando una isión
di e sa y ú il.
Po mi pa e, espe o que esul e sa is ac o ia y ag adable la lec u a del p esen e a-
bajo. Con él, deseo ansmi i el p imo de es a jo en ama de las ma emá icas que en su
co a ida, an o ha dado de si y pa a la que se islumb a un u u o p ome edo lleno de
in es igación y nue os descub imien os. Es así, que sólo anhelo ansmi i con su lec u a,
aunque sólo sea una pizca, la eno me pasión y cu iosidad que la op imización ha susci ado
en mi in e io du an e la ealización de es e abajo de in de g ado.
6CAPÍTULO 1. OPTIMIZACIÓN SIN RESTRICCIONES
Demos ación. Se puede consul a en [21, pág. 56].
Teo ema 1.13. Sea Ω⊆Rnun abie o con exo y J: Ω ⊆Rn→Run uncional di e en-
ciable. En onces se e i ica:
(1) Jes con exo, si y sólo si, J(w)≥J( ) + (∇J( ))T(w− )∀ ,w∈Ω.
(2) Jes es ic amen e con exo, si y sólo si, J(w)> J( ) + (∇J( ))T(w− )∀ ,w∈Ω.
Demos ación. Se puede e en [15, págs. 42-43].
Teo ema 1.14. Sea Ωun abie o con exo, con J: Ω ⊆Rn→Rclase 2 en Ω, se iene,
(1) Jes con exo, si y sólo si, HJ( )es semide inida posi i a ∀ ∈Ω.
(2) Si HJ( )es de inida posi i a ∀ ∈Ω, en onces, Jes es ic amen e con exo.
Demos ación. Se puede consul a en [15, págs. 43-44].
Los esul ados in oducidos, son los que se u iliza án a lo la go del abajo. Pe o pa a
mayo in o mación ace ca de los conjun os y uncionales con exos, se puede consul a [4].
Teo ema 1.15. Sea Ω⊆Rnun conjun o con exo y J: Ω ⊆Rn→Run uncional con exo.
En onces si u∈Ωes un mínimo local, se e i ica:
(1) ues un mínimo global.
(2) Si Jes es ic amen e con exo, ues el único mínimo global.
Demos ación. Pa a p oba (1), se demos a á po educción al absu do, po lo que se
supond á que exis e ¯
u∈Ω al que J(¯
u)< J(u), de modo que uno es un mínimo global.
Usando aho a que el uncional es con exo, se ob iene,
J(λ¯
u+ (1 −λ)u)≤λJ(¯
u) + (1 −λ)J(u)< λJ(u) + (1 −λ)J(u) = J(u)∀λ∈[0,1]
de modo que al oma λsu icien emen e pequeño, se oman pun os an p óximos a ucomo
se quie a en los que el uncional J oma alo es más pequeños que en u, lo que con adice
el hecho de que ues mínimo local, de lo que se deduce el esul ado.
Pa a p oba (2), usando nue amen e la educción al absu do, se supond á que exis e ¯
u∈
Ω−{u}de modo que J(¯
u) = J(u). Y usando la hipó esis de con exidad del uncional,
J(λ¯
u+ (1 −λ)u)< λJ (¯
u)+(1−λ)J(u) = λJ (u)+ (1−λ)J(u) = J(u)∀λ∈[0,1]
lo que con adice el hecho de que usea un mínimo global, luego el mínimo global es
único.
Co ola io 1.16. Sea Ω⊆Rnun conjun o abie o, con exo no acío y dado un uncional
J: Ω ⊆Rn→Rcon inuo, coe ci i o y es ic amen e con exo, en onces el p oblema (P)
iene solución y és a es única.

1.4. FUNCIONALES CUADRÁTICOS 7
1.4. Funcionales cuad á icos
A con inuación, en es a sección, se es udia án los uncionales cuad á icos, que debido
a sus p opiedades, pe mi en analiza de o ma sencilla los concep os in oducidos en la
sección an e io .
De inición 1.17. Sea J:Rn→Run uncional, se dice que és e es cuad á ico si es á
de inido de la siguien e o ma:
J( ) = 1
2 TQ −cT
donde Q= (qij)∈ Mn(R)es simé ica y c∈Rn.
Obse ación 1.18.Nó ese que en la de inición an e io , no es necesa io que Q∈ Mnsea
simé ica. Pues bien, pa a cualquie ∈Rn, se iene que TQ = TQ+QT
2 , y dado
que Q+QTes simé ica independien emen e de que Qlo sea, se puede de ini el uncional
cuad á ico pa a ma ices Q∈ Mn(R)gene ales como:
J( ) = 1
4 TQ+QT −cT
Teo ema 1.19. Sea J:Rn→Run uncional cuad á ico, en onces se e i ica:
(1) ∇J( ) = Q −cyHJ( ) = Q, pa a odo ∈Rn.
(2) Jes con exo, si y sólo si, Qes semide inida posi i a.
(3) Jes es ic amen e con exo, si y sólo si, Qes de inida posi i a.
Demos ación. (1) El uncional J:Rn→Rse esc ibe como:
J( ) = 1
2 TQ −c T=1
2
n
X
i,j=1
jqij i−
n
X
i=1
ci i
De i ando aho a espec o de la componen e iy eniendo en cuen a que Qes simé ica:
dJ
d i
=1
2
n
X
j=1
jqij +1
2
n
X
j=1
qji j−ci=1
2
n
X
j=1
jqij +1
2
n
X
j=1
qij j−ci=
n
X
j=1
jqij −ci= (Q −c)i
Po lo que, ∇J( ) = Q −c. Y si se uel e a de i a una segunda ez:
d2J
d id j
=qij ⇒HJ( ) = Q
(2) Po el eo ema 1.13, se iene:
Jes con exo ⇔J(w)−J( )− ∇J( )T(w− )≥0∀ ,w∈Rn
8CAPÍTULO 1. OPTIMIZACIÓN SIN RESTRICCIONES
en onces, aplicando es e hecho y haciendo un desa ollo de Taylo (que como J( ) iene
g ado dos, en onces el desa ollo de Taylo es exac o si se oma has a la de i ada segunda)
se iene,
J(w) = J( ) + ∇J( )T(w− ) + 1
2(w− )TQ(w− )⇒
⇒J(w)−J( )− ∇J( )T=1
2(w− )TQ(w− )≥0∀ ,w∈Rn
lo cual sucede, si y sólo si, Qes semide inida posi i a.
(3) Se p ocede de o ma análoga al an e io , llegando a la desigualdad es ic a (dado que
el uncional es es ic amen e con exo), po lo que se ob iene pa a Qla de inición de ma iz
de inida posi i a.
Obse ación 1.20.El esul ado es análogo pa a ma ices Q∈ Mn(R) eniendo en cuen a
la obse ación 1.18, de la que se deduce que:
∇J( ) = Q+QT
2 −cHJ( ) = Q+QT
2
1.5. Mé odos pa a la ob ención del mínimo
Hechos los es udios an e io es, es con enien e in oduci algunos algo i mos que nos
pe mi an llega a la ob ención del mínimo que se busca. Pa a ello, la idea undamen al, es
oma un pun o inicial u(0) (p óximo a la solución si es posible), y a pa i de él, cons ui
una sucesión que con e ja a la solución.
Pa a ello, se diseña á un algo i mo gené ico basado en dos e apas. Una de ellas, se á
calcula una di ección d∈Rn, al que J(u(k)+αd)< J(u(k))pa a algún α∈R(a la
que se denomina á di ección de descenso). La o a e apa, es calcula el alo α(al que se
denomina á como paso) que ga an iza el descenso del alo del uncional. Con es e mo i o,
se in oduce el siguien e eo ema que se á de ayuda.
Teo ema 1.21 (Condición su icien e de di ección de descenso).Dado un uncional J:
Rn→Rdi e enciable, en onces si exis e una di ección d∈Rn al que ∇J(u)Td<0,
en onces des una di ección de descenso pa a el pun o u.
Demos ación. Haciendo un desa ollo de Taylo cen ado en u, se ob iene que,
J(u+αd) = J(u) + α∇J(u)Td+o(α)⇒J(u+αd)−J(u)
α=∇J(u)Td+o(α)
α(1.3)
po lo que eniendo en cuen a que des una di ección de descenso, se iene que pa a un α
su icien emen e pequeño, J(u+αd)< J(u), po lo que haciendo el lími e cuando α→0
en la exp esión 1.3, se iene que ∇J(u)Td<0.
1.5. MÉTODOS PARA LA OBTENCIÓN DEL MÍNIMO 9
Algo i mo 1.22 (Algo i mo gené ico de descenso).Se p ocede del siguien e modo:
paso 0: Se p opo ciona el u(0) ∈Rnpa a a anca el algo i mo (si es posible, ce ca de la
solución que se deno a á po u), un alo de ole ancia δyk= 0.
paso 1: Se calcula una di ección de descenso d(k), y un paso αk∈(0,∞)que ga an iza
descenso, es deci , J(u(k)+αkd(k))< J(u(k)). Y se ac ualiza u(k+1) =u(k)+αkd(k),
k=k+ 1.
paso 2: Se comp ueban los c i e ios de con e gencia,
ku(k+1) −u(k)k
1 + ku(k+1)k≤δyk∇J(u(k+1))k< δ
que de cumpli se se inaliza, y en caso con a io, se ol e ía al paso 1.
Obse ación 1.23.Si se desea consul a un pseudocódigo de es e algo i mo gené ico, se
puede e un ejemplo en el Anexo I.
1.5.1. Cálculo del paso
Pa a calcula el paso αk, es impo an e de ini la unción j: [0,∞)→Rcomo sigue:
j(α) = J(u(k)+αd(k))
El obje i o, es halla un αk∈[0,∞)que cumpla que j(αk)< j(0), po lo que se
plan ea un p oblema de minimización unidimensional. Pa a esol e lo, nó ese que si Jes
su icien emen e di e enciable, en onces,
j0(α) = d(k)T
∇J(u(k)+αd(k))⇒j0(0) = d(k)T
∇J(u(k))<0
j00(α) = d(k)T
HJ(u(k)+αd(k))d(k)
y usando es os cálculos, se pueden plan ea di e en es si uaciones, y a su ez dis in as
o mas de cálculo del paso.
Paso óp imo:
El paso óp imo, se deno a al paso exac o que da el óp imo. És e end á ca ac e izado
po j0(α)=0, y en algunos casos pa icula es, como los uncionales cuad á icos de inidos
po una ma iz simé ica de inida posi i a, es posible calcula lo:
j0(α) = dT(Q(u+αd)−c) = dTQu+αdTQd−dTc⇒j0(α)=0⇔α=−dT(Qu −c)
dTQd
10 CAPÍTULO 1. OPTIMIZACIÓN SIN RESTRICCIONES
Dico omia
La si uación an e io , no es nada común en la ealidad. En su de ec o, si se conoce
un in e alo (a, b)⊂(0,+∞)en el que se encuen a el paso αk. Una buena opción se ía
calcula la solución al p oblema j0(α)=0median e el mé odo de dico omia (o de New on-
Raphson si j∈ C2(a, b)). Además, si no se conoce el in e alo (a, b), és e se puede ap oxima
median e algún p ocedimien o numé ico. Pa a conoce de alles sob e su implemen ación,
se puede consul a [7] o en [17, págs. 38-57], en el que se apo an dos e siones, una en
la que se u iliza la de i ada (j0(α)) y o a en la que no es necesa io e alua la. De dichas
e siones, se puede consul a sus pseudocódigos en el Anexo I.
Algo i mos de c i e io de paso g ande y pequeño
Uno de los algo i mos más empleados, se puede engloba den o de una amilia de
mé odos cuyo obje i o se á elegi un paso que no sea ni demasiado pequeño (a lo que se
conoce á como c i e io de paso pequeño (CPP)), ni demasiado g ande (a lo que se conoce á
como c i e io de paso g ande (CPG)). Po an o, se di á que un paso es admisible (CPA)
si no e i ica CPP ni CPG. De es e modo, oda es a amilia de eglas, siguen el siguien e
algo i mo gené ico:
Algo i mo 1.24 (Regla gene al de CPP y CPG).Se sigue el siguien e p ocedimien o:
paso 0: Se apo a un in e alo inicial (αmin, αmax)de al mane a que αmin cumpla CPP
yαmax cumpla CPG.
paso 1: Se oma α= (αmin +αmax)/2y se comp ueba si αcumple CPP. En caso a i -
ma i o, se ac ualiza αmin =αy se uel e al paso 1, y en caso con a io, se pasa al paso
paso 2.
paso 2: Se comp ueba si αcumple el CPG. En caso a i ma i o, se ac ualiza αmax =α,
y en caso con a io, αes admisible, po lo que se inaliza el algo i mo y se oma αcomo
solución.
Obse ación 1.25.En el paso 1 del algo i mo 1.24, se oma como αde p ueba el pun o
medio del in e alo. Pe o en ealidad, se pod ía gene a un pun o de p ueba median e
cualquie o a me odología como la egla de la secan e u o as. Po o a pa e, en el
paso 0, en ez de apo a un in e alo cumpliendo dichas condiciones, se puede hace un
p ocedimien o p e io pa a inicializa el algo i mo con la búsqueda numé ica de un in e alo
e i icando las condiciones eque idas (se puede e un pseudocódigo de es a incialización
en el Anexo I).
El p ocedimien o an e io , p opo ciona una g an a iedad de eglas de cálculo del paso
en unción del los di e en es CPP y CPG que se pod ían oma . En es e ma co, las es
1.5. MÉTODOS PARA LA OBTENCIÓN DEL MÍNIMO 11
eglas más conocidas y usadas, son las siguien es:
1. Regla del A mijo: No cuen a con CPP y se dice que un paso αes demasiado g ande
si j(α)> j(0) + ρj0(0)αpa a un alo de ρ∈(0,1/2).
2. Regla de Golds ein: Un paso αcumple CPP si j(α)< j(0) + m2j0(0)α, y e i ica á
el CPG si j(α)> j(0) + m1j0(0)α, donde m1∈(0,1/2) ym2∈(1/2,1). Además, en
la p ác ica se suele usa m2= 1 −m1.
3. Regla de Wol e-Powell: Un paso αcumple el CPP si j0(α)< m2j0(0) ,y e i ica á el
CPG si j(α)> j(0) + m1j0(0)α, donde 0< m1< m2<1.
Figu a 1.1: Regla de paso con CPG y CPP
En la igu a, se mues a la idea
que subyace de ás de odas es-
as eglas. Tomando como ejemplo
el c i e io de Golds ein, aquellos
pun os que cumplan los c i e ios
CPP (los que es án po debajo de
la línea CPP) y CPG (los que se
encuen an po encima de la ec-
a CPG), dejan de se admisibles
y se mues an con una línea en ojo. Po el con a io, los pun os que es án en e ambas
ec as, son pun os admisibles y se ep esen an con en una línea en e de.
1.5.2. Mé odo del g adien e
Recibe es e nomb e el mé odo que oma como di ección de descenso d(k)=−∇J(u(k)),
y en base a es a di ección, se segui á el algo i mo 1.22, omando como paso αk, el ob enido
al usa alguna de las eglas desc i as en el apa ado 1.5.1.
En caso de pode calcula el αkóp imo, el mé odo ecibi á el nomb e de g adien e con paso
óp imo. Mé odo en el cuál, se u iliza la di ección de máximo descenso.
1.5.3. Mé odo del g adien e conjugado
És e mé odo, mejo a el is o en el apa ado 1.5.2. Esencialmen e, es á pensado en un
p ime momen o pa a uncionales cuad á icos. Su con e gencia se p oduce en a lo sumo n
i e aciones independien emen e del pun o inicial dado pa a a anca el mé odo, po lo que,
no se puede conside a como al un mé odo i e a i o.
Su undamen o, se basa en oma di ecciones conjugadas, es deci , ales que,
d(i)TQd(j)= 0 con i6=j i, j ∈ {0,1, . . .}

12 CAPÍTULO 1. OPTIMIZACIÓN SIN RESTRICCIONES
y explíci amen e, el algo i mo end ía dado po :
Algo i mo 1.26 (G adien e conjugado en uncionales cuad á icos).Se sigue el siguien e
p ocedimien o:
paso 0: Se oma un u(0) ∈Rnde a anque , con su esiduo dado po (0) =Qu(0) −cy
se oma como di ección de descenso d(0) =− (0),k= 0.
paso 1: Se calcula el paso que iene dado explíci amen e po , αk= (k)T (k)
d(k)T
Qd(k)
, con el
que se ac ualiza el i e an e y se oma u(k+1) =u(k)+αkd(k). Luego, se ac ualiza (k+1) =
(k)+αkQd(k).
paso 2: Si (k+1) =0se inaliza, y en caso con a io, se oma βk+1 = (k+1) T (k+1)
(k)T (k), con
el que se ac ualiza la nue a di ección d(k+1) =− (k+1) +βk+1d(k), se oma k=k+ 1 y se
uel e al paso 1.
Obse ación 1.27.Pa a consul a con de alle los aspec os que hay de ás de es e algo i mo
(deducción, con e gencia, implemen ación, e c) se puede consul a [13, págs.102-120].
Es e caso, es ob iamen e pa a el caso en el que el uncional obje i o es cuad á ico.
Po an o, una cues ión in e esan e se ía si es a me odología se pod ía amplia al caso no
cuad á ico. La espues a es posi i a y se plan ean dos p opues as:
1. Fle che -Ree es: Pa iendo de d(0) =−∇J(u(0)), en cada k-i e ación se oma:
βk=k∇J(u(k+1))k2
k∇J(u(k))k2yd(k+1) =−∇J(u(k+1)) + βkd(k)
2. Polak-Ribié e: Pa iendo de d(0) =−∇J(u(0)), en cada k-i e ación se oma:
βk=k∇J(u(k+1))k2
k∇J(u(k))k2yd(k+1) =−∇J(u(k+1)) + βkd(k)
Ob iamen e, en los dos casos an e io es, con dichas exp esiones de la di ección de
descenso, se p ocede usando el algo i mo 1.22, combinándolo con los is os en 1.5.1 pa a
calcula el paso.
1.5.4. Mé odo de New on
O a o ma de abo da el p oblema, se ía calculando el u∈Rnque cumpla que ∇J(u) =
0, dado que se io que es a condición es indispensable pa a se mínimo (sin es icciones).
Pa a ello, se u iliza el mé odo de New on-Raphson aplicado a la unción ∇J( ),
(u(0) dado
u(k+1) =u(k)−HJ(u(k))−1∇J(u(k))k≥0
1.5. MÉTODOS PARA LA OBTENCIÓN DEL MÍNIMO 13
la cual, se enma ca den o del ma co del algo i mo 1.22, omando αk= 1 yd(k)=
−HJ(u(k))−1∇J(u(k)). Po an o, es e mé odo no ga an iza descenso en odas sus i e-
aciones. Es más, la di ección d(k)no end ía po que se de descenso.
Po ello, se puede mejo a el mé odo in oduciendo alguna egla de cálculo de paso en
ez de oma paso ijo 1. Po o o lado, el cos e compu acional es demasiado ele ado debido
a ene que calcula la in e sa de la ma iz hessiana en cada i e ación. De modo que pa a
sol en a es a si uación, se puede p ocede del siguien e modo,







u(0) dado
HJ(u(k))w=−∇J(u(k))
u(k+1) =u(k)+w
que se uel e a enma ca den o del algo i mo 1.22 omando d(k)=wyαk= 1. Y
nue amen e, se puede mejo a el mé odo combinándolo con alguna de las eglas de cálculo
de paso.
1.5.5. Mé odos Cuasi-New on
Sin emba go, en el mé odo de New on esul a cos oso debido a ene que e alua con-
inuamen e la Hessiana. Pa a esol e es e p oblema, se in oducen los mé odos Cuasi-
New on que ienen el mismo undamen o que el is o en 1.5.4 con la peculia idad de usa
una ap oximación de la hessiana del uncional.
Pa a es a ap oximación, se oma una ma iz de a anque H0de inida posi i a y simé-
ica (la iden idad o una ap oximación median e di e encias ini as), pa a luego calcula
en cada i e ación una ac ualización de dicha ma iz median e algunas de las eglas de
ac ualización que que se in oducen a con inuación,















Hk+1 =Hk+s(k)s(k)T
s(k)Ty(k)−Hky(k)y(k)THk
y(k)THky(k)Ac ualización D.F.P
Hk+1 = I−s(k)y(k)T
s(k)Ty(k)!Hk I−y(k)s(k)T
s(k)Ty(k)!+s(k)s(k)T
s(k)Ty(k)Ac ualización B.F.G.S
donde yk=∇J(u(k+1))− ∇J(u(k))ysk=u(k+1) −u(k). De es a o ma, omando como
ap oximación de la hessiana, la dada po la ó mula B.F.P o B.F.G.S en cada k-i e ación,
se de ini ía la di ección d(k)como se io en el apa ado 1.5.4. Así pues, omando dicha
di ección y combinándola con una egla de cálculo de paso, se ob end ía una g an a iedad
de mé odos de Cuasi-New on al aplica el algo i mo 1.22.
14 CAPÍTULO 1. OPTIMIZACIÓN SIN RESTRICCIONES
Finalmen e, una p opiedad in e esan e que puede esul a ú il en ocasiones es que bajo
cie as hipó esis, las ac ualizaciones de las in e sas de la hessiana, pueden man ene el
ca ác e de de inidas posi i as. El siguien e esul ado lo mues a:
Teo ema 1.28. Si Hkes de inida posi i a, ∇J(u(k+1))6=0, y el paso αkes elegido de al
o ma que el i e an e u(k+1) e i ica:
∇J(u(k))Td(k)<∇J(u(k+1))Td(k)
(lo cual es equi alen e a que s(k)Ty(k)>0), en onces la ma iz Hk+1 de inida po un
mé odo B.F.P ó B.F.G.S, es de inida posi i a.
Demos ación. Se puede consul a en [3, págs.60-61].
Po o o lado, en casos donde la dimensión del p oblema es muy ele ada, esul a p ohi-
bi i o implemen a es e algo i mo. Es o es debido al ele ado cos e de ope a y gua da
ma ices con dimensiones muy g andes. Po es e mo i o, en la p ác ica se op a po una
e sión de cos e meno al usa la ac ualización B.F.G.S (ya que es la que mejo es esul ados
apo a).
En dicha e sión (donde se op a po un algo i mo ecu si o), la di ección de descenso
usando la ac ualización B.F.G.S, se ob iene almacenando únicamen e un núme o mde los
s(k)ey(k)calculados en las i e aciones an e io es. Así pues, conside ando una k-i e ación
cualquie a, se pod ía oma el siguien e algo i mo pa a ob ene d(k)(la di ección de des-
censo),
Algo i mo 1.29 (Cálculo de la di ección de descenso B.F.G.S).Tomando de o ma inicial
q=∇J(u(k)), se p ocede como sigue:
paso 1: De iniendo ρk=1
y(k)Ts(k), se p ocede con un bucle en i=k−1, . . . , k−m, donde
se oma γi=ρisiTq,q=q−γiy(i).
paso 2: De iniendo H0
k=s(k−1) Ty(k−1)
y(k−1) Ty(k−1) Iy omando =H0
kq, se p ocede con un bucle en
i=k−m, . . . , k−1, donde se oma β=ρiy(i)T , con el que se ac ualiza = +s(i)(γi−β).
paso 3: Se concluye omando como di ección de descenso d(k)=− .
Median e es a o ma, se sua iza el cos e compu acional en dimensiones muy ele adas.
De hecho, se ha is o en la p ác ica que se ob ienen esul ados muy buenos pa a un alo
men e 3 y 20. En [13, págs.176-185] se pueden e más de alles sob e es a o ma de
implemen ación de la ó mula B.F.G.S. denominada B.F.G.S de memo ia limi ada, y se
puede consul a un pseudocódigo del mé odo Cuasi-New on con una ó mula B.F.G.S de
cos e educido en el Anexo I.
Capí ulo 2
Op imización con es icciones:
Concep os eó icos
En el an e io capí ulo, se ha is o como se abo dan los p oblemas de op imización
ela i os al p oblema (P). Pe o es e ipo de p oblemas sólo se p esen an en si uaciones
muy idílicas que no suceden en la ealidad.
Po consiguien e, se p e ende a pa i de aho a p esen a un nue o ipo de p oblema que
englobe las peculia idades que su gen en la ealidad, y a pa i de es os p oblemas, desa-
olla nue os mé odos que nos pe mi an esol e los ó en su luga , educi los a p oblemas
equi alen es del ipo (P)pa a soluciona los como en el capí ulo an e io .
2.1. P esen ación del p oblema
Con mo i o de lo que se ha explicado, se p esen a el siguien e p oblema de minimización
con es icciones, al que se e e i á de aho a en adelan e como p oblema (Q):
m´ın
∈RnJ( )
Suje o a:
ϕi( )≤0i= 1, . . . , m
φj( )=0 j= 1, . . . , p
(Q)
Como se puede obse a , en es e nue o p oblema no iene po que se solución el mínimo
global de J( ), ya que se á solución del p oblema aquel alo que minimice el uncional
cumpliendo las exigencias ma cadas po las unciones ϕiyφj.
Es as unciones se conocen como es icciones y delimi an el conjun o donde se p e ende
minimiza el uncional obje i o, al que se denomina como conjun o ac ible óconjun o
15
22 CAPÍTULO 2. OPTIMIZACIÓN CON RESTRICCIONES, TEORÍA
2.3. Mul iplicado es de Lag ange
En es a sección, se conside a á un caso pa icula del p oblema (Q), en el que se iene
el p oblema de minimización de un uncional obje i o J:Rn→Rsuje o a es icciones
de ipo igualdad, po lo que no se ienen es icciones de ipo desigualdad. A es e caso, se
deno a á como p oblema (Qig), y se e á que exis e la posibilidad de su esolución median e
un sis ema de ecuaciones no lineales.
Pa a ello, se comienza in oduciendo la no ación pe inen e. En p ime luga , a pa i
de las unciones que de inen las es icciones, se de ine la unción Φ : Rn→Rp, que iene
dada po ,
Φ( ) = (φ1( ), φ2( ), . . . , φp( ))T
de modo que el conjun o ac ible se puede de ini de la siguien e mane a:
S={ ∈Rn: Φ( ) = 0}
De inición 2.12. Un pun o u∈Ses egula pa a las es icciones {φj( )}p
j=1 si los
ec o es g adien es ∇φ1(u),...,∇φp(u)son linealmen e independien es.
Obse ación 2.13.La de inición an e io , no se puede da si p>n.
Teo ema 2.14. Dado un pun o egula u∈S, el espacio angen e a Sen dicho pun o es:
T(u) =  ∈Rn: Φ0(u) =0
donde Φ0(u)se co esponde con:
Φ0(u) = (∇φ1(u)|. . . |∇φp(u))T
Demos ación. Se puede consul a en [16, pág. 302].
Lema 2.15. Dado u∈Sun pun o egula , supóngase que dicho ues un mínimo de J
en S, y que Jes de i able en u. En onces, pa a odo ∈Rn, que e i ique Φ0(u) =0
ambién se iene que h∇J(u), i= 0.
Demos ación. Se puede e en [16, pág. 304].
Teo ema 2.16. Conside ando el p oblema (Qig)donde el uncional y las es icciones
son di e enciables, si dado u∈Sun pun o egula , és e es un mínimo del uncional J
en S. En onces, exis en pnúme os λi, que se conoce án como mul iplicado es de Lag ange
asociados a u, de inidos de o ma única, ales que:
∇J(u) + λ1∇φ1(u) + . . . +λp∇φp(u) = 0

2.3. MULTIPLICADORES DE LAGRANGE 23
Demos ación. Si ∇J(u) = 0, en onces la p opiedad es ob ia omando λ1=. . . =λp= 0.
En onces, suponiendo que ∇J(u)6=0, haciendo uso del lema an e io , si ∈ke (Φ0(u)),
en onces ∈ke ∇J(u)T, po lo que, ke (Φ0(u)) ⊆ke ∇J(u)T. De es e modo,
omando el espacio o ogonal, se iene el con enido con a io, es deci , ke ∇J(u)T⊥⊆
ke (Φ0(u))⊥. Aho a bien, es ob io que ∇J(u)T∈ke ∇J(u)T⊥, po lo que, ∇J(u)T∈
ke (Φ0(u))⊥=Im (Φ0(u)), y en onces, exis en coe icien es λ1, . . . , λp∈R ales que,
∇J(u) = λ1∇φ1(u) + . . . +λp∇φp(u)
lo cual es e iden e que es equi alen e a la esis del eo ema.
És a, no es la única demos ación posible del eo ema. Pues exis en múl iples e siones
pa a llega a ob ene el mismo esul ado. Po ejemplo, en [1, págs. 150-152] se da una
demos ación haciendo uso del Teo ema de la unción implíci a.
Po o a pa e, la condición necesa ia ob enida, pe mi e ob ene un mé odo pa a la
esolución del p oblema (Qig)median e la esolución de un sis ema de ecuaciones no lineales
gene almen e. Pa a ello, se oman como incógni as (λi1≤i≤p)yu.
Aho a bien, como u∈Rnes un ec o de ncomponen es, en o al se ienen n+p
incógni as. Las cuales, queda án de e minadas po las ecuaciones de las es icciones y la
condición de Lag ange, es deci ,
(∇J(u) + Φ0(u)Tλ=0
Φ(u) = 0(2.3)
siendo λel ec o que iene po componen es a los mul iplicado es de Lag ange. Esc ibiendo
dicho sis ema de una o ma más isual, queda ía:



























∂
∂ 1
J(u) + λ1
∂
∂ 1
φ1(u) + . . . +λp
∂
∂ 1
φp(u)=0
.
.
.
∂
∂ n
J(u) + λ1
∂
∂ n
φ1(u) + . . . +λp
∂
∂ n
φp(u)=0
φ1(u)=0
.
.
.
φp(u) = 0
Obse ación 2.17.Si se oma el Lag angiano asociado al p oblema, que se de ine de la
siguien e o ma,
L( ,ξ) = J( ) + Φ( )Tξ ∈Rnξ∈Rp
24 CAPÍTULO 2. OPTIMIZACIÓN CON RESTRICCIONES, TEORÍA
el sis ema 2.3, se puede eesc ibi en o ma compac a como:









L
∂ (u,λ) = ∇J(u) + Φ0(u)Tλ=0
∂L
∂ξ(u,λ) = Φ(u) = 0
De modo que esol e el sis ema de ecuaciones plan eado, es equi alen e a ob ene un pun o
c í ico asociado al p oblema.
Sin emba go, la esolución del sis ema no apo a exac amen e la solución al p oblema de
minimización. Es o es debido a que la condición apo ada po el eo ema es necesa ia pe o
no su icien e. Po ello, una ez ob enidos los alo es de λyuque e i ican las ecuaciones,
es necesa io e alua en un en o no de uel uncional pa a de e mina el ipo de pun o c í ico
que se ha ob enido.
Teo ema 2.18 (Condición su icien e de Lag ange).Se conside a el p oblema (Qig), bajo las
hipó esis de de i abilidad del uncional obje i o y de las es icciones. En onces, suponiendo
que u∈Ses un pun o e i icando la condición de Lag ange con mul iplicado es de Lag ange
λ, e i icando que,
dTHL (u,λ)d>0pa a odo d/∈0con Φ(u)0d=0
en onces ues un mínimo local es ic o del p oblema (Qig).
Demos ación. Se puede consul a en [10, pág 272-273].
Es e eo ema, apo a un caso en el que la condición de Lag ange es su icien e, y po
an o, bajo dichas hipó esis, no hab ía que comp oba si la solución ob enida es mínimo
o no. Po o a pa e, los mul iplicado es de Lag ange aquí in oducidos, ienen di e sas
aplicaciones en dis in as amas del conocimien o. Po ejemplo, la ísica o la economía son
cla os ejemplos de ello, y se puede e en [9] o [20].
2.4. Condiciones de Ka ush-Kuhn-Tucke y F i z-John
En es a sección, se e á una gene alización de la condición de Lag ange is a en 2.16,
al caso que incluye es icciones de desigualdad. Pa a ello, se hace uso de las condiciones
de Ka ush-Kuhn-Tucke y pos e io men e de las condiciones de F i z-John que se de inen
a con inuación.
2.4. CONDICIONES DE KARUSH-KUHN-TUCKER Y FRITZ-JOHN 25
De inición 2.19. Conside ando el p oblema (Q), se de ine su unción Lag angiano aso-
ciada, L( , ν, ξ) : Rn×Rm×Rp→Rcomo sigue:
L( ,ν,ξ) = J( ) +
m
X
i=1
νiϕi( ) +
p
X
j=1
ξjφj( )
De inición 2.20. Dado el p oblema (Q), se supone que el uncional obje i o y las es-
icciones son de i ables. En onces, se dice que un pun o u∈Rnes un pun o de Ka ush-
Kuhn-Tucke pa a el p oblema (Q), si y sólo si, exis en mul iplicado es de Lag ange y de
Ka ush-Kuhn-Tucke (a los que se deno a á po las le as g iegas λyµ espec i amen e)
e i icando las condición!de KKT (KKT) que son las siguien es:
1.- Condición es aciona ia:
∇ L(u,µ,λ) = ∇J(u) +
m
X
i=1
µi∇ϕi(u) +
p
X
j=1
λj∇φj(u) = 0(2.4)
2.- Condición de ac ibilidad
(ϕi(u)≤0i= 1, . . . , m
φj(u)=0 j= 1, . . . , p (2.5)
3.- Condición de holgu a:
(µiϕi(u)=0 i= 1, . . . , m
µi≥0i= 1, . . . , m (2.6)
Pa a calcula aho a los pun os que cumplen las condiciones de Ka ush-Kuhn-Tucke
(KKT), se puede p ocede en dos pasos. El p ime o, es la esolución de un sis ema de
ecuaciones (no lineal gene almen e), y que se co esponden con la imposición de la condición
es aciona ia, de ac ibilidad pa a las es icciones de igualdad y la de holgu a:











∂
∂ k
J( ) +
p
X
j=1
λj
∂
∂ k
φj( ) +
m
X
i=1
µi
∂
∂ k
ϕi( )=0 k= 1, . . . , n
φj( )=0 j= 1, . . . , p
µiϕi( )=0 i= 1, . . . , m
Nó ese que se a a de un sis ema de (n+m+p)ecuaciones y (n+m+p)incóg-
ni as. Es as se ían, las ncomponen es de u, los pmul iplicado es de Lag ange y los m
mul iplicado es KKT. Una ez esuel o, el segundo paso se ía e cuáles de las soluciones
ob enidas son pun os de KKT. Pa a ello, hay que comp oba que son pun os ac ibles, es
deci , comp oba que cumplen las es icciones de desigualdad, y inalmen e, que odos los
mul iplicado es KKT son posi i os.
26 CAPÍTULO 2. OPTIMIZACIÓN CON RESTRICCIONES, TEORÍA
Llegados a es e pun o, se es á en condiciones de p oba que odo mínimo del p oblema
(Q), e i ica las condiciones KKT. Pa a ello, se in oduce la siguien e e sión del Lema de
Fa kas-Mi konski que se á de u ilidad en su demos ación.
Lema 2.21 (Lema de Fa kas-Mi konski).Conside ando el p oblema (Q)y un pun o ac ible
u∈S, el conjun o,
Z=






d∈Rn:
dT∇J(u)<0
dT∇ϕi(u)≤0i= 1, . . . , m
dT∇φj(u) = 0 j= 1, . . . , p







es acío, si y sólo si, exis en mul iplicado es de Lag ange y de KKT e i icando la condición
es aciona ia en u.
Demos ación. Se puede e en [15, págs. 53-54,391] y en [12, pág. 313-314].
Teo ema 2.22 (Ka ush-Kuhn-Tucke ).Sea uun mínimo local del p oblema (Q). Si se
cumple la siguien e condición, a la que se denomina á como condición de cuali icación,
DF S(u, S) = DFL(u, S)(2.7)
en onces exis en mul iplicado es de Lag ange y de KKT e i icando las condiciones KKT.
Demos ación. Dado que ues un mínimo local del p oblema, és e e i ica las condiciones
de ac ibilidad, es deci , 2.5. Aho a bien, sea d∈DFS(u, S), po el eo ema 2.9, se iene
que dT∇J(u)≥0. Pe o aplicando la condición 2.7, d∈DFL(u, S), y así el sis ema,







dT∇J(u)<0
dT∇ϕi(u)≤0i∈I(u)
dT∇φj(u)=0 j= 1, . . . , p
no iene solución y po an o el conjun o Zde inido en el lema de Fa kas–Mi konski es
acío, y po an o, se ob iene que exis en mul iplicado es de Lag ange y de KKT (µi≥0)
e i icando que,
∇J(u) + X
i∈I(u)
µi∇ϕi(u) +
p
X
j=1
λj∇φj(u)=0
po lo que omando µi= 0 i /∈I(u), se ob iene la condición es aciona ia y de holgu a. De
modo que se ob iene el esul ado.
Es a demos ación que se acaba de hace , no es única. De hecho, exis en muy di e sas
o mas de demos a el Teo ema de Ka ush-Kuhn-Tucke , po ejemplo, se puede consul a
2.4. CONDICIONES DE KARUSH-KUHN-TUCKER Y FRITZ-JOHN 27
[2] pa a e o o ipo de demos ación donde se u iliza el Teo ema de Weie s ass. Po o o
lado, la demos ación mos ada en es e abajo, equie e de la condición de cuali icación
2.7, pe o és a no es única. De hecho, puede se subs i uida po o as equi alen es. Con es e
obje i o, se in oduce el siguien e eo ema.
Teo ema 2.23. Sea ∈Sun pun o admisible. Si los ec o es ∇φj( )con j= 1, . . . , p y
∇ϕi( )con i∈I( )son linealmen e independien es, en onces la condición de cuali icación
2.7 se cumple, es deci , DF S( , S) = DFL( , S).
Demos ación. Se puede consul a en [15, pág 394-396].
Obse ación 2.24.Exis e una g an a iedad de condiciones de cuali icación que si en de
u ilidad pa a p oba el eo ema 2.22, pa a ello, e [14, sec. 6.3].
Has a el momen o, se han in oducido los mul iplicado es KKT, pe o ambién se pod ía
habla de los mul iplicado es de F i z-John. És os, se pod ían conside a una gene alización
de los an e io es, pe o que en algunos casos esul an de u ilidad.
De inición 2.25. Dado el p oblema (Q), suponiendo que an o el uncional como las
es icciones son de i ables. En onces, se dice que un pun o u∈Rn e i ica las condiciones
de F i z-John (ó es un pun o de F i z-John), si y sólo si, exis en mul iplicado es de Lag ange
(λ) y de F i z-John (η0,η) ales que:

















η0∇J(u) +
m
X
i=1
ηi∇ϕi(u) +
p
X
j=1
λj∇φj(u)=0
ϕi(u)≤0yφj(u) = 0 pa a i= 1, . . . , m j = 1, . . . , p
ηiϕi(u)=0 pa a i= 1, . . . , m
η0, ηi≥0pa a i= 1, . . . , m y además (η0,η,λ)6=0
Como se puede obse a , és as son las mismas condiciones KKT, sal o que en es e caso,
∇J(u)es á mul iplicado po un elemen o η0≥0. Po an o, si η0>0, al di idi la p ime a
ecuación de las condiciones de F i z-John po η0, se ob ienen las condiciones KKT. Po
an o, la única di e encia exis i á cuando η0= 0. A con inuación, se apo a un esul ado
simila al is o en el eo ema 2.22 pa a las condiciones de F i z-John.
Teo ema 2.26 (Condición necesa ia de F i z-John).Dado el p oblema (Q), suponiendo
que an o el uncional obje i o como las es icciones sean di e enciables. Si u∈Ses un
mínimo local del p oblema (Q), en onces exis en mul iplicado es de Lag ange y de F i z-
John, cumpliendo las condiciones de F i z-John.
Demos ación. Si los ec o es ∇φj(u)con j= 1, . . . , m y∇ϕi(u)con i∈I(u)son li-
nealmen e dependien es, en onces exis en elemen os λ1, . . . , λpyηicon i∈I(u), ales

28 CAPÍTULO 2. OPTIMIZACIÓN CON RESTRICCIONES, TEORÍA
que Pi∈I(u)ηi∇ϕi(u) + Pp
j=1 λj∇φj(u)=0, siendo alguno de ellos dis in os de ce o. Po
an o, omando η0=ηi= 0 con i /∈I(u), se ob ienen inmedia amen e las condiciones de
F i z-John.
Si se supone aho a que los ec o es ∇φj(u)con j= 1, . . . , m y∇ϕi(u)con i∈I(u)son
linealmen e independien es, aplicando el eo ema 2.23, se ob iene la condición de cuali ica-
ción 2.7, y po an o, se es á en condiciones del eo ema 2.22. Po consiguien e, se cumplen
la condiciones KKT, luego, omando η0= 1 yη=µ, se ob ienen ambién las condiciones
de F i z-John.
En onces, un pun o cumpliendo las condiciones de F i z-John, es un candida o a mínimo
(al igual que sucedía con los pun os KKT). Es e hecho, se usa á pos e io men e en el úl imo
capí ulo dado que algún mé odo numé ico pe mi i á ob ene un pun o de F i z-John. Sin
emba go, cuando η0= 0, las condiciones que nos apo a el eo ema 2.26, no dependen del
∇J(u), lo que no apo a in o mación sob e el uncional obje i o en el mínimo. Po es e
mo i o, es poco in e esan e la condición de F i z-John, y a pa i de aho a, se es udia án
los pun os KKT en los que si se e in oluc ado ∇J(u).
Con inuando pues con el es udio de los pun os KKT, en el eo ema 2.22, se p opo ciona
una condición necesa ia de mínimo. Pues cualquie mínimo cumple las condiciones KKT,
sin emba go, és a no es su icien e en gene al. Pa a pode in oduci condiciones su icien es,
es necesa io e o za las hipó esis sob e el p oblema. Con es e mo i o, se in oduce la
siguien e de inición necesa ia pa a in oduci una condición su icien e KKT.
De inición 2.27. Dado el p oblema de op imización (Q), se di á que és e es con exo si
el uncional obje i o y el conjun o admisible son con exos. Además, se ep esen a á a es e
ipo especial de op imización como p oblema (QC).
Obse ación 2.28.En el caso del p oblema (QC), se supond á que las es icciones ϕi( )
son con exas y las φj( )lineales. Es as suposiciones, de i an del hecho de que al se de
es os modos conc e os, el conjun o ac ible que gene an es con exo.
Teo ema 2.29 (Condición su icien e de Ka ush-Kuhn-Tucke ).Dado un p oblema de op-
imización con exa (QC), se iene que dado un pun o admisible u∈S, pa a el cual exis en
mul iplicado es de Lag ange y KKT (λyµ espec i amen e). En onces dicho pun o es un
mínimo del p oblema (QC).
Demos ación. Se conside a un pun o u∈S e i icando las condiciones KKT, sean λy
µsus mul iplicado es de Lag ange y KKT asociados. La unción L( ,µ,λ)es con exa
pa a cualquie a . En onces, usando las p opiedades de las unciones con exas 1.13, y las
2.4. CONDICIONES DE KARUSH-KUHN-TUCKER Y FRITZ-JOHN 29
condiciones KKT, se iene que pa a cualquie pun o ac ible ,
L( ,µ,λ)≥ L(u,µ,λ) + ( −u)T∇ L(u,µ,λ) = L(u,µ,λ) =
=J(u) +
m
X
i=1
µiϕi(u) +
p
X
j=1
λjφj(u) = J(u)(2.8)
pe o como es un pun o ac ible y µi≥0pa a i= 1, . . . , m, en onces se deduce que,
µiϕi( )≤0i= 1, . . . , m
λjφj( )=0 j= 1, . . . , p )⇒ L( ,µ,λ)≤J( )
po lo que usando 2.8 se ob iene que J( )≥J(u), y po consiguien e, ues un mínimo.
Vis os es os esul ados, la in e p e ación geomé ica que se puede hace de ellos y de
las condiciones KKT, se mues a en la siguien e g á ica. En ella, se p esen an dos es ic-
ciones de desigualdad que delimi an un conjun o ac ible. En discon inuo, se p esen an los
g adien es de las unciones en el pun o (1,1) que se supone el mínimo en el conjun o pa a
un cie o uncional.
0 0.5 1 1.5
0
0.5
1
1.5
Figu a 2.4: Condiciones KKT
De es e modo, suponiendo que se es á en las
hipó esis del eo ema 2.22, el g adien e del un-
cional en el mínimo iene una dependencia lineal
espec o de los g adien es de las es icciones ac-
i as. Aho a bien, como las dos es icciones son
ac i as y los mul iplicado es KKT son posi i os,
el conjun o de líneas inas ep esen a el cono de
los posibles alo es que puede oma −∇J(1,1).
Lo cual, es lógico desde el pun o de is a in-
ui i o, dado que −∇J(1,1) es la di ección de
máximo descenso en dicho pun o, y si és a ue-
se ac ible, el (1,1) no pod ía se mínimo local.
De es e modo, se iene una in o mación ela i-
a sob e la di ección de máximo descenso en el
mínimo, y a pa i de ella, de odas las posibles
di ecciones de descenso.
Po o o lado, has a el momen o sólo se han is o condiciones de p ime o den que
ca ac e izan los mínimos. Sin emba go, las condiciones KKT nos an a pe mi i amplia la
in o mación is a has a el momen o, dando condiciones de segundo o den.
30 CAPÍTULO 2. OPTIMIZACIÓN CON RESTRICCIONES, TEORÍA
De inición 2.30. Sea ∈Rn e i icando las condiciones de KKT, si exis en sucesiones
nd(k)ok∈N→dy{δk}k∈N→0 ales que (k)= +δkd(k)∈S, e i icando,
ϕi( (k))≤0i∈I( ) I+( )
ϕi( (k))=0 i∈I+( )yφj( (k))=0 j= 1, . . . , p
donde I+( ) = {i:i∈I( ) ales que µi>0}. En onces se dice que des una di ección de
es icción secuencial nula, y al conjun o de dichas es icciones se deno a po S( ,µ,λ)⊆
DF S( , S).
De inición 2.31. Dado un pun o ∈Rn e i icando las condiciones KKT (con mul ipli-
cado es de Lag ange y KKT λyµ espec i amen e), si d∈DFL( , S)yµidT∇ϕi( ) =
0∀i∈I( ), en onces des una di ección de es icción nula linealizada. Al conjun o de
dichas es icciones se deno a po G( ,µ,λ), y se puede esc ibi como:
G( ,µ,λ) = (d∈Rn:d∈DF L( , S)
dT∇ϕi( ) = 0 i∈I+( ))⊆DFL( , S)
Teo ema 2.32 (Condición necesa ia de segundo o den).Sea u∈Rnun mínimo local del
p oblema (Q). Si se cumple la condición de cuali icación 2.7, se iene,
dTH L(u,µ,λ)d≥0∀d∈S(u,µ,λ)
donde H L(u,µ,λ)deno a la hessiana del Lag angiano espec o de e aluada en (u,µ,λ).
Demos ación. Pa a cualquie d∈S(u,µ,λ), si d=0el esul ado es ob io, po lo que
se supone d6=0. Tomando las sucesiones nd(k)ok∈N→dy{δk}k∈N→0en la o ma de
la de inición 2.30, se iene que Pm
i=1 µiϕi(u(k)) + Pp
j=1 λjφj(u(k))=0, po lo que, usando
es e hecho y las condiciones de KKT (pues ues un pun o KKT po el eo ema 2.22), se
llega a:
J(u(k)) = J(u+δkd(k)) = L(u+δkd(k),µ,λ) = L(u,µ,λ) + δkd(k)T∇ L(u,µ,λ)+
+1
2δ2
kd(k)TH L(u,µ,λ)d(k)+o(δ2
k) = J(u) + 1
2δ2
kd(k)TH L(u,µ,λ)d(k)+o(δ2
k)
(2.9)
Pe o como ues un mínimo local es ic o, pa a un ksu icien emen e g ande, se iene que
J(u+δkd(k))≥J(u). De modo que, usando es e hecho, 2.9 y aplicando lími es, se llega a,
dTH L(u,µ,λ)d≥0
como se que ía demos a .
2.4. CONDICIONES DE KARUSH-KUHN-TUCKER Y FRITZ-JOHN 31
Obse ación 2.33.Si se iene que S(u,µ,λ) = G(u,µ,λ), en onces se end ía de o ma
e iden e que dTH L(u,µ,λ)d≥0pa a odo d∈G(u,µ,λ).
Teo ema 2.34 (Condición su icien e de segundo o den).Dado u∈Rnun pun o cum-
pliendo las condiciones de KKT pa a el p oblema (Q). Si se e i ica que,
dTH L(u,µ,λ)d>0∀d∈G(u,µ,λ)
en onces ues un mínimo local es ic o del p oblema.
Demos ación. Se supone que uno es mínimo, po lo que exis e una sucesión de elemen os
ac ibles u(k)k∈N→u ales que J(u(k))≤J(u). Y sin pé dida de gene alidad, se puede
asumi que,
(u(k)−u
ku(k)−uk)k∈N→d
po lo que aplicando el azonamien o de la demos ación del eo ema 2.10, se ob iene que
dT∇J(u)≤0,. Usando aho a las condiciones KKT,
∇J(u) = −
m
X
i=1
µi∇ϕi(u)−
p
X
j=1
λj∇φj(u)
que al mul iplica po d, si se iene en cuen a que d∈DFS(u, S)⊆DFL(u, S), en onces,
dT∇J(u) = −
m
X
i=1
µidT∇ϕi(u)−
p
X
j=1
λjdT∇φj(u)≥0
de modo que se ob u ie on las dos desigualdades, y po an o dT∇J(u)=0, lo que implica
que Pi∈I(u)µidT∇ϕi(u)=0, y po consiguien e, d∈G(u,µ,λ).
Aho a bien, eniendo en cuen a que J(u(k))≤J(u), se puede hace el siguien e desa ollo,
L(u,µ,λ)≥ L(u(k),µ,λ) = L(u,µ,λ) + 1
2δ2
kd(k)THL(u,µ,λ)d(k)+o(δ2
k)
po lo que al di idi po δ2
ky oma lími es, se llega a que dTHL(u,µ,λ)d≤0, lo que es
una con adicción con la hipó esis, y po consiguien e se ob iene el esul ado.
Es e úl imo esul ado, es ablece una condición su icien e simila a la que se in odujo
en el co ola io 2.11, con la peculia idad de que se hace uso de la Hessiana del Lag angiano.
Pues bien, las condiciones KKT casi implican que dT∇J(u)>0sal o en las di ecciones de
es icción nula linealizadas. Po es e mo i o, se equie e una condición de segundo o den
en ellas.
38 CAPÍTULO 2. OPTIMIZACIÓN CON RESTRICCIONES, TEORÍA
De la o ma en que se de inió la unción dual en 2.39, se iene que és a iene de e minada
po ,
h(ν) = m´ın
∈Rn1
2 TQ −cT +µT(A −b)(2.11)
pe o como se ha supues o que Qes de inida posi i a, pa a un µcualquie a, la unción
1/2 TQ −cT +µT(A −b)es es ic amen e con exa. Además, su mínimo use
puede calcula de o ma exac a y end á de e minado po :
Qu +ATµ−c=0⇒u=Q−1c−ATµ(2.12)
De modo que, subs i uyendo el alo ob enido en 2.12 en la unción dual 2.11, se ob iene
que la unción dual es,
h(ν) = 1
2νTDν+µTd−1
2cTQ−1c
donde D=−AQ−1ATyd=AQ−1(b−c). De modo que el p oblema dual end ía dado
po ,
m´ax
ν∈Rm
1
2νTDν−dTν−1
2cTQ−1c
Suje o a:
νi≥0i= 1, . . . , m
(QPD)
cuya esolución, esul a ela i amen e más sencilla que la del p oblema o iginal, y pa a
la cuál, hay algo i mos especí icos de esolución, que se pueden consul a en [11, págs.
196-207].

Capí ulo 3
Op imización con es icciones:
Mé odos de esolución
Has a aho a, se ha dado espues a a di e en es cues iones sob e el p oblema de op imi-
zación con es icciones del ipo (Q). Es o pe mi e conoce las di e en es p opiedades que
ienen en unción de los ipos de uncionales y es icciones.
Pe o como el obje i o inal es pode esol e los, llegados a es e pun o, se es udia án
di e en es algo i mos que nos pe mi an ob ene una solución. A con inuación, se desc ibi án
mé odos numé icos que dependiendo del ipo de p oblema, apo a án dis in as isiones pa a
su esolución inal.
3.1. Mé odos de penalización
Un p ime mé odo, son los conocidos como mé odos de penalización. Hay dis in os
ipos den o de es a amilia de algo i mos, pe o una ca ac e ís ica común que los de ine.
És a consis e en educi el p oblema con es icciones de ipo (Q), a uno sin es icciones
del ipo (P)pa a esol e lo como se io en el p ime capí ulo.
Pa a ello, su idea p incipal consis e en cons ui un nue o uncional obje i o de al
mane a que si oma un elemen o ue a del conjun o admisible, és e penalice esa elección
aumen ando el alo que oma el uncional. De ahí p o iene el nomb e de penalización,
pues se penaliza la oma de un pun o no ac ible, y dependiendo del ipo de penalización,
se pueden di e encia los dis in os ipos de mé odos que se p esen an a con inuación.
39
40 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS
3.1.1. Penalización ex e io
Es e p ime mé odo, eside en la c eación de una sucesión de subp oblemas del ipo
(P), de al mane a que la sucesión o mada po las soluciones de los subp oblemas, con e ja
a la solución del p oblema (Q).
Con es e mo i o, se c ea una unción P:Rn→Rdenominada unción de penalización
ca ac e izada po ,
(P( )>0si /∈S
P( )=0 si ∈S
y en base a es a unción, se de ine una sucesión de p oblemas (Pε)del siguien e modo:
m´ın
∈RnJε( ) = J( ) + 1
εP( ) (Pε)
Po lo que dada una sucesión de elemen os {εk}k∈Nposi i os con e gen es a ce o, se
ob iene una sucesión u(εk)k∈Nde soluciones de (Pε). La cual, con e ge á a un elemen o u,
siendo és e solución de (Q). Pa a comenza , se e án algunas p opiedades de las unciones
de penalización y las soluciones u(εk).
Lema 3.1. Dado 0<1/ε1<1/ε2, se ienen las siguien es p opiedades:
(1) Jε1u(ε1)≤Jε2u(ε2)
(2) Ju(ε1)≤Ju(ε2)
(3) Pu(ε1)≥Pu(ε2)
Demos ación. Aplicando la de inición de solución del p oblema (Pε), se iene que:
Jε1(u(ε1))≤Jε1(u(ε2))≤Jε2(u(ε2))≤Jε2(u(ε1))(3.1)
Po an o, ya se ha ob enido (1). Aho a, de 3.1, se deduce que,
0≤Jε1(u(ε2))−Jε2(u(ε2))−hJε1(u(ε1))−Jε2(u(ε1))i=1
ε1
P(u(ε2))−1
ε2
P(u(ε2))−
1
ε1
P(u(ε1))−1
ε2
P(u(ε1))=1
ε1−1
ε2P(u(ε2))−P(u(ε1))
de lo que se ob iene (3). Y usando aho a (3) y lo is o en 3.1, se iene,
J(u(ε1))≤J(u(ε2)) + 1
ε1P(u(ε2))−P(u(ε1))< J(u(ε2))
lo que demues a (2) y inaliza la demos ación.
Lema 3.2. Sea ula solución del p oblema (Q)conside ado. En onces pa a cada k∈Nse
iene que:
J(u)≥Jεku(εk)≥Ju(εk)
3.1. MÉTODOS DE PENALIZACIÓN 41
Demos ación. El esul ado es inmedia o conside ando el siguien e desa ollo:
J(u) = J(u) + 1
εk
P(u)≥J(u(εk)) + 1
εk
P(u(εk))≥J(u(εk))
Lema 3.3. Se conside a el p oblema (Q)yu(ε)la solución al p oblema (Pε). En onces,
omando δ=P(u(ε)), se iene que u(ε) ambién es solución del p oblema:
m´ın
∈RnJ( )
Suje o a:
P( )≤δ
(3.2)
Demos ación. Pa a cualquie que sa is aga la condición P( )≤δ, se iene que,
0≤1
εP(u(ε))−P( )=Jε(u(ε))−J(u(ε))−Jε( ) + J( ) =
=hJε(u(ε))−Jε( )i+J( )−J(u(ε))≤J( )−J(u(ε))⇒J( )≥J(u(ε))
ob eniendo así la de inición de mínimo y concluyendo así la demos ación.
Llegados a es e pun o, se es á en condiciones de deduci el algo i mo del mé odo.
En onces, al conside a el p oblema (Q), eniendo en cuen a como se de ine la unción de
penalización, és e se puede eesc ibi como:
m´ın
∈RnJ( )
Suje o a:
P( ) = 0
(3.3)
Aho a bien, omando δlo su icien emen e pequeño, el p oblema 3.2 se á una ap oxi-
mación del p oblema o iginal (Q). Así, la idea básica de es e mé odo, se basa en que según
se educe el pa áme o de penalización εken cada i e ación, se educe el alo de P(u(εk))
como se io en el lema 3.1. Po es e mo i o, si se ija un alo de la ole ancia δpa a
ap oxima el p oblema (Q)median e 3.2, se puede es ablece el siguien e algo i mo.
Algo i mo 3.4 (Penalización ex e io ).Se sigue el siguien e p ocedimien o:
paso 0: Se oma ε0>0,δ > 0yk= 0.
paso 1: Se calcula u(εk+1), solución de (Pε).
paso 2: Si la penalización P(u(εk+1))< δ, en onces se inaliza. En caso con a io, se oma
εk+1 =εk/10,k=k+ 1 y se uel e al paso 1.
42 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS
Obse ación 3.5.La ac ualización del alo ε, no iene po que se la ma cada en el algo i -
mo. És a puede a ia en unción de nues os in e eses, haciendo que la sucesión {εk}k∈N
dec ezca con mayo o meno apidez. Además, en la esolución de los subp oblema (Pε),
se end á que usa algún mé odo de los is os en el p ime capí ulo. Pe o en ellos, se debe
apo a un i e an e inicial, pe o en es e caso, se ía un buen i e an e inicial la solución u(εk)
calculada en la i e ación an e io .
Po o o lado, nó ese que la unción de penalización debe se elegida de al o ma que el
uncional Jε( ) enga mínimo ini o, ya que si no es así, el algo i mo di e ge. Es a si ua-
ción, se puede da en casos donde el uncional obje i o dec ezca según k k → +∞y la
unción de penalización no c ezca con la misma apidez que dec ece J( ).
Aho a bien, una cues ión impo an e es el es udio de la con e gencia del mé odo. Pa a
ello se in oduce el siguien e eo ema.
Teo ema 3.6. Se conside a el p oblema (Q)con un uncional con inuo. En onces, cual-
quie pun o lími e de la sucesión u(εk)k∈Ngene ada po el algo i mo 3.4 es solución del
p oblema o iginal (Q).
Demos ación. Se supone que {u(εk0)}es una subsucesión con e gen e con lími e u. En-
onces, po la con inuidad del uncional J, se iene que:
l´ım
k0→+∞J(u(εk0)) = J(u)(3.4)
Deno ando po J∗el alo del uncional en la solución del p oblema (Q), y eniendo en
cuen a los lemas 3.1 y 3.2, la sucesión {Jεk0(u(εk0))}es c ecien e, y es á limi ada supe io -
men e po J∗. En onces,
l´ım
k0→+∞Jεk0(u(εk0)) = q≤J∗(3.5)
de mane a que, ex ayendo 3.4 de la ecuación 3.5, se iene que,
l´ım
k0→+∞
1
εk0
P(u(εk0)) = q−J(u)(3.6)
y como P(u(εk0))≥0y1/εk0→+∞, po 3.6, implica que:
l´ım
k0→+∞P(u(εk0))=0
Usando aho a la con inuidad de P( ), implica que P(u) = 0, po lo que ues un pun o
admisible pa a el p oblema. Además, po el lema 3.2, J(u(εk0))≤J∗y se iene:
J(u) = l´ım
k0→+∞J(u(εk0))≤J∗
Po consiguien e, ues una solución óp ima ac ible del p oblema o iginal (Q).
3.1. MÉTODOS DE PENALIZACIÓN 43
Obse ación 3.7.De es e eo ema, se deduce que si la sucesión gene ada po el algo i mo 3.4
con e ge a un pun o, és e se á solución del p oblema gene al (Q). Sin emba go, es a sucesión
no iene po que se con e gen e en gene al. Pues bien, puede da se que el mínimo de algún
subp oblema no sea ini o, y po an o, que la sucesión comience a di e gi . Po es e mo i o,
si se pueden asegu a hipó esis de con exidad y coe ci i idad sob e los subp oblemas (Pεk),
se asegu a ía la exis encia y unicidad de la sucesión {u(εk)}k∈Ngene ada po el algo i mo
3.4.
Una cues ión in e esan e aho a, se ía como c ea una unción de penalización P( ). En
ealidad, cualquie unción que cumpla las p opiedades que la de inen, se puede usa . Sin
emba go, algunas iene mejo es p opiedades que o as. Una posible opción, se ía usa la
siguien e denominada penalización cuad á ica:
P( ) =
m
X
i=1
(m´ax {0, ϕi( )})2+
p
X
j=1 |φj( )|2(3.7)
Tal y como es á de inida es a penalización, el uncional Jε( )se á de i able y con inuo.
Pe o al no se con inua la de i ada segunda, puede conlle a p oblemas si se usa un mé odo
de segundo o den.
Pa a ejempli ica isualmen e lo que p oduce la penalización, omando la unción de
penalización 3.7, se a a aplica aho a al siguien e p oblema unidimensional,
m´ın
∈RJ( ) = e
Suje o a:
ϕ1( ) = −
ϕ2( ) = −1
(3.8)
de lo que se ob ienen los siguien es esul ados:
Figu a 3.1: Penalización ex e io

44 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS
En la p ime a igu a se mues a el uncional, las es icciones y el conjun o ac ible.
Mien as, en la segunda imagen, se mues a el uncional obje i o J( )y los di e en es
Jεk( )a medida que se a ina el alo de εksegún se indica en la leyenda. Así pues, como se
obse a, los uncionales Jεk( )aumen an su alo ue a de la egión ac ible mien as que
se man iene el uncional o iginal den o del conjun o admisible.
3.1.2. Penalización in e io
O o mé odo simila al an e io , es el mé odo de la penalización in e io o de la ba e a.
En es e nue o caso, se uel e a usa una unción de penalización, a pa i de la cuál se
de ini á un nue o uncional obje i o, y a pa i de él, una sucesión de subp oblemas cuya
sucesión de soluciones con e ja a la solución del p oblema inicial.
Sin emba go, se in oducen di e encias espec o del caso an e io . En p ime luga , sólo
se a a conside a el p oblema (Qdes), y se p e ende cons ui usa sucesión de soluciones
ac ibles, po lo que cada u(εk)∈S. Pa a in oduci se en el mé odo, se comenza á po la
de inición de la unción de penalización, que se de ine como P:Rn→Rde al mane a
que,
l´ım
d( ,∂S)→0P( ) = +∞yP( )>0∀ ∈S
donde d( , ∂S)deno a la dis ancia del pun o a la on e a de S, es deci , la penali-
zación aumen a según se ap oxima a la on e a del conjun o admisible. En base a es a
penalización, se de ine el siguien e p oblema sin es icciones:
m´ın
∈RnJε( ) = J( ) + εP( ) (Pε)
A con inuación se p esen an a ias p opiedades de es a unción de penalización que son
análogas a la penalización ex e io .
Lema 3.8. Dado 0< ε2< ε1, se iene:
(1) Jε2(u(ε2))≤Jε1(u(ε1))
(2) J(u(ε2))≤J(u(ε1))
(3) P(u(ε2))≥P(u(ε1))
Demos ación. Análoga al lema 3.1 o consul a [15, pág 468]
Lema 3.9. Siendo u(ε)solución del p oblema (Pε)y omando δ=P(u(ε)). En onces u(ε)
es solución del p oblema,
m´ın
∈RnJ( )
Suje o a:
P( )≤δ
(3.9)
3.1. MÉTODOS DE PENALIZACIÓN 45
Demos ación. Pa a odo ∈Rn e i icando que P( )≤δ, se iene,
0≤εP(u(ε))−P( )=Jε(u(ε))−J(u(ε))−Jε( ) + J( ) =
hJε(u(ε))−Jε( )i+J( )−J(u(ε))≤J( )−J(u(ε))⇒J(u(ε))≤J( )
De lo que se ob iene la de inición de mínimo y po an o lo que se que ía p oba .
Cuando el alo de δdel lema an e io es lo su icien emen e g ande, és e si e pa a
ap oxima el siguien e p oblema:
m´ın
∈RnJ( )
Suje o a:
P( )<+∞
(3.10)
Aho a bien, del modo en que se ha de inido la unción de penalización, la es icción
del p oblema 3.10 es equi alen e a que su solución sea ac ible pa a el p oblema inicial
(Q). Sin emba go, dicha solución no se encon a á sob e la on e a de S, ya que en dichos
pun os la penalización iende a in ini o.
Además, si ε > 0es su icien emen e pequeño y el δdel lema an e io es lo bas an e
g ande, en onces u(ε)se encuen a den o de la egión ac ible Sy ap oxima el alo de la
solución del p oblema o iginal. En onces, se puede deduci el siguien e algo i mo.
Algo i mo 3.10 (Penalización In e io ).Se p ocede como sigue:
paso 0: Se oma ε0>0,δ > 0yk= 0.
paso 1: Se calcula u(εk+1), solución de (Pεk).
paso 2: Si εkP(u(εk+1))< δ, se inaliza. En caso con a io, se oma εk+1 =εk/10,k=k+1
y se uel e al paso 1.
Obse ación 3.11.Como sucedía en penalización ex e io , el dec ecimien o de εken el paso
3, no iene que se la indicada, sino que puede se cualquie a. Además, como se usa án los
algo i mos del p ime capí ulo pa a esol e los subp oblemas (Pεk), en es e caso ambién
se puede oma el i e an e an e io como pun o de a anque, ya que és e es a á p óximo a
la solución.
Una ez is o es e algo i mo, se in oduce a con inuación un eo ema que apo a esul-
ados sob e la con e gencia de dicho mé odo.
Teo ema 3.12. Sea J( )un uncional limi ado in e io men e en la egión ac ible S. En-
onces, el algo i mo de penalización in e io e mina de o ma ini a pa a δ > 0, y cuando
no lo hace, en onces se e i ica:
46 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS
(1) l´ımk→∞ εkP(u(εk+1))=0.
(2) l´ımk→∞ J(u(εk+1)) = ´ın ∈In (S)J( ).
Y además, cualquie pun o de acumulación de la sucesión {u(εk)}k∈Nes solución del p o-
blema (Qdes).
Demos ación. Sólo se á necesa io p oba (1) y (2) cuando el algo i mo no e mina de
o ma ini a. Pa a ello, se oma η > 0a bi a io, po lo que exis i á un elemen o (que
depende de η) al que se deno a á po uη∈In (S)de al o ma que,
J(uη)<´ın
∈In (S)J( ) + η
2(3.11)
en onces como {εk} → 0yuη∈In (S), debe exis i un ¯
k∈N al que:
εkP(uη)<η
2∀k≥¯
k(3.12)
Usando aho a que u(εk+1)es el mínimo del uncional Jεk( ):
Jεku(εk+1)≤Jεk(uη)⇒εkPu(εk+1)≤J(uη) + εkP(uη)−Ju(εk+1)(3.13)
Po lo que usando 3.11, 3.12 y 3.13, se ob iene que,
εkPu(εk+1)≤J(uη) + εkP(uη)−Ju(εk+1)≤
≤´ın
∈In (S)J( ) + η
2+η
2−J(u(εk+1))≤η∀k≥¯
k
y como η > 0es a bi a io, se concluye (1). Aho a, pa a p oba (2), u ilizando la desigual-
dad an e io , se iene,
J(u(εk+1))≤J(uη) + εkP(uη)≤´ın
∈In (S)J( ) + η∀k≥¯
k
y como η > 0es a bi a io, se concluye (2).
Una ez is os es os esul ados, es na u al plan ea la cues ión sob e como oma la
unción de penalización P( ). Con es e mo i o, se plan ean las siguien es dos opciones que
son las más gene ales:
P( ) = −
m
X
i=1
1
ϕi( )yP( ) = −
m
X
i=1
1
log(−ϕi( ))
En onces, pa a mos a el e ec o de la penalización in e io de un modo isual, se
conside a el siguien e p oblema,
m´ın
∈RJ( ) = 4
Suje o a:
ϕ1( ) = −1
ϕ2( ) = − −1
(3.14)
3.1. MÉTODOS DE PENALIZACIÓN 47
del que se ob iene los siguien es esul ados:
Figu a 3.2: Penalización in e io
En la p ime a g á ica, se mues a el uncional obje i o con las es icciones y el conjun o
ac ible. Luego, en la segunda g á ica, se mues a de nue o el uncional obje i o, y además,
los uncionales Jε( )pa a dis in os alo es de ε. De es e modo, se obse a la con e gencia
de los uncionales Jε( )al uncional del p oblema o iginal den o de la egión ac ible.
Sin emba go, exis e una peculia idad, pues bien, en la on e a del conjun o, los alo es
de Jε( ) ienden al in ini o, lo que mues a que el mé odo sólo con e ge á a un pun o del
in e io del conjun o admisible.
De es e modo, se mues a isualmen e como es necesa io inicializa el mé odo desde un
pun o ac ible. Además, pa a es icciones de igualdad, el mé odo no se i ía, dado que los
uncionales Jε( )no es a ía de inido en esos pun os.
3.1.3. Mé odo del lag angiano aumen ado
Una ez is os los mé odos basados en penalización de es a sección, se puede obse a
la necesidad de que el pa áme o {εk}k∈N→0. Es e hecho, es una g an des en aja desde
el pun o de is a numé ico, debido a que según se oma εkmás pequeño, la esolución
numé ica de los subp oblemas gene ados, puede esul a más compleja de lo p e is o.
Pa a sol en a es a di icul ad, se in oduce el concep o de Lag angiano aumen ado.
És e, de i a de la unción Lag angiano in oducida en el capí ulo dos, y pe mi i á sol en a
ese p oblema que p esen an los mé odos de penalización. Pa a ello, se plan ea á en p ime
luga el concep o de Lag angiano aumen ado pa a el p oblema con es icciones de igualdad
(Qig).
De inición 3.13. Se de ine la unción Lag angiano aumen ado pa a el p oblema (Qig)
54 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS
del conjun o S, independien emen e del pun o ∈Sescogido, DF( , S) = ∅, de modo
que no exis en di ecciones ac ibles de descenso.
Sin emba go, bajo algunas condiciones, la exis encia de di ecciones ac ibles de descenso
si es á ga an izada. A con inuación, se mues a un esul ado que mues a las peculia idades
de cómo debe se el conjun o admisible.
Teo ema 3.22. Se conside a el p oblema (Q)y se supone que el conjun o admisible Ses
con exo y que el uncional J( ) ambién lo es. En onces, dado un pun o ∈S, siemp e a
a exis i una di ección ac ible en , si y sólo si, no es un mínimo del p oblema (Q).
Demos ación. Ob iamen e, si es mínimo del p oblema, no an a exis i di ecciones de
descenso po el mo i o de se mínimo. Po an o, se asume que no es mínimo, y al
mínimo, se deno a po u∈S. Pe o como J( )es con exo, aplicando 1.13 se deduce,
dT∇J( )<0
siendo d=u− . Aho a bien, como el conjun o admisible Ses con exo y u, ∈S, en onces
d∈DF ( , S). De modo que se e i ica que des una di ección ac ible de descenso.
Llegados a es e pun o, de la o ma en la que se ha p esen ado el mé odo, es ácil p esen-
a un algo i mo gené ico pa a la esolución del p oblema (Q)a a és de las di ecciones
ac ibles, el cual es el siguien e:
Algo i mo 3.23 (Algo i mo gené ico de di ecciones ac ibles).Se siguen los siguien es
pasos:
paso 0: Se oma un i e an e inicial u(0) ∈Syk= 0.
paso 1: Si no exis e una di ección ac ible de descenso d(k)pa a el pun o u(k), en onces se
inaliza. En caso con a io, se calcula d(k).
paso 2: Se calcula el paso αk>0.
paso 3: Se ac ualiza u(k+1) =u(k)+αkd(k),k=k+ 1 y se uel e al paso 1.
Obse ación 3.24.En el paso 2 del algo i mo an e io , se pide calcula el paso αasociado
a una di ección dy un pun o . Sin emba go, es e paso no es el mismo del que se habló
en el p ime capí ulo pa a el caso sin es icciones. Pues bien, dicho alo αes un alo
posi i o que esuel e el p oblema unidimensional,
m´ın
+αd∈SJ( +αd)(3.23)
po lo que se e que se exige que el paso no es opee la ac ibilidad de los pun os de la
sucesión c eada con el algo i mo.

3.2. MÉTODOS DE DIRECCIONES FACTIBLES 55
Pa a ello, en la esolución del p oblema 3.23, se puede op a po hace una búsqueda
numé ica del in e alo [0, δ]que asegu a la ac ibilidad del paso α. De es e modo, pos e-
io men e se pod ía aplica a dicho in e alo un mé odo de búsqueda de paso median e
dico omia (con de i adas o sin ellas) de la o ma que se desc ibie on en 1.5.1. Pa a e un
pseudocódigo que mues e es a inicialización del algo i mo, se puede consul a el Anexo II
al inal del abajo.
Sin emba go, no es ecomendable aplica un algo i mo del ipo CPP y CPG. Es o
es debido a que si el alo δob enido no cumple el CPG, el algo i mo no iene po qué
con e ge a un paso admisible haciendo que pueda oma un paso excesi amen e pequeño.
En es e sen ido, se pod ía op a po algún ipo de modi icación de dichos c i e ios. Po
ejemplo, en [15, pág 493-496] se apo a una p opues a modi icada de la egla del A mijo.
3.2.1. Mé odo de Zou endijk
En el con ex o de los mé odos de di ecciones ac ibles, se conside a á en p ime luga
el mé odo de Zou endijk. És e, puede ene di e en es e siones de su algo i mo según se
a e de un p oblema de op imización con unciones lineales o no lineales. Sin emba go, en
es e apa ado, se conside a á el caso gené ico no lineal como se ha enido haciendo has a
el momen o.
Pa a ello, se comienza conside ando el p oblema de op imización con es icciones de
desigualdad, es deci , un p oblema del ipo (Qdes)pa a el que se desa olla á el mé odo.
En es e con ex o, el siguien e esul ado es la base del mé odo.
Teo ema 3.25. Sea un pun o ac ible del p oblema (Qdes). Suponiendo que el uncional
obje i o y las es icciones ac i as son di e enciables y aquellas que no son ac i as son
con inuas. Si ∇J( )Td<0y∇ϕi( )Td<0pa a odo i∈I( ), en onces des una
di ección ac ible de descenso.
Demos ación. Se supone que dsa is ace que ∇J( )Td<0y∇ϕi( )Td<0,i∈I( ).
Dado que pa a i /∈I( ),ϕi( )<0y las unciones ϕi( )son con inuas en , en onces
debe exis i un δ > 0 al que ϕi( + d)≤0pa a odo ∈[0, δ]. Aho a bien, po la
di e enciabilidad de las unciones ϕi( ), pa a i∈I( ),
ϕi( + d) = ϕi( ) + ∇ϕi( )Td+o( kdk)
Como ∇ϕi( )Td<0, en onces ϕi( + d)< ϕi( )=0pa a un > 0su icien emen e
pequeño. Aho a bien, ϕi( + d)≤0pa a i= 1, . . . , m pa a un lo su icien emen e pequeño
(ya que si i /∈I( )cualquie di ección es ac ible), y po an o exis e un > 0 al que
+ des ac ible. Po consiguien e, como po hipó esis ∇J( )Td<0,d ambién es una
di ección de descenso y en onces se concluye el esul ado.
56 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS
T as lo is o, se deduce una posible o ma de halla di ecciones ac ibles de descenso
dado un pun o admisible . Pues bien, se pod ía plan ea un p oblema que minimice el
máximo en e ∇J( )Tdy∇ϕi( )Tdcon i∈I( ). Po consiguien e, se plan ea el siguien e
p oblema:
m´ın
(z,d)∈Rn+1 z
Suje o a:
∇J( )Td−z≤0
∇ϕi( )Td−z≤0i∈I( )
−1≤dj≤1j= 1, . . . , n
(3.24)
A pa i de es e pun o, se deno a á po ¯z, ¯
da la solución del p oblema 3.24. Como
(z, 0)es ac ible pa a cualquie z≥0, en onces ¯z≤0. Po an o, como en la solución del
p oblema 3.24 ¯z < 0, al aplica el eo ema an e io , se iene que ¯
des una di ección ac ible
de descenso.
Teo ema 3.26 (Teo ema de Go dan).Dada una ma iz Am×n, sólo uno de los siguien es
sis emas iene solución:
(1) Ax <0,x∈Rn.
(2) ATy=0, pa a un y∈Rm, con y≥0ey6=0.
Demos ación. Se puede consul a en [11, pág. 50-51].
Teo ema 3.27. Dado un p oblema del ipo (Qdes), y uun pun o admisible. En onces, u
es un pun o de F i z-John, si y sólo si, en el óp imo del p oblema 3.24, ¯z= 0.
Demos ación. El alo óp imo ¯zdel p oblema 3.24 es ce o, si y sólo si, el sis ema
(∇J(u)Td<0
∇ϕi(u)Td<0∀i∈I(u)
no iene solución. En onces, haciendo uso del eo ema 3.26, és e sis ema no iene solución,
si y sólo si, exis en escala es η0,ηicon i∈I(u) ales que,
η0∇J(u) + X
i∈I(u)
ηi∇ϕi(u)=0 con η0≥0yηi≥0∀i∈I(u)
donde η0oηison es ic amen e mayo es que 0 pa a algún i∈I(u). Lo cual es p ecisamen e
la condición de pun o de F i z-John.
En es e caso, no se puede asegu a la exis encia de un pun o KKT. Además, se ha is o
que η0puede no se es ic amen e posi i o, lo cuál, se ía necesa io y su icien e pa a que el
pun o de F i z-John uese KKT.
3.2. MÉTODOS DE DIRECCIONES FACTIBLES 57
Po o o lado, is o es e úl imo esul ado, se puede deduci el mé odo de Zou endijk.
Pues bien, dado un pun o inicial ac ible, se puede p ocede median e un p ocedimien o
i e a i o en el que se ob enga una di ección ac ible de descenso median e la esolución del
p oblema 3.24. De lo que se deduce el siguien e algo i mo:
Algo i mo 3.28 (Mé odo de Zou endijk).Se sigue el siguien e p ocedimien o i e a i o:
paso 0: Se oma u(0) ∈S ac ible y e oma k= 0.
paso 1: Se calcula I(u(k))y se esuel e el p oblema 3.24 del que se ob iene una solución
(zk,d(k)). En caso de que zk= 0, se inaliza y se ob iene un pun o de F i z-John, y en caso
con a io, se pasa al paso 2.
paso 2: Se calcula el paso αk, se oma u(k+1) =u(k)+αkd(k)y se uel e al paso 1.
Puede pa ece con adic o io que pa a halla una di ección ac ible de descenso, sea
necesa io esol e un nue o p oblema de minimización con es icciones. Sin emba go, el
p oblema plan eado en 3.24, iene una eno me en aja, pues an o el uncional obje i o
como las es icciones son lineales. Po an o, se es á an e un p oblema de p og amación
lineal.
Así, usando es e hecho, se puede ob ene la solución de dicho p oblema median e el uso
del algo i mo del Símplex, que pe mi e su esolución de o ma sencilla. És e algo i mo (el
Símplex), no se ha in oducido en el abajo dado que se es á a conside a p oblemas en el
con ex o no lineal, pe o se puede consul a su deducción e implemen ación en el capí ulo
13 de [13, pág 370] o en el capí ulo 7 de [19, pág 420] (de és e úl imo, se puede consul a
su pseudocódigo en el Anexo II).
En lo que se e ie e a la con e gencia del mé odo, és a no es á asegu ada. De hecho, se
puede e aplicando el con aejemplo de Wol e [11, págs 381-382]. Sin emba go, és e p oble-
ma se sol en a de algún modo haciendo la modi icación que Topkis y Veino p opusie on
en 1967, y que ga an iza la con e gencia a un pun o de F i z-John.
Es a modi icación, consis e en subs i ui el p oblema 3.24 en el algo i mo 3.28, po el
siguien e:
m´ın
(z,d)∈Rn+1 z
Suje o a:
∇J( )Td−z≤0
Ψ0( )Td−z≤ −Ψ( )
−1≤dj≤1j= 1, . . . , n
(3.25)
Nó ese, que sigue es ando den o del ma co de los p oblemas de p og amación lineal,
po lo que es a modi icación no implica una complejidad añadida en la esolución del
subp oblema. Es a nue a me odología de esolución, se conoce ambién como el algo i mo
58 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS
de Topkis-Veino en hono a sus c eado es. En lo que se e ie e a la con e gencia, se puede
apo a el siguien e esul ado del que se omi e su demos ación debido a que és a se basa
en concep os no in oducidos en el abajo, pe o que se pueden consul a en la e e encia
apo ada.
Teo ema 3.29. Se conside a un p oblema del ipo (Qdes)donde el uncional obje i o y las
es icciones son su icien emen e di e enciables. En onces, cualquie pun o de acumulación
de la sucesión {u(k)}k∈Ngene ada po el algo i mo 3.28 con la modi icación de Topkis-
Veino , es un pun o de F i z-John.
Demos ación. Se puede consul a en [11, págs. 386-389].
3.2.2. Mé odo de los conjun os ac i os
O o mé odo de ipo di ecciones ac ibles, es el conocido mé odo de conjun os ac i os.
En es e caso, se desa olla á pa a p oblemas de ipo cuad á ico ( is os en 2.5), debido a
que la esolución de es os p oblemas se usa á en la sección pos e io .
P ime amen e, pa iendo de la no ación desc i a en 2.5, se a a deno a po ai∈Rn
con i= 1, . . . , m la ila i-ésima de la ma iz A, po lo que A= (a1|. . . |am)T. Y de o ma
análoga, ej∈Rncon j= 1, . . . , p se co esponde con la ila j-ésima de la ma iz E, de
modo que E= (e1|. . . |ep)T. Teniendo es o en cuen a, se a a comenza in oduciendo
el siguien e esul ado básico.
Lema 3.30. Sea uun mínimo local del p oblema (QP), en onces ues un mínimo local del
siguien e p oblema:
m´ın
∈Rn
1
2 TQ −cT
Suje o a:
E =
aiT =bii∈I(u)
(3.26)
Recíp ocamen e, sea uun pun o ac ible del p oblema (QP)que e i ica las condiciones
KKT del p oblema 3.26, con mul iplicado es de Lag ange (λ,µ), de mane a que λ∈Rpy
µ∈R|I(u)| al que,
µi≥0, i ∈I(u)(3.27)
en onces u ambién es un pun o cumpliendo las condiciones KKT pa a el p oblema (QP).
Demos ación. Como ues solución del p oblema (QP), és e es ac ible y po an o ambién
es un pun o admisible pa a el p oblema 3.26, pe o además, como los uncionales obje i os
coinciden pa a ambos p oblemas y ues solución de (QP), en onces ambién lo es de 3.26.
3.2. MÉTODOS DE DIRECCIONES FACTIBLES 59
Veamos aho a el segundo esul ado, sea uun pun o admisible pa a el p oblema (QP)
que e i ica las condiciones KKT pa a 3.26 con sus co espondien es mul iplicado es de
Lag ange cumpliendo 3.27, se iene que,
Qu −c+ETλ+X
i∈I(u)
µiai
T=0
µi(aiu−bi)=0 yµi≥0∀i∈I(u)
po lo que de iniendo µi= 0 pa a i∈ {1, . . . , m} I(u), se ob ienen inmedia amen e las
condiciones KKT pa a el p oblema (QP).
Una ez in oducido es e esul ado, se puede de alla la idea en la que se basa el
algo i mo. Cen ándose en ella, pa iendo de un pun o inicial ac ible, se desa olla un
p oceso i e a i o, que en cada i e ación, esuel e un subp oblema de ipo (QPig).
En onces, sea u(0) un i e an e inicial ac ible. A pa i de aquí, en cada k-i e ación,
se calcula el conjun o de índices de las es icciones de desigualdad ac i as, es deci , Ik=
I(u(k))⊂ {1, . . . , m}. En onces, se de inen los alo es,
d(k)= −u(k)c(k)=c−Qu(k)g(k)=1
2(u(k))TQu(k)−cTu(k)
que se u ilizan pa a simpli ica la no ación al hace el siguien e calculo,
JQP ( ) = JQP (u(k)+d(k)) = 1
2(d(k))TQd(k)−(c(k))Td(k)+g(k)
y eniendo en cuen a que g(k)es una cons an e, se de ine el siguien e k-subp oblema:
m´ın
d(k)∈Rn
1
2(d(k))TQd(k)−(c(k))Td(k)
Suje o a:
Ed(k)=0
aid(k)= 0 i∈I(u(k))
(3.28)
Si en el mínimo de dicho subp oblema (al que se deno a á po ˜
d(k)) es el ec o nulo,
en onces dicho alo iene que cumpli las condición es aciona ia de las condiciones KKT.
Así, se iene que −c(k)+ETλ+Pi∈Ikaiµi=0, lo que implica que u(k)cumple la condición
es aciona ia del p oblema o iginal (QP). Así, si además e i ica 3.27, en onces ambién se á
un pun o KKT del p oblema 3.26, y en consecuencia del p oblema inicial (QP). En caso
con a io, se educi á el conjun o Ikeliminando el índice ik al que µik<0, es deci ,
Ik+1 =Ik {ik}. En es e caso, cuando puede que haya a ios índices de dicho modo, se
pod ía p ocede omando el ikco espondien e a:
µik= m´ın
i∈Ik
µ(k)
i<0
µ(k)
i(3.29)

60 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS
Po o a pa e, si ˜
d(k)6=0, en onces se de ine un nue o i e an e como u(k+1) =u(k)+
αk˜
d(k)pa a un αk∈[0,1] de al mane a que u(k+1) sea un pun o ac ible, po lo que el
p oblema en es e pun o es encon a el αkque cumple dicha p opiedad. Es o es posible
dado que ˜
d(k)es una di ección ac ible. Pues bien, como ˜
d(k)cumple las es icciones del
k-p oblema 3.28, omando αk= 1 se cumplen las es icciones del p oblema (QP)que
ienen p esencia en el subp oblema 3.28, es deci :
E(u(k)+˜
d(k)) = Eu(k)+E˜
d(k)=0
aiu(k+1) =aiu(k)+ai˜
d(k)=aiu(k)≤bii∈I(u(k))
De modo que, bas a cons a a la p opiedad pa a las es icciones de inidas po las ilas
i-ésimas de A ales que i /∈I(u(k)). Pues bien, conside ando po un lado el caso ai˜
d(k)≤0
pa a algún i /∈I(u(k)),
aiu(k+1) =aiu(k)+αkai˜
d(k)≤aiu(k)≤bi
po lo que es e caso no in luye, pe o si ai˜
d(k)>0, en onces,
aiu(k+1) =aiu(k)+αkai˜
d(k)≤bi⇔αk=bi−aiu(k)
ai˜
d(k)
de modo que, pa a asegu a la ac ibilidad de u(k+1) se oma:
αk= m´ın 








1,m´ın
i /∈I(u(k))
ai˜
d(k)>0
bi−aiu(k)
ai˜
d(k)









Es impo an e llegado es e pun o, pensa en el conjun o Ik+1 e e en e al nue o i e an e
u(k+1). En onces, si αk<1, se iene que po la o ma en la que se ha omado αkexis e al
menos un i /∈Ik al que,
aiu(k+1) =aiu(k)+αk˜
d(k)=bi
po lo que Ik+1 =Ik∪{i}. Sin emba go, si αk= 1, en onces Ik+1 =Ikya que lo an e io
no sucede ía. Y llegado a es e pun o, se es á en condiciones de plan ea un algo i mo que
pe mi a esol e el p oblema (QP).
Algo i mo 3.31 (Mé odo de los conjun os ac i os).Se p ocede a a és de los siguien es
pasos:
paso 0: Se apo a un u(0) ∈Sy se calcula I0,k= 0.
paso 1: Se ob iene d(k)como la solución al k-subp oblema 3.28. En onces:
Si d(k)6=0, se pasa al paso 2.
3.2. MÉTODOS DE DIRECCIONES FACTIBLES 61
En caso con a io, se comp ueba la condición (3.27), que en caso de cumpli se, se pa a
el algo i mo, y en caso con a io, se calcula el índice ikque no cumple la p opiedad de la
o ma desc i a en (3.29), se de ine Ik+1 =Ik {ik},u(k+1) =u(k)y se pasa al paso 3.
paso 2: Se calcula αky se oma u(k+1) =u(k)+αkd(k). Además, si αk= 1, en onces se
pasa al paso 3, y en caso con a io, se calcula Ik+1 =I(u(k+1))y se uel e al paso 1.
paso 3: Se oma Ik+1 =Ik,k=k+ 1 y se uel e al paso 1.
Obse ación 3.32.Pa a implemen a es e mé odo, es necesa io apo a un pun o inicial
ac ible. Es e hecho, puede esul a edioso en algunos casos. Sin emba go, en MATLAB,
exis en cie os comandos que al combina los apo an cie os mé odos pa a la ob ención de
un pun o inicial ac ible. Una p opues a en es e sen ido, se puede consul a en el Anexo II.
Finalmen e, pa a e mina con el es udio del mé odo, se in oduce un esul ado de
con e gencia del algo i mo plan eado.
Teo ema 3.33. Si pa a odo k, los ec o es ejcon j= 1, . . . , p yaicon i∈I(u(k))son
linealmen e independien es, en onces la sucesión gene ada po el algo i mo (3.31) con e ge
a la solución del p oblema (QP)en un núme o ini o de i e aciones, o bien, el p oblema
(QP)no iene mínimo ini o.
Demos ación. Se puede consul a en el eo ema 9.4.4 de [15, pág 434].
Sin emba go, pa a pode aplica el algo i mo 3.31, es necesa io pode esol e los sub-
p oblemas cuad á icos suje os a es icciones a ines de igualdad (al que se deno a á po
(QPig)).
Pa a ello, pa iendo de un p oblema gené ico (QPig), se supone que ang(E) = p<n
y que las ilas de Eson linealmen e independien es. Pues bien, si no lo son, o bien el
sis ema es incompa ible y po an o no hay elemen os ac ibles, o bien hay es icciones
edundan es.
En el caso p=n, sólo exis e un pun o admisible, po lo que es i ial. En caso con a io,
p<ny se oma Zuna ma iz que iene po columnas una base del ke (E). Aho a bien,
dado un elemen o ac ible u(0) cualquie a, la esolución del p oblema (QPig)es equi alen e
al p oblema:
m´ınd∈RnJQP (u(0) +d)
Suje o a:
Ed =0
(3.30)
La es icción sob e d, hace que es e elemen o pe enezca al ke (E), po lo que debe
exis i un elemen o y∈Rn−p al que d=Zy. Po consiguien e, el p oblema 3.30 se
62 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS
eesc ibe como,
m´ın
y∈Rn−pJQP (u(0) +Zy) = 1
2yTQZy−cZ
Ty+JQP (u(0))(3.31)
donde QZ=ZTQZ ycZ=ZTc−Qu(0). Pe o dado que JQP (u(0))es una cons an e,
la solución al p oblema 3.31 es la misma que al del p oblema cuad á ico sin es icciones:
m´ın
y∈Rn−p
1
2yTQZy−cZ
Ty(3.32)
Así, una ez ob enida la solución al p oblema 3.32 (a la que se deno a á po ˜
d), la solución
al p oblema o iginal (QPig), se á u=u(0) +Z˜
d.
Obse ación 3.34.En es e abajo, se ha op ado po es a p opues a pa a esol e el p oble-
ma (QPig)dado que se adecua al con ex o y los con enidos in oducidos con an e io idad.
Sin emba go, se pod ía consul a [23, Cap. 3] pa a e o os pun os de is a o [18, págs.
86-88] donde se aplica el Lag angiano aumen ado is o en 3.1.3 al p oblema (QPig).
3.3. Mé odos SQP
Uno de los mé odos más ac uales, son los SQP (del inglés sequen ial quad a ic p og am-
ming), el cuál consis e en educi el p oblema (Q)a una se ie de p oblemas cuad á icos
(QP)con es icciones lineales, de al mane a que la sucesión de soluciones de es a se ie de
p oblemas con e ja a la solución del p oblema inicial. A con inuación, se p esen a án dos
p opues as básicas y su deducción. Sin emba go, se omi i án aspec os de la con e gencia
debido a que és a se desma ca del con ex o del abajo, ya que pa a su demos ación se
debe usa aspec os muy especí icos de dichos mé odos, pe o se apo a án e e encias donde
se discu en dichos aspec os.
3.3.1. Mé odo de Lag ange-New on
Un p ime mé odo SQP, es el conocido con el nomb e de Lag ange-New on que esuel e
p oblemas del ipo (Qig).
Pa a su deducción, eco dando lo is o en la sección 2.3, una condición necesa ia pa a
que un pun o u∈Rnsea un pun o KKT, es la exis encia de un ec o λ∈Rpde al o ma
que:
(∇ L(u,λ) = ∇J(u) + Φ0(u)Tλ=0
∇λL(u,λ) = Φ(u) = 0⇔ ∇L(u,λ) = 0
Pa a esol e es e sis ema no lineal, se puede pa i de un pun o inicial (u(0),λ(0))∈
Rn×Rp(p óximo a la solución (u,λ)si es posible) pa a esol e lo median e el mé odo
3.3. MÉTODOS SQP 63
de New on-Raphson. De modo que aplicando dicho p ocedimien o, pa a una k-i e ación
cualquie a, se sa is ace,
H L(u(k),λ(k)) Φ0(u(k))T
Φ0(u(k)) 0 ! ∆u(k)
∆λ(k)!=− ∇J(u(k)) + Φ0(u(k))Tλ(k)
Φ(u(k))!
donde H L(u(k),λ(k))deno a la ma iz hessiana del Lag angiano espec o de la a iable ,
∆u(k)=u(k+1) −u(k)y∆λ(k)=λ(k+1) −λ(k). Aho a bien, la esolución de dicho sis ema,
apo a un pun o KKT pa a el siguien e p oblema cuad á ico:
m´ın
d(k)∈Rn
1
2d(k)TH Lu(k),λ(k)d(k)+∇ Lu(k),λ(k)Td(k)
Suje o a:
Φ0u(k)d(k)+ Φ u(k)=0
(3.33)
Así, si se deno a po ¯
d(k)la solución del p oblema 3.33 y a ¯
λ(k)sus mul iplicado es
de Lag ange asociados, se pod ía ac ualiza cada i e an e como u(k+1) =u(k)+¯
d(k)y
λ(k+1) =λ(k)+¯
λ(k). Sin emba go, es o es muy cos oso debido al cálculo de la Hessiana en
cada i e ación.
Po ello, se ecu e a una ap oximación de la Hessiana como en la sección 1.5.5. Pe o
en es e caso, no se desea ap oxima la in e sa de la Hessiana, sino la Hessiana en sí. Con
es e obje i o, en [13, págs 536-538], se p opone una ac ualización de la Hessiana pa iendo
de una ma iz de inida posi i a, que ha esul ado muy sa is ac o ia lle ada a la p ác ica.
En ella, deno ando po Bkla ap oximación de la ma iz Hessiana en la k-i e ación, iene
dada po ,
Bk+1 =Bk−Bks(k)s(k)TBk
s(k)TBks(k)+ (k) (k)T
s(k)T (k)(3.34)
donde (k)=θky(k)+ (1 −θk)Bks(k)ys(k),y(k)se de inen como en 1.5.5 y θk iene dado
po :
θk=(1si s(k)Ty(k)≥0,2s(k)TBks(k)
(0,8s(k)TBks(k))/(s(k)TBks(k)−s(k)Ty(k))si s(k)Ty(k)<0,2s(k)Bks(k)
Sin emba go, la con e gencia del mé odo p esen ado has a el momen o, no es a ase-
gu ada. Según el azonamien o plan eado, se espe a que u(k+1),λ(k+1)sea un mejo
ap oximado de la solución (u,λ), que u(k),λ(k). Sin emba go, al igual que sucedía en
1.5.4, és o no iene que se cie o a p io i. Pa a asegu a que es e echo sea así, se ecu e
a lo que se conoce como una unción de mé i o. És a, in oluc a comunmen e al uncional
obje i o y la can idad de in ac ibilidad de las es icciones, ya que si el i e an e k+1-ésimo
70 CAPÍTULO 3. OPTIMIZACIÓN CON RESTRICCIONES, MÉTODOS

Anexos
71
Anexo I: Pseudocódigos de
op imización sin es icciones
1J ( ) , g ad_J ( ) ,u , d , a , b , o l ←% Elemen os a apo a
2phi=@( ) J (u+ . ∗d) ; % D e i ni ci o n de la uncion phi ( )
3de _phi=@( )d ’∗g ad_J (u+ ∗d) ; % D e i ni c i o n de la de i ada de phi ( )
4while (abs (b−a ) > o l )
5i (abs( de _phi ( alpha ) ) < 10∗eps)
6 e u n % Se oma como s o l u c i o n alpha
7e l s e i ( de _phi ( alpha ) > 0)
8b=alpha ; % Se modi ica e l ex emo i zq ui e do
9e l s e i ( de _phi ( alpha ) < 0)
10 a=alpha ; % Se modi ica e l ex emo de echo del
in e alo
11 end
12 alpha=(a+b) /2;
13 end
Lis ing 1: Pseudocódigo dico omia con de i adas
1J ( ) ,u , d , a , b , o l ←% Elemen os a apo a
2phi=@( ) J (u+ ∗di ) ; % D e in i ci on de l a uncion phi ( )
3c=(a+b) /2; % Se oma e l pun o medio d el i n e a l o
4while (abs (b−a ) > o l )
5d=(a+c ) /2; e=(c+b) /2;
6phic=phi ( c ) ; % E alucion de phi en c
7i ( phi (d) < phic )
8b=c ; c=d ;
9e l s e i ( phi ( e ) < phic )
10 a=c ; c=e ;
11 e l s e
12 a=d ; b=e ;
13 end
14 end
73
74 ANEXO I: PSEUDOCÓDIGOS DE OPTIMIZACIÓN SIN RESTRICCIONES
15 alpha=(a+b) /2; % Se oma alpha como s ol uc io n
Lis ing 2: Pseudocódigo dico omia sin de i adas
1J ( ) , g ad_J ( ) ,u , d , alpha , ampli icado , i max ←% Elemen os a apo a
2phi=@( ) J (u+ ∗d) ; % D e i ni ci o n de l a uncion phi .
3de _phi=@( )d ’∗g ad_J (u+ ∗d) ; % D e i ni ci o n de l a de i ada de phi .
4phi0=phi (0) ; de _phi0=de _phi (0) ; % E aluacion de phi y de _phi en 0.
5alpha_min=0; % Se oma un al o i n i c i a l pa a el alo minimo de alpha .
6% Se i n i c i a la busqueda de un alpha_max que cumpla CPG:
7in = a l s e ; k=0;
8while (~ in && (k <= i max ) )
9phi_alpha=phi ( alpha ) ; % E aluacion de phi en alpha
10 de _phi_alpha=de _phi ( alpha ) ; % E aluacion de l a de i ada de phi en alpha
11 CPG=(phi_alpha > phi0+m1∗de _phi0∗alpha ) ; % C i e i o de paso g ande
12 CPP=(de _phi_alpha < m2∗de _phi0 ) && (~CPG) ; % C i e i o de paso pequeno
13 k=k+1;
14 i CPG % Se cumple e l CPG
15 alpha_max=alpha ;
16 in = ue ;
17 e l s e i CPP % Se cumple e l CPP
18 alpha_min=alpha ;
19 alpha=alpha∗ampli icado ; % Se aumen a e l alpha ( a mpl i ic ad o > 1)
20 e l s e % El paso es admisible
21 alpha ←% Se oma alpha como s ol uc io n
22 e u n ;% Se i n a l i z a con e xi o
23 end
24 end
Lis ing 3: Pseudocódigo de búsqueda del in e alo de implemen ación c i e ios de ipo CPP
y CPG
1J ( ) , g ad_J ( ) ,u0 , del a , i max ←% Elemen os a apo a
2k=0;
3% Se e a l i z a una i e a c i o n del me odo .
4d←% Se oma una d i e c c i o n de descenso .
5alpha ←% Se c a l c u l a e l paso .
6u=u0+alpha ∗d ; k=k+1;
7% Se p ocede con un p oceso i e a i o :
8while (no m(u−u0 , 2 ) /(1+no m(u , 2 ) ) > d el a ) | | (no m( g ad_J (u ) , I n ) > d e l a )
& (k < i max )
9u0=u ;
10 d←% Se oma una d i e c c i o n de descenso .
11 alpha ←% Se c a l c u l a e l paso .
12 u=u0+alpha ∗d ; k=k+1; % Se e a l i z a n l a s a c u a l i z a c i o n e s p e i ne n e s .
75
13 end
Lis ing 4: Pseudocódigo del algo i mo gené ico de esolución
1J ( ) , g ad_J ( ) ,u0 , d ,m, ol , i max ←% Elemen os a apo a
2k=0;
3n=leng h( u0 ) ; % Dimension del p oblema .
4% R ea liz ac io n de una i e a c c i o n del algo i mo :
5g ad1=g ad_J ( u0 ) ; % E aluacion del g andien e en u0 .
6H0=eye (n) ; % Ma iz i n i c i a l d e in i d a p o s i i a .
7d=−H0∗g ad1 ; % Ob encion de l a d i e c c i o n .
8alpha ←% Se l la ma i a a una unc io n que c a l c u l e e l paso
9u=u0+alpha ∗d ; g ad2=g ad_J ( u) ; s=u−u0 ; y=g ad2−g ad1 ; k=k+1;
10 u0=u ; g ad1=g ad2 ;
11 % Se empieza e l p oceso i e a i o :
12 while (( no m( g ad2 , I n ) > o l ) | | (no m( s ( : , end ) , I n ) > o l ) )
13 gamma=(s ( : , end ) ’∗y ( : , end ) ) /(y ( : , end ) ’∗y ( : , end ) ) ;
14 H0=gamma∗eye (n) ;
15 q=g ad_J ( u0 ) ; a l a = [ ] ;
16 o j=k−1:−1:k−s i z e ( s , 2 )
17 i=j+1+s i z e ( s , 2 )−k ;
18 =1/(y ( : , i ) ’∗s ( : , i ) ) ∗s ( : , i ) ’∗q ;
19 a l a =[ ; a l a ] ;
20 q=q− ∗y ( : , i ) ;
21 end
22 =H0∗q ;
23 o j=k−s i z e ( s , 2 ) : k−1
24 i=j+1+s i z e ( s , 2 )−k ;
25 be a=1/(y ( : , i ) ’∗s ( : , i ) ) ∗y ( : , i ) ’∗ ;
26 = +s ( : , i ) ∗( a l a ( i )−be a) ;
27 end
28 d=− ;
29 % Comp obacion de la d i e c c i o n de desc ens o :
30 i (d ’ ∗g ad1 > 0)
31 d=−d ;
32 end
33 alpha ←% Se l la ma i a a una unc io n que c a l c u l e e l paso
34 u=u0+alpha ∗d ; g ad2=g ad_J ( u) ;
35 i (k > m)
36 s ( : , 1 ) = [ ] ; s =[ s u−u0 ] ;
37 y ( : , 1 ) = [ ] ; y=[y g ad2−g ad1 ] ;
38 e l s e
39 s =[u−u0 s ] ;
40 y=[g ad2−g ad1 y ] ;
41 end

76 ANEXO I: PSEUDOCÓDIGOS DE OPTIMIZACIÓN SIN RESTRICCIONES
42 k=k+1; u0=u ; g ad1=g ad2 ; % Ac ual iza cion de i e a n e s .
43 end
44 u←% Se oma u como so lu ci on ob enida .
Lis ing 5: Pseudocódigo del mé odo Cuasi-New on con cos e educido B.F.G.S
Anexo II: Pseudocódigos de
op imización con es icciones
1u , d , ampli icado , con accion , i max ←% Elemen os a apo a
2% Se i n i c i a l i z a l a busqueda de un i n e a l o en e l que a p l i c a e l alg o i mo .
3a=0; b=1; k=0;
4i (u+b∗d∈S)
5while (u+ampli icado ∗b∗d∈S) && (k < i max )
6b=ampli icado ∗b ; % Se a mp li i ca e l i n e a l o ( am pl i i ca do > 1)
7k=k+1;
8end
9e l s e
10 b=con accion∗b ;
11 while ~(u+con accion∗b∗d∈S)
12 b=con accion∗b ; % Se con ae e l i n e a l o ( c on ac ci on ∈(0 ,1) )
13 end
14 end
Lis ing 6: Pseudocódigo de búsqueda del in e alo donde calcula el paso
1% Resolucion del p oblema de p og amacion l i n e a l :
2% Min un ’ x , Suje o a : Ax <= 0 y x>=0
3% Calculo de una s ol uc io n ba s i ca a c i b l e de i n i c i o :
4[ , c]= s i z e (A) ; % Dimensiones de la ma iz de e s i c c i o n e s
5 un =[ un ; ze os ( , 1 ) ] ; % Re e sc i u a del ec o que de sc i be e l un ci on al
6A=[A eye ( ) ] ; % Re e sc i u a de la ma iz de e s i c c i o n e s
7B=eye( ) ; xB=b ; IB=c+1: s i z e (A, 2 ) ; % Se oma una s ol uc io n basica a c i b l e
8xN=z e o s ( c , 1 ) ; IN=1:c ; % Se de i n e la sol uc i o n complemen a ia
9x=[xN ; xB ] ; I =1: s i z e (A, 2 ) ;
10
11 % Se comienza con e l p oceso i e a i o :
12 o i e =1:i max
13 % Paso 1 :
14 lambda=B’ un ( IB ) ;
15 c = un ( IN)−(lambda ’∗A( : , IN) ) ’ ;
77
78 ANEXO II: PSEUDOCÓDIGOS DE OPTIMIZACIÓN CON RESTRICCIONES
16 i ( c >= 0)
17 b eak
18 end
19 % Paso 2 : De e mina l a columna de pi o a ci on :
20 [ c q , q]=min( c ) ;
21 y=B A( : , IN( q) ) ;
22 i (y <= 0)
23 p in (’ El p oblema es i l i m i a d o n ’ ) ;
24 x = [ ] ; z = [ ] ; ←% Se oman s o l u c i o n e s ac ia s
25 e u n ←% Se e mina
26 end
27 % Paso 3 : De e mina l a i l a de pi o a cio n . A n a l i s i s de Ra ios :
28 w=xB./ y ; k= ind( y <= 0) ; w(k )=I n ;
29 [ he a , p]=min(w) ;
30 % Paso 4 : Pi o acion :
31 x(IN( q) )= he a ;
32 x ( IB )=x ( IB )− he a∗y ;
33 ep=z e os ( , 1 ) ; ep ( p) =1;
34 B=B+(A( : , IN( q) )−B( : , p ) ) ∗ep ’ ;
35 l=IB ( p) ; IB (p )=IN ( q ) ; xB=x ( IB ) ;
36 IN( q)=l ;
37 end
38 x=x ( 1 : c ) ; ←% Se ex aen l a s componen es que son s o lu c io n
39 z= un ( 1 : c ) ’∗x ; ←% Se c a l c u l a e l a lo d el u n c io n a l en la s o l u ci o n
Lis ing 7: Código mé odo Símplex
1K=E; k= ; q= ank (K) ; % Se i n i c i a la ma iz K y e l ec o k con l a s
e s i c c i o n e s de igualdad
2% Se adie en la s e s i c c i o n e s de desigualdad que son linealmen e
in dependien es con l a s que es an almacenadas en K
3 o i =1: leng h(b)
4i ( ank ( [K;A( i , : ) ] ) ~= q )
5K=[K;A( i , : ) ] ;
6k=[k ; b( i ) ] ;
7q=q+1;
8end
9end
10 % Se comple a K con e l esp ac io o ogon al de K
11 i (q < leng h( c ) )
12 K=[K; n u l l (K) ’ ] ;
13 k=[k ; ze os(leng h(c)−q , 1 ) ] ;
14 end
15 u=K k ; % Se oma como pun o i n i c i a l a c i b l e e l que es u l e e l sis ema
Lis ing 8: Ejemplo búsqueda de pun o inicial ac ible en el mé odo de conjun os ac i os
Bibliog a ía
[1] T.M. Apos ol, Análisis ma emá ico, Re e é S.A (1960)
[2] S.I.Bi bil, J.B.G.F ank, G.J.S ill, An eleme a y p oo o he F i z-John
and Ka ush-Kuhn-Tucke condi ions in nonlinea p og amming, The Eu-
opean Jou nal o Ope a ional Resea ch, (2006). Se puede consul a en:
h p:// esea ch.sabanciuni .edu/177/1/3011800000548.pd
[3] D.P.Be sekas, Cons ained op imiza ion and Lag ange mul iplie me hods,Academic
P ess (1982)
[4] J.V.Tiel, Con ex Analysis, An In oduc ion Tex , John Wiley and Sons (1984)
[5] E. Cas illo, J. Conejo, P. Ped egal, R. Ga cía, N. Alguacil, Fo mulación y esolución de
modelos de p og amación ma emá ica en ingenie ía y ciencia, Uni e sidad de Cas illa-
La Mancha (2012)
[6] B.Casas, G. Fies as Janei o, I. Ga cía Ju ado, J. González Díaz, In oducción a la
Teo ía de Juegos, USC edi o a, (2012)
[7] J. M. Viaño, M. B ugue a, Lecciones de Mé odos Numé icos. Volumen 4: Op imiza-
ción, Anda i a (2013)
[8] S.G.Nash, A.So e , Linea and Nonlinea P og amming, McG aw-Hill (1996)
[9] K.Sydsae e , P.Hammond, Ma emá icas pa a el análisis económico, P e ince Hall
(1996)
[10] D.P.Be sekas, Nonlinea P og amming, A hena Scien i ic (1995)
[11] M.S. Baza aa, C.M. She y, Nonlinea P og amming. Theo y and algo i hms, John
Whiley and sons (1979)
[12] G. Allai e, A. C aig, Nume ical Analysis and Op imiza ion. An in oduc ion o Ma -
hema ical Modelling and Nume ical Simula ion, Ox o d Uni e si y p ess (2007)
79