Development and Application of
Online Optimization Algorithms
Presented at NAPAC 2016

Xiaobiao Huang
SLAC National Accelerator Laboratory
October 14, 2016

Outline• Motivation- Beam based correction vs. beam based optimization- Manual tuning vs. automated tuning• Development and test of the RCDS algorithm- The RCDS algorithm- Test with SPEAR coupling correction: simulation and experiment- Usage of RCDS package- Performance stabilizer- AutoTuner• Applications of the RCDS algorithm• Other online optimization algorithms• SummaryX. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

2

Achieving optimal accelerator performance
The process:

The ideal scenario:

Accelerator design

All physics principles are known and included in themodel. Optimization in design is thorough and complete.

Build the machine
according to design

No mechanical (machining and alignment) and magnetic
errors.

Set set-points todesign values

Calibration is accurate. Monitors are accurate. No
variation with time or environment.

Machine in reality

Machine as built is identical to the design.

However, the reality is never ideal.
Solutions: (1) Beam-based correction.
(2) Beam-based optimization (tuning).
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

3

Beam based correction
Beam based correction: correct the operating condition of a subsystem toward theideal (design) condition through beam based measurements and a deterministic
procedure.
Actuators(knobs)Diagnostics(monitors)

Deterministic
methodTargetOrbit
correction

Orbit
correctors

BPMs

Orbit response
matrix

Ideal orbit

Opticscorrection

Quadrupole
correctors

Beta, phaseadvance, orbit
response matrix

Response
Design optics(Jacobian) matrix

What if any of diagnostics, deterministic method, or ideal target is missing?

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

4

Beam based optimization – tuning
Beam based optimization (tuning): adjust the operating condition to optimize
machine performance directly.
𝑥1𝑥2

𝑓1 (𝑥1 , 𝑥2 , … , 𝑥𝑛 )…

System𝑥𝑛
knobs

𝑓2 (𝑥1 , 𝑥2 , … , 𝑥𝑛 )PerformancemeasuresWe know the system works – changing input leads to performance responses.
But we don’t know exactly how it works – the functions are unknown.
Machine tuning is a multi-variable and (potentially) multi-objective
optimization process. The function(s) is evaluated through the machine.

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

5

Manual tuning vs. automated tuning
Manual tuning
Knob changing by humanhands, data processing
and decision making byhuman brain.

Automated tuning
Knob changing, dataprocessing, anddecision making all bycomputer.

Manual tuning

Automated tuning

Slow

Fast

Human dependent

Human independent

Limited to small problems(few knobs)

Scalable to large problems

Why isn’t automated tuning popular yet, long after machines arecompletely computer controlled?
Probably because of the lack of reliable, effective optimization algorithm.
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

6

Challenges to automated tuning algorithms• Noise – functions evaluated on machine have noise.
- Most of the traditional methods are designed for smooth functions.

• Efficiency- Need to converge to the optimum fast.

• Safety, reliability, robustness- Survive occasional outliers.
- Cause no disaster when machine mal-functions.

• (previous) Common auto-tuning algorithms- Iterative 1D scan, Downhill simplex*, Random tries*L. Emery et al, PAC2003, implemented 1D scan and the downhill simplex method.
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

7

The development of the RCDS algorithm• The development was motivated by the need to optimize
storage ring nonlinear beam dynamics.
- Correction of nonlinear dynamics is difficult – lack of direct diagnostics,
deterministic method, and even target.

• Robust conjugate direction search (RCDS)* performs
iterative search over conjugate directions with a robust(against noise), efficient line (1D) optimizer.
- The conjugate direction set may be updated with Powell’s method.
- The 1D robust optimizer is designed to deal with noise.

*X. Huang, J. Corbett, J. Safranek, J. Wu, “An algorithm for online optimization ofaccelerators”, Nucl. Instr. Methods, A 726 (2013) 77-83.

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

8

Search over conjugate directions
Efficient search directions: conjugate directions
A search over conjugate direction does notinvalidate previous searches.
Directions u and 𝐯 are conjugate if
𝐮T ⋅ 𝐇 ⋅ 𝐯 = 0
with 𝐇 being the Hessian matrix of function 𝑓(𝐱),

𝐻𝑖𝑗 =

𝜕2 𝑓
.
𝜕𝑥𝑖 𝜕𝑥𝑗

Around the minimum1
𝑓 𝐱 𝑚 + Δ𝐱 = 𝑓 𝐱 𝑚 + Δ𝐱 T ⋅ 𝐇 ⋅ Δ𝐱.

Inefficient search directions
It takes many tiny steps to get to theminimum when searching along 𝑥 and 𝑦
directions.

2

