OPTIMIZATION
TECHNIQUES
[AcSIR-01-ES-AD-009]
Presented by:
Dr. R. S. Bisht, Pr. Scientist,
rsbisht@cbri.res.in
CSIR-CBRI, Roorkee, India
Contents
• Classical Optimization techniques (single and multivariable
optimization with and without constraints)
• Stochastic Optimization techniques (multivariable optimization with
and without constraints) using PSO
• Hands-on examples will also be done in MATLAB for both Classical
and Stochastic Optimization methods
Classical Optimization
• A function f(x) has a local minimum at 𝑥* if
𝑓(𝑥*)<𝑓(𝑥*+ℎ) where h is a small negative or
positive disturbance around 𝑥*.
• Similarly, a function f(𝑥) has a local maximum at 𝑥* if
𝑓(𝑥*)>𝑓(𝑥*+ℎ) where h is a small negative or
positive disturbance around 𝑥*.
• Necessary Condition: Given a piecewise smooth
function f(𝑥*) that is defined in the interval, 𝑎≤𝑥≤𝑏. If
the function has an extremum 𝑥* within this period,
then,
𝑑𝑓(𝑥*)/𝑑𝑥=𝑓′(𝑥*)=0
Sufficient Condition:
Given a piecewise smooth function f(𝑥) that is defined in
the interval 𝑎≤𝑥≤𝑏.
• If 𝑓′(𝑥*)=𝑓′′(𝑥*)=⋯=𝑓𝑛−1(𝑥*)=0 and 𝑓𝑛(𝑥*)≠0, then
𝑓(𝑥*) is,
1. Minimum if 𝑓 𝑛 (𝑥*)>0 and n is even
2. Maximum if 𝑓 𝑛 (𝑥*)<0 and n is even
3. Neither minimum or maximum if n is odd
(inflection/saddle point)
Proof: This can be easily shown using Taylor’s theorem:
Brook Taylor
(1685-1731),
Wikipedia
Note: The theory cannot make distinction between local and global extrema.
Example-1
Analyze the extrema of 𝑓(𝑥) = 5𝑥6 − 36𝑥5 + 165 /2 𝑥4 − 60𝑥3 + 36 in the interval in the
interval −1 ≤ 𝑥 ≤ 4
MATLAB
%%
% single variable Example-1
x=-1:0.05:4
y=5*x.^6-36*x.^5+165/2*x.^4-
60*x.^3+36;
plot(x,y)
grid on
p1=[30 -180 330 -180 0 0] % single derivative=0
r1 = roots(p1)
Note: 2D plot can be plotted using plot function in MATLAB.
clear all
syms x
y1=5*x.^6-
36*x.^5+165/2*x.^4-
60*x.^3+36; % function
y2=diff(y1) % single derivative
y3=diff(y2) % double derivative
y4=diff(y3) % third derivative
Multivariable Optimization with no Constraints
Necessary Condition: Given a piecewise smooth function
f(𝑥) that is defined in the interval 𝑎≤𝑥≤𝑏.
If the function has an extremum 𝑥* within this period, then,
𝜕𝑓(𝑥∗) 𝜕𝑓(𝑥∗) 𝜕𝑓(𝑥∗)
𝜕𝑥 1 = 𝜕𝑥2
=⋯= =
𝜕𝑥 𝑛 0
In we think in terms of 𝑥 as one-dimensional array of
𝜕𝑓(𝑥∗)
variables, =∇𝑓(𝑥*)=0
𝜕𝑥
Sufficient Condition:
Given a piecewise smooth function f(𝑥) that is defined in
the interval 𝑎≤𝑥≤𝑏, a sufficient condition for a point 𝑥* to
be an extremum is that the matrix of second partial
derivatives (Hessian matrix, J) of f(𝑥) when evaluated at 𝑥*
is,
1. Minimum if 𝐽(𝑥*) is positive definite
2. Maximum if 𝐽(𝑥*) is negative definite
3. Inflection/saddle point if 𝐽(𝑥*) is indefinite*
Note: The theory cannot make distinction between local and global extrema.
Proof: This can be shown using Taylor’s theorem,
It may be more useful to express the above equation in a
matrix form
where J is the Hessian matrix of the function.
Note: The Hessian matrix is always square and symmetric
Hessian Matrix MATLAB
syms x y z
f = x*y + 2*z*x; Otto Hesse
(1811-1874),
hessian(f,[x,y,z])
Wikipedia
Optimal values
convex
concave
The sign of the eigenvalues say something about the
convexity of the function along that direction (positive
implies convex, negative concave, zero inflexion point).
Definition:
Minima: A matrix is positive definite if all eigenvalues are positive.
This means that |J − 𝜆 𝐼| = 0
Maxima: A matrix is negative definite if all eigenvalues are negative.
At saddle point: both positive and negative eigenvalues
Note: Eigenvalues can be calculated using eig function in MATLAB.
Example-1
A saddle point is maximum in one variable and minimum in another. An example
𝑓(𝑥) = 𝑥12 − 𝑥22
Note: A three-dimensional surface plot can be calculated using
surf function in MATLAB.
Example: A three-
dimensional surface
plot
[X,Y] = meshgrid(0:0.5:20);
Z = sin(X) + cos(Y);
surf(X,Y,Z)
[X,Y] = meshgrid(1:0.5:10,1:20);
Z = sin(X) + cos(Y);
surfc(X,Y,Z)
clear all
[x,y] = meshgrid(-2:0.05:2);
f = x.*exp(-x.^2-y.^2)+(x.^2+y.^2)/20;
surfc(x,y,f)
Problem-1
Analyze the extrema of 𝑓(𝑥1,𝑥2)=2−𝑥12 −𝑥1𝑥2− 𝑥22 in the interval in the
interval −2≤𝑥1≤2 and −2≤𝑥2≤2
Visualize the optimal points using MATLAB
Using MATLAB in Calculus
Department of Mathematics, CSI
https://www.math.csi.cuny.edu/Computing/matlab/Tutorial/
Problem-2
Analyze the extrema of 𝑓(𝑥1,𝑥2)=(𝑥1−1)2 (𝑥2+1)−𝑥2 in the interval in the
interval −1≤𝑥1≤3 and −2≤𝑥2≤2
Visualize the optimal points using MATLAB
