M’Hamed Bougara University of Boumerdes

Institute of Electrical and Electronic Engineering

(IGEE)

Applied Optimization

Chapter 1: Introduction to Optimization

Formulation of Optimization Problems

Dr. D FARES
[Link]@[Link]
Computer Engineering M01
Academic year: 2025/2026
 Introductory Problem
Electricity-Production Problem
 An electricity producer operates two production facilities that have capacities of 12 and
16 units per hour, respectively.
 This producer sells the electricity produced at $2 per unit per hour.
 The two production facilities share a cooling system that restricts their operation, from
above and below.
 More specifically, the sum of the hourly output from facility 2 and twice the hourly
output of facility 1 must be at least 8 units.
 Moreover, the sum of the hourly output from facility 2 and two-thirds of the hourly
output from facility 1 must be no more than 18 units.

The producer wishes to determine hourly production from the two facilities to maximize
total revenues from energy sales.

Solve this problem ?

Optimization Terminology
1- Understand the
Engineering Problem
to be solved

2- Mathematical Formulation of
the Problem

3- Select a suitable Optimization

Method /Algorithm 4- Apply The
Method /Algorithm

Obtain Optimum
Solutions 3
Mathematical description of an optimization problem

 An optimization problem has the general form:

Find values of: X = (𝑥1 , 𝑥2, 𝑥3, ....𝑥𝑛 )

that minimize/maximize : 𝑓 𝑋
subject to : Constraints

 Three main elements construct the mathematical model:

Objective
Objective function function
Decision variables
Constraints Decision
Constraints
variables

Applied Optimization IGEE/UMBB 4

 Mathematical description of an optimization problem

Minimize : f (x)
subject to : hi(x) = 0 ( i = 1, 2, . . . , m)
gj(x) ≤ 0 ( j = 1, 2, . . . , p)

• x ϵ ℝn is n-dimensional vector of decision variables.

• f : ℝn →ℝ is the objective function.

• hi(x) and gi(x) are called the equalities and inequalities constraints.

• m and p are the number of equalities and inequalities constraints (depends on the problem).

• Optimal solution 𝒙∗ yields the smallest value of f among all vectors that satisfy the
constraints.
Applied Optimization IGEE/UMBB 5
Mathematical description of an optimization problem

 a maximization problem max f (x) can be easily converted into an equivalent

minimization problem min (−f (x)) and vice versa.

 If 𝒙∗ is the minimizer of f (x) , 𝒙∗ is the maximizer of −f (x).

Applied Optimization IGEE/UMBB 6

 Elements for optimization / mathematical model
Objective
Objective function function

 Also called Cost function. Decision

Constraints
variables
 A mathematical expression that evaluates the performance of a given solution.

 For a set of decision variables x , it produces is a real number f(x).

 Always scalar-valued.

 The goal of the optimization process is to find decision variables that maximize or minimize this
objective function

Applied Optimization IGEE/UMBB 7

Elements for optimization / mathematical model
Decision variables: (Design Variables)

 All optimization problems require at least one decision variable.

 The choices you can control and manipulate to optimize the objective function.

 Represented by a column vector of IR𝑛 (n variables), often denoted by

X = (𝑥1 , 𝑥2, 𝑥3, ....𝑥𝑛 )
Objective
 Value of each decision variable xj (j = 1, 2 .... n) may be: function
 Continuous (default)
 Binary (equals 0 or 1)
 Integer (equals 1 or 2 or 3 ...or N) Constraints
Decision
variables
 Discrete (e.g., takes values 10 mm or 20 mm or 30 mm, etc.

Applied Optimization IGEE/UMBB 8

Elements for optimization / mathematical model
Decision variables: (Design Variables)

 The optimization problem has a set of candidate solutions.

 Each candidate solution X is a vector of decision variables X= (𝑥1 ,...., 𝑥𝑛 ).
 The number of candidate solutions is not the number of decision variables n.

𝑋1 = (𝑥11 , 𝑥21 , 𝑥31 ...., 𝑥𝑛1 )

Set of Candidate 𝑋 2 = (𝑥12 , 𝑥22 , 𝑥32 ...., 𝑥𝑛2 )

Solutions
𝑋 3 = (𝑥13 , 𝑥23 , 𝑥33 ...., 𝑥𝑛3 )

Decision variables

Applied Optimization IGEE/UMBB 9

Elements for optimization/ mathematical model
Constraints:

 The mathematical description of the circumstances, requirements, conditions, or limitations specifying

the values that the decision variables can take.
Objective
 Most problems often have implicit or explicit constraints. function

 Two types of constraints:

Decision
Constraints
variables
1) Equality constraints : h(x) = 0

