Introduction to Design Optimization
Formulating and
analyzing a problem
1
ME 564/SYS 564
Wed Sep 5, 2018
Steven Hoffenson
Goal of Week 2: To learn some strategies to analyze and reduce an optimization
formulation prior to solving
Recap: Class expectations
• Respect from everyone toward everyone
• Collaboration, learning, and helping each other
• Good discussions
• Ask questions when you have them
• Responsible phone/computer use
• Learn through practice
• Start on time (3:00pm) and take 1-2 breaks per session
2
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
3
𝐱𝑘+1 = 𝐱𝑘 − 𝐇(𝐱𝑘)
−1𝛁𝑓 𝐱0
(Weeks 1-2, 4, 9-12)
(Weeks 3, 5-8, 12)
TODAY
Recap: Important problem attributes
4
Quantity What it means Battery examples
Objectives
What we want to
maximize/minimize
Maximize capacity in kWh
Hard constraints
Must-haves, with specific
thresholds
Must meet safety standards
Soft constraints
Wants, with specific
thresholds
Weigh no more than 200 lb;
Capacity of at least 30 kWh; Volume
no more than 15 ft3; Cost no more
than $3,000
Variables Things we can change Dimensions, material choice, layout
Parameters
Quantities that we can’t or
won’t change
Material properties, e.g., density of
a particular lithium-ion battery;
thresholds of soft constraints
Example: Gas turbine
Objective(s) maximize (power out)/(fuel in)
Constraints power out must be at least 1 MW
total cost must be no more than $1M
Design variables air flow rate in, compressor ratio, fuel flow rate in
Parameters Inlet air temperature & pressure, fuel specific heat
Constants gas constant, gravity
5
Recap: Optimization formulation
6
Variables
Objective
function
Parameters
Constraints
“negative null” form
Negative null form
Positive null form
Negative unity form
𝐡 𝐱 = 𝟎
𝐠 𝐱 ≤ 𝟎
𝐠 𝐱 ≥ 𝟎
𝐡 𝐱 = 𝟎
𝐡 𝐱 = 𝟏
𝐠 𝐱 ≤ 𝟏
Example: Negative Null Form
Design an electric motor system with maximum
efficiency E(x) while power output Pout(x) must be
equal to P0 and maximum speed Vmax(x) must be at
least V0.
Original
maximize E(x)
w.r.t. x
subject to Pout(x)=P0
Vmax(x)≥V0
Negative null form
minimize –E(x) or 1/E(x)
w.r.t. x
subject to Pout(x)–P0 = 0
V0 –Vmax(x) ≤ 0
7
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
8
Design space
The “design space” refers to the feasible region
(satisfies the constraints) in the variable space
9
10
Design-objective space
Variables
𝒙𝟐 𝒙𝟏
𝒇(𝒙)
Objective
function
11
Design space – Example
𝑦
𝒈𝟏
Choose a point from the
orange triangular and plug it
into 𝑔1to make sure the
constraint is defined
correctly
e.g.(0,0) 0+2×0-8≤ 0
Constraint
𝑥
Note: x and y are both in
the design/variable space!
12
Design space – Example
𝑥
𝑦
𝒈𝟏
𝒈𝟐
13
Design space – Example
𝑥
𝑦
𝒈𝟑
𝒈𝟐
𝒈𝟒
𝒈𝟏
The intersection of
𝑔1, 𝑔2, 𝑔3, & 𝑔4
demonstrates the
feasible design space
Equality constraints
Often, we can eliminate these algebraically.
14
Equality constraints
• Some algorithms cannot
handle equality constraints
(efficiently)
• When possible, substitute
out the equality constraint
• Otherwise, you may be able
to direct it as an inequality
(we’ll discuss later)
15
Irrelevant variables
• Some variables or
constraints are not relevant
to the rest of the problem
• When possible, we can
come up with a closed form
equation for an irrelevant
variable and remove it
16
min
𝑥
𝑓 𝑥 = 𝑥 + 8𝑥2
s. t. ℎ 𝑥, 𝑧 = 𝑥 + 𝑧 − 3 = 0
min
𝑥
𝑓 𝑥 = 𝑥 + 8𝑥2
𝑧 = 3 − 𝑥
Variable 𝑧 is irrelevant, since it does not affect the rest of the problem
Note: Variables that do not appear in the objective function are often
relevant (we’ll show examples later in this lecture).
Feasibility and
Boundedness
Does a solution satisfying the constraints even exist?
Is there a finite optimal solution?
17
Feasibility
Consider the minimization problem:
18
Formally, we should
get this into negative
null form: Optimal solution
optimizer: x* = 18.8
optimum: f* = 0.59
A problem is well posed when a solution exists
(This problem is well-posed)
Feasibility
Consider the minimization problem:
19
No feasible solution
This problem is not well-posed
Regarding feasibility,
we want to know
whether a solution
exists
Feasibility
Consider the maximization problem:
20
Optimal solution
optimizer: x* = 10
optimum: f* = 20
Regarding feasibility,
we want to know
whether a solution
exists
This problem is well-posed
Feasibility
Is this problem well-posed?
21
min f(x) = x1+x2
w.r.t. x ∈ ℝ2
s.t. g(x) = x1
2 +1≤ 0
The feasible domain is empty.
This problem is not well-posed.
Boundedness
Consider the minimization problem:
22
No optimal solution
This problem is unbounded
For any real “solution”
you find (very high or
very low number), you
will always be able to
find something better.
Boundedness
Consider the design of a cylindrical pill:
23
Simplify:
r is unbounded from above and not well bounded from below
Lower bound and infimum
Lower bound: A number 𝑙 such that 𝑓(𝐱) ≥ 𝑙 for all
𝐱 in your domain
Infimum: the greatest lower bound; 𝑔 ≥ 𝑙 for all 𝑙
Argument of infimum: Value 𝐱 such that 𝑓 𝐱 = 𝑔
If all arguments of the infimum are in your domain,
then your minimization problem is well-bounded.
Note: We call the least upper bound of a model the supremum, with
a similar definition, which is relevant for maximization problems
24
Lower bound and infimum
x
f
f(x) = x2– 1
0
-1
-2
-3
Lower Bound
Lower Bound
Greatest Lower Bound (infimum)
Argument of infimum x = 0
25
Boundedness
Consider the following problem
What is the solution?
26
min f(x) = x
w.r.t. x ∈ 𝒫
Domain 𝒫: Positive real
numbers, i.e. 0 < x < ∞ x
f
f(x)=x
0
Infimum in 𝒫: f(𝐱) = g = 0
Arg. of infimum: 𝐱 = 0
Since 0 ∉𝓟, this problem is not well bounded
Boundedness
27
Unbounded
(minimization problem)
Not well bounded
(minimization problem)
No infimum exists No minimum exists
𝒙 ∈ ℝ
Boundedness
Since we normally have upper and lower bounds
(constraints) on variables, this is often not a problem –
the most common case is when we are minimizing in 𝒫
Here, since x > 0, we want x as close to 0 as possible…
but there is no minimum
28
Infimum – not minimum
𝒙 ∈ 𝓟
Exercise: Well bounded?
• Assume our domain is 𝒫 : Positive real numbers
i.e. 0 < x < ∞ x ff(x)=(x–1)2 – 1 Infimum in 𝒫: Arg. of infimum: -1 1 Since 1 ∈ 𝒫, well bounded0 2 -1 1 29 Exercises: Well Bounded? • Assume our domain is 𝒫 : Positive real numbers i.e. 0 < x < ∞ x ff(x)=(x2–1)2 Infimum in 𝒫: Arg. of infimum: 0 ±1 Since 1 ∈ 𝒫 but -1 ∉ 𝒫, not well bounded 0-1 1 All arguments must be in your domain for boundedness by definition 30 Well-posed vs well-bounded • A well-posed problem has feasible solutions in the domain • There are points that satisfy all constraints • We’re just talking about existence of a feasible design • A well-bounded problem has finite optimal solutions inside the domain • All arguments of the infimum must be in the domain • We’re talking about feasibility of optima 31 Constraint activity Can we simplify our problem formulation by identifying “active” inequality constraints? 32 Constraint activity A constraint is active if removing it changes the optimization result 33 Optimal solution optimizer: x* = 18.8 optimum: f* = 0.59 g(x) is active Constraint activity A constraint is active if removing it changes the optimization result 34 Optimal solution optimizer: x* = 10 optimum: f* = 20 g(x) is inactive Constraint activity A constraint is active if removing it changes the optimization result 35 minimize g1 g2 minimize g1 g2 g1 active, g2 active g1 active, g2 inactive Constraint activity A constraint is active if removing it changes the optimization result 36 minimize g1 g2 minimize g1 g2 g1 active, g2 active g1 active, g2 inactive Constraint activity A constraint is active if removing it changes the optimization result 37 g1 active, g2 inactive g1 g2 Constraint activity A constraint is semiactive if removing it adds to the existing set of optimizers 38 g1 g2 g1 semiactive, g2 inactive Solutions optimizers: χ* = {3, 4} optimum: f* = 1 Solutions to unconstrained problem optimizers: χ* = {1, 3, 4} optimum: f* = 1 Activity theorem Constraint gi is active if and only if f(Xi) < f(X*) I.e., the value of the objective at the minimizers of the relaxed problem is less than its value at the minimizers of the original problem Relaxed problem solution when gi is removed Original solution 39 Activity check Activity Definition Relaxation • Solve original problem • Remove constraint • Solve again • Check if optimum changes • Solve problem without constraint • Add constraint • Check if constraint violated If changed If violated Constraint is active 40 Active constraints • If active constraints are identified early you can reduce the problem size • Active: Equality • Semiactive: Do nothing • Inactive: Remove • When a solution to the constrained problem found: • Active constraints limit you from improving your solution further • If the active constraint bound is a parameter, examine the impact of this parameter to the solution • If an inequality constraint is satisfied equally is it active? • Not necessarily—think about min x2, s.t. x≥0 • This is very rare 41 Monotonicity analysis An easy way to identify active constraints 42 Monotonicity A function 𝑓(𝑥) is monotonically increasing with respect to a variable 𝑥 if: for every 𝑥2 > 𝑥1, 𝑓(𝑥2) > 𝑓(𝑥1)
43
Replace monotonically increasing with: Replace
2nd > with:
(strictly) monotonically increasing >
weakly monotonically increasing/non-decr. ≥
(strictly) monotonically decreasing <
weakly monotonically decreasing/non-incr. ≤
Other types of monotonicity
In all of these cases, we say the function is
monotonic with respect to 𝑥
𝑥
𝑓(𝑥)
Monotonic functions
f(x) = ex f(x) = –x3
f(x+) f(x–)
f(x) = x2
f( x? )
x ≥ 0 f(x+)
x < 0 f(x– )
44
Checking for monotonicity
Check 𝜕𝑓/𝜕𝑥𝑖:
• If 𝜕𝑓/𝜕𝑥𝑖 > 0 everywhere, then
𝑓 is strictly increasing w.r.t. 𝑥𝑖
• If 𝜕𝑓/𝜕𝑥𝑖 ≥ 0 everywhere, then
𝑓 is weakly increasing w.r.t. 𝑥𝑖
• If the sign of 𝜕𝑓/𝜕𝑥𝑖 flips, then
divide it into regions and
perform analysis on each region
separately
45
Monotonicity Theorem
If f(x) and the consistent constraint functions gi(x)
all increase weakly or all decrease weakly with
respect to x, the minimization problem domain is not
well constrained.
min f(x+)
s.t. g1(x
+) ≤ 0
g2(x
+) ≤ 0
g3(x
+) ≤ 0
min f(x–)
s.t. g1(x
–) ≤ 0
g2(x
–) ≤ 0
g3(x
–) ≤ 0
46
Monotonicity Theorem
f
g1
g2
−∞
All increase
min f(x+) = x
s.t. g1(x
+) = x–1 ≤ 0
g2(x
+) = x–2 ≤ 0
f
g1
g2
All decrease
∞
min f(x–) = –x
s.t. g1(x
–) = 1–x ≤ 0
g2(x
–) = 2–x ≤ 047
Monotonicity Principle 1 (MP1)
In a well-constrained minimization problem, every
increasing variable (in the objective) is bounded
below by at least one non-increasing active constraint
48
𝑥
𝑓(𝑥)
𝒈𝟏 𝒙 : 𝒙 − 𝟗 ≤ 𝟎𝒈𝟑 𝒙 :−𝒙 + 𝟓 ≤ 𝟎
𝒈𝟐 𝒙 : 𝒙 + 𝒇(𝒙) − 𝟏𝟎 ≤ 𝟎
𝒇 𝒙+ x increasing in objective
𝒈𝟏 𝒙
+
𝒈𝟐 𝒙
+
𝒈𝟑 𝒙
− x non-increasing, so
MP1 is satisfied
MP1
f
g1
g2𝑥∗ = −∞
Not
well constrained f
g1
g2
Active constraint
bounds from below
min f(x+) = x
s.t. g1(x
+) = x–1 ≤ 0
g2(x
+) = x–2 ≤ 0
min f(x+) = x
s.t. g1(x
–) = –x–1 ≤ 0
g2(x
+) = x–2 ≤ 0
𝑥∗ = −1
49
MP1 Example 1
Apply MP1 to the problem
min f = (1/3)(x1+1)
3 + x2
s.t. g1 = –x1+1 ≤ 0
g2 = –x2 ≤ 0
x1 x2
f + +
g1 –
g2 –
Monotonicity Table
Active with
respect to x1
Active with
respect to x2
g1=0, x1* = 1
g2=0, x2 * = 0
f* =8/3
50
MP1 Example 2
Apply MP1 to the problem
max f = x1 – x2
s.t. g1 = x1+3×2 – 10 ≤ 0
g2 = –x1 – 4×2+2 ≤ 0
g3 = –2×1 + 7×2 – 8≤ 0
x1 x2
–f – +
g1 + +
g2 – –
g3 – +
Monotonicity Table
Negative null form
Active w.r.t. x1
51
MP1 Example 2
Eliminate x1 using g1
min –f = –x1 + x2
s.t. g1 : x1 = –3×2 + 10
g2 = –x1–4×2+2 ≤ 0
g3 = –2×1 + 7×2 – 8≤ 0
x2
–f +
g2 –
g3 +
Monotonicity Table
Negative null form
Active w.r.t. x2
min –f = 4×2 – 10
s.t. g2 = –x2 – 8 ≤ 0
g3 = 13×2 – 28≤ 0
52
Critical constraints
A constraint is critical for 𝒙 in a well-constrained
minimization problem if 𝑥 is increasing in the
objective and all other constraints
53
𝑥
𝑓(𝑥)
𝒈𝟏 𝒙 : 𝒙 − 𝟗 ≤ 𝟎
𝒈𝟐 𝒙 : 𝒙 + 𝒇(𝒙) − 𝟏𝟎 ≤ 𝟎
𝒈𝟑 𝒙 :−𝒙 + 𝟓 ≤ 𝟎
𝒇 𝒙+ x increasing in objective
𝒈𝟏 𝒙
+
𝒈𝟐 𝒙
+
𝒈𝟑 𝒙
− x non-increasing, so
this constraint is uniquely
critical
Monotonicity Principle 2
54
In a well-constrained minimization problem, every relevant
nonobjective variable is bounded both:
1. below by at least one non-increasing semiactive constraint, &
2. above by at least one non-decreasing semiactive constraint.
min f(x1
+)
s.t. g1(x1
+, x2
–) ≤ 0
g2(x1
–, x2
+) ≤ 0
MP2 Example 1
In a well-constrained minimization problem, every relevant
nonobjective variable is bounded both:
1. below by at least one non-increasing semiactive constraint, &
2. above by at least one non-decreasing semiactive constraint.
55
𝑭
𝒍 𝒘
𝒉
𝑬 = Young’s modulus
MP1: 𝒘,𝒉
MP2: 𝒍
MP2: 𝑬
With monotonicity analysis, we can identify appropriate constraints
to turn an unbounded problem into one that is solvable
uniquely
critical
multiply
critical
Equality constraints
• When possible, substitute out the equality
constraint
• Otherwise, you can direct it as an inequality
56
Summary
• Identify if your problem is well-posed and well-
bounded before attempting to solve
• Substitute out equality constraints when possible
• Identify inequality constraint activity (or inactivity)
to reduce the problem
• Monotonicity analysis is an easy way to identify
active constraints early on to:
• Reduce (and potentially solve) the problem
• Ensure the problem is well-bounded
57
Acknowledgements
• Much of this material came from Chapter 3 of the
textbook, Principles of Optimal Design
• Some of the slides and examples came from Emrah
Bayrak, Alex Burnap, and Namwoo Kang at the
University of Michigan
• Some slides also contain material from:
Bazaraa, Mokhtar S., John J. Jarvis, and Hanif D.
Sherali. Linear programming and network flows.
John Wiley & Sons, 2011.
58
Announcement
No office hours on Monday, September 10
Instead, I will be available:
Wednesday, September 12, 9-11am
(or by appointment)
59
Team project (50% of grade)
• In teams of 3-4, you will define a system
design problem with sub-systems,
formulate optimization problems, solve
them, and interpret/justify results
• There will be 4 graded deliverables:
Sep 26: Present project topic proposal (0%)
Oct 28: Progress report, written (10%)
Oct 31: Present progress (5%)
Nov 28: Present final project (10%)
Dec 2: Final report, written (25%)
• Let’s discuss topics and teams during
today’s and next week’s class, and teams
will be formed before Week 3
60
Subsystem
1
Subsystem
2
Optimize individually
for progress report
Subsystem
3
Subsystem
1
Subsystem
2
Subsystem
3
Coordinate and optimize
system for final report
Tomorrow, I will post to Canvas a survey on your
skills and topic interests, due Tuesday at noon.
Examples
61
Active, Semiactive, Inactive?
Consider the following problem:
min f(x) = x1
2 + (x2 – 1)
2 (x2 –3)
2 (x2 – 4)
2
s.t. g1(x) : x1 ≥ 1
g2(x) : x2 ≥ 2
g3(x) : x2 ≤ 5
x1=1 (partial minimization)
min f(x) = 1 + (x2 – 1)
2 (x2 –3)
2 (x2 – 4)
2
s.t. g2(x) : x2 ≥ 2
g3(x) : x2 ≤ 5
X* = {(1,3), (1,4)}
62
Active, Semiactive, Inactive?
min f(x) = x1
2 + (x2 – 1)
2 (x2 –3)
2 (x2 – 4)
2
s.t. g1(x) : x1 ≥ 1
g2(x) : x2 ≥ 2
g3(x) : x2 ≤ 5
X* = {(1,3), (1,4)}
• Remove constraints one at a time (relaxation):
• g1 removed:
• g2 removed:
• g3 removed:
X1 = {(0,3), (0,4)}
X2 = {(1,1), (1,3), (1,4)}
X3 = {(1,3), (1,4)}
Active
Semiactive
Inactive
63
Active, Semiactive, Inactive?
f(1, x2 )
x2
g2 g3
x1
f(x1, 3 )
g1
Relaxing:
• Active constraint: changes optimal set of variables and function value
• Semiactive constraint: does not change optimal function value, adds
more variables to the optimal set of variables
64
Problem Reduction
min f(x) = x1
2 + (x2 – 1)
2 (x2 –3)
2 (x2 – 4)
2
s.t. g1(x) : x1 ≥ 1 (Active)
g2(x) : x2 ≥ 2 (Semiactive)
g3(x) : x2 ≤ 5 (Inactive)
Equality
Let it be
Remove
min f(x) = x1
2 + (x2 – 1)
2 (x2 –3)
2 (x2 – 4)
2
s.t. g1(x) : x1 = 1
g2(x) : x2 ≥ 2
min f(x) = 1 + (x2 – 1)
2 (x2 –3)
2 (x2 – 4)
2
s.t. g2(x) : x2 ≥ 2
Eliminate x1
65
MP1 Example 3
What if the functions are not monotonic?
Apply regional monotonicity to the problem
min f = x1
2 – 3×1 + x2
s.t. g1 = x1–x2 ≤ 0
g2 = 2×1+3×2 ≤ 0
x1 x2
f ? +
g1 + –
g2 + +
Monotonicity Table
Active w.r.t. x1
(g1=0, x2=x1)
66
MP1 Example 3
Apply regional monotonicity to the problem
min f = x1
2 – 2×1
s.t. g2 = 5×1 ≤ 0
x1
f +
g2 +
g3 –
Monotonicity Table
for x1 ≥ 1
𝜕𝑓
𝜕𝑥1
= 2𝑥1 − 2
Check:
𝜕𝑓
𝜕𝑥1
≥ 0 for x1 ≥ 1
Case 1:
g3 = 1–x1 ≤0
g3 is active w.r.t. x1
x1*=1, but not feasible w.r.t g2
No solution in this region!67
MP1 Example 3
Apply regional monotonicity to the problem
min f = x1
2 – 2×1
s.t. g2 = 5×1 ≤ 0
x1
f –
g2 +
g4 +
Monotonicity Table
for x1 ≥ 1
𝜕𝑓
𝜕𝑥1
= 2𝑥1 − 2
Check:
𝜕𝑓
𝜕𝑥1
≤ 0 for x1 ≤ 1
Case 2:
g4 = x1–1 ≤0
g4 is dominated by g2
g2 is active w.r.t x1
x1*=0, f(x1*)=0
68
MP1 Example 4
Apply regional monotonicity to the problem:
min f = x
s.t. g1 = x
2 –5x + 4 ≤ 0
𝜕𝑔
𝜕𝑥
= 2𝑥 − 5
Check:
𝜕𝑔
𝜕𝑥
≥ 0 for x ≥ 2.5
Case 1:
g2 = 2.5–x ≤0
𝜕𝑔
𝜕𝑥
≤ 0 for x ≤ 2.5
Case 2:
g3 = x–2.5 ≤0
f(x+)
g1(x
+)
g2(x
–)
f(x+)
g1(x
–)
g3(x
+)
Case 1:
f(x*)=2.5
Case 2:
f(x*)=1
69
MP2 Example 2
Apply MP2 to the following problem
min f(x1
+) = x1
s.t. g1(x1
+, x2
+) = x1
3 + x2
3 ≤ 0
g2(x1
+, x2
–) = ex1 – e
x2≤ 0
x2 does not appear in the objective
x2 is not relevant
The problem is unbounded
70