Basic Concepts of Optimization
Unimodal and multi modal functions
Functions with only one extreme point, which is termed as
Unimodal otherwise it is termed as Multimodal
1
Basic Concepts of Optimization
Continuous and Discontinuous Functions
• optimization (analytical or numerical)
• It preferable and more convenient to work with continuous
functions of one or more variables than with functions
containing discontinuities.
• Functions having continuous derivatives are also preferred.
2
Basic Concepts of Optimization
The property of continuity. A function of a single variable x is
continuous at a point xo if
If f(x) is continuous at every point in region R, then f(x) is said
to be continuous throughout R.
3
Basic Concepts of Optimization
Not continuous For case B, the function of x has a "kink" in it,
If the decision variables but f(x) does satisfy the property of continuity.
take only discrete values, However, f'(x) = df(x)/dx does not.
the objective function will Therefore, the function in case B is continuous
be discontinuous. but not continuously differentiable.
4
Convexity & Concavity of Functions of One & Two Variables
A function f is said to be concave at an interval I if, for all pairs
of points on the f (x) graph, the line segment that connects these
two points passes below the f(x) curve.
A function 𝑓 is said to be convex at an interval I if, for all pairs of
points on the f(x) graph, the line segment that connects these two
points passes above the f(x) curve.
5
Convexity & Concavity of Functions of One & Two Variables
6
Convexity & Concavity of Functions of One & Two Variables
Convex is negative of Concave
7
Cont…
Example: Analysis for convexity and concavity
For each of the following functions determine if f(x) is convex,
concave, strictly convex, strictly concave, all, or none of
these classes in the range
8
Cont…
To determine convexity or concavity of a function of multiple
variables, the eigenvalues of its Hessian matrix is examined and the
following rules apply.
If all eigenvalues of the Hessian are positive the function is strictly
convex.
If all eigenvalues of the Hessian are negative the function is strictly
concave.
If some eigenvalues are positive and some are negative, or if some
are zero, the function is neither strictly concave nor strictly convex.
9
Cont…
1
0
Cont…
1
1
Cont…
A set of points x satisfying the relation is convex if the Hessian matrix H(x)
is a real symmetric positive-semidefinite matrix.
H(x) is the matrix of second partial derivative of f(x) with respect to each xi:
The status of H can be
used to identify the
character of extrema
1
2
Cont…
Example: Classify the following function using the categories in
Table (previous slide) or state that it does not belong in any of the
categories.
1
3
Unconstrained multivariable optimization problem
48
Linear Programing (LP)
• LP is one of the most widely used optimization techniques and perhaps the most
effective
• It deals with the optimization (maximization or minimization) of linear objective
functions subject to linear constraints.
solution methods
o Graphical Solution
o Simplex Method
• LP problems involving only two variables can be effectively solved by a graphical
technique which provides a pictorial representation of the solution.
• step 1: formulate the given problem as a linear programming problem
• step 2: plot the given constraints as equalities on x1 − x2 coordinate plane and determine the
convex region formed by them
• step 3: determine the vertices of the convex region and find the value of objective function at
each vertex. The vertex which gives the optimal value of the objective function gives the desired
optimal solution to the problem. 491
5
Example 1
Solution
51
Example 2
Solution
52
Example 3
Solution
53
Standard form of LP
54
Simplex Method
o For linear programming problems involving two variables, the
graphical solution method introduced before is convenient.
o However, for problems involving more than two variables or problems
involving a large number of constraints, it is better to use solution
methods that are adaptable to computers.
o One such method is called the simplex method
o It provides us with a systematic way of examining the vertices of the
feasible region to determine the optimal value of the objective
function.
55
Simplex Method
o The basic LP problem consists of two major parts: the objective
function and a set of constraints. In Standard Form
56
Simplex Method
57
Simplex Method
o Note that for a linear programming problem in standard form,
the objective function is to be maximized, not minimized
o A basic solution of a linear programming problem in standard
form is a solution ( x1, x2,…xn, s1, s2,…sm) of the constraint
equations in which at most m variables are nonzero––the
variables that are nonzero are called basic variables. A basic
solution for which all variables are nonnegative is called a basic
feasible solution.
58
Simplex Method-Pivoting
60
Simplex Method
The simplex method is carried out by performing elementary row operations on a
matrix that we call the simplex tableau. This tableau consists of the augmented
matrix corresponding to the constraint equations together with the coefficients of
the objective function
61
Simplex Method
62
Simplex Method-Pivoting
Example: The Simplex Method with Three Decision Variables
63
Simplex Method-Pivoting
64
Simplex Method-Example
A manufacturer produces three types of plastic fixtures. The time required
for molding, trimming, and packaging is given in the Table below. (Times
are given in hours per dozen fixtures.)
How many dozen of each type of fixture should be produced to obtain
a maximum profit?
65
Simplex Method-Example
66
Simplex Method-Example
67
Non-Linear Programming
68
Non-Linear Programming
o Direct Substitution
o Lagrange multiplier method
69
Non-Linear Programming-Direct Substitution
o One method of handling just one or two linear or nonlinear
equality constraints is to solve explicitly for one variable and
eliminate that variable from the problem formulation.
o This is done by Direct Substitution in the objective function and
constraint equations in the problem.
Example
Suppose you want to minimize the following objective function that is
subject to a single equality constraint
70
Non-Linear Programming-Direct Substitution
71
Non-Linear Programming-Lagrangian Multiplier Method
72
Non-Linear Programming-Lagrangian Multiplier Method
Example
73
Non-Linear Programming-Problems Containing only Equality Constraints
74
Non-Linear Programming-Problems Containing only Equality Constraints
75
Non-Linear Programming-Problems Containing only inequality Constraints
76
Non-Linear Programming-Problems Containing only inequality Constraints
77
Non-Linear Programming-Example
78
Non-Linear Programming-solution
79
Non-Linear Programming-Solution
80
Non-Linear Programming-Solution
81
Non-Linear Programming-Examples
1. Find the dimensions of a box of largest volume that
can be inscribed in a sphere of unit radius
2. Find the optimal dimensions for a heated cylindrical
tank designed to hold 10 m3 of fluid. The ends and
sides cost $ 200/m2 and $ 100/m2, respectively. In
addition, a coating is applied to the entire tank area
at a cost of $ 50/m2.
82
Non-Linear Programming-Example
83
Non-Linear Programming-Example
84
Non-Linear Programming-Example
85
Non-Linear Programming-Exercise
86
Mixed Integer Programming-Reading assignment
87
Classification of the types of problems that are encountered in optimization
with discrete variables
88
Some Integer-Programming Models
89
Some Integer-Programming Models
90
More Examples in Chemical Engineering
91
More Examples in Chemical Engineering
92