1) Inequality constraints: g(x) ≤ 0

 Equality constraints are sometimes decomposed into two inequality constraints:

h(x) ≤ 0
h(x) = 0 < == > ቊ
h(x) ≥ 0

Applied Optimization IGEE/UMBB 10

Elements for optimization/ mathematical model
Constraints:
 Constraints limit the possible values of the decision variables by imposing physical, financial, or other
limits.

 We include constraints in such problems to prevent the optimization algorithm from suggesting an
infeasible solution:
 A distance or time cannot be negative, T ≥ 0, d ≥ 0
 The number of hours you spend per day on your activities cannot exceed 24 hours (h ≤ 24)

Applied Optimization IGEE/UMBB 11

Elements for optimization/ mathematical model
Constraints:
 Some constraints are simply upper or lower bounds on the design variables

Minimize : f (x)
subject to : 𝒙 𝝐 [a, b]

 x ϵ [a, b] is called a bracketing constraints

 Applying constraints to a problem can affect the solution

Applied Optimization IGEE/UMBB 12

Feasible solution / Feasible set
 The feasible set Ω : is the set of all possible solutions X that satisfy the constraints of the problem

 Feasible solution:

A solution X is called a feasible solution if and only if it satisfies all constraints of the problem:

 Feasible solution: X= (𝑥1 ,...., 𝑥𝑛 ) ∈ Ω

 Unfeasible solution: X= (𝑥1 ,...., 𝑥𝑛 ) ∈/ Ω

 Optimal solution: the one solution (solutions) that optimize (minimize or maximize) the objective function:

𝑿∗ = (𝑥1∗ ,...., 𝑥𝑛∗ ) ∈ Ω

f(𝑿∗ ) is the minimum (maximum)

Applied Optimization IGEE/UMBB 13

Feasible Region
 The feasible region Ω: (the feasible set ) can be described by a the set of constraints given by
equalities and inequalities in the functional form:

 Ω = 𝑋 𝜖 ℝ𝑛 ∶ hi(X) = 0 , gj(x) ≤ 0, i 𝜖 m, j 𝜖 p
 The mathematical form can be rewritten as:

Minimize : f (X)
subject to : 𝑿𝝐Ω

 We often use the equality and inequality functions to define constraints rather than the set membership
(X∈ Ω ).

 In unconstrained problems, the feasible set Ω is IR𝑛 .

Applied Optimization IGEE/UMBB 14

Formulate the Electricity-Production Problem
 Introductory Problem
Electricity-Production Problem
 An electricity producer operates two production facilities that have capacities of 12 and
16 units per hour, respectively.
 This producer sells the electricity produced at $1 per unit per hour.
 The two production facilities share a cooling system that restricts their operation, from
above and below.
 More specifically, the sum of the hourly output from facility 2 and twice the hourly
output of facility 1 must be at least 8 units.
 Moreover, the sum of the hourly output from facility 2 and two-thirds of the hourly
output from facility 1 must be no more than 18 units.

The producer wishes to determine hourly production from the two facilities to maximize
total revenues from energy sales. ?
 Introductory Problem
Electricity-Production Problem
 An electricity producer operates two production facilities that have capacities of 12 and
16 units per hour, respectively.
 This producer sells the electricity produced at $1 per unit per hour.
 The two production facilities share a cooling system that restricts their operation, from
above and below.
 More specifically, the sum of the hourly output from facility 2 and twice the hourly
output of facility 1 must be at least 8 units.
 Moreover, the sum of the hourly output from facility 2 and two-thirds of the hourly
output from facility 1 must be no more than 18 units.

The producer wishes to determine hourly production from the two facilities to maximize
total revenues from energy sales. ?
 Introductory Problem
Electricity-Production Problem
 An electricity producer operates two production facilities that have capacities of 12 and
16 units per hour, respectively.
 This producer sells the electricity produced at $1 per unit per hour.
 The two production facilities share a cooling system that restricts their operation, from
above and below.
 More specifically, the sum of the hourly output from facility 2 and twice the hourly
output of facility 1 must be at least 8 units.
 Moreover, the sum of the hourly output from facility 2 and two-thirds of the hourly
output from facility 1 must be no more than 18 units.

The producer wishes to determine hourly production from the two facilities to maximize
total revenues from energy sales. ?
The objective of the problem?

• The producer wishes to determine hourly production from the two facilities to maximize total revenues
from energy sales.

 Maximize f (X) = total revenues

