[Link]
blog
Optimization in
Python
Hans-Petter Halvorsen
Free Textbook with lots of Practical Examples
[Link]
Additional Python Resources
[Link]
Contents
• Optimization
– Find minimum (or maximum) of a given
function
– Curve Fitting, where you find an “optimal“
Model based on a given Data Set, i.e., You
find the model parameters for a selected
model that best fits the data set
• The SciPy Library
• Lots of Python Examples
Optimization
Optimization is based on finding the minimum of a given function We find the Minimum
(or Maximum) where
𝑓(𝑥) the derivative is zero
𝑓(𝑥)
𝑑𝑓(𝑥)
=0
𝑑𝑥
Minimum
𝑥
Optimization
• Optimization is important in mathematics,
control and simulation applications
• Basically it is all about finding minimum (or
maximum) of a given function
• E.g., in Model Predictive Control (MPC) you
use optimization to find the optimal control
signal based on some criteria and
constraints
Optimization Challenges
Convex Function Non-Convex Function
Local Minimum
Minimum Global Minimum
Optimizing non-convex functions
Optimizing convex functions is easy can be much more complicated
When you have more than one variable (Multiple variables) it also become more complex
[Link]
Optimization - Example
The cost function often used in MPC is like this:
$! $"
𝐽 = # 𝑦$ − 𝑟 % 𝑄 𝑦$ − 𝑟 + # ∆𝑢% 𝑅 ∆𝑢
!"# !"#
Where 𝑢 is the Control Signal
So the basic challenge is to solve:
𝜕𝐽
=0
𝜕𝑢
By solving this we get the future optimal control (𝑢&'( ) The optimal control signal
used by the MPC controller
In this Tutorial/Video we will only go through some general Optimization problems and not
focus on MPC or other specific applications
Optimization
In this video we will go through 2 types of Optimization problems
Find Minimum of a given Function
Curve Fitting
𝑦 𝑥 = 2𝑥 ) + 20𝑥 − 22
𝑦 = 𝑎𝑥 + 𝑏
Data Points
Find an “Optimal“ Model based on a given Data Set
Minimum
Example – Find Minimum
Example: We want to find for what value of x the function has its minimum value
𝑦 𝑥 = 2𝑥 ! + 20𝑥 − 22
We can of course find the derivative of the
function and find where the derivative is equal
to zero:
𝑑𝑦
= 4𝑥 + 20 = 0
𝑑𝑥
This gives: (−5, −72)
𝑥89: = −5
𝑦 −5 = 50 − 100 − 22 = −72 The minimum of the function
“Simple“ Solution Python Solution:
import numpy as np
Example: We want to find for what value import [Link] as plt
of x the function has its minimum value
xstart = -20
𝑦 𝑥 = 2𝑥 ! + 20𝑥 − 22 xstop = 20
increment = 0.1
x = [Link](xstart,xstop,increment)
We use Python to iterate through all y = 2 * x*x + 20 * x - 22
values of 𝑦(𝑥) using a While Loop.
[Link](x,y)
Inside the While Loop we compare 𝑦(𝑖) [Link]()
and 𝑦(𝑖 + 1). If 𝑦 𝑖 + 1 is larger than
𝑦(𝑖) we have found the minimum. i = 0
while y[i] > y[i+1]:
The Python results becomes the i = i+1
same as the analytical solution:
print(x[i])
(−5, −72) print(y[i])
[Link]
Optimization with
SciPy
Hans-Petter Halvorsen
SciPy
• SciPy is a free and open-source Python
library used for scientific computing and
engineering
• SciPy contains modules for optimization,
linear algebra, interpolation, image
processing, ODE solvers, etc.
SciPy
• The optimize Module in the SciPy Library
provides functions for minimizing (or
maximizing) objective functions
• Functions:
– fminbound(), fmin(),
minimize_scalar(), minimize()
[Link]
Scalar Function - Example
import numpy as np
Given the following function: import [Link] as plt
from scipy import optimize
𝑦 𝑥 = 2𝑥 ) + 20𝑥 − 22 def func(x):
y = 2 * x**2 + 20*x - 22
return y
(same as in previous example)
xmin = -20
We use the [Link]() xmax = 20
dx = 0.1
function in the SciPy Library N = int((xmax - xmin)/dx)
x = [Link](xmin, xmax, N+1)
y = func(x)
[Link](x,y)
[Link]([xmin,xmax])
x_min = [Link](func, xmin, xmax)
(-5.0 ,-72.0) y_min = func(x_min)
print(x_min)
We get the same results as previous example print(y_min)
[Link]
Multiple Variables
in SciPy
Hans-Petter Halvorsen
Rosenbrock's Banana Function
The function below is known as Rosenbrock's Banana Function:
Rosenbrock’s banana function is a famous
𝑓 𝑥, 𝑦 = (𝑎 − 𝑥)>+𝑏(𝑦 − 𝑥 > )> test case for optimization software
We will find the Minimum of this function
This function is used to verify performance
and robustness of optimization algorithms
since it is demanding to find the minimum
for this function.
The global minimum is inside a long, narrow, parabolic
shaped flat valley. To find the valley is trivial. To converge
to the global minimum, however, is difficult.
[Link]
Rosenbrock's Banana Function
𝑓 𝑥, 𝑦 = (𝑎 − 𝑥)) +𝑏(𝑦 − 𝑥 ) ))
It has a global minimum at (𝑥, 𝑦) = (𝑎, 𝑎) ), where 𝑓(𝑥, 𝑦) = 0
Usually these these parameters are set such that 𝑎 = 1 and 𝑏 = 100. Only in the trivial case
where 𝑎 = 0 the function is symmetric, and the minimum is at the origin.
We set 𝑎 = 1 and 𝑏 = 100
𝑓 𝑥, 𝑦 = (1 − 𝑥)>+100(𝑦 − 𝑥 >)>
We will find the Minimum of this function
It has a global minimum at 𝑥, 𝑦 = 𝑎, 𝑎) = (1,1)
[Link]
Rosenbrock's Banana Function
𝑓 𝑥, 𝑦 = (𝑎 − 𝑥)) +𝑏(𝑦 − 𝑥 ) )) import [Link] as opt
Global minimum at (𝑥, 𝑦) = (𝑎, 𝑎) ) def banana(x):
a = 1
Setting 𝑎 = 1 gives global minimum at b = 100
(𝑥, 𝑦) = (1,1) y = (a-x[0])**2 + b*(x[1]-x[0]**2)**2
return y
The Python code gives the following
results: xopt = [Link](func=banana, x0=[-1.2,1])
Optimization terminated successfully. print(xopt)
Current function value:
0.000000
Iterations: 85 Note! x[0]=x and x[1]=y
Function evaluations: 159
[1.00002202 1.00004222]
Python – Alternative Code
import [Link] as opt
In previous code example we
def banana(var): used x[0]=x and x[1]=y
a = 1
b = 100
x, y = var The code alternative illustrated
y = (a-x)**2 + b*(y-x**2)**2 here is probably more readable
return y
var is a NumPy array consisting 2
elements, namely x and y values
xopt = [Link](func=banana, x0=[-1.2,1]) in this case
print(xopt)
You should also try with other values for 𝑎 and 𝑏
(especially for 𝑎, since a affects the minimum)
[Link]
Using other
Optimization Functions
Hans-Petter Halvorsen
SciPy – Other Functions Banana Function Examples
Previous Example using fmin() New Example using minimize()
import [Link] as opt import [Link] as opt
def banana(var): def banana(var):
a = 1
b = 100 a = 1
x, y = var b = 100
y = (a-x)**2 + b*(y-x**2)**2 x, y = var
return y
y = (a-x)**2 + b*(y-x**2)**2
xopt = [Link](func=banana, x0=[-1.2,1]) return y
print(xopt)
xopt = [Link](banana, x0=[-1.2,1])
print(xopt)
Scalar Function Examples
SciPy – Other Functions
Previous Example using fminbound() New Example using minimize_scalar()
import numpy as np import numpy as np
import [Link] as plt import [Link] as plt
from scipy import optimize from scipy import optimize
def func(x): def func(x):
y = 2 * x**2 + 20*x - 22 y = 2 * x**2 + 20*x - 22
return y return y
xmin = -20
xmin = -20
xmax = 20
xmax = 20
dx = 0.1
dx = 0.1
N = int((xmax - xmin)/dx)
N = int((xmax - xmin)/dx)
x = [Link](xmin, xmax, N+1)
x = [Link](xmin, xmax, N+1)
y = func(x)
y = func(x)
[Link](x,y)
[Link]([xmin,xmax]) [Link](x,y)
[Link]([xmin,xmax])
x_min = [Link](func, xmin, xmax)
y_min = func(x_min) res = optimize.minimize_scalar(func)
print(x_min) print(res)
print(y_min)
SciPy – Other Functions
• The [Link] contains many different optimization
functions that use different optimization methods
• You need to find and use the functions and methods that
is best for your Optimization problem
• This Tutorial/Video only scratches the surface of the
Optimization Topic
• For more information about Optimization in SciPy, read
the documentation:
[Link]
[Link]
Curve Fitting
Hans-Petter Halvorsen
Curve Fitting
Curve Fitting is all about fitting data to a Mathematical Model
Mathematical Model
Data
• Curve Fitting is also an Optimization problem
• You find an “optimal“ Model based on a given Data Set.
• You find the model parameters for a selected model that best fits
the data set
Curve Fitting
• Python has curve fitting functions
that allows us to create empiric data
model.
• We will show a basic example
• More about Curve Fitting in another
Video/Another part of the Textbook
Example
import numpy as np
from [Link] import curve_fit
import [Link] as plt
start = 0
stop = 2*[Link]
Assume we want to fit some given data to increment = 0.5
the following model: x = [Link](start,stop,increment)
a = 2
𝑦 𝑥 = a 3 sin(𝑥 + 𝑏) b = 10
[Link]()
Data Points (red y_noise = 0.2 * [Link](size=[Link])
y = a * [Link](x + b)
dots) used to find the y = y + y_noise
Model [Link](x,y, 'or')
def model(x, a, b):
y = a * [Link](x + b)
return y
popt, pcov = curve_fit(model, x, y)
print(popt)
Model (blue line) found increment = 0.1
from the data xmodeldata = [Link](start,stop,increment)
ymodel = model(xmodeldata, *popt)
[-2.03108093 0.629067 ] 𝑦 𝑥 ≈ −2sin(𝑥 + 0.6)
[Link](xmodeldata,ymodel)
Least Square Method (LSM)
The least squares method requires the model
to be set up in the following form based on
input-output data : The Least Square fit
𝑌 = Φ𝜃
The Least Square Method is given by: Data Points
𝜃-. = Φ/ Φ 01
Φ/ 𝑌
LSM Example
Given the following Data: The Least Square fit
𝑥 𝑦
0 15 𝑦 = 𝑎𝑥 + 𝑏 𝑦 = 𝑎𝑥 + 𝑏
1 10
2 9 We need to find 𝑎 and 𝑏
3 6
4 2
Data Points
5 0
15 = 𝑎 E 0 + 𝑏
15 0 1
10 = 𝑎 E 1 + 𝑏 10 1 1
9=𝑎E2+𝑏 1 𝑎
6=𝑎E3+𝑏
𝑌 = Φ𝜃 9
6
=
2
3 1 𝑏
𝜃-. = Φ/ Φ 01
Φ/ 𝑌
2=𝑎E4+𝑏 2 4 1
0=𝑎E5+𝑏 0 5 1
Python Code
import numpy as np
Phi = [Link]([[0, 1], [1, 1], [2, 1], [3, 1], [4, 1], [5, 1]])
Y = [Link]([[15],[10],[9],[6],[2],[0]]) Compare built-in LSM and LMS from scratch
theta_ls = [Link](Phi, Y, rcond=None)[0]
print(theta_ls)
theta_ls = [Link]([Link]() * [Link](Phi)) * [Link]() * Y
print(theta_ls)
From the Python code we get the following results:
[-2.91428571 14.28571429]
This means 𝑎 = −2.91 and 𝑏 = 14.29
Or:
𝑦 = −2.91𝑥 + 14.29
Additional Python Resources
[Link]
Hans-Petter Halvorsen
University of South-Eastern Norway
[Link]
E-mail: [Link]@[Link]
Web: [Link]