Powell’s method can update the directions
using past search results to develop a
conjugate set.

*W.H. Press, et al, Numerical Recipes*M.J.D. Powell, Computer Journal 7 (2) 1965 155

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

9Anatomy of a line optimizer that is sensitive to noiseLine optimizer – Brent’s method
Step 1: Initially bracketing the minimum.
Step 2: Successive interpolation to converge to the minimum.

Inverse quadratic interpolation (figure from Numeric Recipes*.)With noise, the comparison of values in both steps can go wrong and thealgorithm won’t converge.
*W.H. Press, et al, Numerical Recipes
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

10

The robust 1D optimizer
The robust optimizer is aware of noise in bracketing and uses noise level tofilter out outliers. Noise level is detected before optimization.
-0.5

objective-0.6

bracketingfill-infittednew minimum

-0.7
-0.8
-0.9
-0.06

Initial solution

X. Huang et al, Nucl. Instr.
Methods, A 726 (2013) 77-83.

-0.04

-0.02


0

0.02

Bracketing: step size is increased in the search. Bracket ends are higher thanminimum by 3 noise sigma.
Fitting: fill in additional points when necessary to better sample within the bracket
and then fit a parabola.
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

11

Implementation of RCDS
• Parameters are bounded and normalized to [0, 1]- Parameters in online optimization always have limited ranges.
- Keeping parameters within pre-defined ranges is a safety measure.
- Normalizing parameters makes algorithm code independent of actual
problems• Powell’s method of automatic updating of conjugate
direction set is implemented.
- In real life problems usually only a few directions are replaced before
terminating. So we hardly benefit from this procedure for online problems.

• The interface between the algorithm and a particularapplication is the objective function and a simple setup
script.
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

12

Testing the algorithm with a simulation problem
Testing problem: coupling correction for the SPEAR3 storage ring with skew
quadrupoles.
Objective: maximize beam loss over 6
seconds (Touschek loss rate ∝ 1/𝜎𝑦 ).
Knobs: 13 skew quads
Setup: (1) errors are added to 42 skew
quadrupoles. Initially all 13 correcting
skew quads are off, with coupling ratioof 0.9%.
(2) Noise level for loss rate is about
0.06 mA/min, with initial loss rate at 0.6
mA/min.
(3) Initial conjugate direction set is from
SVD of the Jacobian matrix of the orbit
response matrix w.r.t. skew quads.

Skew quadrupoles arecoils on sextupoles.

The SPEAR3 storage ring𝐉 = 𝐔𝐒𝐕 𝑇
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

Each column in 𝐉 is for a skew quad.
Conjugate directions are represented
by columns in 𝐕.
13

Simulation results for three direct search methods
POWELL-1

run1 6srun2 6srun3 60s
run4 no noise

-1.5
-2
-2.5
0

500

1500

2000

RCDS

-0.5

objective (mA/min)

1000
count

-1

run1 6srun2 6srun3 6srun4 no noise

-1.5
-2
-2.5
-3
0

500

1000
cnt

SIMPLEX-0.5

objective (mA/min)objective (mA/min)

-0.5

1500

2000

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

run1 6srun2 6srun3 6srun4 no noise

-1
-1.5
-2
-2.5
-3
0

500

1000
count

1500

2000

(1) Showing history of the best solution.
(2) The simplex method is efficient without
noise, but fails to reach the minimum withnoise.
(3) Powell’s method works without noise, but
fails with noise. The initial direction set are
individual skew quads.
(4) The RCDS method is efficient with orwithout noise.
The performances of algorithms for noisy
problems depends on the problems.
14

Detailed look of an RCDS run

Distance to best solution innormalized parameters.

History of objective

The algorithm converges fast but it does
not stay right at the minimum – it keeps
probing around.

History in parameter space

So usually we need to sort the solutions
and apply the best one to the machine.

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

15

Comparison of algorithm performancesBest performance for several algorithms

coupling ratio

10

-2

RCDS
simplex
Powell
IMAT
MOGA

10

-3

10

-4

0

History of best coupling ratio
500

1000
count

1500

2000

“IMAT”: iterative scan of each skew quad with the robust 1D optimizer.
The difference between “IMAT” and “RCDS” clearly shows the power of using
conjugate direction set for problems with highly coupled parameters.
Only “IMAT” and “RCDS” have steady gains toward the minimum – amanifest of the noise-resistance feature of the robust 1D optimizer.
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

16

Coupling correction experiments on SPEAR3 with RCDS
Using loss rate (normalized) as objective

Using 𝜎𝑦 from pinhole camera as objective

2-27-2013

0

all
best

60

-0.5
sigmay (um)-loss rate (mA/min)

