Concept of Optimization and Its Various Types

Submitted to: Presented by:

Dr. Lini Mathew
Prof. &Head
Ravi Nath-221517
NITTTR Chandigarh Ruchika Vyas-221518

DEPARTMENT OF ELECTRICAL ENGINEERING

National Institute of Technical Teachers Training and Research
Sector-26, Chandigarh - 160019
Contents
• Introduction and definition
• Components of Optimization
• Types of Optimization
• Gradient Descent Method of Optimization
• Hill Climbing Analogy
• Intelligent Methods of Optimization
• References
Optimization
Introduction
• Optimization is everywhere around us. It is a part and parcel of every
human (intelligent) activity.
• It is applied across many disciplines. It is applied in operation and
research to determine the optimal course of action.
• Optimization appears in machine learning as a central object in the
learning problems. It is at the core of power system, control system,
communication, internet and so many things.
• Optimization is much more than programming and computation.
• It is mainly about choosing the best alternative out of a given set of
alternatives.
Introduction
• Optimization is a fundamental concept in Mathematics, Engineering,
Economics and various other disciplines.
• It plays a crucial role in decision-making processes, resource
allocation and system design, contributing to the efficiency and
effectiveness of solutions in complex problems.
Definition
• In the Simplest terms it is doing the most with the least.

• An optimization is the act of achieving the best possible result under

the given circumstances.

• Primary objective may not be to optimize absolutely but to

compromise effectively & thereby produce the best formulation under
a given set of restrictions.

• Find value(s) of the variables that minimize or maximize the objective

function while satisfying the constraints.
Components of an Optimization Problem
Components of an Optimization Problem
The goal is typically to maximize or minimize a certain objective function,
subject to a set of constraints. Here's a detailed breakdown:-
• Objective Function (Cost Function): An objective function express
performance of a system, need to be minimized or maximized. In
mathematical terms it's a function that takes a set of parameters (decision
variables) as input and produces a single value representing the performance or
cost or loss etc.

• Variable (Design or Decision Variable): A set of unknowns, define the

objective function and constraints, can be continuous, discrete or Boolean.

• Constraints: They are conditions, allows the unknowns to take on certain

values but exclude others to render the design to be feasible.
Types of Optimization
 Conventional Optimization Types

Conventional Optimization Methods

Linear Programming Methods Non Linear Programming Methods

Single Variable Method Multi-Variable Method

Analytical Method Numerical Methods

Constrained Method Unconstrained Method

Optimization Type and Example
• The general optimization task is to maximize or minimize a function f(x) by
varying x.
• The function f(x) is called the objective function or cost function or loss
function.
• The function may be a scalar (i.e. f(x) single objective) or a vector(multi-
objective). The multi-objective functions are more complex ones.
• However, x is, in general a vector. Therefore, it is possible to reduce all
f:RnR e.g. f(x1,x2,x3) = x12+x22+x32 here f:R3 R

• The optimization problems can be minimization problems. i.e. all the problems
can be written as to find x that minimizes f(x) and any maximization problem
can be written as minimization of 1/f(x).
• The optimal solution to the problem is denoted as x* =arg min(f(x)).
 Optimization Type and Example
• The problem here is unconstrained. i.e. find x that
f(x)
minimizes R. That is no constrain on x.
• The local extremum have the property f’(x)=0
• Such point are called stationary points or critical
X points.

• The stationary point may be a local minimum or

maximum or a saddle point.
• If f’’(x) 0,It is a local minimum.
• If f’’(x), It is a local maximum.
• If f’’(x)0, It could be a saddle point.
• The absolute lowest/highest level of f(x) is called the
global minimum/maximum.
 Optimization Multivariate x
• In this case the unconstrained optimization problem is to find x that minimizes f(x) with x
ϵRn. i.e. there is no constrain on x. Since x is now a vector quantity it is needed to evaluate
the gradient ∂f/ ∂x=xf
• It can be shown that any local extremum will have the property xf=0 i.e.
∂f/ ∂x1=∂f/ ∂x2=…..∂f/ ∂x3…=0
• Such points are called stationary points or critical points.
• The stationary point may be a local minimum or maximum or saddle point.
• The type of critical point is decided by the nature of the Hessian = H i,j=∂2f/ ∂xi∂xj
Hessian is symmetric matrix It is guaranteed to have the real eigen (λs) values
If Hi,jis positive definite then it is a local minimum. i.e. If all the Eigen values (λs) of H are
Positive.
If Hi,jis negative definite then it is a local maximum. i.e. If all the Eigen values (λs) of H are
negative.
Constrained Optimization
The general constrained optimization task is to maximize or minimize a function
f(x) by varying x given certain constraints on x.

• For example find minimum of f(x1,x2,x3) = (x12+2x22 +x32); where IIx2II1

