LECTURE#10
10/11/04
OPTIMIZATION
In our last class we had an introductory lesson on Optimization. Specifically, we learned the following:
(1)What is optimization in principle? – an act of minimization or maximization.
(2)Optimization is based on the principle of an objective/cost function that needs to be ‘optimized’.
(3)In hydro-sciences, optimization is needed in almost levels of prediction, estimation and operation of monitoring systems (e.g. weather radar network maintained by NWS).
(4)In engineering, the standard practice is to cast all optimization problems as a minimization problem. Most standard methods to solve optimization problems are based on minimization concepts.
(5)Any maximization problem can be inverted as a minimization problem.
(6)An optimization problem can have constraints assigned to it that refine the ‘search space’ (i.e., the domain within which you are allowed to look for solutions’
(7)There can be ‘local’ minima (lots of good solutions, but may be not as good as you’d want) as well as a ‘global’ minimum (the best university solution)
(8)If the objective function is a non-linear function – the optimization problem is termed Non-linear Optimization. For natural phenomenon, most problems tend to be of “non-linear” type.
(9)Currently, there is no non-linear optimization routine that can guarantee you of a global minimum.
(10)Minimum occurs when the gradient of the objective function is zero. The sufficient condition for a minimum is that the double derivative must be positive. In a vector format, the gradient and double derivatives are known as Jacobian and Hessian, respectively.
(11)Some examples of optimization in hydro sciences – a) optimization of operations of a multi-purpose reservoir; b) calibration of hydrologic models to estimate model parameters from historical data.
In today’s class, we shall cover almost all the basic things need to know to formulate and solve a real-world optimization problem. Hopefully, after this class, you’ll be able to identify whether someone using the term ‘optimization’ is really making sense!
The First Rule on Optimization:
Stating your optimization problem completely. This involves:
(1)Mathematically formulating your objective/cost function
(2)Identifying your constraints and mathematically representing them as inequalities or equalities (=0) type formats.
Suppose, X were a vector, X = {X1, X2, X3, …….Xn}T
Then if F(X) were the objective function, we would state he optimization problem as,
Find X={X1, X2, X3, …….Xn}T which minimizes F(X)
Subject to constraints,
gj (X) o, j=1, 2, …….. m
and
lj (X)= o, J= 1, 2, …….p
here X is and n-dimensional vector called the design vector. One example of X can be as follows for the case of hydrologic model calibration
X= {Ksat, Infiltration Ratepetential, Leaf Area Index, River flow velocity} for hydrologic mode
First, let’s look into formulating the objective function F(X) when a problem is thrown at us. Stating elegantly the Optimization problem is actually solving almost half the battle, as the rest is really easy (there are lost of numerical routines available to solve the problem according to given complexity, or suitable assumptions can be made to make the problem ‘solvable’.)
An Example of Formulating the Objective Function
Problem 1: A manufacturing firm produces two products A and B using two limited (Resource 1 Resource 2) resources. The maximum amount of resources 1 available per week is 1000 and the maximum amount of resource 2 is 250. The production of one unit of A requires 1 unit of resource 1 and 0.2 unit of resource 2. The production of one unit of B requires 0.5 unit of resource 1 and 0.5 unit of resource 2. The unit cost of resource 1 is (0.375-0.00005 u1) where u1 is the number of units of resource 1 used. The unit cost of resource 2 is (0.75-0.0001 u2) where u2 is the number of units of resource 2 used. The selling prices of one unit of A and B is,
PA=2.00-0.0005xA-0.00015xB
PB=3.50-0.0002xA-0.0015xB
Where XA and XB are the number of units sold for products A and B respectively. Assuming the firm is able to sell all units the it manufactures, formulate the problem of maximizing the profit over a week.
Let vector = . . The requirement of resource 1 per week is XA+0.5XB and
that for resource 2 is (0.2XA+0.5XB).
Constraints are :-
XA+0.5XB 1000
0.2XA+0.5 250 also (obviously )
XA 0 XB 0 (negative values are meaningless)
Total cost for resource 1 & 2 per week :
(XA+0.5XB) [0.375-0.00005(XA+0.5XB)]
(0.2XA+0.5XB) [0.750-0.0001(0.2 XA+0.5 XB)]
Total income (return)
= XA(2.00-0.0005XA-0.00015 XB)+XB(3.50-0.0002 XA-0-0015 XB)
Objective function = Income - cost = profit
Problem 2: A hydrologic model calibration exercise. Formulate the objective function to minimize in order to estimate the best parameters that yield the closest fit of simulated stream flow to observed stream flow.
Let Qobs: = dischange at observed time step i = 1,2, ...... Nst
Qsimi = Dischargsiulated at time at time step.
Objective function is something that represents closeness of Fit : F(X) = Qobsi-Qsimi
or Efficiencey = 1-
error = Qobsi - Qsimi
or RMSE = 1/N(Qobsi - Qsimi)2] 1/2
Some Classical Optimization Techniques
Single variable Optimization
Point of Inflection:
We mentioned earlier that he necessary and sufficient condition for a minimum (local /relative) is that gradient and the double derivative must be zero and positive, respectively. But can there be a situation where the derivative is zero yet the point is neither a minimum nor a maximum?
Actually there can be. Such points can be known as ‘points of inflection’ like the one shown below graphically.
Figure to be drawn in class
For such points , will be zero but not (non zero) / Stationary pt/pt of inflection =0 but its not a maximum/minimumFor stationary point is a check
Problem: Determine the maximum and minimum values of the function:
F(x) = 12x5-45x4+40x3+5
Problem: Determine the maximum and minimum values of the function:
F (x) = 12x5 – 45x4+40x3+5
Solution
Solution: f(x) = 60(x4-3x3+2x2)
f (xn) = 0 @ x=0, x-1 and x-2
Let is investigate these points,
f(x) = 60 (4x3-9x2+4x)
at x =1' f(x) = -60 minimum
at x =2 f''(x) = 240 maximum
at x = 0 f''(x) = 0 Let's investigate
f(x) = 60 (122 - 10x+4) = 240 at x=0
Saddle Points: The case for two variables x1 and x2
In case of function of two variables F (x,y), the Hessian matrix may be neither positive nor negative definite at points where the Jacobian is zero. In such case the point is called a saddle point (similar to an inflection point – imagine rotating the curve in the previous page by 360 degrees).
Figure to be drawn in class
A saddle point is a point which corresponds to a relative minimum or maximum of f(x,y) with respect to one variable and a relative opposite with other variable.
Homework Challenge: Bring it in Next Class!
Find the dimensions of a box of largest volume which can be inscribed in a sphere of unit radios.
[Hint: Draw your coordinate system (x1, x2 and x3 are the three axes). Assume the origin to be the center of the sphere. Assume now the sides of the box to be 2x1, 2x2 and 2x3. Volume of the box = 8x1x2x3
Since the corners of the box line on the surface of the sphere of unit radius, x1, x2 and x3 have to satisfy the constraint. Formulate that constraint and then try eliminating one of the variables. Next, write the objective function]
Let the orgin of coordinate system X1 X2 X3 be the centre of sphere
Figure to be drawn in class
Now, the sides of the box be 2X1 2X2 & 2x3 i.e, symmetric about original.
Volume of box = 8x1x2x3---- (1)
You also know the constraint:-
x12+ x32+ x32 = 1 [Unit radius (Pythagoras Theorem)]
Now choose to eliminate x3 ,
x3 = (1-x12+ x22)1/2. Substitute this in (1), yu get volume of box F(x1 x2). Do derivatives (partial)
,
Solve the equation.You may step here.You may check to see if your solution is maximum
The purpose of the previous problem was to bring us to the problem of optimizing functions under equality constraints one way of solving such constrained optimizing is to get rid of the constraints somehow incorporating them in the objective function. One such method is the “Lagrange Multiplier method” and the modified objective function is known as ‘Lagrange function’ which is then minimized the usual way as an unconstrained function.
Example:
Minimize: F(x,y)=kx-1y-2
Subject to g(x,y)=x2+y2-a2=0
We first write the Lagrange function
L (x, y, ) = f(x, y) + g (x,y) where is the Lagrange multiplier
= Kx-1y-2+(x2+y2-a2)
Now solve
(1)= 0 = Kn-1y-2+2x
(2)= 0 = 2Kn-1y-3+2y
(3)= 0 = x2 +y-2+a2
From (1) & (2) you get, 2 =
Or, x* = if x* y* are solution.
Now, (3) gives x* = = y*
Subsequently we may check these, points for sufficiency condition.
Assessment
Ok, by now, we should all be able to formulate the optimization problem by first identifying the mathematical form of the objective function and the constraints. For unconstrained optimization, the solution method (in principle) is known (gradient and double derivative requirements). For constraints (equality), we can incorporate them in the objective function and convert it to an unconstrained optimization problem.
Now, depending on the type of objective function, we can classify our problem as linear, non-linear, quadratic, integer etc.
Of particular interest and elegance is Linear Programming. A lot of objective functions that have a linear form with linear constraints (inequality) can actually be solved graphically! It’s that simple (unfortunately, not too many optimization problems in our hydro science field is that LINEAR).
But for general interest, let’s do the following problem:
A certain profit model f is given as function of y and x, as f(x,y)=50x+100y subject to the following constraints,
10x+5y2500 (1)
4x+10y2000 (2)
x+1.5y450(3)
And the variables x and y can not take negative values, so
x>0 (4)
y>0 (5)
Now, find values of x and y for which profit is maximize.
Figure to be drawn in class
Figures to be drawn
Now, just draw various for various values of c. At one pt for are line it will just touch the vertex
NEXT CLASS:
Limitations of classical optimization techniques for hydrologic problems.
Why the limitation – discussion
Techniques to overcome the limitations through non-classical techniques
Genetic Algorithm – what is it? Discussion
Combining genetic algorithm with classical techniques
Read paper of Duan et al. (1992) – Reading Assignment on Shufflex Code
Distribute Shufflex Code in Fortran to anyone who is interested.