6-17-2013

70

-1

all
best

50
40
30

-1.5
20

-2
0

50

100

count

150

200

250

10
0

50

100

15

current (A)quad strength
Beam loss rate is measured
by monitoringthe
10 Skew
beam current change on a5 6-second interval(no fitting). Noise sigma 0.04 mA/min. Data0were taken at 500 mA with 5-min top-off.

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

200

250

300

𝜎𝑦 noise level at 0.3 micron.
All 13 skew quads were off initially.

Pinhole camera resolution is limited.

-5

Initially all 13 skew quads-10were off.
At 500 mA, the best solution
had a lifetime of-15
4.6 hrs. This was better than the LOCO
-20
0
2
4
6
8
correction (5.2 hrs)
skew quad index

150
count

run 2-27-2013
run 3-26-2013
run 4-23-2013
LOCO 2-13-2013
LOCO 4-23-2013

10

12

14

17

Applications of RCDS on real-life problems• SPEAR3- Kicker bump matching- Transport line optics- Transport line steering- GTL steering and optics- Injection efficiency w/ sextupoles

X. Huang, J. Safranek, PRSTAB 18, 084001 (2015)• LCLS- Undulator taper optimization

J. Wu, K. Fang, X. Huang, 2014-2016• BEPC-II luminosity optimization- Steering and coupling- Interaction point beta

• ESRF

H. Ji, et al, Chinese Physics C 2015 Vol. 39 (12)S. M. Liuzzo, et al, IPAC’16, THPMR015- beam lifetime w/ sextupoles- Injection steering
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

18

Online dynamic aperture optimization for SPEAR3

Optimizing injection efficiency with
reduced kicker bump.
Knobs: 8 sextupole knobs – each knob isa pattern of 10 sextupole families that do
not change chromaticities.

DA was increased from 15.1 mm to20.6 mm by optimization.
Momentum aperture (MA) was notaffected.

X. Huang, J. Safranek, PRSTAB 18, 084001 (2015)
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

19

LCLS taper profile optimization
3.51

initial
best

3.5
3.49

K

3.48
3.47
3.46

All solutions tried in first run.

3.45
3.44
0

5

10

15
20
Undulator section

25

30

35

Knobs: 4 parameters that control the taper profile, two phase shifters.
For U1-U8, and U10-U15: Kj = K0 (1 – a0 j ) with j = 1,…,15
For U17-U33: Kj = K1 [1 – a1 (j - 16) – a2 (j – z2)2] with j = 17,…,33.
Objective: FEL photon beam intensity.
J. Wu, K. Fang, X. Huang, 2014
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

20

Recent result by Juhao Wu, 9/1/2016

SELF-SEEDING FEL OPTIMIZATION
5.5 KeV Self-seeding FEL
More than doubled
U17-U32 continuous function: does
not work well
Zig-zag taper profile: ~ 1 mJ in 10 fs
RCDS
Optimization

Starting
point

Knobs: 16
parameters that
control the taper
profile. For U17-U32:
each K is freely
optimized withbounds.
Objective: FEL
photon beam
intensity.

ESRF optimization of beam lifetime with sextupoles

Lifetime for the 16-bunch mode in one month
before and after optimization.

Objective: lifetime normalized by current, bunch length,and vertical size (average over 13 beam size monitors)
S. M. Liuzzo, et al, IPAC’16, THPMR015
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

22

The usage of the Matlab RCDS code
• A Matlab RCDS package is available, with instructions andexamples.
A Python version has also been developed and is available.
• The setup for a new problem is extremely simple:- Modify an objective function template• Make changes to knobs and take measurement of performance• Record data

- Modify a setup and launch script• House keeping: record initial parameters, set parameter ranges• Measure and specify noise level (only needed once)• Launch RCDS
• Sort solutions and apply the best solution.

--- S. M. Liuzzo, et al, IPAC’16
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

23

Some comments on RCDS
• RCDS is not simply a variation of Powell’s method- Yes, RCDS is implemented as Powell’s method with the new robust line
optimizer.
- But in online application one seldom benefits from conjugate direction update
because only limited directions are replaced.
- It is the robust line optimizer that gives rise to the effectiveness of RCDS.

