background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
1/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
Organization (S):
EDF-R & D/AMA















Manual of Reference
R4.03 booklet: Analyze sensitivity
Document: R4.03.06



Algorithm of retiming




Summary:

In this document the algorithm of retiming of MACR_RECAL is presented. It is about an algorithm of
Levenberg-Marquardt with terminals.
One initially describes the general method before specifying certain elements of them. Are detailed it
calculation of the functional calculus, the Jacobienne matrix, determination of the initial parameter of regularization thus
that its evolution, the management of the terminals and the criterion of convergence.
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
2/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
Count
matters
1
Introduction ............................................................................................................................................ 3
2
Algorithm of Levenberg-Marquardt ..................................................................................................... 4
2.1
Position of the problem ....................................................................................................................... 4
2.2
Resolution ........................................................................................................................................ 4
3
Implementation practices ......................................................................................................................... 7
3.1
Definition of the functional calculus ........................................................................................................... 7
3.2
Form of the matrix Jacobienne ............................................................................................. 8
3.3
Regularization of the linear system ................................................................................................. 9
3.3.1
Initial value of
.................................................................................................................. 9
3.3.2
Evolution of the value of
..................................................................................................... 9
3.4
Limitations of the field of evolution of the parameters ....................................................................... 9
3.5
Adimensionnement ........................................................................................................................ 10
3.6
Criterion of convergence ................................................................................................................. 11
4
Total algorithm ................................................................................................................................. 12
5
Bibliography ........................................................................................................................................ 12
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
3/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
1 Introduction
Before approaching the problems of retiming strictly speaking, it is useful to recall some
elements on the identification of parameters. Let us suppose that one wishes to identify
N
parameters to be left
of a given mechanical test. Within the framework of this identification, one defines the sizes:
·
C
, the vector of N parameters to be identified, pertaining to
O
, convex closed
N
R
.
·
D
, the vector of the sizes calculated during a simulation of the test by using them
parameters
C
, in opposition to
exp
D
, the vector of the sizes measured during a test
experimental. Both belong to space
L
observable sizes.
simulation of the experimental test, parameterized by the vector
C
, can be realized by
various methods: finished differences, finite elements, elements of border,…. It is it
that we will call the direct problem.
The goal of the identification is to determine the set of parameters
C
reducing the difference enters
sizes measured and experimental (by strongly hoping that the reduction of this variation is
sufficient to obtain the set of parameters wished…). A cost functional calculus is thus introduced
noted
J
depending on
C
and measuring the distance enters
D
and
exp
D
.
()
exp
D
D
C
J
-
=
éq 1-1
where || . || indicate a standard on
L
.
The identification is thus expressed in the form of the problem of minimization according to:
()
()
C
J
C
J
O
C
O
C
=
Min
*
*
that
such
To determine
Lastly, one defines retiming as the minimization of a particular type of said functional calculuses
“least squares” which are expressed in the form:
()
()
C
C
J
=
=
NR
N
N
J
1
2
éq 1-2
It is commonly allowed that the most effective algorithm of the minimization for this type of
functional calculuses is the algorithm of Levenberg-Marquardt. It is the latter which is established in
order MACR_RECAL of Code_Aster and that we present in the continuation.
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
4/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
2
Algorithm of Levenberg-Marquardt
2.1
Position of the problem
There are several families of algorithms of minimization [bib1]. For the problems relatively
regular, the most used are the methods of descent. Their principle is to generate in manner
iterative a continuation
()
NR
C
K
K
defined by:
()
K
K
K
K
G
C
C
+
=
+1
éq 2.1-1
such as, for
()
(
)
*
,
+
+
=
R
X
X
X
F
K
K
G
C
J
·
()
X
F
is decreasing in the vicinity of
+
0
·
()
()
X
F
F
X
K
0
Min
>
=
K
G
is the direction of descent to the pitch
K
. It is the method of determination of
K
G
who conditions
nature thus effectiveness of the algorithm used, knowing that these techniques are mainly based
on approximations of
J
with command 1 or command 2. For the algorithm of Levenberg-Marquardt, one
handle an approximation with command 2 of the functional calculus.

2.2 Resolution
Within the framework of retiming, one handles square least cost functional calculuses of the type:
()
()
C
C
J
=
=
NR
N
N
J
1
2
éq 2.2-1
where for example
()
()
(
)
exp
N
calc
N
N
F
F
J
-
=
C
C
, with obvious notations.

The characteristic of these cost functional calculuses lies in the fact that one knows the form of theirs
derived first and seconds:
()
(
)
()
=
=
NR
N
I
N
N
I
C
J
J
1
2
C
C
J
C
éq
2.2-2
()
(
)
()
=




