程序代写代做代考 Excel algorithm matlab Design optimization algorithms and tools

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