Design optimization algorithms and tools
Introduction to algorithms
and programming
ME 564/SYS 564
Wed Sep 12, 2018
Steven Hoffenson
Goal of Week 3: To learn some basic derivative-free algorithms and get
experience using Excel Solver and MATLAB for optimization
1
Teams
Team I Team 1 Team A Gold Team
Siyi Jack Remy Marta
Junlin Nick O. Nick D. Alkim
Siyuan Joe Yu Candace
Raif
2
Human-powered
washing machine
Front-line logistics
RC airplane?
Rifle cartridge?
3D printer?
Management system
Car (autonomous)?
Power system?
Common
interests
Take some time to do re-introductions, discuss interests and competencies
in these topics, discuss team norms/meetings.
Then, work on your decomposition and modeling strategy. What are the
objectives, constraints, and variables for the system and subsystems, and
how will you evaluate the impact of inputs on outputs? This is not
something that we will explicitly cover in this class.
Racing shell
RC airplane?
3D printer?
Recap: Optimization formulation
3
Variables
Objective
function
Parameters
Constraints
“negative null” form
A solution should tell us
the optimal value of the
objective, 𝑓∗, as well as
the optimizers—the
values 𝒙∗ that achieve 𝑓∗
Take a few minutes to discuss in your teams
how you will model your f’s, g’s, and h’s
Recap: Explore the problem space
• Does a solution exist? (feasibility)
• Is the problem well-bounded?
• Are the constraints active?
• Are the functions monotonic?
• Can the formulation be simplified?
Answering these questions can help detect
formulation errors and save time (and sometimes
solve the problem!)
4
Recap: How to optimize
1. Formulate the problem
a) Define system boundaries
b) Develop analytical models
c) Explore/reduce the problem space
d) Formalize optimization problem
2. Solve the problem
a) Choose the right approach/algorithm
b) Solve (by hand, code, or software)
c) Interpret the results
d) Iterate if needed
5
𝐱𝑘+1 = 𝐱𝑘 − 𝐇(𝐱𝑘)
−1𝛁𝑓 𝐱0
(Weeks 1-2, 4, 9-12)
(Weeks 3, 5-8, 12)
TODAY
Today’s topics
• Linear programming
• Properties
• Three ways to solve
• Practice using Excel
• Derivative free algorithms
• Coordinate/pattern search
• Space-filling search
• Downhill random search
• MATLAB programming exercise
6
Linear programming
If 𝑓, 𝑔, and ℎ are all linear functions, we have a
linear programming problem
7
𝑥
𝑦
𝒈𝟑
𝒈𝟐
𝒈𝟒
𝒈𝟏
Method 1: Graphing
8
𝑥
𝑦
𝒈𝟑
𝒈𝟐
𝒈𝟒
𝒈𝟏
direction of
improving
objective
𝒇𝟏
𝒇𝟐
𝒇𝟑
This is challenging
for 3 variables and
impossible for 4+
We can see that the optimizer
is the intersection of 𝑔1 and
𝑔2, so we just need to solve 2
equations of 2 unknowns
Method 2: Monotonicity Analysis
9
min
𝑥,𝑦
𝑓 𝑥−, 𝑦− = −2𝑥 − 𝑦
s. t. 𝑔1 𝑥
+, 𝑦+ =𝑥 + 2𝑦 − 8 ≤ 0
𝑔2 𝑥
+, 𝑦− = 𝑥 − 𝑦 − 1.5 ≤ 0
𝑔3 𝑥
− = −2𝑥 + 1 ≤ 0
𝑔4 𝑦
− = −2𝑦 + 1 ≤ 0
From MP1, we know 𝑔1 must be active!
𝑦 = 4 − 0.5𝑥
min
𝑥,𝑦
𝑓 𝑥− = −1.5𝑥 − 4
s. t. 𝑔2 𝑥
+ = 1.5𝑥 − 5.5 ≤ 0
𝑔3 𝑥
− = −2𝑥 + 1 ≤ 0
𝑔4 𝑥
+ = 𝑥 − 7 ≤ 0
Which
dominates?
𝑥 ≤ 3.67 or
𝑥 ≤ 7
Because 𝑥 ≤ 3.67 is
stronger, 𝑔2 is the
active one
So, 𝑥∗ = 11/3
𝑦∗ = 13/6
𝑓∗ = −19/2
Method 3: LP algorithm
Note: The Simplex Algorithm is a standard method in
linear algebra to do this using slack variables and pivot
tables; this is an equivalent matrix algorithm:
1. Start with a point at the vertex of the feasible design
space (an x that lies at the intersection of n
constraints, where n is the number of variables);
these active constraints form the active set
2. Choose a direction to move for improvement, and
move to an adjacent, better extreme point; this
results in swapping one constraint in the active set
3. Repeat (2) until no more improvement can be found
10
Linear program properties
11
1. All objectives and constraints
are monotonic
2. Solutions will always be at
vertices of the feasible space,
or along an entire
edge/face/hyperplane section
min
𝒙
𝒄𝑇𝒙
s.t. 𝒉 = 𝑨1𝒙 − 𝒃1 = 0
𝒈 = 𝑨2𝒙 − 𝒃2 ≤ 0
c is a vector of parameters in
the objective function
𝑨𝟏, 𝑨𝟐, 𝒃𝟏, 𝒃𝟐 are matrices & vectors
of parameters in the constraints
Exercise: Excel Solver
Together, we will
do the example
from before:
12
Then, try it out on your own on the below:
Derivative-free search
algorithms
“Smart” ways to search the design
space based on heuristics or intuitive
rules
13
Derivative-free search
• Pattern search (Hooke-Jeeves, MADS, GPS)
• Space-filling search (DIRECT)
• Downhill random search (Simulated Annealing)
14
Note: Section 7.2 also includes Genetic Algorithm and Particle
Swarm Optimization – we will cover those in a few weeks
Coordinate search
1. Pick a start point 𝑥0
2. Test points some distance 𝑑 away from the current point in many
directions within the variable space
3. When a better point is found, move there and repeat (2)
4. If no better point is found, decrease 𝑑 and go back to (2)
5. When 𝑑 is small enough, quit
15
Hooke-Jeeves direct search
Kramer, O., Echeverría Ciaurri, D., and Koziel, S. (2011) “Derivative-Free Optimization”, in S. Koziel and X.S. Yang (Eds.)
Computational Optimization, Methods and Algorithms, Series: Studies in Computational Intelligence, Springer, pp. 61-83, 2011.
Coordinate search in action
16By Guillaume Jacquenot – Own work, CC BY-SA 3.0,
https://commons.wikimedia.org/w/index.php?curid=6439859
Generalized Pattern Search (GPS)
This is an extension of Hooke-Jeeves to include a global
search step
1. Pick a starting point and mesh/step size
2. Global search: Create mesh over design space and
evaluate the objective at some points in mesh
3. Local poll: Search in some pre-defined set of
directions from current best point
4. If no improvements found, reduce mesh/step size
and repeat
5. Continue until mesh spacing small enough or max
iterations met
17
Nelder-Meade algorithm
Applies simplex concepts to non-LP problems:
1. Define a simplex (an n+1-sided, n-dimensional “polygon”),
and evaluate the objective at each vertex
2. Identify the best side, and transform the simplex around
that side: Reflect, expand, or contract, depending on how
good the reflection point is compared to the others
3. Stop when the vertices are close enough (in the design or
objective space) or when you’ve done too many iterations
18
when
𝑓𝑙 ≤ 𝑓𝑟 < 𝑓𝑠
when 𝑓𝑟 < 𝑓𝑙
and 𝑓𝑒 < 𝑓𝑟
when 𝑓𝑠 ≤ 𝑓𝑟 < 𝑓ℎ
and 𝑓𝑐 ≤ 𝑓𝑟
when 𝑓ℎ ≤ 𝑓𝑟
and 𝑓𝑐 < 𝑓ℎ
otherwise
Pattern/direct search – Pros/cons
19
Advantages
• Conceptually straightforward
• Deterministic (repeatable)
• Tend to converge on a local optimum
• No need for derivatives or other problem information
Disadvantages
• Must identify a feasible starting point or points
• Dimensionality: Cost increases with many variables
• Slow local convergence
• No global exploration
• Not particularly efficient, since you may be evaluating
functions in obviously “bad” directions
Space-filling: DIRECT
20
http://hosting.cs.vt.edu/hpcs2008/HPCS08DIRECTtut.pdf
DIRECT =
Dividing
Rectangles
Iteration 1234
DIRECT with Two Variables
Rectangle size
f(x)
figures from John Whitefoot, 2010 lecture
Each iteration selects rectangles
to further divide based on:
1. Function value (low)
2. Rectangle size (large)
3. Constraint violation (low)
21
DIRECT – Pros/Cons
Advantages
• Systematic search balances local and global search
• Can be re-started where you left off
• Deterministic (repeatable)
• No parameters to tune
• Can handle integers and equality constraints
• Very robust
Disadvantages
• Dimensionality: Struggles with many (e.g., >10) variables
• Slow local convergence
22
Simulated Annealing (SA) overview
• Based on cooling metals: Seeking lowest energy state
• Performs random search with some probability of
accepting worse point (to search globally)
• Probability of accepting worse point based on
Metropolis criterion, which decreases over time
Temp
time
T
f
fp exp)(
23
Simulated Annealing Algorithm
Flowchart
yes
Initial point, x0
Algorithm
Core
Reduce temperature
Reduce max. step size
Termination criteria
satisfied?
Set current point
to optimum
START
END
no
Stay at xn
Initial point, x0
Make current point, xn
Random step to xn+1
Evaluate xn+1
Is xn+1 better
than xn?
Accept Point?
(based on Metropolis
criterion)
Is xn+1 better than
current optimum?
Record new
optimum
yes
no
no
yes
no
yes
24
Simulated Annealing – Pros/Cons
Advantages
• Doesn’t need to systematically cover the space – can be
more efficient for high-dimension problems
Disadvantages
• Highly dependent on starting point
• Doesn’t always cover the design space (local)
• Random search not very “smart”
• Can repeat areas already searched
• Can require many function evaluations
• Many parameters to tune that influence result
• Penalty function weights
• Temperature cooling schedule
25
Constraint handling
Penalty functions are an easy way to add constraints
26
Penalty Functions for Constraints
When algorithm doesn’t specifically handle
constraints, can add them to the objective via a
penalty function
2
1
))(,0max()(),(min
m
i iiP
xgwxfPenaltyxf
Penalty
g(x)
0
-2 -1 0 1
Penalty
g(x)
0
-2 -1 0 1
Linear Quadratic
27
Summary
• Linear programs are special cases
• All functions monotonic
• Solutions must lie on boundary of design space
• Simplex algorithm is efficient
• Derivative-free algorithms for nonlinear problems
are straightforward and robust, but may take
longer and converge on local optima
• Coordinate search
• Nelder-Meade
• Space-filling DIRECT
• Simulated Annealing
28
Acknowledgements
• Much of this material came from Chapters 5.8, 7.1,
and 7.3 of the textbook, Principles of Optimal
Design
• Some of the slides and examples came from Dr.
John Whitefoot while he was at the University of
Michigan
29
MATLAB Programming:
Simulated Annealing code
• Based on cooling metals: Seeking lowest energy state
• Performs random search with some probability of accepting
worse point (to search globally)
• Probability of accepting worse point based on Metropolis
criterion, which decreases over time
30
T
f
fp exp)(
Temp
time
We will write a code
that does this in class