+
=
NR
N
J
I
N
N
J
N
I
N
ij
C
C
J
J
C
J
C
J
1
2
.
2
C
C
H
éq
2.2-3
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
5/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
Then, by supposing that the second term of the preceding equation is negligible in front of the first
(what is true when them
K
J
are linear in
C
: this term is null), one can rewrite:
()
(
)
=
NR
N
J
N
I
N
ij
C
J
C
J
1
.
2
C
H
éq
2.2-4
It is interesting on this level to introduce the matrix of sensitivity or Jacobienne matrix defined by:
















=
N
NR
NR
NR
N
C
J
C
J
C
J
C
J
C
J
C
J
C
J
C
J
2
1
2
2
1
2
1
2
1
1
1
With
éq
2.2-5

One can thus express the gradient and Hessien by:
()
J
With
C
J
C
T
K
2
=
éq 2.2-6
()
With
With
C
H
T
K
2
éq 2.2-7
with
[
]
T
NR
J
J…,
,
1
=
J
.

Then let us write the development limited to command 2 of
J
:
()
() (
)
() (
) () (
)
K
K
T
K
K
T
K
K
C
C
C
H
C
C
C
J
C
C
C
J
C
J
C
-
-
+
-
+
.
2
1
.
éq 2.2-8
That is to say
K
K
C
C
G
-
=
, the pitch of descent at the point
K
C
, it must check the condition of stationnarity of
the quadratic approximation:
() ()
0
=
+
K
K
K
G
C
H
C
J
C
éq
2.2-9
According to the expression of the gradient and Hessien of
J
, one can write:
(
)
J
With
G
With
With
T
K
T
-
=
éq
2.2-10
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
6/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
The solution of this equation leads to an algorithm known under the name of Gauss-Newton, very
effective but which presents nevertheless some disadvantages:
·
(
)
With
With
T
can be almost singular and cause the non-existence of solution.
·
There is no control on
K
G
, which can be too large and thus leave the parameters
acceptable space.
To mitigate these disadvantages, one prefers to use the algorithm of Levenberg-Marquardt which proposes
a regularization of the algorithm of Gauss-Newton:
(
)
J
With
G
I
With
With
T
K
T
-
=
+

éq
2.2-11
where
is a scalar and
I
the matrix identity.
It is noticed that if
0
=
, one finds the direction given by Gauss-Newton and if
+
, one
find the direction given by the opposite one of the gradient of
J
i.e the greatest slope.
The algorithm of Levenberg-Marquardt thus consists, on the basis of a value of
“raised enough”,
to decrease it by a factor 10 for example, with each decrease of
J
. One passes thus
gradually of an algorithm of greater slope to the algorithm of Gauss-Newton. One thus can
to present this procedure in the form:
·
Choice of a starting point
0
C
and of an initial value of
·
With the iteration
K
, to solve
(
)
K
K
K
T
K
T
G
C
C
J
With
G
I
With
With
+
=
-
=
+
+1
·
If
() ()
K
K
C
J
C
J
<
+1
, then
10
/
=
if not
10
*
=
·
Test of convergence
Note:
We considered above the algorithm of Levenberg-Marquardt under the angle of
regularization of the algorithm of Gauss-Newton. It is possible to give a lighting
different with this algorithm by regarding it as an algorithm from area of confidence
[bib2]. Indeed, one can show easily that the system [éq 2.2-11] is the condition of
stationnarity of the problem of minimization:
To determine
K
G
such as


+
=
K
T
T
K
T
T
K
K
G
With
With
G
J
With
G
G
2
1
.
ArgMin
subjected to
K
K
D
G
Where
(
)
0
1
+
-
=
-
and
J
With
I
With
With
T
T
K
D
.
It is a very simple establishment of the algorithm of Levenberg-Marquardt within which
various questions are not tackled:
·
How to define the functional calculus
J
when one has several tests?
·
How to choose the initial value of
?
·
How to make evolve/move
in a finer way?
·
How to define the field of evolutions of each parameters?
We will clarify these various points in the continuation.
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
7/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
3
Implementation practical
3.1
Definition of the functional calculus
At the time of a retiming, the user often has several different measurements; it is about
discrete physical sizes, possibly of different nature, measured during one or
several tests. They are related to a noted given parameter
T
(time, X-coordinate,…) that one
can thus represent by:




=




=




