Discrete optimization problem
In the paper a mathematical model is considered that allows simultaneous optimization of a program motion and
 an ensemble of perturbed motions. Analytical expressions for functional variations are suggested that help constructing various directed methods of optimization. Given mathematical...
Saved in:
| Published in: | Вопросы атомной науки и техники |
|---|---|
| Date: | 2004 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Національний науковий центр «Харківський фізико-технічний інститут» НАН України
2004
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/78976 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Discrete optimization problem / E.D. Kotina // Вопросы атомной науки и техники. — 2004. — № 1. — С. 147-149. — Бібліогр.: 3 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860160930695872512 |
|---|---|
| author | Kotina, E.D. |
| author_facet | Kotina, E.D. |
| citation_txt | Discrete optimization problem / E.D. Kotina // Вопросы атомной науки и техники. — 2004. — № 1. — С. 147-149. — Бібліогр.: 3 назв. — англ. |
| collection | DSpace DC |
| container_title | Вопросы атомной науки и техники |
| description | In the paper a mathematical model is considered that allows simultaneous optimization of a program motion and
an ensemble of perturbed motions. Analytical expressions for functional variations are suggested that help constructing various directed methods of optimization. Given mathematical apparatus can be effectively used in the optimization of the dynamics of charged particles in linear accelerators.
Запропонована математична модель оптимізації програмного руху (руху синхронної частки) і ансамблю обурених
рухів. Розглядаються мінімаксні функціонали, що дозволяють оцінювати динаміку часток по “найгіршим” частках.
Предлагается математическая модель оптимизации программного движения (движения синхронной частицы) и ансамбля возмущенных движений. Рассматриваются минимаксные функционалы, позволяющие оценивать динамику частиц по “наихудшим” частицам.
|
| first_indexed | 2025-12-07T17:54:34Z |
| format | Article |
| fulltext |
DISCRETE OPTIMIZATION PROBLEM
E.D. Kotina
Saint-Petersburg State University, Saint-Petersburg, RUSSIA
In the paper a mathematical model is considered that allows simultaneous optimization of a program motion and
an ensemble of perturbed motions. Analytical expressions for functional variations are suggested that help construct-
ing various directed methods of optimization. Given mathematical apparatus can be effectively used in the optimiza-
tion of the dynamics of charged particles in linear accelerators.
PACS: 517.97:621.384.6
1. INTRODUCTION
Discrete problems of control are important in the
theory and practice of optimal control, because many
problems are described exactly by differential equa-
tions. In practice the information on the stage of the pro-
cess comes in discrete moments of time and the control
of the process also comes step by step.
Problems of control in discrete systems received at-
tention of many researches. Two approaches to the
problem can be found. The first approach is based on
the Bellman principle of optimality. The second one is
the variational approach which links to the apparatus
principle of L.S. Pontryagin.
Conventional formulations of optimal control prob-
lems are quite known and they had been studied quite
well [1]. These problems can be considered as problems
of control of particular trajectories. At the same time, in
works of D.A.Ovsyannikov such methods of optimal
control and optimization of ensemble of trajectories or
beam trajectories have been developed [2].
Let us note that the problems of control of ensemble
of trajectories naturally emerge under the study of opti-
mization of charged particle beam dynamics in acceler-
ating and focusing structures.
2. MATHEMATICAL MODEL
Let particle dynamics be given by a difference equa-
tion system:
==+ ),,()1( uxkfkx
−=−−
=
1,,2)),(),2(),1(),(,(
1,0)),(),(,(
2
1
Nkkukxkxkxkf
kkukxkf
(1)
−=
−−
=
==+
.1,,2
)),(),2(),...,(),2(),...,(,(
1,0)),(),(),(,(
),,,()1(
2
1
Nk
kukykykxkxkF
kkukykxkF
uyxkFky
(2)
Here )(kx is the −n dimensional phase vector defining
the program motion, )(ky is the −m dimensional phase
vector defining the perturbed motion, )(ku is the −r
dimensional control vector; ),,( uxkf is the −n dimen-
sional vector function defining the process dynamics at
each step. For all { }Nk ,,1,0 ∈ the vector function
),,( uxkf is assumed to be definite and continuous on
)(kUx ×Ω in all its arguments ),( ux along with partial
derivatives with respect to these variables.
))(),(),(,( kukykxkF is the −m dimensional vector
function, for all { }Nk ,,1,0 ∈ it is assumed to be defi-
nite and continuous on )(kUyx ×Ω×Ω in all its argu-
ments ),,( uyx along with partial derivatives with re-
spect to these variables and second partial derivatives
,,,
222
ki
l
mi
l
ji
l
uy
F
xy
F
yy
F
∂∂
∂
∂∂
∂
∂∂
∂
;,,2,1, mil =
;,,2,1 nm = .,,2,1 rk =
Here xΩ is the region in nR , yΩ is the region in mR ,
1,,1,0),( −= NkkU is the compact set in .rR In this
case we consider the Jacobian
)(
))(),(),(,())(),(),(,(
ky
kukykxkFkukykxkJJ k ∂
∂==
to be nonzero for all changes of ).(),(),(, kukykxk
The given type of system (1)-(2) is determined by
the kind of discrete equations which can be described as
the motion of charged particles in accelerator with drift
tubes [2]. System (1)-(2) can be reduced to
)).(),(),(,()1(
)),(),(,()1(
kukykxkFky
kukxkfkx
=+
=+
However, this is not useful as this leads to the rise of
steps of phase vectors and the loss of physical sense of
beam trajectories.
We assume, that 0)0( xx = is fixed and the initial
state of the system (2) is described by the set −0M a
compact set of nonzero measure in mR . Let us call the
sequence of vectors { })1(,),1(),0( −Nuuu as the con-
trol of the system (1)-(2) and denote it by u for brevity.
Its associated sequence of vectors { })(,),1(),0( Nxxx
is called the trajectory of program motion and is de-
noted by ),( 0 uxxx = . Denote by ),,()( 0 uxkxkx = the
phase state of the program particle at k th step. Simil-
arly, let us call the sequence of vectors
{ })(,),1(),0( Nyyy as the trajectory of perturbed mo-
tion and denote it by ),,( 0 uyxyy = . Denote by
),,,()( 0 uyxkyky = the phase state of the particle at the
k -th step.
The set of trajectories ),,( 0 uyxy corresponding to
the initial state 0x , the control u and different states
00 My ∈ will be referred to as a bundle of trajectories
or simply the bundle. The phase state of beam at the k
___________________________________________________________
PROBLEMS OF ATOMIC SIENCE AND TECHNOLOGY. 2004. № 1.
Series: Nuclear Physics Investigations (42), p.147-149. 147
th step is also called as the cross section of the bundle of
trajectories and is denoted by ukM , , i.e.
{ } ,),,,,()(:)( 000, MyuxykykykyM uk ∈==
the controls satisfying conditions
1,,1,0),()( −=∈ NkkUku are admissible.
We introduce the following functionals:
,)()()(
1
1
1 ∑
−
=
+=
N
k
NNNkkk xgcxgcuI (3)
∫∑ ∫ +=
−
= uNuk M
NN
N
k M
kkkkk dyygdyuyxuI
,,
)(),,()(
1
1
2 ϕ , (4)
)()()( 21 uIuIuI += (5)
characterizing the phase state of the bundle of trajecto-
ries and the control parameters. Here ),(kxxk =
,)( ,ukk Mkyy ∈= the function kϕ is defined and con-
tinuous on )(kUyx ×Ω×Ω for all k in all its argu-
ments together with partial derivatives with respect to
yx, and u ; kg is continuously differentiable function
defined in xΩ for all k ; g is a continuously differenti-
able function defined in yΩ , kc is constant for all k .
Functional (3) characterizes the dynamics of the pro-
gram motion, functional (4) characterizes the dynamics
of the ensemble of perturbed motions, while functional
(5) allows simultaneous estimation of the program and
perturbed motions as well as their simultaneous optim-
ization. We will consider the functional minimization
problem for all admissible controls.
3. VARIATION OF FUNCTIONAL
Let us consider the admissible control u and u~ .
Their associated trajectories are denoted by ),( 0 uxx
and )~,(~
0 uxx , and associated trajectories of perturbed
motions are denoted by
),,( 0 uyxy и )~,,~(~
0 uyxy . (6)
The difference )()(~)( kukuku −=∆ is called the varia-
tional of the control u at the k th step, difference
),,()~,,(~),()( 00 uxkxuxkxxkxkx k −=∆=∆ is called
the trajectory increment ),( 0 uxx at the k th step, and
the difference
),,()~,,~(~),()( 00 uyxyuyxyykyky k −=∆=∆ is called
the trajectory increment of perturbed motion at the k th
step. With u∆ and yx ∆∆ , referred to as the variation
of control u and the increments of trajectories of
),( 0 uxx and ),,( 0 uyxy respectively. It is evident
that, by the common properties of continuity 0→∆ x
as 0→∆ u , and 0→∆ y as 0→∆ u uniformly in
00 My ∈ , )(max
1,,1,0
kxx
Nk
∆=∆
−= , here
))(),(()( kxkxkx ∆∆=∆ . The norm y∆ and norm
u∆ are defined in a similar manner.
Let us denote variations of trajectories of the system
(1) − (2) as )(),( kykx δδ at admissible variation of con-
trol u∆ and given u .
Now we will write down for system (1) − (2) ac-
cording equations in variations:
),(
)(
)(
)(
)(
)(
)1( ku
ku
kfkx
kx
kfkx ∆
∂
∂
+
∂
∂
=+ δδ 1,0=k
),(
)(
)()2(
)2(
)(
)1(
)1(
)()(
)(
)()1(
ku
ku
kfkx
kx
kf
kx
kx
kfkx
kx
kfkx
∆
∂
∂+−
−∂
∂
+−
−∂
∂+
∂
∂=+
δ
δδδ
1,,2 −= Nk , (7)
),(
)(
)()(
)(
)()(
)(
)()1( ku
ku
kFky
ky
kFkx
kx
kFky ∆
∂
∂+
∂
∂+
∂
∂=+ δδδ
1,0=k ,
+−
−∂
∂+−
−∂
∂+
∂
∂+
−
−∂
∂+−
−∂
∂+
∂
∂=+
)2(
)2(
)()1(
)1(
)()(
)(
)(
)2(
)2(
)()1(
)1(
)()(
)(
)()1(
ky
ky
kFky
ky
kFky
ky
kF
kx
kx
kFkx
kx
kFkx
kx
kFky
δδδ
δδδδ
),(
)(
)( ku
ku
kF ∆
∂
∂
.1,,2 −= Nk (8)
In this case, xx δ−∆ and yy δ−∆ are infinitesimals
of higher order than u∆ .
Let us consider the mapping of the set ukM , into the
set ukM ~, that is defined by the trajectories (6) emanat-
ing from the same points of the set 0M . Denote it by
)(~~
kk yyy = . (9)
Let us write down the Jacobian of this transformation
[2]:
( ),),(),(1
~
det kky
k
k ykyoykydiv
y
y
∆+∆+=
∂
∂
where ∑
= ∂
∆∂=∆
m
i i
i
ky ky
kykyykydiv
1 )(
))(,()),( .
Furthermore, by the above assumptions,
( )uoykydivykydiv kyky ∆=δ−∆ ),(),( is uniform
with respect to Nk ,,2,1 = and 00 My ∈ .
Similarly [2], it is easy to show, that there take place
following relationships:
,)(
)(
)(
)(
)(
)(
)()1(
1
∆
∂
∂+
∂
∂+
∂
∂
+=+
− ku
ku
Jkx
kx
Jky
ky
JJ
kydivkydiv
kkk
k
yy
δδ
δδ
1,0=k ,
+
∂
∂
+=+ − )(
)(
)()1( 1 ky
ky
JJkydivkydiv k
kyy δδδ
+
∂
∂
+−
−∂
∂
+−
−∂
∂
)(
)(
)2(
)2(
)1(
)1(
kx
kx
Jky
ky
Jky
ky
J kkk δδδ
,)(
)(
)2(
)2(
)1(
)1(
∆
∂
∂
+−
−∂
∂
+−
−∂
∂
+ ku
ku
J
kx
kx
J
kx
kx
J kkk δδ
1,,2 −= Nk . (10)
Taking into account equations (7), (8), (10) and
initial values of variations ,0)0(,0)0( =δ=δ yx
148
,0)0( =ydivyδ and using the methods of investigation
of functionals of types (3)-(5), presented at the works
[1-2, 4] variations of functionals (3)-(5) (at admissible
variation of control u∆ ) can be represented in the fol-
lowing form:
),(
)(
))(),(,(
)1(
1
0
1 ku
ku
kukxkfkI
N
k
T ∆
∂
∂
+= ∑
−
=
ξδ (11)
where )(kξ is the following auxiliary function:
,
)(
)(
)(
)()1()(
kx
xg
c
kx
ifik kk
k
m
ki
TT
∂
∂
+
∂
∂+= ∑
=
ξξ
here
3,,2,1
2,1
,2
,1
−=
−−=
+
−
=
Nkпри
NNkпри
k
N
m
,1,,2,1 −= Nk
with the terminal condition ,
)(
)(
)(
Nx
xgcN NN
N
T
∂
∂
=ξ
)(kξ n -vector;
+
∂
∂++
∂
∂+= ∑ ∫
−
= )(
)()1(
)(
)()1(
1
0
2
,
ku
kfkJ
ku
kFkpJI T
k
N
k M
T
j
uk
γδ
),(
)(
))(),(),((
)(
)1( kudy
ku
kukykx
ku
Jkq k
kk ∆
∂
∂+
∂
∂+ ϕ
(12)
here )(),(),( kkpkq γ are the following auxiliary func-
tions:
,)1()( kk kqJkq ϕ++=
,
)(
))(),(),((
)(
)()1(
)(
)1()(
1
ky
kukykx
ky
iFipJ
ky
JiqJkp
k
m
ki
i
kj
T
j
i
m
ki
i
kj
j
T
∂
∂+
∂
∂+
+
∂
∂+=
∑ ∏
∑ ∏
= =
=
−
=
ϕ
+
∂
∂+= ∑ ∏
=
−
=
m
ki
i
kj
i
j
T
kx
JiqJk
1
)(
)1()(γ
+
∂
∂++
∂
∂+∏ ∏
= =
i
kj
i
kj
T
j
T
j kx
ifiJ
kx
iFipJ
)(
)()1(
)(
)()1( γ
,
)(
))(),(),((
ky
kukykxk
∂
∂ ϕ
here
−−=−
−=+
=
1,2,1
3,,1,2
NNkN
Nkk
m
,
if ,1−> ik then let be 1
1
=∏
−
=
i
kj
jJ ;
with the terminal conditions:
,0)(),()(,
)(
)()( =γ=
∂
∂= NygNq
Ny
ygNp N
NT
here )(kγ is the n -vector, )(kp is the m -vector, )(kq
is the scalar.
The variation of functional (5) has the following form:
.21 III δδδ += (13)
The relationships (11), (12) can be written in the follow-
ing form
,11 ugradII ∆=δ ,22 ugradII ∆=δ
where ,
)1(
)1()(,,
)1(
)0()1(1
−∂
−∂
∂
∂=
Nu
NfN
u
fgradI TT ξξ
and components of 2gradI will be integrals on ukM , of
corresponding expressions in brackets in formula (12).
Obviously, the sum of these gradients will be the gradi-
ent of functional (5).
The representation of functional variations (11)-(13)
allows constructing a variety of directional methods of
optimization for functionals (3)-(5). In particular, we
can use the gradient methods of optimization.
4. CONCLUSION
In this paper we considered the mutual optimization
of a particular trajectory and the ensemble of trajecto-
ries. Analytical representations for variations of exam-
ined functionals were found. Note that we often find ne-
cessity of joint optimization in solving various opti-
mization problems, in particular, in the problems of
charged particle beam dynamic optimization in linear
accelerators [3].
5. ACNOWLEDGEMENTS
The Russian Fond of Fundamental Researches, pro-
ject 03-01-00726, supported this work.
REFERENCES
1. A.I.Propoy. Elements of the Theory of Optimal
Discrete Processes // Nauka publishing house. M.;
1973 (in Russian)
2. D.A.Ovsyannikov. Modelling and Optimization of
Charged Particle Beam Dynamics. Leningrad State
University publishing house, Leningrad, 1990 (in
Russian)
3. B.I.Bondarev, A.P.Durkin, A.D.Ovsyannikov. New
Mathematical Optimization Models for RFQ Struc-
tures // Proc. of Particle Accelerator Conference,
New York. 1999, p.2808-2810,
ОПТИМИЗАЦИЯ В ДИСКРЕТНЫХ СИСТЕМАХ ПРИ МИНИМАКСНОМ КРИТЕРИИ
Е.Д. Котина
Предлагается математическая модель оптимизации программного движения (движения синхронной частицы) и ан-
самбля возмущенных движений. Рассматриваются минимаксные функционалы, позволяющие оценивать динамику ча-
стиц по “наихудшим” частицам.
ОПТИМІЗАЦІЯ В ДИСКРЕТНИХ СИСТЕМАХ ПРИ МІНІМАКСНОМУ КРИТЕРІЇ
Є.Д. Котина
___________________________________________________________
PROBLEMS OF ATOMIC SIENCE AND TECHNOLOGY. 2004. № 1.
Series: Nuclear Physics Investigations (42), p.147-149. 149
Запропонована математична модель оптимізації програмного руху (руху синхронної частки) і ансамблю обурених
рухів. Розглядаються мінімаксні функціонали, що дозволяють оцінювати динаміку часток по “найгіршим” частках.
150
Discrete Optimization Problem
1. Introduction
Е.Д. Котина
|
| id | nasplib_isofts_kiev_ua-123456789-78976 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1562-6016 |
| language | English |
| last_indexed | 2025-12-07T17:54:34Z |
| publishDate | 2004 |
| publisher | Національний науковий центр «Харківський фізико-технічний інститут» НАН України |
| record_format | dspace |
| spelling | Kotina, E.D. 2015-03-24T15:35:06Z 2015-03-24T15:35:06Z 2004 Discrete optimization problem / E.D. Kotina // Вопросы атомной науки и техники. — 2004. — № 1. — С. 147-149. — Бібліогр.: 3 назв. — англ. 1562-6016 PACS: 517.97:621.384.6 https://nasplib.isofts.kiev.ua/handle/123456789/78976 In the paper a mathematical model is considered that allows simultaneous optimization of a program motion and
 an ensemble of perturbed motions. Analytical expressions for functional variations are suggested that help constructing various directed methods of optimization. Given mathematical apparatus can be effectively used in the optimization of the dynamics of charged particles in linear accelerators. Запропонована математична модель оптимізації програмного руху (руху синхронної частки) і ансамблю обурених
 рухів. Розглядаються мінімаксні функціонали, що дозволяють оцінювати динаміку часток по “найгіршим” частках. Предлагается математическая модель оптимизации программного движения (движения синхронной частицы) и ансамбля возмущенных движений. Рассматриваются минимаксные функционалы, позволяющие оценивать динамику частиц по “наихудшим” частицам. The Russian Fond of Fundamental Researches, project 03-01-00726, supported this work. en Національний науковий центр «Харківський фізико-технічний інститут» НАН України Вопросы атомной науки и техники Динамика пучков Discrete optimization problem Оптимізація в дискретних системах при мінімаксному критерії Оптимизация в дискретных системах при минимаксном критерии Article published earlier |
| spellingShingle | Discrete optimization problem Kotina, E.D. Динамика пучков |
| title | Discrete optimization problem |
| title_alt | Оптимізація в дискретних системах при мінімаксному критерії Оптимизация в дискретных системах при минимаксном критерии |
| title_full | Discrete optimization problem |
| title_fullStr | Discrete optimization problem |
| title_full_unstemmed | Discrete optimization problem |
| title_short | Discrete optimization problem |
| title_sort | discrete optimization problem |
| topic | Динамика пучков |
| topic_facet | Динамика пучков |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/78976 |
| work_keys_str_mv | AT kotinaed discreteoptimizationproblem AT kotinaed optimízacíâvdiskretnihsistemahprimínímaksnomukriteríí AT kotinaed optimizaciâvdiskretnyhsistemahpriminimaksnomkriterii |