Module: Optimization with constraints
Master 1
Lecturer: Pr. Taieb Hamaizia
—————————————————–
1 Chapter 01:
1.1 Introduction in optimization with constraints
Optimization with constraints is a fundamental concept in mathematics, engi-
neering, economics, and various other …elds. It involves the process of maximiz-
ing or minimizing a function subject to certain constraints. These constraints
can represent limitations on the variables involved in the optimization problem.
The general form of an optimization problem with constraints can be ex-
pressed as:
Minimize (or maximize)
f (x1 ; x2 ; :::; xn )
Subject to:
g1 (x1 ; x2 ; :::; xn ) 0
g2 (x1 ; x2 ; :::; xn ) 0
...
gm (x1 ; x2 ; :::; xn ) 0
Where:
f is the objective function that you want to minimize or maximize.
x1 ; x2 ; :::; xn are the variables that you can adjust to optimize the objective
function.
g1 ; g2 ; :::; gm are the constraint functions that de…ne the limitations or con-
ditions that the decision variables must satisfy.
The goal is to …nd the values of the decision variables (x1 ; x2 ; :::; xn ) that
optimize the objective function (f ) while still satisfying all the constraints
(g1 ; g2 ; :::; gm ).
1.2 Types of problems
Optimization problems with constraints can be classi…ed into several types based
on various characteristics.
1
1.2.1 Linear Programming (LP):
In linear programming, both the objective function and the constraints are
linear.
Example:
8
>
> min f (x; y; z) = min x + y z
<
st
>
> g1 (x; y; z) = 2x + y = 0
:
g2 (x; y; z) = x + 3z = 1
1.2.2 Nonlinear Programming (NLP):
In nonlinear programming, either the objective function or the constraints (or
both) are nonlinear.
Example:
8
>
> min f (x) = min 10x (0:01x3 + 50)
<
st
>
> x 1000
:
x 800
1.2.3 Quadratic Programming (QP):
In quadratic programming, the objective function is quadratic, and the con-
straints can be linear or quadratic.
Example:
8
>
> min f (x; y) = min x2 y 2
<
st
>
> x + y 100
:
2x + y 240
1.2.4 Convex Optimization:
Convex optimization deals with optimization problems where the objective func-
tion and the feasible region (de…ned by constraints) are convex.
Example:
8
>
> min f (x; y) = min 100x + 120y 0:5x2 0:8y 2
<
st
>
> x + y 100
:
2x + 3y 240
1.2.5 Stochastic Optimization:
Stochastic optimization deals with optimization problems where some parame-
ters are uncertain or subject to randomness.
2
1.3 Constraints
Constraints in optimization refer to the conditions or limitations that must be
satis…ed when …nding the optimal solution to a problem. These constraints
de…ne the feasible region, which is the set of all possible solutions that meet the
problem’s requirements.
Constraints can be classi…ed into several types, including:
1.3.1 Equality Constraints:
Constraints that require certain expressions to be equal.
g(x) = 0
1.3.2 Inequality Constraints:
Constraints that require certain expressions to be less than or equal to or greater
than or equal to some values.
h(x) 0
or
g(x) 0
1.3.3 Bound Constraints:
Constraints that limit the variables to speci…c ranges.
xmin x xmax
1.3.4 Linear Constraints:
Constraints that involve linear combinations of variables.
n
X
ai xi b
i=0
1.3.5 Nonlinear Constraints:
Constraints that involve nonlinear functions of the variables.
f (x) 0
1.3.6 Integer Constraints:
Constraints that restrict the variables to integer values.
xi 2 Z
3
1.3.7 Discrete Constraints:
Constraints that restrict the variables to discrete values from a …nite set.
xi 2 fa1 ; a2 ; :::; ak g
Remark 1 Constraints play a crucial role in optimization problems as they
de…ne the boundaries within which the optimal solution must lie.
1.4 How to determine the constraints
Determining the constraints in an optimization problem involves identifying the
limitations or conditions that the solution must satisfy
- Determine the feasible region by considering the intersection of all con-
straints.
In higher dimensions, this may involve …nding the intersection of planes,
surfaces, or hyperplanes de…ned by the constraints.
If the problem is in two dimensions, …nd the intersection points of the con-
straint lines or curves. These intersection points represent potential vertices of
the feasible set.
Examples
1.0
-1.0 0.5 -1.0
-0.5 0.0 -0.5
z 0.0 0.0
-0.5
y 0.5 0.5 x
-1.0
1.0 1.0
x2 + y 2 + z 2 1
4
x+y 2 x2 + y 2 25
x y 5 x y2 + 3 0
