Métodos numéricos en optimización

T aballo Fin de G ao
Mé odos numé icos en op imización
Cheyenne Amo oso Sanmiguel
2019/2020
UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
GRAO DE MATEMÁTICAS
T aballo Fin de G ao
Mé odos numé icos en op imización
Cheyenne Amo oso Sanmiguel
Julio 2020
UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
T abajo p opues o
Á ea de Coñecemen o: Ma emá ica Aplicada
Tí ulo: Mé odos numé icos en op imización
B e e desc ición do con ido
Implemen ación de mé odos numé icos de op imización con y sin es-
icciones u ilizando Py hon. Compa ación con mé odos de lib e ías
de código lib e.
Recomendacións
Buenas capacidades de p og amación.
iii

Índice gene al
Resumen
iii
In oducción
xi
1. Mé odos de numé icos 1
1.1. Mé ododeGauss-New on ............................ 3
1.1.1. Desc ipción y p opiedades . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2. Implemen ación del mé odo de Gauss-New on . . . . . . . . . . . . . 6
1.2. Mé odo de Gauss-New on amo iguado . . . . . . . . . . . . . . . . . . . . . 6
1.2.1. Implemen ación del mé odo de Gauss-New on amo iguado . . . . . 7
1.3. Mé odo de Le enbe g-Ma qua d . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1. Desc ipción y p opiedades . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.2. Implemen ación.............................. 10
1.4. Mé odos Quasi-New on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.1. Mé odoDogbox.............................. 14
1.4.2. Mé odoNL2SOL............................. 17
2. Resul ados numé icos 21
2.1. Desc ipción de los p oblemas . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.1. Tes 1:Gauss1 .............................. 22
2.1.2. Tes 2:Hahn1............................... 23
2.1.3. Tes 3:Benne 5 ............................. 24
2.2. Resul adosob enidos............................... 26
2.2.1. Resul ados Tes 1: Gauss1 . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.2. Resul ados Tes 2: Hahn1 . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.3. Resul ados Tes 3: Benne 5 . . . . . . . . . . . . . . . . . . . . . . . 31
3. Conclusiones 35
i
ÍNDICE GENERAL
A. Concep os básicos 37
B. Quasi-New on 39
B.1.Mé ododeBe s ................................. 40
B.2. Mé odo de Ba holomew-Biggs . . . . . . . . . . . . . . . . . . . . . . . . . 40
B.3.Mé ododeFle che -Xu.............................. 41
C. Código Py hon 45
C.1.Gauss-New on................................... 45
C.2. Gauss-New on amo iguado . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Bibliog a ía 49
xi
INTRODUCCIÓN
mane a:
m´ın
θ∈Rn (θ) = m´ın
θ∈Rn
1
2 (θ)T (θ) = m´ın
θ∈Rn
1
2
m
X
i=1
[ i(θ)]2, m ≥n,
siendo
i(θ) = yi−h(xi,θ)
,
i:Rn→R
.
La in e p e ación geomé ica que podemos da a es e ipo de p oblemas es encon a
un pun o en la supe cie
z= (ω)
en
Rm
lo más p óximo posible al o igen. En el caso de
la eg esión conside amos la supe cie
z= (h(x1,θ), ..., h(xm,θ)) ∈Rm
.
El abajo se es uc u a en dos capí ulos como sigue: en el Capí ulo 1 es udia emos los
aspec os más ele an es de algo i mos u ilizados en el p oblema gene al de es imación de
pa áme os. Pa a ello nos guia emos p incipalmen e po Sun y Yuan (2006), Bjo ck (1996)
y Gill e al. (1981). En el Capí ulo 2 se mos a á el desempeño de los algo i mos sob e una
base de da os omada de Shen e al. (2013), ealizándose una compa ación de los dis in os
mé odos explicados y las dis in as implemen aciones de cada uno de ellos. Los cálculos
y la p og amación se lle a án a cabo a a és de
Py hon
median e las biblio ecas lib es
Vi anen e al. (2020), an de Wal e al. (2011) y Hun e (2007). Se inclui án además
es apéndices, en el p ime o de ellos encon a emos una se ie de concep os básicos pa a
una mejo comp ensión de lo expues o en el p ime capí ulo. En el segundo se mos a án
algunos mé odos más gene ales pa a la esolución del p oblema expues o. Finalmen e, se
inclui á en un e ce apéndice el código implemen ado po la au o a de es e abajo pa a
aquellos mé odos que no ue a posible encon a p og amado en ninguna biblio eca de
Py hon
.

