18-660: Numerical Methods For Engineering Design and Optimization
18-660: Numerical Methods For Engineering Design and Optimization
18-660: Numerical Methods For Engineering Design and Optimization
Slide 1
Overview
Linear Regression
Ordinary least-squares regression
Minimax optimization
Design of experiments
Slide 2
Linear Regression
Linear regression (also referred to as response surface
modeling) is widely used for many engineering problems
We do not know the analytical form of f(x)
But we can generate a set of sampling points for f(x)
Fit an approximate function for f(x) from these sampling points
f(x) f (x ) ≈ α1 ⋅ b1 (x ) + α 2 ⋅ b2 (x ) +
Model Basis
coefficients functions
Slide 3
Linear Regression
Major steps of linear regression
Select a model template (e.g., polynomial function)
Generate a number of sampling points
Compute performance values at these sampling points
Create a set of linear equations to solve model coefficients
A simple example
f(x) = exp(x), x ∈ [-1, 1]
We will use this simple example to show how we can generally
build a regression model from sampling data
Slide 4
Linear Regression Example
Step 1: select a model template
f ( x ) ≈ bx + c
Slide 5
Linear Regression Example
Step 4: create linear equations for model coefficients
f ( x ) ≈ bx + c
Samples 1 2 3 4 5
x -1 -0.5 0 0.5 1
f(x) 0.3679 0.6065 1.0000 1.6487 2.7183
−1 1 0.3679
− 0.5
1 0.6065
b
0 1 ⋅ = 1.0000 i-th sampling point
c
0.5 1 1 . 6487
1 1 2.7183
Slide 6
Linear Regression Example
Step 5: solve over-determined linear equations
# of equations is greater than # of coefficients – over-determined
No exact solution exists to satisfy all equations, but we can find
the least-squares solution:
A ⋅α = B
min A ⋅α − B
2
Ordinary least-squares
α 2
(OLS) regression
Vector
For a vector ε ∈ RM, ||ε||2 is defined as:
M
ε 2
= ∑ε
i =1
i
2
Slide 7
Linear Regression Example
ε1
i-th row ε
2 Error at the i-th
A ⋅α = B A ⋅α − B = ε 3 sampling point
ε M
M
A ⋅α − B ∑ i (α )
ε
2 2
min min
α 2 α
i =1
Slide 8
Linear Regression Example
M samples A ⋅α = B (M > N)
N coefficients
Slide 9
Linear Regression Example
Step 5: solve over-determined linear equations
−1 1 0.3679
3
Linear
− 0.5 1 0.6065 2.5 exp(x)
b
0 1 ⋅ = 1.0000 2
c
exp(x)
1.5
0.5 1 1 . 6487
1 1 2.7183 1
0.5
0
-1 -0.5 0 0.5 1
x
b = 1.1486 Linear model results in large error
c = 1.2683
Slide 10
Quadratic Model Example
What if we build a quadratic model for y = exp(x)?
Select a model template
f ( x ) ≈ ax 2 + bx + c
Slide 11
Quadratic Model Example
Create a set of linear equations to solve model coefficients
f ( x ) ≈ ax 2 + bx + c
Samples 1 2 3 4 5
x -1 -0.5 0 0.5 1
f(x) 0.3679 0.6065 1.0000 1.6487 2.7183
1 −1 1 0.3679
0.25 − 0.5
1 a 0.6065
0 0 1 ⋅ b = 1.0000
0.25 0.5 1 c 1.6487
1 1 1 2.7183
x2 x f(x) values
Slide 12
Quadratic Model Example
Build quadratic model for y = exp(x)
1 −1 1 0.3679 3
Quadratic
0.25 − 0.5
1 a 0.6065 2.5 exp(x)
0 0 1 ⋅ b = 1.0000 2
exp(x)
0.25 0.5 1 c 1.6487 1.5
1 1 1 2.7183 1
0.5
0
-1 -0.5 0 0.5 1
x
a = 0.5477
Quadratic model results in much
b = 1.1486 better accuracy in this example
c = 0.9944
Slide 13
Linear Model vs. Quadratic Model
Linear RSM exp(x ) ≈ 1.1486 x + 1.2683
Quadratic RSM exp( x ) ≈ 0.5477 x + 1.1486 x + 0.9944
2
2
Minimize least-
exp(x)
1.5
squares error
1
0.5
Direct Taylor
expansion
0
-1 -0.5 0 0.5 1
x
i-th row of A
i-th row
Error at the i-th
sampling point
A ⋅α − B
min max A(i, :) ⋅ α − Bi
α i
Minimize the maximal
absolute error
Slide 15
Minimax Optimization
Other optimality criteria can be similarly formulated
A ⋅α = B
i-th row of A
i-th row
Error at the i-th
A(i, :) ⋅ α − Bi sampling point
min max
α
A ⋅α − B
i Bi
Minimize the maximal
relative error
Slide 16
Minimax Optimization
General minimax problems are difficult to solve
Cost function does not have continuous derivative
ε(α)
max(ε1, ε2)
ε1(α) ε2(α)
Slide 17
Minimax Optimization
However, our minimax problem for regression modeling can
be re-formulated into a special form
min t
α ,t
Cost function
A(1, :) ⋅ α − B1 ≤ t
A(2, :) ⋅ α − B2 ≤ t
S.T. Constraints
Subject to A(M , :) ⋅ α − BM ≤ t
Slide 18
Minimax Optimization
min t min t
α ,t α ,t
A(1, :) ⋅ α − B1 ≤ t − t ≤ A(1, :) ⋅ α − B1 ≤ t
− t ≤ A(2, :) ⋅ α − B ≤ t
A(2, :) ⋅ α − B2 ≤ t 2
S.T. S.T.
A(M , :) ⋅ α − BM ≤ t − t ≤ A(M , :) ⋅ α − BM ≤ t
Slide 19
Design of Experiments (DOE)
We already know the basics for linear regression
Open problem:
How can we select few samples to achieve good accuracy?
Slide 20
Design of Experiments (DOE)
Linear model example (continued)
(x1 = −1 x2 = 0 f1 )
f (x1 , x2 ) = a ⋅ x1 + b ⋅ x2 + c (x1 = 0 x2 = 0 f2 )
(x1 = 1 x2 = 0 f3 )
x1 x2 1
− 1 0 1 a f1
0 0 1 ⋅ b = f
2
1 0 1 c f 3
Slide 21
Design of Experiments (DOE)
Linear model example (continued)
x2
No variation is applied to x2
-1 0 1 x1
x2
Slide 22
Design of Experiments (DOE)
A bad quadratic model example: f(x1, x2) = a11⋅x12 + a12⋅x1⋅x2 +
a22⋅x22 + b1⋅x1 + b2⋅x2 + c
x2 (x1 = 0 x2 = 0 f1 )
(x1 = 0 x2 = −1 f2 )
(x1 = 0 x2 = 1 f3 )
-1 0 1 x1 (x1 = −1 x2 = 0 f4 )
(x1 = 1 x2 = 0 f5 )
Slide 23
Design of Experiments (DOE)
Quadratic model example (continued) (x = 0 x = 0 f )
1 2 1
(x1 = 0 x2 = −1 f2 )
f ( x1 , x2 ) = a11 ⋅ x + a12 ⋅ x1 ⋅ x2 + a22 ⋅ x
2 2
1 2
(x1 = 0 x2 = 1 f3 )
+ b1 ⋅ x1 + b2 ⋅ x2 + c
(x1 = −1 x2 = 0 f4 )
(x1 = 1 x2 = 0 f5 )
x2
Slide 25
Design of Experiments (DOE)
Design of experiments (DOE) is a research area that studies
how to optimally select sampling points for modeling
D. Montgomery, Design and Analysis of Experiments, John Wiley & Sons, 2004
Slide 26
Summary
Linear regression
Ordinary least-squares regression
Minimax optimization
Design of experiments
Slide 27