• RCDS is not simple iterative parameter scan
- It works with combined knobs.
- Parameter scan usually have fixed scan ranges and pre-determined, uniform
step sizes. Choice of step size (or # of steps) is problem dependent.
- RCDS uses bracketing, variable step size, and quadratic fitting – a lot more
efficient.
- RCDS algorithm does not need problem-dependent setup.

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

24

A variant of RCDS to stabilize performance• We saw the need to stabilize performance for drifting
systems and developed and tested an RCDS stabilizer for it.
In this test thestabilizer were tuning
four steering magnets
at the end of the BTS.
When upstream
steering magnets
were manuallychanged, thestabilizer responded
and brought injection
efficiency back.

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

25

AutoTuner – An interactive GUI based on RCDS
• A GUI is substantially easier to use – increased productivity
and reduced training requirements.
• The code is completely re-written to allow interruption.
AutoTuner has beentested on SPEAR3
and its injector withmany knobs.

It supports single knob (PV or function) and multi-knob(combined knobs).
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

26

Other algorithms - Genetic algorithm (NSGA-II)• Genetic algorithm is inefficient even without noise.
NSGA-II

objective (mA/min)-0.4

run1 6srun2 10s
run3 no noise-0.6

Same SPEAR3 coupling correction
simulation problem.

-0.8

Population: 100; Ran 60 generations; 10%
mutation, 90% crossover.

-1

clogged
-1.2
0

1000

2000

3000
cnt

4000

5000

6000

• Noise gives a bias to the selection operation.
6s loss rate evaluation time

average error (mA/min)

0.02

Bad guys (solutions with favorable
random errors) tend to enter the next
generation. This prevents converging to
the true minimum.

Noise in the population
as it evolves.

0
-0.02
-0.04
-0.06
-0.08
-0.1
0

10

20

30
generation

40

50

60

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

X. Huang et al, Nucl. Instr.
Methods, A 726 (2013) 77-83.
27

Genetic algorithm and particle swarm algorithm
Online coupling correction with genetic algorithm
0Genetic algorithm

2

-50

1.5

-100

objective

normalized beam loss (count/mA2)

2.5

1

Particle swarm algorithm

-150
-200

0.5

-250
0

-0.5
0

Experiment by X. Huang, K. Tian (2014)

K. Tian, J. Safranek, Y. Yan, PRSTAB
17, 020703 (2014)
2

4

6

8

-300
0
10

500

1000

1500
cnt

2000

2500

3000

Time(hr)Using beam loss monitor signal (low noise) as
objective. It took 20,000 evaluations.

Same setup as the genetic algorithm
experiment. It took 3,000 evaluations.

… while RCDS only took 200 evaluations (see slide 17) for a much noisier setup.

When online global search is desired, it seems the particle swarm algorithm isa better choice: (1) more efficient; (2) no bias introduced by noise.
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

28

The Extremum Seeking (ES)* method• The ES method is theoretically elegant.
The optimization parameters (knobs) arerotated with various frequencies andamplitudes, and subject to modulation by
the cost function.
with

noise

At the high frequency limit, the behavior approaches that of a gradient descentmethodPros: (1) noise is averaged out; (2) a simple and general framework; (3) can dynamicallytrack the optimum.

Cons: (1) algorithm control parameters are problem specific and need tuning;(2) may not be as efficient as other direct search method (e.g. RCDS, simplex);(3) Parameter update rate is bounded, but parameters are not.
*A. Scheinker, M. Krstic, IEEE Trans. Automatic Control, 58, 1107 (2013).
A. Scheinker, M. Krstic, Systems & Control Letters, 63, 25 (2014)
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

29

Test of the ES method on SPEAR3*
The problem: injection kicker bump matching
Knobs: pulse amplitude, width, and delay of K1 andK2, and two skew quads – 8 knobs total.
Objective: residual oscillation of stored beam

objective

Illustration by A. Scheinker
knobs
3-25-2013, LE lattice250

RCDS result
X. Huang, et al, NIMA 726(2013) 77-83

objective (micron)

200
150
100
50

*A. Scheinker, X. Huang, J. Wu, SLAC-PUB-16508 (2016)
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

0
0

20

40

60
count

80

100

120

30

ES – dynamic tracking of the objective
In this test one parameter (K3 voltage, not an optimization variable) is varied, while
the ES algorithm serves as a feedback to make compensation.

The ability to maintain performance with a drifting system isimportant.
If there is no ES feedback
X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

31

Summary• Computer controlled systems can be optimized online
without a model or knowledge of system interior.
• The RCDS algorithm is a robust and efficient method foronline optimization, tested on many accelerator problems.

• Automatic tuning GUI and performance stabilizer based on
RCDS have been developed and tested.
• Other algorithms were also tested for online optimization.

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

32

Acknowledgements• Thanks to James Safranek for many helpful discussions.

• Thanks to users of RCDS that helped demonstrate themethod, especially- Juhao Wu (SLAC), Yi Jiao, Hongfei Ji et al (IHEP), S. M. Liuzzo et al (ESRF)

X. Huang, Online optimization algorithm,10/14/2016, at NAPAC'16

33