Capí ulo 1
Mé odos de numé icos
En es e capí ulo es udia emos di e en es mé odos numé icos en op imización pa a p o-
blemas de suma de cuad ados de unciones no lineales. Los algo i mos pa a la op imización
no lineal sin es icciones con múl iples a iables se pueden clasica en los siguien es es
g upos:
1. Búsqueda sin el uso de de i adas. Ejemplos de es o son el mé odo simplex, el algo-
i mo de Hooke y Jee es, el mé odo de Rosenb ock y el mé odo de las di ecciones
conjugadas.
2. Búsqueda usando in o mación de la de i ada p ime a. En es e caso enemos el mé odo
de máximo descenso, el mé odo del g adien e conjugado y los mé odos quasi-New on.
3. Búsqueda usando in o mación de la de i ada segunda como, po ejemplo, el mé odo
de New on.
A lo la go de es e capí ulo asumi emos que las componen es
i(ω)
son de clase dos.
Deno a emos al jacobiano de
(ω)
po
J(ω)∈Rm×n
donde
J(ω)ij =∂ i(ω)
∂ωj
(1.1)
y a las ma ices Hessianas de
i(ω)
son
Gi(ω)∈Rn×n
, donde
Gi(ω)jk =∂2 i(ω)
∂ωj∂ωk
, i = 1, ..., m.
(1.2)
Po o a pa e, el g adien e de
(ω)
se deno a á con
∇ (ω) =
m
X
i=1
i(ω)∇ i(ω) = J(ω)T (ω),
(1.3)
1
2
CAPÍTULO 1. MÉTODOS DE NUMÉRICOS
y su Hessiana con
∇2 (ω) =
m
X
i=1
(∇ i(ω)∇ i(ω)T+ i(ω)∇2 i(ω)) = J(ω)TJ(ω) + S(ω),
(1.4)
donde
S(ω) =
m
X
i=1
i(ω)∇2 i(ω).
(1.5)
Exis en dos o mas de e el p oblema (4). La p ime a de ellas, como ya mencionábamos
en la in oducción, es in e p e a lo como la esolución de un sis ema sob ede e minado de
m
ecuaciones no lineales
i(ω)=0, i = 1, ..., m.
En es e caso podemos ap oxima
(ω)
po un modelo lineal cen ado en un pun o dado,
ωk
,
˜ k(ω) = (ωk) + J(ωk)(ω−ωk).
(1.6)
Cuando
m > n
enemos el sis ema sob ede e minado
k(ω) = 0
, el cual podemos esol e
como un p oblema de mínimos cuad ados lineal pa a así ap oxima una solución.
La segunda o ma de e es e p oblema es a a lo como un caso especial de op imiza-
ción en
Rn
. Pa a ello empleamos un modelo cuad á ico en o no a
ωk
qk(ω) = (ωk) + ∇ (ωk)T(ω−ωk) + 1
2(ω−ωk)T∇2 (ωk)(ω−ωk).
(1.7)
Haciendo uso de las ecuaciones (1.3) y (1.4) llegamos a la siguien e exp esión
qk(ω) = 1
2 (ωk)T (ωk)+(J(ωk)T (ωk))T(ω−ωk)+1
2(ω−ωk)T(J(ωk)TJ(ωk)+S(ωk))(ω−ωk).
(1.8)
Empleando el mé odo de New on, el mínimo de la unción
qk
se puede calcula de la o ma
ωk+1 =ωk−(J(ωk)TJ(ωk) + S(ωk))−1J(ωk)T (ωk),
(1.9)
el cual con e ge localmen e de o ma cuad á ica.
El p incipal p oblema de es e mé odo es que al calcula las
mn2
de i adas segundas
necesa ias pa a ob ene el é mino
S(ωk)
el cos e compu acional puede se ela i amen e
al o. Po lo an o, puede esul a ú il omi i dicho é mino. De (1.5) deducimos que cuando
i(ω), i = 1, ..., n,
es p óximo a ce o o es le emen e no lineal, en cuyo caso
∇2 i(ω)
se
ap oxima a ce o, el é mino
S(ω)
es pequeño y puede omi i se. A pa i de es e azonamien-
o se siguen los mé odos de Gauss-New on y Le enbe g-Ma qua d que a a emos más
1.1. MÉTODO DE GAUSS-NEWTON
3
en de alle a con inuación. En es e capí ulo a a emos ambién los mé odos quasi-New on
que sí u ilizan in o mación de la de i ada segunda, aunque no di ec amen e y sí median e
ap oximaciones ecu si as.
1.1. Mé odo de Gauss-New on
1.1.1. Desc ipción y p opiedades
El mé odo Gauss-New on puede pensa se de dos mane as dis in as: la p ime a de ellas es
pensa que se ob iene omi iendo el é mino de segundo g ado,
S(ω)
, en el modelo cuad á ico
(1.8). De es a o ma llegamos a la siguien e ap oximación
qG
k(ω) = 1
2 (ωk)T (ωk) + (J(ωk)T (ωk))T(ω−ωk) + 1
2(ω−ωk)TJ(ωk)TJ(ωk)(ω−ωk),
(1.10)
y aplicando el mé odo de New on a la condición necesa ia de mínimo se ob iene la solución
median e
ωk+1 =ωk−(J(ωk)TJ(ωk))−1J(ωk)T (ωk).
(1.11)
Cabe des aca que pa a que es o enga sen ido es necesa io que la ma iz
J(ωk)
sea de
ango comple o.
Como hemos explicado an e io men e, es e azonamien o se á ú il cuando
i(ω), i =
1, ..., n
, sea p óximo a ce o o le emen e no lineal. Si nos encon amos en es e caso es espe-
able que el compo amien o del mé odo sea simila al mé odo de New on dado en (1.9).
En pa icula , en el caso de que nos encon emos con un p oblema consis en e al que
(˜ω)=0
, donde
˜
ω
es solución, la elocidad de con e gencia local se á idén ica con ambos
mé odos. Sin emba go, en el caso de esiduos g andes la elocidad de con e gencia local
se á in e io en el mé odo de Gauss-New on.
La segunda o ma de pensa es e mé odo es como una se ie de ap oximaciones de
(ω)
de la o ma (1.6). Si deno amos po
sk
a la co ección de la ap oximación
ωk
, dicha
co ección se ob end á al esol e el p oblema de mínimos cuad ados
m´ın
s∈Rn
1
2|| (ωk) + J(ωk)s||2
2.
(1.12)
De es a o ma, la nue a ap oximación se á
ωk+1 =ωk+sk
.
En el caso de que la ma iz
J(ωk)
enga ango comple o la solución al p oblema lineal de
mínimos cuad ados es única y emos que coincide con la ob enida median e el azonamien o
4
CAPÍTULO 1. MÉTODOS DE NUMÉRICOS
an e io
sk=−(J(ωk)TJ(ωk))−1J(ωk)T (ωk).
(1.13)
Tenemos que
∇ (ωk)
es dis in o de ce o, po lo que deducimos que
sk
se a a de una
di ección de descenso ya que
sT
k∇ (ωk) = sT
kJ(ωk)T (ωk) = −sT
kJ(ωk)TJ(ωk)sk≤0,
(1.14)
donde la desigualdad se á es ic a si no se cumple que
J(ωk)sk= 0
. Es a úl ima igualdad
es equi alen e a
J(ωk)T (ωk) = ∇ (ωk) = 0
.
En el caso de que
J(ωk)
es é mal condicionado o sea singula ambién pod emos cal-
cula
sk
usando descomposiciones de
J(ωk)
como, po ejemplo, la ac o ización QR o la
descomposición en alo es singula es o SVD (
Singula Value Decomposi ion
). Si
J(ωk)
no
es de ango comple o podemos oma
sk
como
sk=−J(ωk)I (ωk),
(1.15)
donde
J(ωk)I
deno a la ma iz pseudo-in e sa de
J(ωk)
.
A con inuación analiza emos la con e gencia del mé odo. Pa a ello enuncia emos es
eo emas que nos pe mi i án conclui lo siguien e:
1. Si
S(˜
ω)=0
, el mé odo iene con e gencia cuad á ica.
2. Si
S(˜
ω)
es pequeño compa ado con
J(˜
ω)TJ(˜
ω)
el mé odo es localmen e Q-linealmen e
con e gen e.
3. Si
S(˜
ω)
es demasiado g ande el mé odo no con e ge á.
Teo ema 1.1.1.
Sea
:Rn−→ R, ∈ C2
. Supongamos que
˜
ω
es el mínimo local del
p oblema
(4)
y que
J(˜
ω)TJ(˜
ω)
es denida posi i a. Supongamos además que la sucesión
{ωk}
gene ada po el Algo i mo 1.1.5 con e ge a
˜
ω
. En onces, si
∇2 (ω)
y
(J(ω)TJ(ω))−1
son Lipschi zianas en un en o no de
˜
ω
, se cumple
||ωk+1 −˜
ω||2≤ ||(J(˜
ω)TJ(˜
ω))−1||2||S(˜
ω)||2||ωk−˜
ω||2+O(||ωk−˜
ω||2
2)
(1.16)
Demos ación.
Ve Sun y Yuan (2006) (p. 357-358).

1.1. MÉTODO DE GAUSS-NEWTON
5
Teo ema 1.1.2.
Sea
: Ω ⊂Rn−→ R, ∈ C2(Ω)
donde
Ω
es un conjun o con exo y
abie o. Sea
J(ω)
de Lipschi z con inua en
Ω
, es deci ,
||J(u)−J( )||2≤γ||u− ||2,∀u, ∈Ω,
(1.17)
y
||J(ω)||2≤α, ∀ω∈Ω
. Supongamos que exis en
˜
ω∈Ω
y
λ, σ ≥0
al que, si
J(˜
ω)T (˜
ω) =
0
,
λ
es el meno alo p opio de
J(˜
ω)TJ(˜
ω)
y
||(J(ω)−J(˜
ω))T (˜
ω)||2≤σ||ω−˜
ω||2,∀ω∈Ω.
(1.18)
Si
σ < λ
, en onces, pa a cualquie
c∈(1,λ
σ)
, exis e
ε > 0
al que
∀ω0∈N(˜
ω, ε)
la
secuencia gene ada po el mé odo de Gauss-New on median e el Algo i mo 1.1.5 es á bien
denida, con e ge a
˜
ω
y sa is ace
||ωk+1 −˜
ω||2≤cσ
λ||ωk−˜
ω||2+cαγ
2λ||ωk−˜
ω||2
2
||ωk+1 −˜
ω||2≤cσ +λ
2λ||ωk−˜
ω||2<||ωk−˜
ω||2.
(1.19)
Demos ación.
Ve Sun y Yuan (2006) (p. 358-359).

Teo ema 1.1.3.
Conside emos que las suposiciones del Teo ema 1.1.1 o las del Teo ema
1.19 se e ican. Si
(˜
ω) = 0
, en onces exis e
ε > 0
al que pa a cualquie
ω0∈N(˜
ω, ε)
la sucesión
{ωk}
gene ada po el mé odo de Gauss-New on con e ge de o ma cuad á ica
a
˜
ω
.
Demos ación.
Ve Sun y Yuan (2006) (p. 360).

El siguien e ejemplo (Fle che , 1980, pág. 94) mues a que el mé odo de Gauss-New on
unciona bien pa a p oblemas con esiduos pequeños. Sin emba go, cuando sean g andes o
los p oblemas sean cla amen e no lineales el mé odo no se á localmen e con e gen e.
Ejemplo 1.1.4.
Conside amos el p oblema con
m
=2 y
n
=1 dado po
1(ω) = ω+ 1, 2(ω) = λω2+ω+ 1
donde
λ
es un pa áme o cualquie a. Tenemos el siguien e p oblema esc i o de o ma es-
ánda
m´ın
ω∈Rn (ω) = m´ın
ω∈Rn
1
2
2
X
i=1
i(ω)2= m´ın
ω∈Rn
1
2[(ω+ 1)2+ (λω2+ω+ 1)2],