Decision variables:
• An electricity producer operates two production facilities that have capacities of 12 and 16 units per hour,
respectively. This producer sells the electricity produced at $2 per unit per hour.

 The decision variables are the number of units produced by each facility:
• x1: number of units produced by facility 1
• x2: number of units produced by facility 2
• X=(x1, x2)

The objective function:

 f (X) = 2 x1 + 2 x2
Applied Optimization IGEE/UMBB 19
Constraints?

 two production facilities that have capacities of 12 and 16 units per hour, respectively.
 x1 ≤ 12
 x2 ≤ 16

 The sum of the hourly output from facility 2 and twice the hourly output of facility 1 must be at least 8
units.
 2 x1 + x2 ≥ 8

 the sum of the hourly output from facility 2 and two-thirds of the hourly output from facility 1 must be no
more than 18 units.
2
 x1 + x2 ≤ 18
3

Implicit constraints ?
 x1 ≥ 0
 x2 ≥ 0

Applied Optimization IGEE/UMBB 20

Final formulation of the Electricity-Production Problem ?

Maximize f (X) = 2 x1 + 2 x2 (1)

Subject to
2 x1 + x2 ≥ 8 (2)
2
x1 + x2 ≤ 18 (3)
3
x1 ≤ 12 (4)
x2 ≤ 16 (5)
x1, x2 ≥ 0 (6)

 The solution that maximizes f(X), the optimal solution, is denoted 𝑿∗ = (𝑥1∗ , 𝑥2∗ ), called the maximizer.

 Any point X(x1, x2) satisfying equations (2) to (6) is called a feasible solution, it is not necessary the
optimal solution.

 The set of all candidate solutions X satisfying the constraints (2) to (6) is called the feasible set Ω.

Applied Optimization IGEE/UMBB 21

 Natural Gas-Transportation Problem
A natural gas producer owns two gas fields and serves two markets. The company would like to determine
how to transport natural gas from the two fields to the two markets to minimize its total transportation cost.

 Capacity of each gas field:

Field 1: Capacity= 7 units
Field 2: Capacity= 12 units

 Demand of each market:

Market 1: Capacity= 10 units
Market 2: Capacity= 8 units

 Transportation cost between each gas field and market [$/unit]:

Applied Optimization IGEE/UMBB 22

The objective of the problem?

Minimize f (X) = Total transportation cost.

The decision variables:

• x: The units of natural gas transported from field i to market j.
• We can define the variable by 2 index sets 𝑥𝑖,𝑗 :
i: field from which the gas is being transported
j: market to which it is being shipped
𝑥1,1 : units of natural gas transported from field 1 to market 1
𝑥1,2 : units of natural gas transported from field 1 to market 2
𝑥2,1 : units of natural gas transported from field 2 to market 1
𝑥2,2 : units of natural gas transported from field 2 to market 2

X = (𝑥1,1 , 𝑥1,2 , 𝑥2,1 , 𝑥2,2 )

The objective function:
f (X) = 5 𝑥1,1 + 4 𝑥1,2 + 3 𝑥2,1 +6 𝑥2,2

Applied Optimization IGEE/UMBB 23

Constraints?

1) capacity limits on how much can be produced by each field:

Capacity of each gas field:
Field 1: Capacity= 7 units
Field 2: Capacity= 12 units
𝑥1,1 + 𝑥1,2 ≤ 7
𝑥2,1 + 𝑥2,2 ≤ 12

2) Demand of each market should be satisfied:

Market 1: Capacity= 10 units
Market 2: Capacity= 8 units

𝑥1,1 + 𝑥2,1 =10

𝑥1,2 + 𝑥2,2 =8

3) implicit constraints ?
𝑥1,1 ≥ 0 ; 𝑥1,2 ≥ 0 ; 𝑥2,1 ≥ 0 ; 𝑥2,2 ≥ 0
Applied Optimization IGEE/UMBB

24
Final formulation of the Natural Gas-Transportation Problem:

Minimize f (X) = 5 𝑥1,1 + 4 𝑥1,2 + 3 𝑥2,1 +6 𝑥2,2 (1)

Subject to
𝑥1,1 + 𝑥1,2 ≤ 7 (2)
𝑥2,1 + 𝑥2,2 ≤ 12 (3)

𝑥1,1 + 𝑥2,1 =10 (4)

𝑥1,2 + 𝑥2,2 =8 (5)