• For example Design the fastest vehicle with a constraint on fuel efficiency etc.
• All constraints can be converted into two types of constraints:-
• Equality constraints e.g. minimize f(x1,x2,x3) subject to (x1 +x2+x3)=1;
or (x1 +x2 +x3-1) =0

• Inequality constraints e.g. minimize f(x1,x2,x3) subject to (x1 +x2+x3)1;

or (x1 +x2 +x3-1)

• Canonical Form:-All optimization problems can be written as

Minimize f(x) subject to Constraint that x ϵ S Feasible Points
Where S= {x I∀ , g(i)(x)=0 and ∀ , h(j)(x)≤0}
Constrained Optimization Using Generalized Lagrange
Function
• The constrained optimization problem requires us to minimize the function
f(x) while ensuring that the point discovered belongs to the feasible set S.
• In general, this is a difficult problem, there are several techniques that achieve
this
• But a very common approach is to define a new function called the
Generalised Lagrangian Function
• L(x, λ, α) =f(x)+.g(i)(x) + αj.h(j)(x)

Where λ and α are two variable vectors added,f(x) is our original function,
g(i)(x)=Equality Function and h(j)(x)= Inequality Function.
Optimization Numerically
The Need of Numerical Optimization
• Numerical techniques deals in numbers rather than analytical expressions.
• Analytical techniques require explicit expressions for objective function in terms of
features (variables).e.g. J(w)=(w12+w22+w32+4)
• Analytical Methods work by setting the gradient of J(w)=0
• In many cases it either has very hard expression or doesn’t has any expression at all.
• Numerical techniques are suited to the real world problems. And the solutions are
practical. They are based on iterative processes.
• Here we try to drive the gradient of J(w)or wJ(w)=0
Optimization Gradient Descent Method
Iterative process
• Initial guess for w.
• Find the value of J(w). This may be
obtained through a program instead of an
expression.
• Find wJ(w) numerically.
• If wJ(w)=0 then stop else it is needed to
update the guess.
• Iteratively the guess is improved.
• The gradient descent is a very common Iterative process
method of improving the guess.
Gradient Descent Method Scalar Case
• The aim here is to improve our guess for
optimum (W*) such that we move from a
region of higher gradient to a region of lower
gradient.
• For scalar (i.e. one component) w this method
is simple.
• wnew = wold – α(dJ/dw)
• Here α is the positive arbitrary parameter and
it decides the rate of convergence.

Gradient Descent Method Scalar Case

Gradient Descent Method Vector Case
• At any point gradient gives the direction
of steepest descent.
• For vector (i.e. multiple components) w
this method is complex.

• The general gradient descent algorithm

is
wnew = wold – α(wJ)
• Here α is an arbitrary number chosen by
the user. It decides the rate of
convergence.
Gradient Descent Method
• Incases where it either has a very hard expressions or doesn’t has any
expression at all.
• Evaluation of gradient descent by finite difference method which is
complex.
• dJ/d(wj)={J(w1,w2 …(wj+ wj)…wn)-J(w1,w2,…wj…wn)}/(wj)
Where (w1,w2,…wj…wn) are the features of the system.
• The process becomes very expensive if features are large.
Gradient Descent Method
Disadvantage
• Evaluation of gradient descent by finite difference method which is complex.
• No of iteration are very much. It depends on learning rate α.
• This method can lead to converge to local optima instead of global optima .
Stopping Criterion
• Number of Iterations
• Desired error value ϵ is reached.
Hill Climbing Analogy of Optimization
• Start point –Initial guess
• Objective Function- the landscape corresponds to the
values of the objective function. Our goal is to find the
peak
• Local Search- to move in the direction of the steepest
uphill slope
• Iterative process- Each step takes us higher
• Constraints- Fencing wall and blindfolded climbers
• Drawback- The method get stuck at the local maxima
(optima) and may not reach the global optima.
Optimization Broad Search Methods
Three Broad Search Methods : calculus-based, enumerative and random.
• Calculus-based methods: These subdivide into two main classes: indirect and direct.
• Indirect methods seek local extrema by solving the usually nonlinear set of equations,
resulting from setting the gradient of the objective function equal to zero. Given a
smooth, unconstrained function, finding a possible peak starts by restricting search to
those points with slopes of zero in all directions.
• Direct (search) methods seek local optima by hopping on the function and moving in
a direction related to the local gradient. This is simply the notion of hill climbing: to
find the local best, climb the function in the steepest permissible direction.
• Both the calculus-based methods are local in scope: the optima they seek are the best
in a neighborhood of the current point.
 Optimization Broad Search Methods