6
CAPÍTULO 1. MÉTODOS DE NUMÉRICOS
de mane a que
˜
ω= 0
. Llegamos a que, en es e caso pa icula ,
ωk+1 =2λ2ω3
k+λω2
k+ 2λωk
1 + (2λωk+ 1)2.
Obse amos que si
λ= 0
en onces
ω1=0=˜
ω
, lo que mues a que, cuando el p oblema
es lineal, el mé odo de Gauss-New on lo esuel e en una única i e ación. En el caso de que
λ6= 0
ωk+1 =λωk+O(||ωk||2
2).
Así, cuando
λ
es sucien emen e pequeño la con e gencia del mé odo se á lineal, mien as
que si
|λ|>1
el mé odo no se á con e gen e.
1.1.2. Implemen ación del mé odo de Gauss-New on
El mé odo p esen ado en la sección an e io no es á, bajo mi conocimien o, p og amado
en ninguna biblio eca lib e de Py hon, po lo que ha sido implemen ado po la au o a de
es e abajo. El código u ilizado podemos encon a lo en el apéndice C.1. El algo i mo
p og amado, basado en la desc ipción dada del mé odo de Gauss-New on, es el siguien e:
Algo i mo 1.1.5.
(Gauss-New on)
Paso 0. Dados
ω0
,
ε > 0
,
k:= 0
.
Paso 1. Si
||∇ (ωk)||2≤ε
, s op.
Paso 2. Cálculo de
sk
esol iendo
J(ωk)TJ(ωk)sk=−J(ωk)T (ωk).
Paso 3.
ωk+1 =ωk+sk
,
k:= k+ 1
. Vol e al Paso 1.

Como ya hemos comen ado, cabe la posibilidad de que
J(ωk)
no sea una ma iz de
ango comple o. Como solución se p opone calcula
sk
como
sk=−J(ωk)I (ωk)
donde
J(ωk)I
deno a la ma iz pseudo-in e sa de
J(ωk)
.
1.2. Mé odo de Gauss-New on amo iguado
Según los p oblemas obse ados en el ejemplo mos ado en la sección an e io , en la
p ác ica se u iliza un mé odo de Gauss-new on con búsqueda de línea o ambién llamado
mé odo de Gauss-New on amo iguado (
damped Gauss-New on
). Sea
αk
un escala y
sk
la solución de 1.12, que denomina emos di ección de Gauss-New on, el mé odo es como
sigue
ωk+1 =ωk+αksk.
(1.20)
1.2. MÉTODO DE GAUSS-NEWTON AMORTIGUADO
7
Se e ica que
sk
se man iene in a ian e an e ans o maciones lineales sob e la a iable
independien e
ω
y, como ya imos an e io men e, es una di ección de descenso.
Pa a que es a modicación del mé odo sea un algo i mo iable enemos que ene
cuidado con la elección de
αk
. Gene almen e exis en dos mane as que acili an la elección
del escala :
1. Toma
αk
como el mayo núme o de la secuencia
1,1
2,1
4, ...
al que se cumpla la
desigualdad
|| (ωk)||2
2− || (ωk+αksk)||2
2≥1
2αk||J(ωk)sk||2
2
(1.21)
2. Toma
αk
como la solución de
m´ın
α|| (ωk+αk)||2
2
(1.22)
Obse ación
1.2.1
.
El p ime mé odo explicado pa a la búsqueda de
αk
se a a básica-
men e de la egla de búsqueda de paso A mijo-Golds ein
1
, mien as que el segundo es el
cálculo del paso óp imo.
Tomando de o ma adecuada
αk
enemos que es e mé odo siemp e oma pasos de des-
censo, po lo an o es localmen e con e gen e. De hecho, se a a de un mé odo globalmen e
con e gen e en la mayo ía de los casos pe o con inúa siendo muy len o cuando el esiduo
es g ande o los p oblemas son cla amen e no lineales.
1.2.1. Implemen ación del mé odo de Gauss-New on amo iguado
Al igual que ocu ía con el mé odo de Gauss-New on es e mé odo no es á p og amado
en ninguna biblio eca lib e de Py hon, po lo que ha sido implemen ado po la au o a
de es e abajo. En el apéndice C.2 podemos encon a el código u ilizado. El algo i mo
p og amado, basado en la desc ipción dada, es el siguien e:
Algo i mo 1.2.2.
(Gauss-New on amo iguado)
Paso 0. Dados
ω0
,
ε > 0
,
k:= 0
.
Paso 1. Si
||∇ (ωk)||2≤ε
, s op.
Paso 2. Cálculo de
sk
esol iendo
J(ωk)TJ(ωk)sk=−J(ωk)T (ωk).
Paso 3. Cálculo de
αk
. Dos opciones:
1
La egla de A mijo-Golds ein sigue el esquema siguien e: (i) Se elige
> 0, β ∈(0,1), ε ∈(0,1)
.
(ii) Se oma
p= 0
y se comp ueba si se e ica
q(βp )≤q(0) + βp εq0(0)
.
(iii) Si se cumple se oma
α=βp
, en caso con a io se hace
p=p+ 1
y se uel e a (i).
8
CAPÍTULO 1. MÉTODOS DE NUMÉRICOS
1. Toma
αk= m´ax 1,1
2,1
4, ...
al que se e ique
|| (ωk)||2
2− || (ωk+αksk)||2
2≥1
2αk||J(ωk)sk||2
2
2. Toma
αk
como la solución de
m´ın
α|| (ωk+αk)||2
2
Paso 4.
ωk+1 =ωk+αksk
,
k:= k+ 1
. Vol e al Paso 1.

1.3. Mé odo de Le enbe g-Ma qua d
En la sección 1.2 eíamos que el mé odo Gauss-New on amo iguado e a globalmen e
con e gen e en la mayo ía de los casos. Sin emba go, cuando
J(ω)
no sea de ango com-
ple o es e mé odo end á dicul ades pa a abaja o el algo i mo con e ge á a un pun o
no es aciona io. Pa a soluciona es e p oblema podemos ene en cuen a las segundas de-
i adas (Sección 1.4), o bien, es abiliza el mé odo Gauss-New on amo iguado.
Pa a lle a a cabo la segunda es a egia mencionada conside amos la écnica de e-
gión de conanza (
us - egion echnique
), con la que ob enemos el mé odo de Le enbe g-
Ma qua d . Es e algo i mo ue publicado po p ime a ez po Kenne h Le enbe g, Le en-
be g (1944), y edescubie o en 1963 po Donald Ma qua d , Ma qua d (1963).
1.3.1. Desc ipción y p opiedades
El mé odo de Gauss-New on podíamos pensa lo de dos mane as dis in as: una de ellas
e a pensa lo como una se ie de ap oximaciones de
(ω)
de la o ma (1.6) ob eniendo un
p oblema lineal de mínimos cuad ados (1.12). Desa o unadamen e, es a linealización no
es e ec i a pa a odos los
(ω−ωk)
. Pa a soluciona es o empleamos la écnica de egión
de conanza y añadimos una es icción. Conside amos en onces el siguien e modelo de
egión de conanza:
m´ın
ω∈Rn
1
2|| (ωk) + J(ωk)(ω−ωk)||2
2
s.
||ω−ωk||2≤∆k,
(1.23)
1.3. MÉTODO DE LEVENBERG-MARQUARDT
9
que podemos e lo como un p oblema no lineal de mínimos cuad ados con es icciones.
Es e modelo puede eesc ibi se como
m´ın
ω∈Rn
1
2 (ωk)T (ωk) + (ωk)TJ(ωk)(ω−ωk) + 1
2(ω−ωk)TJ(ωk)TJ(ωk)(ω−ωk)
s.
||ω−ωk||2<∆k.
Deno amos
s=ω−ωk
. La solución al p oblema (1.23) se ob end á esol iendo el sis ema
(J(ωk)TJ(ωk) + µkI)s=−J(ωk)T (ωk),
(1.24)
de donde ob enemos que
ωk+1 =ωk−(J(ωk)TJ(ωk) + µkI)−1J(ωk)T (ωk).
(1.25)
El pa áme o
∆k≥0
se enca ga de con ola las i e aciones y limi a el amaño de
sk
. Nó ese
que el pa áme o
sk
es á bien denido incluso cuando
J(ωk)
no es de ango comple o. Si
se e ica que
||(J(ωk)TJ(ωk))−1J(ωk)T (ωk)||2≤∆k
en onces se cumple que
µk= 0
.
En o o caso, exis e
µk>0
al que la solución
sk
sa is ace
||sk||2= ∆k
y
(J(ωk)TJ(ωk) + µkI)sk=−J(ωk)T (ωk).
(1.26)
O a o ma de e es e mé odo es como una mezcla en e Gauss-New on y el mé odo de
descenso de g adien e (
s eepes descen me hod
), de al mane a que es e mé odo pe mi e
elegi dos di ecciones dis in as. En el caso de que
µk= 0
la di ección se ía la misma que
en el Gauss-New on, mien as que si
µk
es demasiado g ande el sis ema (1.24) se educi ía
a
µkIs=−J(ωk)T (ωk).
(1.27)
y la di ección que ob end íamos es a ía muy p óxima a la de máximo descenso.
A con inuación enuncia emos una se ie de p opiedades del mé odo Le enbe g-Ma qua d
donde deno a emos
s=s(µ)
como la solución del sis ema
(J(ω)TJ(ω) + µI)s=−J(ω)T (ω).
Teo ema 1.3.1.
Cuando
µ
aumen a de o ma monó ona desde ce o,
||s(µ)||2
dec ece á de
o ma es ic amen e monó ona.
Demos ación.
Ve Sun y Yuan (2006, pág. 363-364).