=
)
(
)
(
)
(
)
(
)
(
)
(
exp
1
exp
1
exp
exp
2
1
exp
2
1
exp
2
exp
1
1
exp
1
1
exp
1
P
L
P
L
L
M
M
NR
NR
T
F
T
T
F
T
F
T
F
T
T
F
T
F
T
F
T
T
F
T
F
M
M
M
M
M
M
éq 3.1-1
Each one of these experimental measurements has sound during




=




=




=
)
~
,
(
~
)
~
,
(
~
)
(
)
~
,
(
~
)
~
,
(
~
)
(
)
~
,
(
~
)
~
,
(
~
)
(
1
1
2
1
2
1
2
1
1
1
1
1
K
K
L
K
K
L
K
L
J
K
J
K
K
I
K
I
K
K
T
F
T
T
F
T
F
T
F
T
T
F
T
F
T
F
T
T
F
T
F
C
C
C
C
C
C
C
calc
calc
calc
calc
calc
calc
calc
calc
calc
M
M
M
M
M
M
C
C
éq 3.1-2
calculated for a play of parameter
K
C
given. Let us notice that the calculated sizes are not
inevitably in same number as the measured sizes nor evaluated for the same value of
parameter
T
. One can then define the functional calculus least squares to be minimized by:
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
0
1
2
exp
exp
1
2
exp
2
2
exp
2
1
2
exp
1
1
exp
1
C
J
C
C
C
C
J
=
=
=




-
+
+




-
+




-
=
P
I
I
L
I
K
L
I
L
M
I
I
I
K
I
NR
I
I
I
K
I
K
T
F
T
F
T
F
T
F
T
F
T
F
T
F
T
F
T
F
,
,
,
calc
calc
calc
éq
3.1-3
It is important to notice that:
·
if a calculated measurement
calc
J
F
is not defined in one moment
I
T
, then one interpolates linearly
its value
·
if an experimental measurement
exp
J
F
is null, one does not divide the quantity
)
(
)
(
exp
I
K
J
I
J
T
F
T
F
,
C
calc
-
and it is present just as it is in the expression of the functional calculus
·
the functional calculus
J
is standardized so as to be worth 1. at the beginning of the iterations of retiming
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
8/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
3.2
Form of the Jacobienne matrix
For the calculation of the Jacobienne matrix, one defines the vector
J
errors by:


























-
-
-
-
=
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
exp
exp
1
exp
2
1
2
1
exp
2
exp
1
1
exp
1
1
exp
1
1
1
1
exp
1
L
P
L
K
P
L
P
K
NR
NR
K
NR
K
T
F
T
F
T
F
T
F
T
F
T
F
T
F
T
F
T
F
T
F
T
F
T
F
,
,
,
,
C
C
C
C
J
calc
calc
calc
calc
M
M
M
éq
3.2-1
That is to say:
)
(
)
(
)
(
exp
exp
I
K
I
K
K
I
K
K
I
T
F
T
F
T
F
J
,
C
calc
-
=
éq
3.2-2
One finds the form of the Jacobienne matrix then of [éq 2.2-5]:
























=
N
2
1
2
1
N
2
1
N
2
1
C
J
C
J
C
J
C
J
C
J
C
J
C
J
C
J
C
J
C
J
C
J
P
L
P
L
P
L
NR
NR
NR
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
2
1
2
1
1
1
1
1
1
1
1
1
1
éq
3.2-3

Where the terms are calculated by direct finished differences:
I
N
I
N
I
I
N
I
C
C
C
C
J
C
C
C
C
J
C
C
C
C
J
)
,…,
,…,
(
_
)
,…,
,…,
(
)
,…,
,…,
(
1
1
1
1
1
1
1
I
1
1
+
éq
3.2-4
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
9/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
3.3
Regularization of the linear system
We tackle here the problem of the determination and the evolution of the parameter of regularization
. One defines with this intention:
·
Max
max
=
(Eigenvalues of
With
With
T
),
Min
min
=
(Eigenvalues of
With
With
T
),
cond =
max
/
min
if
min
0
·
()
() (
)
(
) (
) (
)
K
T
T
K
T
T
K
K
C
C
I
With
With
C
C
J
With
C
C
C
J
C
Q
-
+
-
+
-
+
=
.
.
2
1
.
3.3.1 Initial value of
Knowing the sizes above, the following algorithm is defined:
·
If
min
= 0, then
=1.E-3
max
·
If not
- If cond < 1.E5, then
= 1.E-16
max
- If not
= ABS (1.E5
max
min
-
)/10001
Note:
In the last case, the value allotted to
causes to bring back the conditioning of
With
With
T
with 1.E5
3.3.2 Evolution of the value of
To make evolve/move
, the ratio is defined
K
R
=
)
(
)
(
)
(
)
(
1
1
+
+
-
-
K
K
K
K
C
Q
C
Q
C
J
C
J
, which makes it possible to evaluate the validity of
the quadratic approximation of
J
: the closer it is to 1, plus this approximation is valid. One in
deduced the following algorithm [bib2]:
·
If
K
R
< 0.25, then
10
*
=
·
If
K
R
> 0.75, then
15
/
=
3.4
Limitations of the field of evolution of the parameters
For various reasons such as guaranteeing the physical validity of the parameters (module
of strictly positive Young, Poisson's ratio ranging between 0 and 0.5,…), it is necessary of
to limit their field of evolution. One thus imposes that
C
remain in an acceptable field
O
,
convex closed
N
R
. This thus imposes stresses on the parameters:
inf
sup
C
G
C
C
>
+
>
K
K
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
10/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
After dualisation of these conditions by introduction of the multipliers of Lagrange
inf
µ
and
sup
µ
, one
solves the system:
To find
K
G
inf
µ
sup
µ
such as
(
)




=
=
-
+
<
<
+


=
=
-
+
>
>
+
-
=
+
+
+
]
,
1
[
0
)
(
)
(
]
,
1
[
0
)
(
)
(
sup
sup
sup
sup
inf
inf
inf
inf
sup
inf
N
I
N
I
I
I
K
K
K
K
I
I
K
K
K
K
T
K
T
µ
C
G
C
0
µ
C
G
C
µ
C
G
C
0
µ
C
G
C
J
With
µ
µ
G
I
With
With
This resolution is carried out using an algorithm of active stresses. For any precision on this
algorithm, to refer to [bib3] or [bib4].

3.5 Adimensionnement
One is often brought to identify parameters of various physical nature. Commands of
size of these parameters can be extremely different. This can generate the very strong ones
differences in the orders of magnitude of the components of the gradient and Hessien of
functional calculus cost and to compromise the resolution.
To mitigate this difficulty, it is imperative of adimensionner the unknown factors before beginning
resolution. Here a simple and effective procedure.
That is to say
[
]
0
0
2
0
1
0
…,
,
,
N
T
C
C
C
=
C
, the initial vector of the sizes to be rebuilt. The matrix is defined
of adimensionnement
D
:
D
=










-
C
C
C
C
1
0
2
0
0
0
N 1
N
éq
3.5-1
Then, if them
0
I
C
are all nonnull, one can define the adimensional unknown factors by:
0
1
0
.
~
C
D
C
-
=
éq
3.5-2
In the same way, an adimensional cost functional calculus is introduced:
)
)
~
.
)
~
~
C
J
C
D
J
C
J
(
(
=
(
=
éq
3.5-3
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
11/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
Like its gradient:
)
.
~
.
)
~)
~
.
~)
~
~
)
~
~
~
C
J
D
C
C
C
C
J
C
C
D
J
C
C
J
C
J
C
C
(
(
(
(
(
=
=
=
=
éq
3.5-4
And its Jacobienne matrix:
0
*
~
J
ij
ij
C
With
With
=
éq
3.5-5
From an algorithmic point of view, the calculation of the Jacobienne matrix is done classically with
functional calculus
J
, then it is adimensionnée as well as the current parameters
C
, before being
transmitted to the algorithm of minimization. At the exit of this last, parameters
c~
are
redimensionnés to allow the calculation of the functional calculus
J
.

3.6
Criterion of convergence
The criterion of convergence used in MACR_RECAL consists in testing the decrease of the gradient of
the functional calculus. It is reminded the meeting that the use of this criterion is naturally justified by the fact that
the objective of the algorithm of retiming is to cancel this gradient.
||
(
||
||
(
||
0
K
)
)
C
J
C
J
C
C
<
Prec.
éq
3.6-1
Where Prec is by defect taken equal to 1.E-3.
background image
Code_Aster
®
Version
7.1
Titrate:
Algorithm of retiming
Date:
26/08/03
Author (S):
NR. TARDIEU
Key
:
R4.03.06-A
Page
:
12/12
Manual of Reference
R4.03 booklet: Analyze sensitivity
HT-66/03/005/A
4 Algorithm
total
So as to clarify the sequence of the various operations described above, one presents
formally the algorithm of retiming:
·
Initializations
-
K
= 0
- calculation of
With
, adimensionnement of
With
- Calculation of
initial
- Total Iterations
- Adimensionnement of
K
C
- Resolution of the equation of Levenberg-Marquardt
- Imposition of the respect of the terminals
- Redimensioning of
1
+
K
C
- Calculation of
()
1
+
K
C
J
- Updating of
- Calculation of
With
, adimensionnalisation of
With
- Test of convergence
-
K
=
K
+ 1
·
End


5 Bibliography
[1]
J.C. CULIOLI: “Introduction to optimization”, Ellipses, 1994
[2]
Mr. S. BAZARAA, H.D. SHERALI & C.M. SHETTY: “Nonlinear Programming, Theory and
Algorithms “, Wiley & Sounds, 1979
[3]
“Contact by conditions kinematics”, Document Code_Aster [R5.03.50]
[4]
K. KUNISCH & F. RENDL; “Infeasible Year activates set method for quadratic programming with
simple bounds “, SIAM Newspaper one Optimization, Volume 14, Number 1, 2003