Problem with calculus-based methods
• Miss the main event (the higher peak).
• They depend upon the existence of derivatives (well-defined slope values). Even if we
allow numerical approximation of derivatives, this is a severe shortcoming. The real
world of search is fraught with discontinuities and vast multimodal (i.e., consisting of
many ‘hills’) noisy search spaces.
• Methods depending upon restrictive requirements of continuity and derivative
existence, are unsuitable for many problems.
Optimization Broad Search Methods
Enumerative schemes
• Within a finite search space, the search algorithm starts looking at objective function
values at every point in the space, one at a time.
• Although the simplicity of the type of algorithm is attractive, and enumeration is a
very human kind of search, such schemes have applications wherein the number of
possibilities are small.
• Random walks and random schemes that search and save the best, in the long run, can
be expected to do no better than enumerative schemes. We must be careful to separate
the strictly random search
 Optimization Broad Search Methods
Methods from randomized techniques
•The genetic algorithm is an example of a search procedure that Uses random choice
as a tool, to guide a highly exploitative search through a coding of parameter space.
•More complex Problems are solved. If the space to be searched is large, is known not to be
perfectly smooth and unimodal, or is not well Understood; or if the fitness function is noisy;
and if the task does not require a global optimum to be found—i.e., if quickly finding a
sufficiently good solution is enough—a GA will give a fairly good result over other
methods.
•If the space is not large, it can be searched exhaustively by enumerative search methods,
and one can be sure that the best possible solution has been found.
Optimization Broad Search Methods
Methods from randomized techniques:-
• If the space is smooth and unimodal, a gradient descent algorithm will be much more
efficient than a GA.
• If the space is well understood, Search methods using domain-specific heuristics can
often be designed to outperform GA.
• If the fitness function is noisy, a one-candidate-solution-at-a-time Search method such
as simple hill climbing might be irrecoverably led astray by the noise; but GAs, since
they work by accumulating fitness statistics over many generations, are thought to
outperform robustly In the presence of small amounts of noise.
Similarity Between Conventional And Genetic
Optimization

Conventional Genetic
• Objective function • Fitness function
• Decision variable • Genetic representation
• Recombination • Cross over
• Perturbation • Mutation
• Set of decision variable values • Population
Intelligent Optimization Techniques
Intelligent optimization techniques involve approaches that leverage advanced algorithms,
often inspired by nature or machine learning, to efficiently search for optimal solutions.
Intelligent optimization techniques excel in handling complex, high-dimensional, and
dynamic problem spaces, making them valuable in various fields such as engineering,
finance, and artificial intelligence. Here are some types:-
Genetic Algorithms (GA): Mimicking the process of natural selection, GAs use genetic
operators like crossover and mutation to evolve a population of potential solutions.
Particle Swarm Optimization (PSO): Inspired by the collective behavior of swarms,
particles in the solution space adjust their positions based on their own and their neighbors'
best-known solutions
Ant Colony Optimization (ACO): Drawing inspiration from the foraging behavior of ants,
ACO uses pheromone trails to guide the search for optimal solutions.
Intelligent Optimization Techniques
Artificial Neural Networks (ANN): for Optimization: Using neural networks to model
and optimize complex functions, often in black-box scenarios where the underlying
function is not well-defined.
Evolutionary Algorithms: Encompassing various algorithms like Genetic
Programming, Evolution Strategies, and Differential Evolution, these methods evolve
populations of solutions over generations.
Tabu Search: A local search algorithm that prevents revisiting recently explored
solutions, enhancing exploration of the solution space.
Reinforcement Learning (RL): Applying RL techniques to optimize decisions by
learning from interactions with the environment.
Intelligent Optimization Techniques
Swarm Intelligence: Beyond PSO, other swarm-based techniques, like the Bee
Algorithm or Firefly Algorithm, leverage collective behaviour to find optimal solutions
Hyperparameter Optimization with Bayesian Optimization: Utilizing probabilistic
models to efficiently search for optimal hyperparameters in machine learning models.
Simulated Annealing: Though also mentioned in non-intelligent techniques, it can be
considered intelligent due to its ability to escape local optima by probabilistically
accepting worse solutions, mimicking the annealing process.
Meta-heuristic Algorithms
Meta-heuristic is a general algorithmic framework which can be applied
to different optimization problems with relatively few modifications to
make them adapted to a specific problem.
 References
• https://youtu.be/bLP1UuASh5g?feature=shared
• https://youtube.com/playlist?list=PLyqSpQzTE6M-SISTunGRBRiZk7op
YBf_K&feature=shared
• https://youtu.be/H0dvJ2A4clw?feature=shared
• M Gopal “Digital Control and state Variable Methods”,McGrawHill,4 th
ED,2017.
• G. Venter,” Review of Optimization Techniques” Encyclopedia of
Aerospace Engineering. Edited by Richard Blockley and Wei Shyy c 2010
John Wiley & Sons, Ltd.
Thank You