MATHEMATICAL ANALYSIS AND NUMERICAL MATHEMATICS VOLUME: 12 |NUMBER: 2 |2014 |JUNE
P ac ical Aspec s o P imal-Dual Nonlinea
Rescaling Me hod wi h Dynamic Scaling
Pa ame e Upda e
Richa d ANDRASIK
Depa men o Ma hema ical Analysis and Applica ions o Ma hema ics,
Facul y o Science, Palacky Uni e si y Olomouc,
s . 17. lis opadu 12, 771 46 Olomouc, Czech Republic
and asik. ic[email p o ec ed]
Abs ac . P imal-dual nonlinea escaling me hod
wi h dynamic scaling pa ame e upda e (PDNRD) is an
op imiza ion me hod om a class o nonlinea escal-
ing echniques. P e ious wo k does no discuss p ac-
ical aspec s o PDNRD me hod such as he explana-
ion and he se ing o he pa ame e s. To comple e
his amewo k, he pa ame e s we e desc ibed. Mo e-
o e , PDNRD me hod was applied on wo quad a ic
p og amming p oblems wi h quad a ic cons ain s and
ecommenda ions abou he se ing o he pa ame e s
we e made.
Keywo ds
Con ex op imiza ion, dynamic scaling pa ame-
e upda e, nonlinea escaling me hod, pa am-
e e s se ing.
1. In oduc ion
The op imiza ion heo y is de eloping in pa allel wi h
he appea ance o eal-li e p oblems and wi h he need
o sol e hem. Thanks o ha , some ypes o p ob-
lems gained a special s a us among he o he s and
many ools o sol e hese p oblems ha e been de el-
oped. An example is he linea p og amming (LP). In
1947, Geo ge Dan zig in oduced he simplex me hod
o sol ing LP [3]. Howe e , he simplex me hod has a
s ong compe i o – in e io -poin me hods, especially
p imal-dual in e io -poin me hods [15].
In he ield o he nonlinea p og amming (NLP),
in e io -poin me hods ha e been also applied. How-
e e , he si ua ion in NLP is mo e complica ed in com-
pa ison wi h LP calcula ions and in e io poin me h-
ods a e some imes expe iencing nume ical di icul ies.
This ac mo i a ed Roman Polyak and Igo G i a o
design an al e na i e me hod based on he nonlinea
escaling (NR) heo y.
Nowadays, NR me hods can sol e la ge-scale NLP
p oblems wi h housands o a iables and cons ain s.
They we e success ully used o he adio he apy ea -
men planning and a e applied a some hospi als in
USA and Eu ope [1].
The basic idea o NR me hods is a nonlinea ans-
o ma ion o cons ain unc ions o imp o e he p op-
e ies o Lag angian. O iginally, he modi ied ba ie
me hods [8] we e in oduced along wi h ew modi ied
ba ie unc ions. A e wa ds, he log-sigmoid unc ion
was also conside ed usable o NR [9], [10]. Conse-
quen ly, he pieces o knowledge we e e ined, pu o-
ge he and a gene aliza ion o hese echniques led o
he concep o NR me hods and NR unc ions. Simila
o p og ess wi h in e io -poin me hods, he p imal-
dual nonlinea escaling (PDNR) me hod was de el-
oped [11].
PDNR me hod is locally con e gen wi h he Q-
linea con e gence a e. To imp o e hese p ope ies,
PDNR me hod can be combined wi h ano he op i-
miza ion me hod (e.g. he p imal-dual pa h- ollowing
me hod) o ob ain he global con e gence [11]. An-
o he way how o imp o e he con e gence o PDNR
me hod is a dynamic scaling pa ame e upda e [5] o-
ge he wi h some globaliza ion s a egy (e.g. a s ep
leng h compu a ion). Recen ly, gene aliza ions and
o he imp o emen s [12], [13] we e de eloped o im-
p o e he asymp o ic con e gence a e and o educe
he compu a ional e o . The main pu poses o his
pape a e o desc ibe in de ail pa ame e s o PDNRD
me hod and o gi e ecommenda ions abou hei se -
ing.
The pape is o ganized as ollows. Fi s , he con ex
op imiza ion p oblem is s a ed and basic assump ions
c
2014 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 144
MATHEMATICAL ANALYSIS AND NUMERICAL MATHEMATICS VOLUME: 12 |NUMBER: 2 |2014 |JUNE
a e discussed. Then, NR unc ions a e de ined and he
key idea o NR me hod is explained. A e wa ds, basic
p imal-dual a ian o NR me hod is p esen ed. Nex ,
PDNRD me hod is explained and i s pa ame e s a e
desc ibed. Finally, nume ical expe imen s wi h di e -
en pa ame e se ings we e made and he esul s a e
p esen ed in Sec ion 7.
2. S a emen o he P oblem
We conside he con ex op imiza ion p oblem
(minimize (x),x∈ <n,
subjec o ci(x)≥0,i= 1, . . . , . (1)
Func ion is con ex and unc ions cia e conca e,
∀i= 1,. . ., . Le S⊆ <nbe he admissible se
o p oblem Eq. (1). Fo simplici y we de ine mapping
c:<n→ < as
c(x)=(c1(x), c2(x), . . . , c (x))T,∀x∈ <n.
We suppose ha :
•Func ions ,ci,∀i= 1, . . . , , a e a leas wice
con inuously di e en iable on he se <n.
•The op imal se X∗=A gmin { (x); x∈S}is
bounded and no emp y.
•The Sla e condi ion holds.
Fo p oblem Eq. (1) we de ine he Lag angian
L(x;λ) = (x)−
X
i=1
λici(x).(2)
Due o assump ion (C), Ka ush-Kuhn-Tucke ’s
(KKT) condi ions can be used o es he op imali y.
I ˆx∈X∗ hen he e is a ec o ˆ
λ∈ < such ha
∇xL(ˆx;ˆ
λ)=0,
ˆ
λ≥0,
ˆ
λici(ˆx)=0,∀i= 1, . . . , .
(3)
Con e sely, i a pai (ˆx, ˆ
λ)∈S× < sa is ies Eq. (3)
hen ˆx∈X∗.
3. Nonlinea Rescaling
Func ions
Fi s , we de ine unc ions ha will be used o ans o m
cons ain s o p oblem Eq. (1).
De ini ion 1. Twice con inuously di e en iable unc-
ion ψ: ( 0; +∞)→ <, whe e −∞ < 0<0, sa is ying
condi ions
(i)ψ(0) = 0, ψ0(0) = 1,
(ii)ψ0( )>0,∀ ∈( 0; +∞),
(iii)ψ00( )<0,∀ ∈( 0; +∞),
(i )∃a > 0 : ψ( )≤ −a 2,∀ ∈( 0; 0),
( )∃b > 0 : ψ0( )≤b −1,∀ > 0,
( i)∃c > 0 : ψ00( )≥ −c −2,∀ > 0
is called NR unc ion.
Rema k 1. I ollows om (ii) and (iii) ha NR unc-
ion ψis inc easing and conca e on he whole domain.
Because o (ii) and ( ) i is ue ha lim
→+∞ψ0( ) = 0.
Simila ly om (iii) and ( i) i holds ha lim
→+∞ψ00( ) =
0.
Fo example, he exponen ial ans o ma ion, he
modi ied loga i hmic unc ion and he hype bolic ba -
ie unc ion de ined by he ollowing o mulas
ψ1( )=1−e− ,
ψ2( ) = ln ( + 1),
ψ3( ) =
+1 .
a e nonlinea escaling unc ions [11].
Fig. 1: G aphs o unc ions ψ2(blue) and ψq2( ed), τ=−1
2.
Func ions ψi,i= 2,3, can be modi ied so ha
ψi∈ C2(<). The unc ion ψ1is al eady wice con-
inuously di e en iable and he ollowing modi ica ion
is no necessa y, o cou se i can be done. Fo a gi en
pa ame e τ∈(−1; 0) he quad a ic ex apola ion is
de ined by he ela ions
ψqi( ) = ψi( ), o ≥τ,
qi( ) = Ai 2+Bi +Ci, o < τ,
whe eas coe icien s o he unc ion qican be de e -
mined om he o mulas
ψi(τ) = qi(τ), ψ0
i(τ) = q0
i(τ), ψ00
i(τ) = q00
i(τ).
c
2014 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 145
MATHEMATICAL ANALYSIS AND NUMERICAL MATHEMATICS VOLUME: 12 |NUMBER: 2 |2014 |JUNE
F om his equa ions we ob ain
Ai=1
2ψ00
i(τ),
Bi=ψ0
i(τ)−τψ00
i(τ),
Ci=ψi(τ)−τψ0
i(τ) + 1
2τ2ψ00
i(τ).
4. Nonlinea Rescaling
App oach
NR me hods a e based on he idea o ans o m p ob-
lem Eq. (1) using a nonlinea escaling unc ion ψde-
ined on he whole eal axis o he equi alen p oblem
(minimize (x), x ∈ <n,
subjec o k−1ψ(kci(x)) ≥0,i= 1, . . . , . (4)
F om he de ini ion o NR unc ion, i is ob ious ha
p oblems Eq. (1) and Eq. (4) ha e he same admissible
se s, because
ψ(kci(x)) ≥0⇔ci(x)≥0,∀i= 1, . . . , .
Hence, he op imal se s a e also he same. Posi i e eal
numbe kis he scaling pa ame e , which can be ixed
o dynamically enla ged du ing he i e a ion p ocess,
see Algo i hm 3.
The Lag angian o equi alen p oblem Eq. (4) is
gi en by he ollowing o mula:
L(x;λ, k) = (x)−k−1
X
i=1
λiψ(kci(x)).(5)
Fo any ∈Nwe deno e
<
+={ ∈ < ; i≥0},
<
++ ={ ∈ < ; i>0}.
Suppose o a while ha we know he solu ion o he
dual p oblem λ∗∈ <
+. Then i is su icien o mini-
mize he unc ion L(x;λ∗, k)in he p imal a iable x.
The cons ained op imiza ion p oblem would be ans-
o med o an uncons ained op imiza ion p oblem.
Since he Lag ange mul iplie s λ∗a e no known, we
es ima e hem and upda e hem in e e y s ep o he
me hod - jus like he p imal p oblem. In consequence,
he cons ained op imiza ion p oblem is con e ed o
a sequence o uncons ained op imiza ion p oblems.
New on’s me hod o i s a ian is applied in each s ep
o minimize he Lag angian Lin he p imal a iable.
Algo i hm 1. (The basic concep o NR me hods)
Le k > 0be a scaling pa ame e . Ini ial app oxima-
ions x0∈ <nand λ0∈ <
++ a e gi en. We suppose
ha an app oxima ion (xs, λs)∈ <n× <
++,s∈N0,
is known al eady. We ind he nex p imal-dual pai
(xs+1, λs+1)using he ollowing o mulas
xs+1 :∇xL(xs+1;λs, k) = 0,
λs+1
i=ψ0kci(xs+1)λs
i, i = 1, . . . , . (6)
The NR me hod con e ges o any ixed bu la ge
enough k > 0unde he s anda d second o de op i-
mali y condi ions [5].
Rema k 2. I λs∈ <
++, hen also λs+1 ∈ <
++. This
p ope y ollows om condi ion (ii)o NR unc ion ψ.
In o he wo ds, NR me hods a e in e io -poin me hods
in he dual a iable.
The Algo i hm 1 is well de ined due o he ollowing
heo em.
Theo em 1. Suppose ha X∗is bounded. Fo any
gi en (λ, k)∈ <
++ × <++ he e exis s one and only
one ˆx∈ <nsuch ha
L(ˆx;λ, k) = min
x∈<nL(x;λ, k).
P oo : [10], page 206.
The main pu pose o NR is o imp o e p ope ies
o he Lag angian. The classical Lag angian L– as
a connec ion be ween he cons ained and he uncon-
s ained op imiza ion – does no always wo k, because
he exis ence o he uncons ained Lag ange minimize
is unknown in gene al. On he o he hand, he uncon-
s ained minimize o he Lag angian Lalways exis s
(acco ding o Theo em 1). Mo eo e , NR d ama ically
sha pens he eac ion o he Lag angian o he con-
s ain iola ion, which has an impac on he compu-
a ions.
In compa ison o in e io -poin me hods, he e is no
"in ini e wall". NR me hods a e ex e io poin me h-
ods. Also, he unbounded inc ease o he scaling pa-
ame e is no needed o gua an ee he con e gence o
he me hod.
We illus a e he in luence o NR on he Lag angian
on he ollowing simple example.
Example 1. The Lag angian o he ollowing p oblem
(minimize x, x ∈ <1,
subjec o x+ 1 ≥0,(7)
and he Lag angian o he equi alen p oblem a e con-
side ed.
(minimize x, x ∈ <1,
subjec o k−1ψq2(k(x+ 1)) ≥0,(8)
c
2014 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 146
MATHEMATICAL ANALYSIS AND NUMERICAL MATHEMATICS VOLUME: 12 |NUMBER: 2 |2014 |JUNE
We ake a look on he g aphs o bo h Lag angians,
which a e de ined by he o mulas
L(x;λ) = x−λ(x+ 1),
L(x;λ, k) = x−k−1λψq2(k(x+ 1)) .(9)
NR undamen ally changes he shape o he La-
g angian. The sha p eac ion o he Lag angian L o
he cons ain iola ion is ob ious in Fig. 2.
Fig. 2: The Lag angian o he p oblem Eq. (7) - on he op -
and o he equi alen p oblem Eq. (8) wi h k= 1 - on
he bo om.
We p ojec he g aphs o he bo h Lag angians o
he phase plane in Fig. 3. Suppose ha we wan o
ind Lag ange minimize o λ= 2. A e subs i u ion,
o mulas Eq. (9) ha e he o m:
L(x; 2) = −x−2,
L(x; 1, k) = x−k−12ψq2(k(x+ 1)) .
The unc ion L(x; 2) is a dec easing linea unc ion.
We canno ind he Lag ange minimize o i , because
i is unbounded below.
I we ea ange he i s equa ion in o mulas Eq. (9)
in he ollowing way:
L(x;λ) = (1 −λ)x−λ,
i is appa en ha o any λ6= 1 we canno ind he
Lag ange minimize . On he o he hand, we know om
Theo em 1 ha he Lag angian Lhas a minimize o
any λ > 0. This is he main con ibu ion o NR.
Fig. 3: The p ojec ion o he Lag angian o he p ob-
lem Eq. (7) - on he op - and o he equi alen p ob-
lem Eq. (8) wi h k= 1 - on he bo om - o he phase
plane.
5. P imal-dual Nonlinea
Rescaling Me hod
The upda e o he Lag ange mul iplie s is clea om
equa ions Eq. (6). When we wan o calcula e xs+1,
we mus sol e a nonlinea sys em o equa ions using
New on’s me hod. Al hough his app oach wo ks well
a om he solu ion, p imal-dual a ian o he NR
me hod pe o ms be e in he neighbo hood o he so-
lu ion [5]. In Sec ion 6, we will combine hese wo
echniques o ob ain a s able and globally con e gen
me hod.
Le app oxima ions x∈ <n,λ∈ <
++ be known. We
suppose ha
ˆx=x+ ∆x,
ˆ
λ=¯
λ+ ∆λ, (10)
c
2014 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 147
MATHEMATICAL ANALYSIS AND NUMERICAL MATHEMATICS VOLUME: 12 |NUMBER: 2 |2014 |JUNE
whe e (∆x, ∆λ)is a p imal-dual New on s ep and ¯
λis
a p edic o o he Lag ange mul iplie s, which is gi en
by he ollowing o mula
¯
λ= Ψ0(kc(x)) λ,
whe e
Ψ0(kc(x)) = diag (kci(x))
i=1 .
The eason, why de ine ¯
λin his way is hidden in he
equali y
∇xL(x;λ, k) = ∇xL(x;¯
λ).
One s ep o New on’s me hod consis s o sol ing he
sys em o (n+ )linea equa ions
N(·)∆x
∆λ=−∇xL(x;¯
λ)
0,(11)
whe e a pai (∆x, ∆λ)is unknown and
N(·) = ∇2
xxL(x;¯
λ)−∇c(x)T
−kΨ00 (kc(x)) Λ∇c(x)I .
Symbols Ψ00 (kc(x)),Λdeno es diagonal ma ices de-
ined as
Ψ00 (kc(x)) = diag (ψ00(kci(x)))
i=1 ,
Λ = diag (λi)
i=1 .
I N(·)is spa se, we can use nume ical algeb a
echniques o spa se ma ices [15] o sol e he sys-
em Eq. (11).
In he opposi e case, we exp ess ∆λ om he second
equa ion o he sys em Eq. (11) and we subs i u e i o
he i s equa ion. Now, we mus sol e only a sys em
wi h nequa ions, ins ead o a sys em o (n+ )equa-
ions. The sys em has he ollowing o m
M(·)∆x=−∇xL(x;¯
λ),(12)
whe e
M(·) = ∇2
xxL(x;¯
λ)−k∇c(x)TΨ00 (kc(x)) Λ∇c(x).
Rema k 3. I is ob ious ha M(·)is a symme ic
ma ix. I can be shown [11], page 120 ha i he sec-
ond o de op imali y condi ions hold ue a he poin
(x∗;λ∗), hen M(·)is a posi i e de ini e ma ix o all
(x;λ)su icien ly close o he op imal p imal-dual pai ,
when he scaling pa ame e is su icien ly la ge.
Algo i hm 2. (One s ep o PDNR me hod)
Le k∈ <++ be ixed. The app oxima ions x∈ <n,
λ∈ <
++ a e gi en.
•We compu e a dual p edic o
¯
λ= Ψ0(kc(x)) λ.
•We calcula e he New on s ep (∆x, ∆λ) om sys-
em Eq. (11), o
•we ind ou he p imal New on s ep ∆x om o -
mula Eq. (12) and hen we compu e he dual New-
on s ep using he ollowing ela ion
∆λ=kΨ00 (kc(x)) Λ∇c(x)∆x.
•We calcula e he new p imal-dual app oxima ion
x:= x+ ∆x, λ := ¯
λ+ ∆λ.
The Algo i hm 2 desc ibes only one s ep o PDNR
me hod. Al hough, he inpu ec o o mul iplie s be-
longs o <
++, i is no gua an eed ha he upda ed
ec o o mul iplie s has also all i s componen s posi-
i e. In con as , his s a emen is ue o Algo i hm 1,
acco ding o Rema k 2. The e o e, PDNR me hod can-
no s and alone in a gene al case and he imp o emen
is needed (see Algo i hm 3).
6. Dynamic Scaling Pa ame e
Upda e
To ob ain a highe con e gence a e o he me hod,
we dynamically change he scaling pa ame e . Mo e-
o e , we use New on’s me hod wi h a s ep leng h (e.g.
he back acking line sea ch algo i hm) o sol e o mu-
las Eq. (6).
We in oduce a unc ion which measu es he dis-
ance be ween he app oxima ion (x, λ)and he solu-
ion (x∗, λ∗).
De ini ion 2. The unc ion ν:<n×< → <+, de ined
as ollows
ν(x, λ) = max { k∇xL(x;λ)k,
−min1≤i≤ ci(x),
−min1≤i≤ λi,
P
i=1 |λici(x)| },
(13)
is called he me i unc ion.
Fo mula (13) is mo i a ed by KKT condi ions. F om
he i s o de op imali y condi ions i ollows ha
ν(ˆx, ˆ
λ) = 0 ⇔(ˆx, ˆ
λ)∈X∗.
Fo known p imal-dual pai (x, λ)we se he pa am-
e e kacco ding o he ela ion
k=ν(x, λ)−1/2.(14)
I is ob ious ha i a p imal-dual sequence
{(xs, λs)}+∞
0 ends o (x∗, λ∗), hen ν(xs, λs)→0+
and also ks→+∞when s→+∞.
c
2014 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 148

MATHEMATICAL ANALYSIS AND NUMERICAL MATHEMATICS VOLUME: 12 |NUMBER: 2 |2014 |JUNE
To p e en om a singula i y in sys em Eq. (11), we
sol e he ollowing egula ized sys em
Nk(·)∆x
∆λ=−∇xL(x;¯
λ)
0,(15)
whe e he p imal-dual pai (x, λ)is an app oxima ion
o solu ion, kis he scaling pa ame e , ¯
λ= Ψ0(kc(x)) λ
is he dual p edic o o he Lag ange mul iplie s and
Nk(·) = ∇2
xxL(x;¯
λ) + 1
k2In−∇c(x)T
−kΨ00 (kc(x)) Λ∇c(x)I .
I is impo an o ema k ha he egula iza ion has
no e ec o he 1.5-supe linea con e gence a e o
PDNRD me hod [5].
In a compa ison o in e io -poin me hods, he in-
e se ma ix o Nk(·)exis s a he op imal poin o
e e y k∈ <++.
Assume ha he app oxima ion (x, λ)o he poin
(x∗, λ∗)is known. Fi s , we use PDNRD me hod. I
he e is a supe linea dec ease o he me i unc ion, we
ha e ound he nex app oxima ion. In he opposi e
case, we use he p imal New on s ep ∆x(calcula ed
du ing he use o PDNRD me hod) o minimize he
unc ion L(x;λ, k), whe e λand ka e ixed. We ap-
ply he back acking line sea ch me hod o gua an ee
he global con e gence in he minimiza ion p ocess. In
his way, we ob ained he globally con e gen PDNRD
me hod wi h he 1.5-supe linea con e gence a e.
Algo i hm 3. (The globally con e gen PDNRD
me hod)
An ini ial app oxima ion x0∈ <nis gi en. An accu-
acy pa ame e ε > 0and an ini ial scaling pa ame e
k∈ <++ a e gi en. Pa ame e s q∈(0; 1),η∈(0; 0.5),
ω > 1,σ > 0and θ > 0a e also gi en. Se x:= x0,
λ:= (1,1,...,1) ∈ < ,λg:= λand H:= ν(x, λ).
•I H≤ε, hen s op, ou pu (x, λ).
•Find ¯
λand (∆x, ∆λ) om p imal-dual sys em
Eq. (15) wi h known (x, λ)and se
ˆx:= x+ ∆x, ˆ
λ:= ¯
λ+ ∆λ, ˆ
H:= ν(ˆx, ˆ
λ).
•I ˆ
H≤min H3/2−θ,1−θ, hen se
x:= ˆx, λ := ˆ
λ, H := ˆ
H, k := max 1
√H, k
and go o s ep 1.
•Find α∈(0; 1iso ha i holds
L(x+α∆x;λg, k)−L(x;λg, k)
≤ηα∆xT∇xL(x;λg, k),
using he back acking line sea ch algo i hm.
•Se
x:= x+α∆x, ˆ
λ:= Ψ0(kc(x))λg.
•I
k∇xL(x;λg, k)k ≤ σ
kkˆ
λ−λgk,
hen go o s ep 8.
•Find (∆x, ∆λ) om p imal-dual sys em Eq. (15)
wi h known (x, λg)and go o s ep 4.
•I ν(x, ˆ
λ)≤qH, hen se
λ:= ˆ
λ, λg:= ˆ
λ, H := ν(x, ˆ
λ), k := max 1
√H, k
and go o s ep 1.
•Se k:= ωk and go o s ep 7.
7. Nume ical Expe imen s
F om he ini e elemen app oxima ion o con ac p ob-
lems o he linea elas ici y wi h he ic ion in h ee
space dimensions a ise a minimiza ion p oblem





minimize 1
2xTAx−xTb,x∈ <n
subjec o g2
i−x2
i+m−x2
i+2m≥0,i∈ I,
xi−li≥0,i∈ I,
(16)
whe e n= 3mis he numbe o a iables, A∈ <n×n
is a symme ic and posi i e de ini e ma ix, b∈ <n,
g∈ <m
+,l∈ <mand I={1,2, . . . , m}. This is a con-
ex p og amming p oblem so we can use NR app oach
o sol e i . We use he unc ion ψq2wi h τ=1
2 o
escale he condi ions and subsequen ly we ob ain he
equi alen p oblem. The eason o his choice is ha
o a su icien ly la ge class o unc ions c(x)is he unc-
ion −ln c(x)sel -conco dan . I we apply New on’s
me hod o a sel -conco dan unc ion, we can say some-
hing mo e abou he con e gence o New on’s me hod
[2]).
PDNRD me hod was es ed on wo model p oblems
- he cho d p oblem, which in con a y o Eq. (16) con-
ains also uncons ained a iables, and he s eel b ick
p oblem, whose ini e elemen app oxima ion leads ex-
ac ly o Eq. (16). All compu a ions we e pe o med in
MATLAB on he PC In el Co e i7 (2.4GHz) wi h 8GB
RAM. In ables below we epo ed he numbe o i e -
a ions (i ) , he numbe o solu ions o he p imal-dual
sys em (nS) and he solu ion ime in seconds ( ime).
I some da a is missing, i means ha he solu ion ime
was oo long in he compa ison o he o he cases in
he able.
c
2014 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 149
MATHEMATICAL ANALYSIS AND NUMERICAL MATHEMATICS VOLUME: 12 |NUMBER: 2 |2014 |JUNE
7.1. Cho d P oblem
We conside a p oblem
min
u∈K J(u),(17)
whe e
J(u) = 1
2Z1
0ku0( )k2d −Z1
0
u( )T ( )d ,
K={u∈H1
0(0; 1)2:u2( )≥0,∀ ∈(0; 0.5),
ku( )k ≤ 1.4,∀ ∈(0.5; 1) },
( ) = 36π2sin 6π , −4π2sin 2π T.
Fig. 4: The cho d de o ma ion.
Minimiza ion p oblem Eq. (17) desc ibes a loaded
cho d ixed a he endpoin s. The cho d is pa ially
abo e a plain and pa ially inside a cylind ical ube
Fig. 4. The unc ion u( )is he cho d de lec ion. The
cho d p oblem was p esen ed as a model p oblem in
[6].
The objec i e unc ion 1
2xTAx−xTb,x∈ <n
ma ches he con ex quad a ic unc ional J(u), linea
cons ain s in p oblem Eq. (16) ma ches he cons ain
u2( )≥0,∀ ∈(0; 0.5) om he de ini ion o he se
Kand quad a ic cons ain s ma ches ku( )k ≤ 1,4,
∀ ∈(0.5; 1).
Fi s , we decided i he p imal-dual sys em has a
spa se ma ix. We say ha he ma ix is spa se i i
has a mos 10 % nonze o elemen s. In Fig. 5, he
s uc u e o he ma ix Nk(·)∈ <192×192 o n= 128 is
depic ed. This ma ix has only 636 nonze o elemen s
(1.7 %). Hence, Nk(·)is he spa se ma ix. In he same
way we could a gue o o he choices o n.
We sol ed he cho d p oblem o di e en se ings o
pa ame e s o PDNRD me hod. The main esul om
Tab. 1 is a non-inc easing numbe o i e a ions and also
a non-inc easing numbe o solu ions o he p imal-dual
sys em while inc easing he numbe o a iables. The
bes choice o he scaling pa ame e was kini = 10 in
Fig. 5: The s uc u e o he ma ix Nk(·)∈ <192×192 ( he
cho d p oblem). Black colou indica es 636 nonze o el-
emen s.
Tab. 1: The cho d p oblem. PDNRD me hod wi h pa ame e s
ω= 10,σ=1
2kini ,θ= 0.4,q= 0.5,η= 0.01,
ε= 10−6.
kini
n 10 102103
64 32 10/31/0.173 4/23/0.118 7/7/0.021
128 64 7/50/0.238 6/33/0.126 3/79/0.351
256 128 8/60/0.515 8/37/0.454 3/143/1.099
512 256 11/65/1.989 5/49/2.037 7/150/5.036
1024 512 12/70/10.330 6/72/13.088 8/100/22.229
2048 1024 12/58/37.640 6/70/53.256 7/66/50.650
4096 2048 13/74/221.834 – –
i /nS/ ime i /nS/ ime i /nS/ ime
Tab. 2: The cho d p oblem (n= 1024). PDNRD wi h pa am-
e e s ω= 10,σ=1
2kini ,kini = 10,ε= 10−6.
η= 0.01
q θ = 0.1θ= 0.4
0.1 6/49/8.015 6/49/8.054
0.5 10/65/11.554 12/70/10.518
0.9 30/99/16.347 31/77/13.548
η= 0.3
q θ = 0.1θ= 0.4
0.1 6/49/8.133 6/49/8.036
0.5 10/68/11.503 12/71/10.671
0.9 30/92/15.094 31/78/12.885
i /nS/ ime i /nS/ ime
his case, because o he bes pe o mance o la ge
p oblems.
F om Tab. 2 i is ob ious ha he choice q= 0.1was
he bes one. Pa ame e s ηand θhad no signi ican
impac on he compu a ion in his case.
7.2. S eel B ick P oblem
Le us conside a s eel b ick lying on he igid obs acle.
The b ick occupies he domain S= (0; 3) ×(0; 1) ×
c
2014 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 150
MATHEMATICAL ANALYSIS AND NUMERICAL MATHEMATICS VOLUME: 12 |NUMBER: 2 |2014 |JUNE
(0; 1). The bounda y ∂Sis di ided in o h ee pa s
Γu={0}×(0; 1) ×(0; 1),
Γc= (0; 3) ×(0; 1) ×{0},
Γp=∂S ¯
Γu∪¯
Γc,
on which di e en bounda y condi ions a e gi en (see
Fig. 6). The p oblem is desc ibed in he de ail in [6].
Fig. 6: The s eel b ick.
The p og ess was simila o he p e ious one con-
side ing he cho d p oblem. Fi s , he ma ix Nk(·)
was es ed whe he i is spa se o no . In Fig. 7, he
s uc u e o he ma ix Nk(·)∈ <150×150 o n= 90 is
depic ed. This ma ix con ains 8340 nonze o elemen s
(37 %). Hence, he ma ix Nk(·)is no spa se and we
sol ed he p imal-dual sys em in a di e en way (see
Sec ion 5).
Fig. 7: The s uc u e o ma ix Nk(·)∈ <150×150 (s eel b ick
p oblem). Black colou indica es 8340 nonze o elemen s.
The numbe o a iables was deno ed as n= 3 m
and he numbe o condi ions as = 2 m. The s eel
b ick p oblem was sol ed o di e en choices o n. Ac-
co ding o he da a in Tab. 3, he bes se ing o he
ini ial alues o he scaling pa ame e was kini = 10
in his p oblem. Numbe nS ose wi h inc easing kini .
The esul s om Tab. 4 suppo s ha he choice
η= 0.01 is be e han η= 0.3. The pa ame e θhas
no signi ican impac on he compu a ion.
Tab. 3: The s eel b ick p oblem. PDNRD me hod wi h pa am-
e e s ω= 10,σ=1
2kini ,θ= 0.4,q= 0.5,η= 0.01,
ε= 10−6.
kini
n 10 102103
54 36 6/39/0.153 5/54/0.268 4/119/0.570
90 60 6/38/0.218 6/45/0.239 4/102/0.743
180 120 8/40/0.257 4/90/0.700 4/136/1.653
324 216 7/37/0.663 10/35/0.619 4/130/3.146
648 432 12/67/7.258 10/77/10.003 6/123/15.696
i /nS/ ime i /nS/ ime i /nS/ ime
Tab. 4: The s eel b ick p oblem (n= 648). PDNRD me hod
wi h pa ame e s ω= 10,σ=1
2kini ,kini = 10,ε=
10−6.
η= 0.01
q θ = 0.1θ= 0.4
0.1 5/46/5.562 5/46/5.767
0.5 12/45/4.460 12/67/7.135
0.9 12/67/7.545 12/67/7.105
η= 0.3
q θ = 0.1θ= 0.4
0.1 5/44/5.593 5/44/5.482
0.5 11/41/4.398 12/62/8.820
0.9 12/62/8.761 12/62/8.718
i /nS/ ime i /nS/ ime
The cha ac e is ic p ope y o PDNRD me hod is
he "ho " s a o he me hod (as i was obse ed and
p o ed in [11]). "Ho " s a means ha om some
poin only one New on s ep is needed o su icien ly
sh ink he dis ance be ween a cu en app oxima ion
and he solu ion. We can expec ha a compu a ional
e o o sol e he p oblem wi h he accu acy 10−12
will no be d ama ically highe han wi h an accu acy
10−6. Ou esul s suppo his s a emen (compa e
Tab. 3 and Tab. 5).
Tab. 5: The s eel b ick p oblem. PDNRD me hod wi h pa am-
e e s ω= 10,σ=1
2kini ,kini = 10,θ= 0.4,q= 0.5,
η= 0.01,ε= 10−12.
n kini = 10
54 36 8/45/0.165
90 60 10/51/0.252
180 120 12/44/0.269
324 216 10/47/0.806
648 432 14/71/7.371
i /nS/ ime
7.3. Pa ame e s
When using a nume ical me hod he se ing o he pa-
ame e s is e y impo an . Expe ience wi h nume ical
expe imen s helps us o ind he op imal se ing. Based
c
2014 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 151
MATHEMATICAL ANALYSIS AND NUMERICAL MATHEMATICS VOLUME: 12 |NUMBER: 2 |2014 |JUNE
on he es s o PDNRD me hod on examples om Sec-
ions 7.1 and 7.2, we made conside a ions abou a sui -
able se ing o he pa ame e s.
Fac o ω
The ac o ωa ec s he a e o he inc ease o he
scaling pa ame e . Fo ω∈ h5; 20iwe ob ain almos
he same esul s. So we se ω= 10. Howe e , e en o
he o he choices ω > 1 he e a e no any signi ican
changes. A mos , i may happen ha i akes a ew
ex a s eps o he me hod.
Pa ame e σ
The choice o he pa ame e σis less impo an han
he choice o he a io be ween σand he ini ial choice
o he scaling pa ame e kini . I is he ac ion σ
k
which decides abou he numbe o inne i e a ions
(and hus abou he numbe o New on s eps in he
damped phase o New on’s me hod). I is clea ha
o σ >> k he e a e oo li le inne s eps. On he
o he hand, o σ << k he e is oo many o hem.
Acco ding o he esul s o he nume ical expe imen s,
he choice σ=1
2kini is sui able.
Pa ame e θ
The pa ame e θa ec s whe he he inne sol e
uns o no . I we se θ= 0, he inne sol e uns when-
e e he 1.5-supe linea dec ease o he me i unc ion
was no achie ed. Choosing θ= 0.5, we a e saying ha
we a e sa is ied wi h only linea dec ease o he me i
unc ion. The e o e, i is wise o se θ∈ h0; 0.5i. I
appea s (see Tab. 2 and Tab. 4) ha he me hod does
no depend on his pa ame e .
In he condi ion, which is ela ed o he pa ame e
θ, he e m min H3/2−θ,1−θis calcula ed. We can
ask why do no simply use he e m H3/2−θins ead o
he p e ious one. As we know, he classical New on
me hod is e ec i e only in he neighbo hood o he so-
lu ion, so i we a e " a " om he solu ion he damped
New on me hod is be e sui ed o use. The exp es-
sion " a " means ha he me i unc ion is g ea e han
1−θ.
Fac o q
The numbe o inne s eps is in luenced by he ac-
ion σ
k oge he wi h he ac o q. This ac o also a -
ec s how o en is he scaling pa ame e inc eased. Due
o he way in which is his pa ame e used in PDNRD
me hod, i is needed o se q∈(0; 1). Mo eo e , we
mus choose he ac o qso ha he me hod does no
use oo many inne s eps. Based on he da a in Tab. 2
and Tab. 4, any ac o q∈(0; 1) was sui able. Howe e ,
he bes esul s we e ob ained by se ing q= 0.1.
Pa ame e η
The back acking line sea ch pa ame e ηis usually
chosen in he ange om 0.01 o 0.3(see [2] page 466).
Acco ding o da a in Tab. 2 and Tab. 4 he choice o
he pa ame e η∈ h0.01; 0.3iis a bi a y.
Ini ial alue o he scaling pa ame e
Based on he esul s shown in Tab. 1 and Tab. 3,
inc easing he ini ial alue o he scaling led o in-
s abili ies in compu a ions. The bes esul s in he
bo h model examples we e ob ained wi h kini = 10.
The e o e, we ecommend se ing kini a ound en o
less. Fu he eason o se kini a he lowe is ha he
scaling pa ame e can be inc eased du ing he compu-
a ion, bu i canno be dec eased.
Ini ial app oxima ion
The compu a ion also depends on he ini ial app ox-
ima ion. The numbe o s eps can be dec eased, i
"lucky" ini ial app oxima ion is chosen. In p oblems
like a beam de lec ion o con ac p oblems we choose
an ini ial s a e o he sys em as he ini ial app oxima-
ion, because he shape changes o a body a e usually
e y small. Thus we se x0= (0,0,...,0).
8. Conclusion
The p ac ical aspec s o PDNRD me hod we e de-
sc ibed. Especially, he meaning o he pa ame e s o
PDNRD me hod we e explained in de ail. PDNRD
me hod was es ed on wo quad a ic p og amming
p oblems wi h quad a ic cons ain s ( he cho d p ob-
lem and he s eel b ick p oblem). Based on he es s,
he ecommenda ions abou se ing he pa ame e s
we e made.
The solu ion o he p imal-dual sys em is he mos
expensi e ope a ion, hus he numbe o solu ions o
he p imal-dual sys em de e mines he o al complexi y
o compu a ions. I was ound ou ha he inc easing
numbe o a iables in bo h p esen ed p oblems has no
a consequence in he inc easing numbe o solu ions o
he p imal-dual sys em (see Tab. 1 and Tab. 3). This
ac suppo s he applicabili y o PDNRD me hod on
p oblems o an a bi a y size.
Acknowledgmen
This esea ch was suppo ed by he g an P F 2013,
013 Ma hema ical models o he In e nal G an Agency
o Palacky Uni e si y Olomouc.
c
2014 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 152