The Normalization F ators

w i =

( 1

^if

n r < n p

exp( − γ · dX _i ² )

^if

n r ≥ n p

(3.6.1)

where the fator

γ

^{is determined by}

γ = − ^ln(ε _{dX ¯} ^{res 2 )}

^{, with}

dX ¯

orresponding to the

(n p − n)

^{th best iterate. This gives the weighting fator}

ε res

^{for this}

partiular residualelement. Inthisways theweighting fatorsfor the

resid-ual elements orresponding to the best iterates are kept above or equal to

the threshold value

ε _res

^{, and all other points are onsidered low priority.}

Theweighting funtion for

ε r = 0.10

^{isseen ingure3.6.2. Ifthere arenot}

enough rows in the residual to math the number of unknown parameters,

allresidual rows areweighted equallywithafator

1

^.

IftheParameterExtrationproblemisoverdetermined,theweightingfators

makesure thatthe bestpointsaregiven the highestpriority. Asmentioned

before the weighting fators do not inuene the solution, if the system is

onsistent. The threshold valueis usedto deide,how important arole the

'unneessary'iterates should playinndingthe optimal parameter set.

If theParameter Extration problem is underdetermined, it is usually

pos-sibleto satisfyall equations exatly. Inthis asethe weighting fatorshave

no eet on the solution, sine if

r(p ^∗ ) = 0

^{then also}

W · r(p ^∗ ) = 0

^{. The}

strategy for determining the weighting fators inthease

n _r < n _p

^is

there-forenot important,aslong asthe

w

^{'sarenot equal to zero.}

Astrategy for hoosing thenormalization fatorsisto put:

a j = 1

√ ε M + k f i (x j ) k 2

for

j = 1, . . . , k

^(3.7.1)

d = 1

√ ε M + k J f,i (x ₀ ) k 2

(3.7.2)

v = 1

√ ε M + k p k k 2

(3.7.3)

wheretheiterates

x ₀ , . . . , x _k

^{arethesortediterates} orrespondingto setion 3.6. Thefator

v

^{in(3.7.3)isusedforsalingthe}regularization term,ifthis isinluded inthe residual formulation.

Eah of therst

k

^{residual elements isthedierene between the surrogate}

and the ne model response in

k

^{dierent iteration points. We sale these}

residual elements aording to the norm of the ne model response in the

iterate.

The gradient residual is saled with the normalization fator

d

^{, whih is}

found by means of the norm of the ne model gradient. To avoid innite

saling fators, when

k f i (x i ) k 2

^or

k J _f,i (x ₀ ) k 2

^{are very small, we add}

√ ε M

to thedenominator of all normalization fators.

Finallythe regularization term,whenpresent,issaledaordingtothe

ini-tialparametervetor

p k

^{,whihholdsthemappingparameters}orresponding to the

k

^{th surrogate model.}

Chapter 4

Test Problems

4.1 Introdution

The Spae Mapping method performed by the three algorithms in setion

2.1has been tested on various test problems. Thetwo test problems TLT2

and TLT7 arefrom theSMIS framework by Frank Pedersen. Another test

problem is the Rosenbrok funtion, whih has been tested in its lassial

formaswell asinan augmented version.

The Spae Mapping method an produe very dierent results, depending

on theimplementation and theformulation of theresidual. In all test runs

theimplementation ofthe threealgorithms orrespondto thedesriptionsin

hapter2.

ThetestshavebeenperformedontheSUNFire3800serverontheIMM

sys-tem withthe following data: 8CPU, 16 GB RAM and thelok frequeny

1200 MHz.

A very important fator for the general performane of the SpaeMapping

methodisonnetedwiththeParameter Extrationproblems. Asdesribed

intheprevious hapter the formulation of theresidual anbevaried bythe

use of normalization fators, weighting fators and regularization. These

threeapproahesan be ombinedwiththeredutionoftheparameter

ve-tor. There are manyoptions to hoose fromand every one of these options

havean inuene ontheresults.

The test investigations presented here are onerned only with the

formu-lation of the Parameter Extration problems. Through the work with the

implementation and the following test runsof thealgorithms, theeets of

a ertain approah has been somewhat laried. On the basis of this the

options have been hosen to provide dierent senarios, whih dene the

algorithms used. All senarios have been used on the three problem types.

Inevery test run we mustdene four tolerane options for usein the

stop-pingriterafor thethree algorithms. Theseoptions are:

ε _F

^{: Stoppingriterion for the objetivefuntion.}

ε hx

^{: Stoppingriterion for the step lengthfor}

x

^-iterates.

ε _hp

^{: Stoppingriterion for the step lengthfor}

p

^-iterates.

ε _K

^{: Stoppingriterion for the gradient residual math.}

Inthesetup leitisurrently onlypossibleto settwotolerane parameters

ε 1

^and

ε 2

^{,where the rstisthedesiredaurayfor themain problem,and}

the latter is the desired auray, when solving the Parameter Extration

problem. Weuse

ε ₁ = ε _F = ε _hx

^and

ε ₂ = ε _hp = ε _K

^.

Furthermorethemaximalnumberoffuntionevaluationsineahofthe

algo-rithmsis needed. These values areset aording to thepartiular problem.

Theoptions inmarquardt mustalso be dened f.p.19.

The tolerane options and marquardt-options in some ases have an eet

on the results. On that ground we use either one of the following sets of

options,dependingon theproblem:

• ε ₁ = 10 ^{− 14}

^,

ε ₂ = 10 ^{− 4}

^{and opts}

=

^{[1e-8 1e-4 1e-4 200 1e-12℄.}

• ε ₁ = 10 ^{− 14}

^,

ε ₂ = 10 ^{− 14}

^{and opts}

=

^{[1e-8 1e-14 1e-14 200 1e-12℄.}

Theinitial trust region radius for all test problems is

∆ ⁽⁰⁾ = 10 ^{− 1} · k x ⁽⁰⁾ k ²

^.

The parameter

η

^{,that denes the step length in}diffjaobian, is xed at

η = 10 ^{− 5}

^{for both forward dierene} approximations wrt.

x

^andwrt.

p

^.

TheupdatingofthepenaltyfatorisdoneonlybythestrategyinAlgorithm

3. Finally we only onsider minimax optimization orresponding to

p = ∞

inAlgorithm1 and 2,whereas Algorithm 3 orrespondsto minimization in

the

2

^-norm.

4.1.1 The Test Senarios

Forshowingtheeetsofagivenapproahregardingtheresidualdenition,

we ompare the test runs from dierent residual proles. We here present

anoverviewof theinvestigated test senarios.

Regularization

Toshowtheeetsofinludingtheregularizationtermintheresidualvetor

we ompare the testruns withtheproles:

•

Regularization of theresidual vetor asdesribed in setion3.3. The regularization term isadded to theresidualvetor (1.3.12) whihnow

has

n r = k + n + n p

^elements.

•

^No regularization of the residual vetor. The residual has the formu-lation(1.3.12) andonsistsof

n r = k + n

^elements.

Bothasesareinludingompletenormalizationoftheresidualelements

or-responding to

a _j = √ ε M + k ¹ f i (x j ) k ²

^for

j = 1, . . . , k

^and

d = √ ε M + k J ¹ f,i (x 0 ) k ²

^.

Whentheregularization termispresent,itismultiplied withthe

normaliza-tionfator

v = _√ ¹

ε M + k p ⁽⁰⁾ _i k 2

.

The Normalization Fators

For investigating the inuene of thenormalization fators we test the

fol-lowing ases:

•

Normalization of all residual elements: The normalization fatorsare given by

a j = √ ε M + k ¹ f i (x j ) k 2

for

j = 1, . . . , k

^and

d = √ ε M + k J ¹ _f,i (x 0 ) k 2

.

•

^Partlynormalizationoftheresidualelements: Onlythegradient resid-ualissaled orresponding to

a ₁ , . . . , a _k = 1

^and

d = √ ε M + k J ¹ f,i (x 0 ) k 2

.

•

^No normalization ofthe residual elements:

a i = 1

^for

i = 1, . . . , k

^and

d = 1

^.

The Weighting Fators

The eet of the weighting fatorsare onsidered and we ompare the

se-narios:

•

^{No weighting ofthefuntion valueresidual,}

w i = 1

^for

i = 1, . . . , k

^.

•

^{Weighting of the residual elements} orresponding to the Gauss dis-tributed weight funtion, and the strategy in setion 3.6 with the

weights

w ₁ , . . . , w _k

^{given by(3.6.1) .}

The two ases are ombined with a omplete normalization of the residual

elements.

The Number of MappingParameters

The last test senario onerns the number of mapping parameters. We

onsidertwo ases:

•

^{Withafull-sizeparametervetor: Thenumberofmappingparameters}

is

n p = n ² + n + 1

^.

•

^{With a redued parameter vetor} orresponding to using a diagonal inputmappingmatrix

A

^{: Thenumberofmappingparameters is}

n _p =

2n + 1

^.

In the problem setup-le the size of

p

^{is ontrolled by the ag diagA. For}

diagA

= 0

^{theinput mapping matrix}

A

^{is full,and for diagA}

= 1

^{we have}

adiagonal

A

^.

4.1.2 Visualization of The Results

The results of the Matlab runs of the test problems will be presented in

dierent ways. The SMIS framework ontains dierent plotting programs,

whihanbealledaftertheendedSpaeMappingiterationsforatest

prob-lem. Thefollowing plots areusedto showtheresults:

Convergene of the Iteration Sequene

Thetestproblemsallhaveknownoptimizersoftheneandtheoarsemodel,

whih makes it possible to see if the Spae Mapping method onverges or

not. Theoptimizers

x ^∗

^and

z ^∗

^{mustbe provided intheproblem setup-le.}

Twomeasuresfortheonvergenetotheoptimizerareplotted withdierent

plotsymbolsasa funtionof the iteration number:

k x ^(k) − x ^∗ k 2

♦ F (x ^(k) ) − F(x ^∗ )

Theseplotsareomparablewiththeresultsof[1℄. Theformulationsarestill

valid,when

x ^∗

^and

F (x ^∗ )

^{areequal to zero.}

Approximation Error

The surrogate model provides an alternative to the ne model, whih is

heaper to evaluate than the ne model. The surrogate model is used as

a loal approximation to the ne model, and the region, where the model

approximationisgood,isofinterest. WiththenewSpaeMapping

formula-tionwithbothinputandoutputmappings,thesurrogateandthenemodel

math exatly intheexpansion point. To evaluate theresults we are

inter-estedinthemodelmathinginthe region aroundtheexpansion point. The

modelmathingofthesurrogatemodelanbeompared withthemathing

ofaTaylormodel, whihisusedfor approximationinlassialoptimization

methods.

Inlassialoptimizationwithrstorderinformationavailable, weuseaT

ay-f (x + h) = f(x) + J _f (x)h + O( k h k ² 2 )

andwhenonlyusingtherstorderinformation,wegetthelinearizedmodel:

l(h) = f (x) + J f (x)h

Theapproximationerror isthengiven by

f (x + h) − l(h)

^{. Ameasureofthe}

approximationerror suitable for plottingis:

E l (h) = k f (x + h) − l(h) k 2

and it is obvious, that the error grows quadratially as we move from the

expansionpoint.

In the Spae Mapping Method we use the surrogate model as an

approxi-mation to the objetive funtion. The norm of the dierene between the

surrogateandthenemodelanbeusedasameasureoftheapproximation

error given by:

E s (h) = k f(x + h) − s(x + h) k 2

Beause of the new Spae Mapping formulation with the output mapping

we are ensured an exat funtion value math in theexpansion point. F

ur-thermorethe residualfuntionusedintheParameter Extrationguarantees

asatisfatorygradient mathinthis point.

For two-dimensional problems (

n = 2

^{) thetwo} approximationerrors

E l

^and

E s

^{an be visualizedin}three-dimensional plots,withtheerrorsplotted ina region ofthe

(x ₁ , x ₂ )

^-plane.

Diret Optimization

The SMIS framework also ontains two algorithms, whih an be used for

diret optimization based on rst order derivatives of the ne model. The

rst algorithm diret is an implementation of a rst order method whih

uses approximations to the rst order derivatives from a Broyden update.

Theseondalgorithm diretdexploitsthegradientsreturned diretlyfrom

themodelfuntions.

Theiterationsequenefromthediretoptimizationanbeusedtoompare

theSpaeMappingmethodwiththeinterpolatingsurrogatewithalassial

optimization method.

In document IMM YGBY2004ESAESRETR.54 ei (Sider 53-60)