Formulating and analyzing a problem
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
1
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
(Weeks 1-2, 4, 9-12)
TODAY c)
2.
(Weeks 3, 5-8, 12)
Explore/reduce the problem space d) Formalize optimization problem
Solve the problem
a) Choose the right approach/algorithm
b) Solve (by hand, code, or software)
c) Interpret the results d) Iterate if needed
𝐱𝑘+1 = 𝐱𝑘 − 𝐇(𝐱𝑘) −1𝛁𝑓 𝐱0
3
Recap: Important problem attributes
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
4
Example: Gas turbine
Objective(s)
Constraints
Design variables
Parameters
Constants
maximize (power out)/(fuel in)
power out must be at least 1 MW total cost must be no more than $1M
air flow rate in, compressor ratio, fuel flow rate in
Inlet air temperature & pressure, fuel specific heat
gas constant, gravity
5
Recap: Optimization formulation
Objective function
Constraints
Negative null form
𝐡𝐱=𝟎 𝐠𝐱≤𝟎
Positive null form
𝐡𝐱=𝟎
𝐠𝐱≥𝟎
Negative unity form
𝐡𝐱=𝟏 𝐠𝐱≤𝟏
Parameters
Variables
“negative null” form
6
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 w.r.t. subject to
–E(x) or 1/E(x) x
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
Design-objective space
𝒇(𝒙)
Objective function
𝒙𝟐 𝒙𝟏
Variables
10
Design space – Example
Note: x and y are both in the design/variable space!
𝑦
Constraint
𝒈𝟏
𝑥
Choose a point from the
orange triangular and plug it
into 𝑔 to make sure the 1
constraint is defined correctly e.g.(0,0)0+2×0-8≤0
11
Design space – Example
𝑦
𝒈𝟐
𝒈𝟏
𝑥
12
Design space – Example
𝑦
𝒈𝟐
The intersection of 𝑔,𝑔,𝑔,&𝑔
𝒈𝟒
𝑥
123 4
demonstrates the 𝒈𝟑 feasible design space
𝒈𝟏
13
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
min 𝑓 𝑥 =𝑥+8𝑥2 𝑥
𝑧=3−𝑥
min 𝑓 𝑥 =𝑥+8𝑥2 𝑥
s.t. h𝑥,𝑧 =𝑥+𝑧−3=0
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).
16
Feasibility and Boundedness
Does a solution satisfying the constraints even exist? Is there a finite optimal solution?
17
Feasibility
Consider the minimization problem:
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)
18
Feasibility
Consider the minimization problem:
Regarding feasibility, we want to know whether a solution exists
This problem is not well-posed
19
No feasible solution
Feasibility
Consider the maximization problem:
Regarding feasibility, we want to know whether a solution exists
This problem is well-posed
20
Optimal solution
optimizer: x* = 10 optimum: f* = 20
Feasibility
Is this problem well-posed?
min f(x) = x1+x2 w.r.t. x ∈ R2
s.t. g(x) = x12 +1≤ 0
The feasible domain is empty. This problem is not well-posed.
21
Boundedness
Consider the minimization problem:
For any real “solution” you find (very high or very low number), you will always be able to find something better.
This problem is unbounded
22
No optimal solution
Boundedness
Consider the design of a cylindrical pill:
Simplify:
r is unbounded from above and not well bounded from below 23
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
0
-1
-2 -3
x
f
f(x) = x2– 1
Argument of infimum x = 0
Greatest Lower Bound (infimum) Lower Bound
Lower Bound
25
Boundedness
Consider the following problem
f
f(x)=x
0
min f(x) = x w.r.t. x ∈ 𝒫
Domain 𝒫: Positive real numbers, i.e. 0 < x < ∞
What is the solution?
x
Infimum in 𝒫: f(𝐱) = g = 0
Arg. of infimum: 𝐱 = 0
Since 0 ∉ 𝓟, this problem is not well bounded
26
Boundedness
𝒙∈R
No infimum exists
No minimum exists
Not well bounded
(minimization problem)
Unbounded
(minimization problem)
27
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
Infimum – not minimum
28
Exercise: Well bounded?
• Assume our domain is 𝒫 : Positive real numbers i.e. 0 < x < ∞
f(x)=(x–1)2 – 1
f
Infimum in 𝒫: -1 Arg. of infimum: 1
012 -1
x
Since 1 ∈ 𝒫, well bounded
29
Exercises: Well Bounded?
• Assume our domain is 𝒫 : Positive real numbers i.e. 0 < x < ∞
f(x)=(x2–1)2
f
Infimum in 𝒫: 0
Arg. of infimum:
±1
Since 1 ∈ 𝒫 but -1 ∉ 𝒫, not well bounded
-1
01
x
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
g(x) is active
33
Optimal solution
optimizer: x* = 18.8 optimum: f* = 0.59
Constraint activity
A constraint is active if removing it changes the optimization result
g(x) is inactive
Optimal solution
optimizer: x* = 10 optimum: f* = 20
34
Constraint activity
A constraint is active if removing it changes the optimization result
minimize
minimize
g2
g2
g1
g1
g1 active, g2 active
g1 active, g2 inactive
35
Constraint activity
A constraint is active if removing it changes the optimization result
minimize
minimize
g2
g1
g2
g1
g1 active, g2 active
g1 active, g2 inactive
36
Constraint activity
A constraint is active if removing it changes the optimization result
g1
g2
g1 active, g2 inactive
37
Constraint activity
A constraint is semiactive if removing it adds to the existing set of optimizers
g1
g2
Solutions to unconstrained problem
optimizers: χ* = {1, 3, 4} optimum: f* = 1
g1 semiactive, g2 inactive
Solutions
optimizers: χ* = {3, 4} optimum: f* = 1
38
Activity theorem
Relaxed problem solution when gi is removed
Original solution
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
39
Activity check
Activity Definition
• Solve original problem
• Remove constraint
• Solve again
• Check if optimum changes
Relaxation
• 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
𝑓(𝑥)
for every 𝑥2 > 𝑥1, 𝑓(𝑥2) > 𝑓(𝑥1)
Other types of monotonicity
Monotonicity
A function 𝑓(𝑥) is monotonically increasing with respect to a variable 𝑥 if:
Replace monotonically increasing with:
Replace 2nd > with:
(strictly) monotonically increasing
>
weakly monotonically increasing/non-decr.
≥
(strictly) monotonically decreasing
<
weakly monotonically decreasing/non-incr.
≤
𝑥
In all of these cases, we say the function is
monotonic with respect to 𝑥
43
Monotonic functions
f(x) = ex
f(x+)
f(x) = –x3
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
All increase
All decrease
f g1 g2
f g1 g2
−∞ ∞
min s.t.
f(x+) = x
g1(x+) = x–1 ≤ 0 g2(x+) = x–2 ≤ 0
min s.t.
f(x–) = –x g1(x–) = 1–x ≤ 0 g2(x–) = 2–x ≤470
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
𝑓(𝑥)
𝒈𝟐 𝒙 : 𝒙+𝒇(𝒙)−𝟏𝟎≤𝟎
𝒈𝟑 𝒙:−𝒙+𝟓≤𝟎
𝒈𝟏 𝒙 : 𝒙 − 𝟗 ≤ 𝟎
𝒇 𝒙+ x increasing in objective 𝒈𝟏 𝒙+
𝒈𝟐 𝒙+
𝒈𝟑 𝒙− x non-increasing, so MP1 is satisfied
𝑥
48
MP1
Not
well constrained f
Active constraint bounds from below
𝑥∗ = −∞
g1 g2
f g2
𝑥∗ = −1
g1
g1(x–) = –x–1 ≤ 0
min s.t.
f(x+) = x
g1(x+) = x–1 ≤ 0
min s.t.
f(x+) = x
g (x+) = x–2 ≤ 0 22
49
g (x+) = x–2 ≤ 0
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 g1=0, x1* = 1
g2=0, x2 * = 0 f* =8/3
Monotonicity Table
x1
x2
f
+
+
g1
–
g2
–
Active with respect to x2
Active with respect to x1
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
Monotonicity Table
x1
x2
–f
–
+
g1
+
+
g2
–
–
g3
–
+51
Negative null form Active w.r.t. x1
MP1 Example 2
Eliminate x1 using g1
min s.t.
–f =–x1 +x2
g1 : x1 = –3×2 + 10
g2 = –x1–4×2+2 ≤ 0
g3 = –2×1 + 7×2 – 8≤ 0
min –f =4×2 –10 s.t. g2 = –x2 – 8 ≤ 0
g3 = 13×2 – 28≤ 0 Monotonicity Table
x2
–f
+
g2
–
g3
+
Negative null form Active w.r.t. x2
52
Critical constraints
A constraint is critical for 𝒙 in a well-constrained minimization problem if 𝑥 is increasing in the objective and all other constraints
𝑓(𝑥)
𝒈𝟐 𝒙 : 𝒙+𝒇(𝒙)−𝟏𝟎≤𝟎
𝒈𝟑 𝒙:−𝒙+𝟓≤𝟎
𝒈𝟏 𝒙 : 𝒙 − 𝟗 ≤ 𝟎
𝒇 𝒙+ x increasing in objective 𝒈𝟏 𝒙+
𝒈𝟐 𝒙+
𝒈𝟑 𝒙− x non-increasing, so this constraint is uniquely critical
𝑥
53
Monotonicity Principle 2
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
54
MP2 Example 1
In a well-constrained minimization problem, every relevant nonobjective variable is bounded both:
1. 2.
below by at least one non-increasing semiactive constraint, & above by at least one non-decreasing semiactive constraint.
multiply critical
uniquely
critical
𝑭
𝒉 𝒍𝒘
𝑬 = Young’s modulus
MP1: 𝒘, 𝒉 MP2: 𝒍
MP2: 𝑬
With monotonicity analysis, we can identify appropriate constraints to turn an unbounded problem into one that is solvable
55
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)
Subsystem 1
Subsystem 2
• 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: Oct 28: Oct 31: Nov 28: Dec 2:
Present project topic proposal (0%) Progress report, written (10%) Present progress (5%)
Present final project (10%)
Final report, written (25%)
Optimize individually for progress report
• Let’s discuss topics and teams during today’s and next week’s class, and teams will be formed before Week 3
Subsystem 1
Subsystem 3
Subsystem 3
Tomorrow, I will post to Canvas a survey on your skills and topic interests, due Tuesday at noon.
Coordinate and optimize
system for final report
Subsystem 2
60
Examples
61
Active, Semiactive, Inactive?
Consider the following problem:
min s.t.
f(x) = x12 + (x2 – 1)2 (x2 –3)2 (x2 – 4)2 g1(x) : x1 ≥ 1
g2(x) : x2 ≥ 2
g3(x) : x2 ≤ 5
x1=1 (partial minimization)
f(x) = 1 + (x2 – 1)2 (x2 –3)2 (x2 – 4)2 g2(x) : x2 ≥ 2
g3(x) : x2 ≤ 5
X* = {(1,3), (1,4)}
min s.t.
62
Active, Semiactive, Inactive?
min f(x) = x12 + (x2 – 1)2 (x2 –3)2 (x2 – 4)2
s.t.
g1(x) : x1 ≥ 1 g2(x) : x2 ≥ 2 g3(x) : x2 ≤ 5
Remove constraints one at a time (relaxation): • g1 removed:
• g2 removed: • g3 removed:
•
X* = {(1,3), (1,4)}
X1 = {(0,3), (0,4)}
Active Semiactive
Inactive
X2 = {(1,1), (1,3), (1,4)}
X3 = {(1,3), (1,4)}
63
Active, Semiactive, Inactive?
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
f(x1, 3 )
f(1, x2 )
g2
g1
g3
x1 x264
Problem Reduction
min s.t.
f(x) = x12 + (x2 – 1)2 (x2 –3)2 (x2 – 4)2
g1(x) : x1 ≥ 1 g2(x) : x2 ≥ 2 g3(x) : x2 ≤ 5
(Active) Equality (Semiactive) Let it be (Inactive) Remove
min s.t.
f(x) = x12 + (x2 – 1)2 (x2 –3)2 (x2 – 4)2 g1(x) : x1 = 1
g2(x) : x2 ≥ 2
Eliminate x1
min f(x) = 1 + (x2 – 1)2 (x2 –3)2 (x2 – 4)2 s.t. g2(x) : x2 ≥ 2
65
MP1 Example 3
What if the functions are not monotonic? Apply regional monotonicity to the problem
min f = x12 – 3×1 + x2 s.t. g1 = x1–x2 ≤ 0
g2 = 2×1+3×2 ≤ 0
Monotonicity Table
x1
x2
f
?
+
g1
+
–
g2
+
+
Active w.r.t. x1 (g1=0, x2=x1)
66
MP1 Example 3
Apply regional monotonicity to the problem
min f = x12 – 2×1 s.t. g2 = 5×1 ≤ 0
Check:
𝜕𝑓 = 2𝑥1 − 2 𝜕𝑥1
Case 1:
𝜕𝑓 ≥ 0 for x1 ≥ 1 𝜕𝑥1
Monotonicity Table for x1 ≥ 1
x1
f
+
g2
+
g3
–
g3 is active w.r.t. x1
x1*=1, but not feasible w.r.t g2
g3 = 1–x1 ≤0
No solution in this regio67n!
MP1 Example 3
Apply regional monotonicity to the problem
min f = x12 – 2×1 s.t. g2 = 5×1 ≤ 0
Check:
𝜕𝑓 = 2𝑥1 − 2 𝜕𝑥1
Case 2:
𝜕𝑓 ≤ 0 for x1 ≤ 1 𝜕𝑥1
Monotonicity Table for x1 ≥ 1
x1
f
–
g2
+
g4
+
g4 is dominated by g2 g2 is active w.r.t x1
x1*=0, f(x1*)=0
g4 = x1–1 ≤0
68
MP1 Example 4
Apply regional monotonicity to the problem:
min f =x
s.t. g1 = x2 –5x + 4 ≤ 0
Check:
𝜕𝑔 = 2𝑥 − 5 𝜕𝑥
𝜕𝑔 ≥ 0 for x ≥ 2.5 f(x+)
𝜕𝑥
Case1:
f(x*)=2.5
Case2:
f(x*)=1
Case 1:
Case 2:
𝜕𝑔 ≤ 0 for x ≤ 2.5 𝜕𝑥
f(x+) g (x–)
g1(x+) g2(x–)
1 + g3(x )
g3 = x–2.5 ≤0
g2 = 2.5–x ≤0
69
MP2 Example 2
Apply MP2 to the following problem
min f(x1+) = x1
s.t. g1(x1+, x2+) = x13 + x23 ≤ 0
g2(x1+, x2–) = ex1 – ex2 ≤ 0
x2 does not appear in the objective
x2 is not relevant
The problem is unbounded
70