𝑥1,1 ≥ 0 ; 𝑥1,2 ≥ 0 ; 𝑥2,1 ≥ 0 ; 𝑥2,2 ≥ 0 (7)

 Any point X = (𝑥1,1 , 𝑥1,2 , 𝑥2,1 , 𝑥2,2 ) satisfying equations (2) to (7) is a feasible solution.

 The set of all candidate solutions X satisfying the constraints (2) to (7) is called the feasible set Ω.

Applied Optimization IGEE/UMBB 25

 Local and Global Optimality

 Feasible Region/Graphical Optimization

Local and Global Optimality
Example:

• Local minimizers: x=1 , x= 4

• Local maximizers: x= -3 , x=3 , x= 5

• Global minimizer: x=1

• Global maximizer: x= -3

• Points x from the range [-1 0] are both

local minimum and maximum, but not global

Applied Optimization IGEE/UMBB 27

 Local and Global Optimality
Global Minimizer:
The point 𝑋 ∗ 𝜖 Ω is a the global minimizer of 𝑓 over Ω if:
𝑓(𝑋 ∗ ) ≤ 𝑓(𝑋 ) for all X 𝜖 Ω
Local Minimizer:
The point 𝑋 ∗ 𝜖 Ω is a the local minimizer of 𝑓 over Ω if there exists a distance ε > 0 such that:
𝑓(𝑋 ∗ ) ≤ 𝑓(𝑋 ) for all X 𝜖 Ω and 𝑋 − 𝑋 ∗ ≤ ε

Global Maximizer:
The point 𝑋 ∗ 𝜖 Ω is a the global maximizer of 𝑓 over Ω if:
𝑓(𝑋 ∗ ) ≥ 𝑓(𝑋 ) for all X 𝜖 Ω
Local Maximizer:
The point 𝑋 ∗ 𝜖 Ω is a the local maximizer of 𝑓 over Ω if there exists a distance ε > 0 such that:
𝑓(𝑋 ∗ ) ≥ 𝑓(𝑋 ) for all X 𝜖 Ω and 𝑋 − 𝑋 ∗ ≤ ε

Applied Optimization IGEE/UMBB 28

 Local and Global Optimality
 If we replace ≥ by > (or ≤ by <) we have strict maximizer (strict minimizer).

 Strict or Strong maximizer/minimizer.

Strong Global Minimizer:

𝑓(𝑋 ∗ ) < 𝑓(𝑋 ) for all X 𝜖 Ω

Strong Local Minimizer:

𝑓(𝑋 ∗ ) < 𝑓(𝑋 ) for all X 𝜖 Ω and 𝑋 − 𝑋 ∗ ≤ ε

Strong Global Maximizer:

𝑓(𝑋 ∗ ) > 𝑓(𝑋 ) for all X 𝜖 Ω

Strong Local Maximizer:

𝑓(𝑋 ∗ ) > 𝑓(𝑋 ) for all X 𝜖 Ω and 𝑋 − 𝑋 ∗ ≤ ε

Applied Optimization IGEE/UMBB 29

 Local and Global Optimality
Example:

• Weak local minimizer: point B

⇒ 𝑓 at point B is equal to 𝑓 of the points
having close distance to B 𝑋 − 𝑋 ∗ ≤ ε

• Strong local minimizer: points A, C,

and D.

• Strong global minimizer: point C.

Applied Optimization IGEE/UMBB 30

Local and Global Optimality
Example:

𝑋 ∗ is a Strong global minimizer

Applied Optimization IGEE/UMBB 31

Feasible Region/Graphical Optimization
 The feasible region Ω can be described by a the set of constraints given by equalities and
inequalities in the functional form:
Ω = 𝑋 𝜖 ℝ𝑛 ∶ hi(X) = 0 , gj(x) ≤ 0, i 𝜖 m, j 𝜖 p

Graphical Optimization

Feasible / Non feasible problems

Feasible region of Electricity production Problem
 Maximize f (X) = 2 x1 + 2 x2
Subject to
2 x1 + x2 ≥ 8
2
x1 + x2 ≤ 18
3
x1 ≤ 12
x2 ≤ 16
x1, x2 ≥ 0 .

2 x1 + x2 ≥ 8
Boundary
Linear inequality

 We can graph these inequality constraints.

 Feasible region of Electricity production Problem
Maximize f (X) = 2 x1 + 2 x2
Subject to
2 x1 + x2 ≥ 8
2
x1 + x2 ≤ 18
3
x1 ≤ 12
x2 ≤ 16
x1, x2 ≥ 0

 The feasible region is the overlap

of the constraint graphs .

 All the points belonging to the feasible region Ω

are interior points, they are candidate solutions.

 Six corners: (0, 16) (3, 16) (12, 10) (12, 0)