16
CAPÍTULO 1. MÉTODOS DE NUMÉRICOS
donde
b=||P C||2
||C||2∈[0,1]
. T i ialmen e
qk(s(a))
disminuye de o ma monó ona alcanzando
así un alo más bajo pa a el modelo.
Es p obable que el algo i mo exhiba una con e gencia len a cuando el ango de
J(ω)
es meno que el núme o de a iables.
Implemen ación
De la desc ipción dada del mé odo de Dogbox en la subsección an e io se sigue el
siguien e algo i mo:
Algo i mo 1.4.1.
(Dogbox)
Paso 0. Elegimos el i e an e inicial
ω0
, el pa áme o inicial de la egión de conanza
∆0
y
jamos
k:= 0
.
Paso 1. Cons uimos el modelo cuad á ico en o no a
ωk
, es deci ,
m´ın
ω∈Rn(J(ωk)T (ωk))T(ω−ωk) + 1
2(ω−ωk)TMk(ω−ωk),
s.
||ω−ωk||∞≤∆k,
Paso 2. Calculamos
sk
:
i
N=−Mk(J(ωk)T (ωk))
es ac ible
sk=N
else
i
C= (ωk)TJ(ωk)J(ωk)T (ωk)
( (ωk)TJ(ωk)BkJ(ωk)T (ωk)J(ωk)T (ωk)
es ac ible
encon a el máximo
α
al que
C+α(N−C)∈Tk
,
sk=C+α(N−C)
else
encon a el máximo
β
al que
PC ≡βC ∈Tk
y el máximo
α
al que
PC +α(N−PC)∈Tk
,
sk=PC +α(N−PC)
Paso 3. Calculamos el adio
δk= (ωk)− (ωk+sk)
qk(0)−qk(sk)
.
Paso 4. Elegimos el nue o pun o
ωk+1
:
i
δk≤0.1
ωk+1 =ωk
else
ωk+1 =ωk+sk
Paso 5. Ac ualizamos
∆k
:
i
δk<0.25
∆k+1 =||sk||2/4

1.4. MÉTODOS QUASI-NEWTON
17
else i
δk>0.75
y
||sk||2= ∆k
∆k+1 = 2∆k
else
∆k+1 = ∆k
Paso 6.
k:= k+ 1
. Vol e al Paso 1.

Al igual que ocu ía con el mé odo de Le enbe g-Ma qua d , en la biblio eca lib e
Scipy encon amos dis in os módulos que implemen an es e algo i mo. En es a memo ia
u iliza emos dos:
scipy.op imize.leas _squa es
y
scipy.op imize.cu e_
. Analiza emos su
compo amien o y lo compa a emos an o con las implemen aciones de los es an es mé-
odos desc i os en es e abajo como en e ellos.
1.4.2. Mé odo NL2SOL
La aplicación di ec a de los mé odos quasi-New on al p oblema de mínimos cuad ados
no lineales desc i o an e io men e, en ocasiones en la p ác ica, no esul an an ecien es.
Una de las azones po las que ocu e es o es que es os mé odos igno an la in o mación que
apo a
J(ωk)
, pe o a menudo
J(ωk)TJ(ωk)
es la pa e dominan e de
∇2 (ω)
. Una es a e-
gia posible es, en luga de ap oxima
∇2 (ω)
, inclui una ap oximación quasi-New on del
é mino desconocido de la segunda de i ada,
S(ω)
. Sea
Bk
la ap oximación de la ma iz
S(ωk)
, se iene en onces
(Bk+J(ωk)TJ(ωk))sk=−J(ωk)T k.
(1.44)
Dado que
S(ωk+1) =
m
X
i=1
i(ωk+1)∇2 i(ωk+1)
podemos oma
Bk+1 =
m
X
i=1
i(ωk+1)(Hi)k+1
como la ap oximación de
S(ωk+1)
, donde
(Hi)k+1
es una ap oximación de
∇2 i(ωk+1)
.
Tenemos en onces
Bk+1(ωk+1 −ωk) =
m
X
i=1
( i(ωk+1)(Hi)k+1)(ωk+1 −ωk)
=
m
X
i=1
i(ωk+1)(∇ i(ωk+1)− ∇ i(ωk))
=J(ωk+1)T (ωk+1)−J(ωk)T (ωk+1) =: yk,
(1.45)
18
CAPÍTULO 1. MÉTODOS DE NUMÉRICOS
lo cual es una condición quasi-New on impues a sob e
Bk
.
En Dennis e al. (1981) se sugie e una egla de ap oximación pa a
S(ωk)
simple, ge-
ne al y geomé ica. La idea es elegi un conjun o de ca ac e ís icas deseables pa a la
ap oximación y pos e io men e selecciona
S(ωk+1)
como el pun o ac ible más ce cano
a
S(ωk)
. Veamos en onces qué p opiedades debe e ica
S(ωk+1)
. Es azonable comen-
za con
S(ω0)=0
dado que es ba a o compu acionalmen e y, además, es lógico pensa
que
q0=qG
0
. Supongamos en onces que
S(ωk)
es á disponible. Reco damos que que emos
ap oxima
Pm
i=1 i(ω)∇2 i(ω)
, po lo an o es ob io que debe se simé ico. Dennis e al.
(1981) se basa en el siguien e esul ado pa a p opo ciona un o mula de ac ualización así
como sus p opiedades.
No ación
1.4.2
.
Sea
A∈ Mm×n(C)
, se dene la no ma de F obenius, llamada ambién
no ma de Hilbe Schmid , como
||A||F:= ( (ATA))1
2=Pm
i=1 Pn
j=1 |aij|21
2
.
Teo ema 1.4.3.
Sea
T
ksk>0
y
T∈Rn×n
una ma iz simé ica y denida posi i a al
que
TTTsk= k
donde
k=∇ (ωk+1)− ∇ (ωk).
En onces la ac ualización
Bk+1 =Bk+(yk−Bksk) T
k+ k(yk−Bksk)T
sT
k k
−(yk−Bksk)Tsk
(sT
k k)2 k T
k
(1.46)
es la única solución del p oblema de minimización
m´ın ||T−T(Bk+1 −Bk)T−1||F
s.
(Bk+1 −Bk)
simé ica
, Bk+1sk=yk.
Dennis e al. (1981) emplea on la condición quasi-New on (1.45) y la ó mula de ac ua-
lización (1.46), y p esen a on un nue o algo i mo quasi-New on con egión de conanza
que ecibe el nomb e de NL2SOL. En cada e apa es necesa io esol e el subp oblema
m´ın
ω∈Rn
1
2 (ωk)T (ωk)+(J(ωk)T (ωk))T(ω−ωk)
+1
2(ω−ωk)T(J(ωk)TJ(ωk) + Bk)(ω−ωk)
s.
||ω−ωk||2≤∆k.
(1.47)
Se cumple que, en el caso en el que el esiduo sea ce o, la ma iz
Bk
debe ía desapa ece
o, al menos, ace ca se a
0
. Sin emba go, en el algo i mo p opues o, la ac ualización (1.46) no
1.4. MÉTODOS QUASI-NEWTON
19
ga an iza que desapa ezca la ma iz
Bk
. Cuando es o ocu e, el mé odo de Gauss-New on
es supe io al NL2SOL. Además, es o puede in e e i con la con e gencia supe lineal del
mé odo.
Pa a soluciona dicho p oblema u iliza emos una modicación di ec a del au oescalado.
La idea es ac ualiza
γkBk
en luga de
Bk
pa a ob ene
Bk+1
. Podemos oma como ac o
de escalado
γk=|(ωk+1 −ωk)Tyk|
|(ωk+1 −ωk)TBk(ωk+1 −ωk)|.
(1.48)
Dado que que emos que
Bk
no sea demasiado g ande omamos
γk= m´ın |(ωk+1 −ωk)Tyk|
|(ωk+1 −ωk)TBk(ωk+1 −ωk)|,1
(1.49)
A pa i de los expe imen os numé icos eejados en Dennis e al. (1981) obse amos
que pa a p oblemas con esiduos g andes, el algo i mo quasi-New on NL2SOL es signica i-
amen e en ajoso. Sin emba go, pa a p oblemas con esiduos signica i amen e pequeños,
el endimien o de NL2SOL y del algo i mo de Le enbe g-Ma qua d implemen ado en Mo-
é (1978) es simila . En el caso de los p oblemas con esiduo nulo seguimos p e endo el
mé odo de Gauss-New on.
20
CAPÍTULO 1. MÉTODOS DE NUMÉRICOS
Capí ulo 2
Resul ados numé icos
A lo la go de es e capí ulo analiza emos el compo amien o de los algo i mos desc i os
empleando el lenguaje de p og amación in e p e ado
Py hon
1
. Como ya hemos comen a-
do, ha emos uso an o de biblio ecas lib es como SciPy, donde encon amos implemen ados
los mé odos de Le enbe g-Ma qua d y Dogbox, como de código p opio en el caso de los
algo i mos es an es.
La alidación de los algo i mos desc i os la ealiza emos median e p oblemas de dis in-
os g ados de dicul ad omados de
S a is ical Re e ence Da se s P ojec
(STRD) desa o-
llado po el
S a S a is ical Enginee ing Di ision and he Ma hema ical and Compu a ional
Sciences Di ision
del
Na ional Ins i u e o S anda ds and Techonology
(NIST), que p o-
po ciona bases de da os e e enciadas con alo es ce icados. En p ime luga , ha emos
una desc ipción de los dis in os p oblemas pa a, pos e io men e, mos a y analiza los
esul ados ob enidos.
Encon a el mejo  código es una a ea casi imposible y muy dependien e de la de-
nición de mejo . Pa a cualquie a que sea el c i e io u ilizado, el p ocedimien o de p ueba
debe in en a medi la capacidad del código pa a encon a soluciones. Los p oblemas de
mínimos cuad ados no lineales son in ínsecamen e di íciles y, gene almen e, es posible en-
con a un conjun o de da os que haga alla incluso a los códigos más obus os. Po lo
1
Se a a de un lenguaje de p og amación mul ipa adigma, ya que sopo a p og amación o ien ada a
obje os, p og amación impe a i a y, en meno medida, p og amación uncional. Es un lenguaje in e p e-
ado, dinámico y mul ipla a o ma. Se adminis a po la Py hon So wa e Founda ion y posee una licencia
de código abie o, denominada Py hon So wa e Founda ion License, que es compa ible con la Licencia
pública gene al de GNU a pa i de la e sión 2.1.1, e incompa ible en cie as e siones an e io es. En es e
abajo se ha usado la e sión 3.7.1.
21

22
CAPÍTULO 2. RESULTADOS NUMÉRICOS
an o, la mayo ía de las e aluaciones de so wa e de mínimos cuad ados no lineales ambién
deben inclui una medida de la conabilidad del código, es deci , el código debe econo-
ce co ec amen e cuándo ha encon ado una solución. Los conjun os de da os empleados
son pa icula men e adecuados pa a ales p uebas de obus ez y conabilidad. Se incluyen
p oblemas de mínimos cuad ados no lineales gene ados y del mundo eal. Los alo es
ce icados son soluciones "mejo es disponibles", ob enidas con p ecisión de 128 bi s y
con madas po , al menos, dos algo i mos y paque es de so wa e di e en es que u ilizan
de i adas analí icas.
2.1. Desc ipción de los p oblemas
En es a sección p esen a emos 3 p oblemas es o denados po g ado de dicul ad, se-
gún la clasicación del NIST. Emplea emos dichos p oblemas pa a analiza an o el buen
compo amien o de los algo i mos desc i os en el p ime capí ulo como su implemen ación.
2.1.1. Tes 1: Gauss1
Los da os empleados en es e p oblema son da os gene ados que se co esponden con
dos no males en una base de dec ecimien o exponencial con e o es no males de media
ce o y a ianza 6.25. Sea
{(xi, yi)}250
i=1
una mues a donde
xi, yi∈R
son los alo es de las
a iables explica i a y espues a, espec i amen e, co espondien es al
i
-ésimo indi iduo.
Sea
θ∈R8
el ec o de pa áme os desconocidos. Conside a emos el ajus e no lineal dado
po :
yi=h(xi,θ) + εi, εi∈N(0,6.25), i = 1, ..., 250,
donde
h(x, θ) = θ1·exp(−θ2x) + θ3·exp −(x−θ4)2
θ2
5+θ6·exp −(x−θ7)2
θ2
8.
El p oblema a esol e sigue la ó mula gene al (4):
m´ın
θ∈R8 (θ) = m´ın
θ∈R8
1
2 (θ)T (θ) = m´ın
θ∈R8
1
2
250
X
i=1
[ i(θ)]2,
siendo
i(θ) = yi−h(xi,θ)
,
i:R8→R
,
i= 1, ..., 250.
En la Figu a 2.1 ep esen amos el ajus e benchma k omando como alo es ce i-
cados
θ=
(9.8778210871e+01, 1.0497276517e-02, 1.0048990633e+02, 6.7481111276e+01,
2.1. DESCRIPCIÓN DE LOS PROBLEMAS
23
Figu a 2.1: Ajus e de Gauss1 con la unción del benchma k.
2.3129773360e+01, 7.1994503004e+01, 1.7899805021e+02, 1.8389389025e+01). Emplean-
do dichos alo es ce icados ob enemos que
RSS(θ) =
1.3158222432e+03.
Al ealiza la implemen ación de es e p oblema u iliza emos dos i e an es iniciales dis-
in os:
θ1
0= (97.0,0.009,100.0,65.0,20.0,70.0,178.0,16.5),
θ2
0= (94.0,0.0105,99.0,63.0,25.0,71.0,180.0,20.0).
2.1.2. Tes 2: Hahn1
Los da os empleados en es e p oblema son el esul ado de un es udio del NIST que
in oluc a la dila ación é mica del cob e. La a iable espues a es el coecien e de dila a-
ción é mica, y la a iable independien e es la empe a u a medida en g ados Kel in. Sea
{(xi, yi)}236
i=1
una mues a donde
xi, yi∈R
son los alo es de las a iables explica i a y
espues a, espec i amen e, co espondien es al
i
-ésimo indi iduo. Sea
θ∈R7
el ec o de
pa áme os desconocidos. Conside a emos el ajus e no lineal dado po :
yi=h(xi,θ) + εi, i = 1, ..., 236,
donde
h(x, θ) = θ1+θ2x+θ3x2+θ4x3
1 + θ5x+θ6x2+θ7x3.
24
CAPÍTULO 2. RESULTADOS NUMÉRICOS
El p oblema a esol e sigue la ó mula gene al (4):
m´ın
θ∈R7 (θ) = m´ın
θ∈R7
1
2 (θ)T (θ) = m´ın
θ∈R7
1
2
236
X
i=1
[ i(θ)]2,
siendo
i(θ) = yi−h(xi,θ)
,
i:R7→R
,
i= 1, ..., 236.
En la Figu a 2.2 ep esen amos el ajus e benchma k omando como alo es ce i-
cados
θ=
(1.0776351733e+00, -1.2269296921e-01, 4.0863750610e-03,-1.4262662514e-06, -
5.7609940901e-03, 2.4053735503e-04, -1.2314450199e-07). Empleando dichos alo es ce i-
cados ob enemos que
RSS(θ) =
1.5324382854e+00.
Figu a 2.2: Ajus e de Hahn1 con la unción del benchma k.
Al ealiza la implemen ación de es e p oblema u iliza emos dos i e an es iniciales dis-
in os:
θ1
0= (10,−1,0.05,−0.00001,−0.05,0.001,−0.000001),
θ2
0= (1,−0.1,0.005,−0.000001,−0.005,0.0001,−0.0000001).
2.1.3. Tes 3: Benne 5
Los da os empleados en es e p oblema son el esul ado de un es udio del NIST que
in oluc a el modelado de magne ización de supe conduc i idad, donde la a iable espues a
es el magne ismo, y la a iable independien e es el iempo omando como unidad de medida
2.1. DESCRIPCIÓN DE LOS PROBLEMAS
25
los minu os. Sea
{(xi, yi)}154
i=1
una mues a donde
xi, yi∈R
son los alo es de las a iables
explica i a y espues a, espec i amen e, co espondien es al
i
-ésimo indi iduo. Sea
θ∈R3
el ec o de pa áme os desconocidos. Conside a emos el ajus e no lineal dado po :
yi=h(xi,θ) + εi, i = 1, ..., 154,
donde
h(x, θ) = θ1(θ2+x)
−1
θ3.
El p oblema a esol e sigue la ó mula gene al (4):
m´ın
θ∈R3 (θ) = m´ın
θ∈R3
1
2 (θ)T (θ) = m´ın
θ∈R3
1
2
154
X
i=1
[ i(θ)]2,
siendo
i(θ) = yi−h(xi,θ)
,
i:R3→R
,
i= 1, ..., 154.
En la Figu a 2.3 ep esen amos el ajus e benchma k omando como alo es ce icados
θ= (−2.5235058043e+ 03,4.6736564644e+ 01,9.3218483193e−01)
. Empleando dichos
alo es ce icados ob enemos que
RSS(θ)=5.2404744073e−04
.
Figu a 2.3: Ajus e de Benne 5 con la unción del benchma k.
Al ealiza la implemen ación de es e p oblema u iliza emos dos i e an es iniciales dis-
in os:
θ1
0= (−2000,50,0.8),
θ2
0= (−1500,45,0.85).
32
CAPÍTULO 2. RESULTADOS NUMÉRICOS
mos que sea el más ecien e debido a que no se alcanza la solución p opues a. Po lo an o,
a la is a de los esul ados expues os, ob enemos que en e los mé odos implemen ados
que sí alcanzan los alo es ce icados el que iene un meno cos e compu acional es el
mé odo de Le enbe g-Ma qua d al emplea el módulo
cu e_
. Des aca el mé odo de
Gauss-New on amo iguado alacanzando la solución en un iempo muy compe i i o. En la
gu a 2.8 se ep esen an los ajus es ob enidos.
Tiempo E o RSS
Gauss-New on 1.585631e+00 s 2.2892082490e-02 5.2404744072e-04
Gauss-New on amo iguado 4.452369e-01 s 2.2892082490e-02 5.2404744072e-04
Le enbe g-Ma qua d (cu e_ ) 8.676696e-02 s 2.2892082490e-02 5.2404744073e-04
Le enbe g-Ma qua d (leas _squa es) 2.393365e-02 s 2.3478732372e-02 5.512508738e-04
Le enbe g-Ma qua d (leas sq) 1.595163e-02 s 2.4900365520e-02 6.200282030e-04
Dogbox (cu e_ ) 1.087105e-01 s 2.2892082490e-02 5.2404744073e-04
Dogbox (leas _squa es) 9.129357e-02 s 2.2892082490e-02 5.2404744073e-04
Cuad o 2.5: Resul ados ob enidos pa a Benne 5 con el i e an e inicial
θ1
0
.
Figu a 2.8: Ajus es de Benne 5 pa iendo del i e an e inicial
θ1
0
.

2.2. RESULTADOS OBTENIDOS
33
En el Cuad o 2.6 se p esen an los esul ados ob enidos empleando como i e an e inicial
θ2
0
. No se ap ecian di e encias de compo amien o en e los mé odos u ilizados alcanzán-
dose en odos los casos los alo es ce icados. De nue o, ob enemos que el mé odo más
ecien e es Le enbe g-Ma qua d median e el módulo
cu e_
. En la gu a 2.9 se ep e-
sen an los ajus es ob enidos.
Tiempo E o RSS
Gauss-New on 1.681291e+00 s 2.2892082490e-02 5.2404744073e-04
Gauss-New on amo iguado 2.098632e-01 s 2.2892082490e-02 5.2404744073e-04
Le enbe g-Ma qua d (cu e_ ) 1.097035e-02 s 2.2892082490e-02 5.2404744073e-04
Le enbe g-Ma qua d (leas _squa es) 2.493477e-02 s 2.2894309265e-02 5.2414939672e-04
Le enbe g-Ma qua d (leas sq) 1.595736e-02 s 2.2892082491e-02 5.2404744080e-04
Dogbox (cu e_ ) 1.994944e-02 s 2.2892082490e-02 5.2404744073e-04
Dogbox (leas _squa es) 1.499319e-02 s 2.2892082490e-02 5.2404744073e-04
Cuad o 2.6: Resul ados ob enidos pa a Benne 5 con el i e an e inicial
θ2
0
.
Figu a 2.9: Ajus es de Benne 5 pa iendo del i e an e inicial
θ2
0
.
Según los esul ados expues os en el Cuad o 2.5 y en el Cuad o 2.6 ap eciamos que em-
34
CAPÍTULO 2. RESULTADOS NUMÉRICOS
pleando el mé odo de Le enbe g-Ma qua d median e el módulo
cu e_
el cos e compu-
acional se educe en una oc a a pa e al u iliza como i e an e inicial a
θ2
0
espec o a
u iliza
θ1
0
. Des aca que en ambos casos el mé odo de Gauss-New on amo iguado mejo a
al mé odo de Gauss-New on alcanzando la solución en un iempo muy compe i i o espec-
o al es o. Debemos ene siemp e en conside ación que ambos mé odos, Gauss-New on y
Gauss-New on amo iguado, son de implemen ación p opia.
Capí ulo 3
Conclusiones
El obje i o de es e T abajo de Fin de G ado e a analiza el uncionamien o de algunos
de los mé odos exis en es pa a la esolución del p oblema de ajus e no lineal y compa a
sus dis in as implemen aciones p esen es en
Py hon
.
Las conclusiones gene ales as habe ealizado el p esen e T abajo de Fin de G ado
son las siguien es:
Se han complemen ado los conocimien os adqui idos en el G ado de Ma emá icas
impa idos en las asigna u as de Mé odos Numé icos: 'Cálculo Numé ico nunha Va-
iable', 'Análise Numé ica Ma icial' y 'Mé odos Numé icos en Op imización e Ecua-
cións Di e enciais'.
Se han ap endido los undamen os de una se ie de mé odos numé icos que pe mi en
la esolución de p oblemas de op imización de mínimos cuad ados no lineales con el
n pode aplica dichos conocimien os a ealiza un análisis de los p opios mé odos,
su implemen ación en o denado y aplica los a p oblemas conc e os.
Se han adqui ido nue os conocimien os en el ámbi o de la p og amación, ap endiendo
un nue o lenguaje que no se incluye en el p og ama o ma i o del G ado en Ma e-
má icas como es
Py hon
.
Se han ex aído ambién una se ie de conclusiones pa icula es as la ealización del
abajo:
El mé odo de Le enbe g-Ma qua d aplicado en los p oblemas benchma k desc i os
en el p esen e T abajo de Fin de G ado ha demos ado se signica i amen e más
ecien e en el cálculo de pa áme os en e al es o de mé odos expues os.
35
36
CAPÍTULO 3. CONCLUSIONES
Aunque en los esul ados expues os no sea posible ap ecia lo con cla idad, se deduce
que en los casos en los que el esiduo sea pequeño o el p oblema no sea cla amen-
e no lineal los mé odos de Gauss-New on y Gauss-New on amo iguado esul an
se muy compe i i os. Es o no es posible ap ecia lo debido a que ambos han sido
implemen ados po la au o a de es e abajo.
A juicio de la au o a del p esen e T abajo de Fin de G ado hab ía esul ado in e esan e
ealiza la implemen ación de los mé odos p opues os en el Apéndice B; en pa icula , el
mé odo p opues o po Fle che -Xu.
Apéndice A
Concep os básicos
En es e apéndice expond emos una se ie de concep os básicos a ene en cuen a pa a
una mejo comp ensión del abajo. Pa a ello nos guia emos po Viaño y Bu gue a (2013)
donde pod á encon a se más in o mación.
Sea
Ω⊆Rn
un conjun o abie o y
: Ω ⊆Rn−→ R
. Di emos que un pun o
u∈Ω
es mínimo local o ela i o de
si exis e
ε > 0
al que
B(u, ε)⊂Ω
y, además,
(u)≤ (ω),∀ω∈B(u, ε)
. Si la desigualdad es es ic a di emos que es un mínimo local
es ic o. Di emos que se a a de un mínimo global o absolu o si
(u)≤ (ω),∀ω∈Ω
.
De nue o, si la desigualdad es es ic a di emos que se a a de un mínimo global es ic o.
Po denición, el mínimo global es ic o, si exis e, es único.
Sea
ω∈Ω
y supongamos que
es de i able en
ω
. Deno amos po
∇ (ω)
al ec o
g adien e de
en
ω
. Tenemos la siguien e condición necesa ia de mínimo ela i o.
Teo ema A.0.1.
Sea
Ω⊆Rn
un conjun o abie o, no acío y sea
: Ω ⊆Rn−→ R
un
uncional con un mínimo ela i o en
u∈Ω
. Si
es de i able en
u
en onces se e ica que
∇ (u) = θ
.
Supongamos aho a que
es dos eces de i able en
ω∈Ω
, deno amos po
∇2 (ω)
la
ma iz Hessiana de
en
ω
.
Teo ema A.0.2.
Sea
Ω⊆Rn
un conjun o abie o, no acío y sea
: Ω ⊆Rn−→ R
un
uncional con un mínimo ela i o en
u∈Ω
. Se supone
de i able en un en o no de
u
y
dos eces de i able en
u
. En onces se e ica:
1.
∇ (u) = θ
.
2. La ma iz hessiana de
es semidenida posi i a.
37

38
APÉNDICE A. CONCEPTOS BÁSICOS
Veamos aho a una se ie de condiciones sucien es que nos pe mi en a ma la exis encia
de un mínimo ela i o
Teo ema A.0.3.
Sea
Ω⊆Rn
un conjun o abie o y no acío,
u∈Ω
. Sea
: Ω ⊆Rn−→
R
un uncional de i able en un en o no de
u
y al que
∇ (u) = θ
. En onces:
1. Si la unción
es dos eces de i able en
u
y su ma iz hessiana es denida posi i a
en
u
en onces la unción
admi e un mínimo ela i o es ic o en
u
.
2. Si la unción
es dos eces de i able en una bola
B(u, )⊆Ω
de o ma que la ma iz
hessiana es semidenida posi i a en odos los pun os de la bola en once
admi e un
mínimo ela i o en
u
.
Apéndice B
Quasi-New on
En es e apéndice se mos a án algunos mé odos numé icos más gene ales pa a la eso-
lución de los p oblemas de minimización de suma de cuad ados de unciones no lineales.
Es os mé odos podemos inclui los den o del ma co de los quasi-New on. Reco demos que
la es a egia a segui e a in oduci una ap oximación quasi-New on del é mino
S(ωk)
que
deno ábamos po
Bk
de mane a que
(Bk+J(ωk)TJ(ωk))sk=−J(ωk)T (ωk).
Tomando
Bk+1 =
m
X
i=1
i(ωk+1)(Hi)k+1,
donde
(Hi)k+1
e a una ap oximación de
∇2 i(ωk+1)
, llegábamos a que
Bk+1
enía que
sa is ace
Bk+1(ωk+1 −ωk) =
m
X
i=1
( i(ωk+1)(Hi)k+1)(ωk+1 −ωk)
=
m
X
i=1
i(ωk+1)(∇ i(ωk+1)− ∇ i(ωk))
=J(ωk+1)T (ωk+1)−J(ωk)T (ωk+1) =: yk.
De o ma análoga, si pedimos que se e ique
(Bk+1 +J(ωk+1)TJ(ωk+1))sk=J(ωk+1)T k+1 −J(ωk)T (ωk)
ob enemos que
Bk+1
debe cumpli
Bk+1sk=J(ωk+1)T (ωk+1)−J(ωk)T (ωk)−J(ωk+1)TJ(ωk+1)sk:= ˜
yk.
De es a o ma llegamos a una nue a condición quasi-New on.
39
40
APÉNDICE B. QUASI-NEWTON
B.1. Mé odo de Be s
Siguiendo es a es a egia, en Be s (1976), se desc ibe un nue o algo i mo donde se
p opone emplea la siguien e ó mula de ango uno
Bk+1 =Bk+(˜
yk−Bksk)(˜
yk−Bksk)T
sk(˜
yk−Bksk).
Es a ó mula de ango uno ha sido epo ada po a ios au o es, incluyendo en e ellos a
B oyden, Mu agh y Sa gen .
Dado que se u iliza un algo i mo ecu si o de ango uno pa a gene a
B
la es imación
comple a no es a á disponible has a que no se comple en las
n
i e aciones. La con ibución
de
Bk
a ec a a la de e minación de la di ección
sk
siemp e que las
n
i e aciones hayan sido
ealizadas. De lo con a io, la di ección de búsqueda
sk
se calcula di ec amen e como una
di ección de Gauss, lo que equi ale a oma
∇2 (ωk) = J(ωk)TJ(ωk)
. Como ocu ía con
el mé odo NL2SOL es azonable oma en la p ime a i e ación la ap oximación de Gauss.
La ap oximación de Gauss esul a algo más en ajosa si los esiduos son lineales o
casi nulos pe o es e algo i mo con inúa siendo muy compe i i o espec o al mé odo de
Gauss-New on. La con ibución de
B
se uel e signica i a pa a esiduos no lineales y
pun os donde
i(ω)
es g ande. El algo i mo esul a e ec i o en p oblemas gene ales que
se ca ac e izan po esiduos dis in os de ce o, p incipalmen e po que la con ibución de
B
es á incluída en la es imación o al de la Hessiana. En Le enbe g-Ma qua d ya se incluía
es a ma iz
B
pe o se ep esen aba como
λI
. Aunque no se llegó a p oba ,los esul ados
numé icos dados en Be s (1976) ienden a indica que el algo i mo es cuad á icamen e
con e gen e, lo que se debe a la con ibución de la ma iz
B
.
B.2. Mé odo de Ba holomew-Biggs
En Ba holomew-Biggs (1977) se p opone un nue o algo i mo de o ma análoga al
mé odo NL2SOL expues o en el Capí ulo 1. Con espec o a la cues ión de elegi las
ó mulas de ac ualización necesi amos que es as man engan a la ma iz
Bk
simé ica,
pe o no hay azón pa a supone que deba se denida posi i a. Sin emba go, es p e-
e ible que
Bk+1 +JT(ωk+1)J(ωk+1)
sí sea denida posi i a; de lo con a io
(Bk+1 +
JT(ωk+1)J(ωk+1))sk+1 =JT(ωk+1) (ωk+1)
puede no da una di ección de descenso. Las
B.3. MÉTODO DE FLETCHER-XU
41
dos modicaciones conside adas ue on la ac ualización de ango dos dada po Powell
Bk+1 =Bk+yk−Bksk)sT
k+sk(yk−Bksk)T
sT
ksk
−sksT
k(yk−Bksk)Tsk
(sT
ksk)2
y la ó mula de ango uno p opues a po Wol e
Bk+1 =Bk+(yk−Bksk)(yk−Bksk)T
(yk−Bksk)Tsk
.
Supongamos que la ap oximación
Bk
es exac amen e igual a
Pm
i=1 i(ωk)∇2 i(ωk)
y que
odas las sub unciones
i(ωk)
son cuad á icas po lo que las ma ices
∇2 i(ωk)
son cons-
an es. Debido a que, en gene al,
k+1 6= k
, la e dade a ma iz
Pm
i=1 i(ωk+1)∇2 i(ωk+1)
die e de
Bk
po una ma iz de ango
n
como esul ado de los cambios ealizados en
i(ωk)
.
Po lo an o, no se puede ga an iza , simplemen e median e el uso de una ac ualización
basada en que
Bk+1
sea co ec o incluso siendo
Bk
co ec o. Se p opone en onces una es a-
egia de ac ualización basada en el caso especial de que
k+1 =γk k
pa a algún escala
γk
.
Si se e ican las condiciones expues as enemos que
Pm
i=1 i(ωk+1)∇2 i(ωk+1) = γkBk
.
Si denimos
γk= T
k+1 k
T
k k
y eescalamos la ma iz
Bk
enemos que la ma iz
Bk+1
de-
be ía eeja los cambios ealizados en
Pm
i=1 i(ωk)∇2 i(ωk)
. Se p oponen en onces dos
modicaciones de las ó mulas de ac ualización
Bk+1 =γkBk+(yk−γkBksk)sT
k+sk(yk−γkBksk)T
sT
ksk
−sksT
k(yk−γkBksk)Tsk
(sT
ksk)2
y
Bk+1 =γkBk+(yk−γkBksk)(yk−γkBksk)T
(yk−γkBksk)Tsk
.
La cues ión de la mejo ac ualización pa a
Bk
se encuen a oda ía abie a. Como
mencionábamos al p incipio, es deseable que la ac ualización man enga denida posi i a la
ma iz
(Bk+1 +JT(ωk+1)J(ωk+1))
. Se ía in e esan e desa olla un algo i mo que u ie-
a la capacidad de cambia au omá icamen e de una ap oximación Gauss-New on a una
ap oximación basada en una de las ac ualizaciones dadas cuando hay indicios de que el
p oblema a a a es conside ado di ícil.
B.3. Mé odo de Fle che -Xu
En la Sección 1.1 hemos is o que pa a un p oblema de esiduos pequeños, el mé odo de
Gauss-New on con e ge a una elocidad lineal ápida que, con p ecisión limi ada, puede se
p e e ible a la con e gencia supe lineal del mé odo BFGS. Fle che y Al-Baali (1985) p o-
ponen un mé odo híb ido, HY1, in en ando combina las mejo es ca ac e ís icas de ambos
48
APÉNDICE C. CÓDIGO PYTHON

