Optimization Techniques in Machine Learning
(MAS5007)
Module-1
Understanding the Optimization: Engineering application of
Optimization – Statement of an Optimization problem – Optimal
Problem formulation – Classification of Optimization problem.
Optimum design concepts: Definition of Global and Local optima
Optimization Problems:
Optimization problems are mathematical problems where we
aim to find the best solution from a set of feasible solutions.
The "best" usually means either maximizing or minimizing a
particular objective function, subject to certain constraints.
Here are the main types of optimization problems with brief
explanations and simple examples:
1. Linear Programming (LP)
Definition: Optimization where both the objective function
and constraints are linear.
Example:
Maximize: Z = 3x + 2y
Subject to:
x + y ≤ 4,
x ≥ 0, y ≥ 0
Use case: Resource allocation, production planning.
2. Integer Programming (IP)
Definition: Same as LP, but some or all variables must be
integers.
Example:
Maximize: Z = 5x + 4y
Subject to:
2x + y ≤ 8,
x, y ≥ 0 and integer
Use case: Scheduling, assigning tasks.
3. Non-linear Programming (NLP)
Definition: Either the objective function or some constraints
are non-linear.
Example:
Minimize: Z = x² + y²
Subject to:
x+y=1
Use case: Portfolio optimization, energy management.
4. Dynamic Programming (DP)
Definition: Breaks a complex problem into simpler
subproblems and solves each just once, storing the solutions.
Example: Finding the shortest path in a weighted graph (like
Dijkstra’s algorithm).
Use case: Route planning, operations research.
5. Convex Optimization
Definition: A special case of NLP where the objective is a
convex function, and constraints form a convex set.
Example:
Minimize: Z = x² + y²
Subject to:
x+y=1
(This is convex because x² + y² is convex)
Use case: Signal processing, control systems.
6. Combinatorial Optimization
Definition: Optimization over discrete and finite solution
space, often involving combinations.
Example: Travelling Salesman Problem (TSP) – finding the
shortest route that visits each city once.
Use case: Network design, scheduling.
7. Stochastic Optimization
Definition: Optimization under uncertainty, where some
variables are probabilistic.
Example: Maximize expected profit when demand is
uncertain.
Use case: Stock market models, supply chain management.
8. Multi-objective Optimization
Definition: Optimizing multiple objectives simultaneously,
often conflicting.
Example: Maximize profit and minimize environmental
impact.
Use case: Engineering design, sustainable development.
Global Minima vs Local Minima:
Local Optima
A local optimum refers to a point within the domain of a
function where the function attains the lowest (or highest)
value in its local neighborhood. Mathematically, a point x* is
said to be a local minimum (maximum) if there exists a
neighborhood around x* such that f(x*) ≤≤f(x) (or
f(x*) ≥≥ f(x)) for all x within that neighborhood.
In other words, a local optimum is a point where the function
is lower (or higher) than its neighboring points.
Global Optima
The global optimum of a function refers to the point within its
domain where the function attains the lowest (or highest)
value over the entire function. In other words, it is the overall
best solution for the optimization problem. a common form
for a global maximum is a concave downward quadratic
function:f(x)=−a(x−b)2+cf(x)=−a(x−b)2+c, where a > 0
determines the concavity, b is the x-coordinate of the
maximum, and c is the maximum value of the function.
Local and Global Optimum in Convex and Non-Convex
function
Convex Function
In a convex or concave function since the graph is bowl-
shaped both the local optimum value and global optimum are
the same value we can see in the below graph that the graph
has only-one valley so we easily find the optimum value.
According to the need, we can transform our objective
function from convex to concave if we want to find the
maximum of the objective function and vice versa if we want
to find the minimum of the objective function.
Local(or global) minimum in convex function
What we have done here is on the x-axis, we have different
values for the decision variable x, and on the y-axis, we have
the function value. And when you plot this you can quite
easily notice in the graph that marked the point at which this
function attains its minimum value.
So, there is no question of multiple minima to choose from
there is only one minimum here, and that is marked in the
graph. So, in this case, we would say that this minimum is
both a local minimum and also a global minimum.
In fact, we can say it is a local minimum because, in the
vicinity of this point, this is the best solution that you can get.
And if the solution that we get in the vicinity of this point is
also the best solution globally then we also call it the global
minimum.
Thus, a point can be both a local and a global minimum if it
outperforms its neighbors and stands as the best solution
globally.
Non-convex Function
Non-convex optimization poses significant challenges due to
the presence of multiple local optima. Various optimization
algorithms, such as genetic algorithms, simulated annealing,
and particle swarm optimization, are utilized to explore the
search space and find good solutions. However, none of these
methods guarantee finding the global optimum, and their
effectiveness depends on the specific characteristics of the
problem at hand.
Now, take a look at the graph below. Here we have a function
and again it is a univariate optimization problem. So, on the x-
axis, we have different values of the decision variable and on
the y-axis, we plot the function. Now, we may notice that
there are two points where the function attains a minimum.
Accordingly, we can see
Local Minimum (x1):* This is a point, denoted as x1*,
where the function has a lower value than at any nearby
points in its immediate vicinity. In the neighborhood of
x1*, the function does not attain a lower value. However,
x1* might not be the absolute lowest point for the entire
function, as there could be other points with even lower
values in different regions.
Global Minimum (x2):* This is the absolute lowest point
of the entire function, considering all possible values
over its entire domain. In our description, x2* is the
global minimum because it represents the lowest point
for the entire function, surpassing the values at x1* and
any other potential local minima.