(4, 0) (0, 8)
Nonlinear objective functions
=> the optimum values can either be at the boundaries or between them.
Linear objective functions

=> the optimum values can only be at the boundaries.

 Ω = 𝑋 𝜖 ℝ𝑛 ∶ hi(X) = 0 , gj(x) ≤ 0, i 𝜖 m, j 𝜖 p

 If the constraints are all inequalities, they divide the points in space into three types:

Interior points  a point for which gj(x) < 0 for all j.

Boundary points  a point for which at least one gj(x) = 0.

Exterior points  a point for which at least one gj(x) > 0.

Feasible region of Electricity production Problem
 Feasible region of Electricity production Problem
Maximize f (X) = 2 x1 + 2 x2
Subject to
2 x1 + x2 ≥ 8
2
x1 + x2 ≤ 18
3
x1 ≤ 12
x2 ≤ 16
x1, x2 ≥ 0

 The feasible region is highlighted

with dark dots, the interior of a
polygon.
 Feasible region of Electricity production Problem
Maximize f (X) = 2 x1 + 2 x2
Subject to
2 x1 + x2 ≥ 8
2
x1 + x2 ≤ 18
3
x1 ≤ 12
x2 ≤ 16
x1, x2 ≥ 0

 The optimal solution:

𝑿∗ = (𝑥1∗ , 𝑥2∗ ) = (12, 10).
𝒇∗ = f (12, 10) = 44

 𝑿∗ = (12, 10) is the global maximizers

since 𝑓(𝑋 ∗ ) = 44 ≥ 𝑓(𝑋 ) for all X𝜖 Ω
Feasible Region
Example:

minimize 𝑓 𝑥 = 𝑥12 + 𝑥22 + 2𝑥2

subject to: ℎ1 (x) = 𝑥12 + 𝑥22 − 1= 0
𝑔1 (x) = 𝑥1 + 𝑥2 − 0.5 ≥ 0
𝑔2 (x) = 𝑥1 ≥ 0
𝑔3 (x) = 𝑥2 ≥ 0

ℎ1 (x) => 𝑥12 + 𝑥22 = 1

 Circle of radius 1 centered at the origin.

𝑔1 (x) => 𝑥2 ≥ −𝑥1 + 0.5

 straight line.

𝑔2 (x) and 𝑔3 (x)

 Nonnegativity.

 the feasible region is the arc of circle ℎ1 (x) = 0 located in the first quadrant of the (x1,x2) plane.
Applied Optimization IGEE/UMBB 41
Feasible region
Matlab Code to plot the feasible region:

% Define the objective function f(x)

F = X1.^2 + X2.^2 + 2 * X2; % Plot the surface of the function
surf(X1, X2, F, 'FaceAlpha', 0.5, 'EdgeColor', 'none'); % Surface
% Define the constraints plot
h1 = X1.^2 + X2.^2 - 1; colorbar; % Add color bar
g1 = X1 + X2 - 0.5;
g2 = X1; % Overlay the feasible region
g3 = X2; F_feasible = NaN(size(F)); % Initialize F for feasible region
F_feasible(feasible_region) = F(feasible_region); % Assign feasible
% Create a logical array for the feasible region
values
feasible_region = (h1 <= 0) & (g1 >= 0) & (g2 >= 0)
& (g3 >= 0); surf(X1, X2, F_feasible, 'FaceColor', 'g', 'FaceAlpha', 0.5); %
% Create the 3D surface plot Feasible region
figure;
hold on;

Applied Optimization IGEE/UMBB 42

Feasible region
Example:

 Geometrically, this set is given by the points in the intersection of two disks corresponding to the constraints

Applied Optimization IGEE/UMBB 43

Feasible region

Example:
x∈ IR2  a 2D
• x1+x2 ≤ 5
• x1− x2 ≤ 2
• x1 ≥ 0
• x2 ≥ 0

Applied Optimization IGEE/UMBB 44

Feasible region
Example:
x∈ IR3  a 3D
· x1​+x2​ + x3 ​≤ 10
· x1 ≥ 0
· x2 ≥ 0
· x3 ≥ 0

Applied Optimization IGEE/UMBB 45

Feasible region
Example:
x12+x22 ≤ 4

 The feasible region is

a Circle with radius 2

Applied Optimization IGEE/UMBB 46

Feasible region

Example:
• X1 + X2 ≤ 5
• X1 ≥ 0
• X2 ≥ 0
• X1 , X2 are integers

Applied Optimization IGEE/UMBB 47