Bibliog a ía
Ba holomew-Biggs, M. C. (1977). The es ima ion o he hessian ma ix in nonlinea leas
squa es p oblems wi h non-ze o esidual.
Ma hema ical P og amming
, 12:6780.
Be s, J. T. (1976). Sol ing he nonlinea leas -squa e p oblem: Applica ion o a gene al
me hod.
Jou nal o Op ima ions Theo y and Applica ions
, 18(4):469483.
Bjo ck, A. (1996). Leas squa es me hods. In Cia le , P. G. y Lions, J. L., edi o s,
Handbook
o Nume ical Analysis, Vol. I
. No h-Holland.
Dennis, J. E., Gay, D. M., y Welsch, R. E. (1981). An adap i e nonlinea leas -squa es
algo i hm.
ACM T ansac ions on Ma h. So wa e
, 7(3):348368.
Fle che , R. (1980).
P ac ical Me hods o Op imiza ion, Vol. 1, Uncons ainedOp imiza ion
.
John Wiley and Sons, New Yo k.
Fle che , R. y Al-Baali, M. (1985). Va ia ional me hods o nonlinea leas squa es.
Ope-
a ional Res. Soc.
, 36:405421.
Fle che , R. y Xu, C. (1987). Hyb id me hods o nonlinea leas squa es.
IMA Jou nal o
Nume ical Analysis
, 7:371389.
Gill, P. E., Mu ay, W., y W igh , M. H. (1981).
P ac ical Op imiza ion
. Academic P ess,
London.
Hun e , J. D. (2007). Ma plo lib: A 2D G aphics En i onmen .
Compu ing in Science and
Enginee ing
, 9:9095.
Le enbe g, K. (1944). A me hod o he solu ion o ce ain p oblems in leas squa es.
Qua .
Appl. Ma h
, 2:164168.
Ma qua d , D. W. (1963). An algo i hm o leas -squa es es ima ion o nonlinea pa ame-
e s.
SIAM J. Appl. Ma h
, 11(2):431441.
49
50
BIBLIOGRAFÍA
Mo é, J. J. (1978). The le enbe g-ma qua d algo i hm: implemen a ion and heo y.
In Wa son, G., edi o ,
Lec u e No es in Ma hema ics 630: Nume ical Analysis
, Be -
lín,Heidelbe g. Sp inge -Ve lag.
Mo é, J. J. (1983). Recen de elopmen s in algo i hms and so wa e o us egion me -
hods. In Bachem, A., G o schel, M., y Ko e, B., edi o s,
Ma hema ical P og amming:
The S a e o he A
, Be lín,Heidelbe g. Sp inge -Ve lag.
Mo é, J. J., Ga bow, B. S., y Hils om, K. E. (1980).
Use Guide o Minpack-1
. A gonne
Na ional Labo a o y, A gonne, Illinois.
Powell, M. J. D. (1970). A new algo i hm o uncons ained op imiza ion. In Rosen, J.,
Mangasa ian, O., y Ri e , K., edi o s,
Nonlinea P og amming
, pages 3165, London.
Academic P es.
Shen, V. K., Side ius, D. W., K ekelbe g, W. P., y Ha ch, H. W. (2013). Nis s anda d
e e ence simula ion websi e. Technical Repo 173, Na ional Ins i u e o S anda ds and
Technology, Gai he sbu g MD, 20899.
h p://doi.o g/10.18434/T4M88Q
.
Sun, W. y Yuan, Y.-X. (2006).
Op imiza ion Theo y and Me hods
. Sp inge US.
an de Wal , S., Colbe , S. C., y Va oquaux, G. (2011). The NumPy A ay: A S uc u e
o Ecien Nume ical Compu a ion.
Compu ing in Science and Enginee ing
, 13:2230.
Viaño, J. M. y Bu gue a, M. (2013).
Lecciones de Mé odos Numé ico: 4. Op imización
.
Anda i a Edi o a, S.L., San iago de Copos ela.
Vi anen, P., Gomme s, R., Oliphan , T. E., Habe land, M., y Reddy, T.
e al. (2020).
SciPy 1.0: Fundamen al Algo i hms o Scien ic Compu ing in Py hon.
Na u e Me -
hods
, 17:261272.
Voglis, C. y Laga is, I. E. (2004). A ec angula us egion dogleg app oach o uncons-
ained and bound cons ained nonlinea op imiza ion. In
P oc. WSEAS In e na ional
Con e ence on Applied Ma hema ics
, pages 17.