Non Linear Programming
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Non Linear Programming as PDF for free.
More details
- Words: 1,359
- Pages: 11
ENGI 9627 - Environmental Systems Engineering
LECTURE 7: NONLINEAR PROGRAMMING Instructor: Dr. Bing Chen Faculty of Engineering & Applied Science Tel: +1(709)737-8958 Email: [email protected]
1. Introduction ¾ Nonlinear Programming (NLP) Min s.t.
f(X) h(X) = 0 g(X) ≤ 0 X≥0
Where some of the constraints, h(x) or g(x), or the objective function, f(x), is nonlinear
¾ Much of the world is nonlinear Biological systems ==> exponential growth Trajectory ==> parabola (quadratic function) In many contexts, the elements of a linear model are really approximations of more complex relationship. 2 © Bing Chen, 2007
1. Introduction – Cont’d Example 7.1 – A manufacturing problem
3 © Bing Chen, 2007
2. Local and Global Extrema ¾ Maxima and Minima A point x* is a local (or relative) maximum of a function f if there exists some ε > 0 such that f(x*) ≥ f(x) for all x with |x-x*| < ε. on a graph of a function, its local maxima will look like the tops of hills. A local minimum is a point x* for which f(x*) ≤ f(x) for all x with |x-x*| < ε. On a graph of a function, its local minima will look like the bottoms of valleys. A global (or absolute) maximum is a point x* for which f(x*) ≥ f(x) for all x. Similarly, a global minimum is a point x* for which f(x*) ≤ f(x) for all x. Any global maximum (minimum) is also a local maximum (minimum); however, a local maximum or minimum need not also be a global maximum or minimum. 4 © Bing Chen, 2007
¾ Derivative tests First derivative test Second derivative test
¾ Examples f(x) = x2 f(x) = x3/3 – x Etc. 5 © Bing Chen, 2007
¾ Stationary Point A stationary point is a point on the graph of a function where the tangent to the graph is parallel to the x-axis (in 2D) or the plane tangent to the surface is parallel to the XY plane (in 3D). An equivalent definition is where the derivative of the function equals zero.
¾ Inflection Point An inflection point is a point where the concavity changes. A point of inflection is not necessarily a stationary point. All inflection points have the property of f''(x) = 0 but the reverse is not necessarily true
¾ Saddle Point An inflection point in two or more dimension is called saddle point 6 © Bing Chen, 2007
¾ Strictly Convex/Concave A Strictly convex function is one for which a straight line drawn between any two points on the function will everywhere overestimate the function between the two points A strictly concave function is one for which a straight line drawn between any two points on the function will everywhere underestimate the function between the two points How to determine if a function is strictly convex or concave 9Check the second derivative or hessian 9Adding a constant or linear function does not change it 7 © Bing Chen, 2007
3. Unconstrained NLP ¾ A NLP programs does not have a constraint for the decision variables It can still have decision variables belong to subset of Real Numbers (such as integers)
Max or Min Z = f(X) s.t. No Constraint ¾ Condition of Optimality Functions of single variable Functions of two variables 8 © Bing Chen, 2007
¾ Condition of Optimality - Maxima
Necessary condition for functions of one variable to have a local maxima at x = x* is
Sufficient condition for functions of one variable to have a local maxima at x = x* is
9 © Bing Chen, 2007
¾ Condition of Optimality - Minima
Necessary condition for functions of one variable to have a local minima at x = x* is
Sufficient condition for functions of one variable to have a local minima at x = x* is
10 © Bing Chen, 2007
¾ Condition of Optimality - Maxima
Necessary condition for bivariate functions to have a local maxima at x = x* is
Sufficient Condition for bivariate functions to have a local Maxima at x = x* is (f11f22 - f12f21) > 0 and f11 and f22 < 0, where
11 © Bing Chen, 2007
¾ Condition of Optimality - Minima
Necessary condition for bivariate functions to have a local maxima at x = x* is
Sufficient Condition for bivariate functions to have a local Maxima at x = x* is (f11f22 - f12f21) > 0 and f11 and f22 > 0, where
12 © Bing Chen, 2007
¾Saddle Point If (f11f22 - f12f21) < 0 then it is a Saddle Point at x1 = x1*, x2 = x2*
13 © Bing Chen, 2007
Example 7.2 – Optimal Reservoir Size for Irrigation Total benefit (TB) from irrigation water with water supply requirement of q is estimated to be: TB = 100q – 0.0005q2 Total cost (TC) of the reservoir depends on q, given by TC = 44.42q0.90 + 0.098q1.45 Determine the optimal reservoir size (q) to maximize the net benefit.
14 © Bing Chen, 2007
Example 7.3 – Optimization of Sedimentation Process The cost of processing industrial waste by sedimentation depends on the retention time (t) adopted for the design of the plant. The cost depends on flow capacity (q) and is given by 1. A fixed charge of 3q cost unit 2. Plant cost defined as 0.8q2t3.25 3. A tax or penalty cost dependent on the quality of the effluent and can be given by the exponential term 14qe-t Minimize the cost of sedimentation process.
15 © Bing Chen, 2007
4. Constrained NLP ¾ A NLP programs does have constraints for the decision variables Max or Min Z = f(X1, X2, X3, …, Xn) S.t. g1 (X1, X2, X3, …, Xn) = b1 g2 (X1, X2, X3, …, Xn) = b2 … gn (X1, X2, X3, …, Xn) = bn
¾ Solution of constrained problem Calculus of Substitution Method of Lagrangian Multiplier 16 © Bing Chen, 2007
4.1 Calculus of Substitution Example 7.4 – Best Hydraulic Section For open channel flow, the Manning equation is commonly used:
where: Q = discharge (ft3/sec.); n = Manning roughness factor, a constant that depends on channel material; A = flow cross-sectional area (ft2) (assume rectangular section, width b and height h); R = hydraulic radius (ft), = A/P, where P is wetted cannel perimeter (ft); and S = slope of the energy grade line, also equal to channel slope for steady, uniform flow. The cost of the channel lining is proportional to total wetted perimeter (b + 2h). To minimize the cost of the channel lining. 17 © Bing Chen, 2007
4.1 Calculus of Substitution – Cont’d Example 7.5 – Optimal Tank Design A vertical cylindrical tank is open at the top which is used to hold k m3 of liquid. It is known that bottom must be twice as thick as the sides. To determine the most economic design (with an optimal shape, diameter-toheight ratio).
18 © Bing Chen, 2007
4.1 Lagrange Multiplier Max or Min Z = f(X1, X2, X3) S.t. g1 (X1, X2, X3) = b1 g2 (X1, X2, X3) = b2 We let λ1 and λ2 as the Lagrangian Multiplier associated with the first and second constraints respectively and form the new unconstrained objective as L= f (X1, X2, X3) + λ1 [ b1- g1 (X1, X2, X3)] + λ2 [ b2 - g2 (X1, X2, X3)] L is the Lagrangian Function that can be optimized by simple calculus by taking the partial derivatives Please recall – we talked this method in Lecture #1. 19 © Bing Chen, 2007
4.1 Lagrange Multiplier – Cont’d
20 © Bing Chen, 2007
4.1 Lagrange Multiplier – Cont’d Example 7.5 – Sheet Metal Forming We have a square of sheet metal with side S that is to be cut and folded into a topless box of maximum volume. Shaded areas will be cut off. To determine the dimensions of cutting, x, y, and z.
21 © Bing Chen, 2007
LECTURE 7: NONLINEAR PROGRAMMING Instructor: Dr. Bing Chen Faculty of Engineering & Applied Science Tel: +1(709)737-8958 Email: [email protected]
1. Introduction ¾ Nonlinear Programming (NLP) Min s.t.
f(X) h(X) = 0 g(X) ≤ 0 X≥0
Where some of the constraints, h(x) or g(x), or the objective function, f(x), is nonlinear
¾ Much of the world is nonlinear Biological systems ==> exponential growth Trajectory ==> parabola (quadratic function) In many contexts, the elements of a linear model are really approximations of more complex relationship. 2 © Bing Chen, 2007
1. Introduction – Cont’d Example 7.1 – A manufacturing problem
3 © Bing Chen, 2007
2. Local and Global Extrema ¾ Maxima and Minima A point x* is a local (or relative) maximum of a function f if there exists some ε > 0 such that f(x*) ≥ f(x) for all x with |x-x*| < ε. on a graph of a function, its local maxima will look like the tops of hills. A local minimum is a point x* for which f(x*) ≤ f(x) for all x with |x-x*| < ε. On a graph of a function, its local minima will look like the bottoms of valleys. A global (or absolute) maximum is a point x* for which f(x*) ≥ f(x) for all x. Similarly, a global minimum is a point x* for which f(x*) ≤ f(x) for all x. Any global maximum (minimum) is also a local maximum (minimum); however, a local maximum or minimum need not also be a global maximum or minimum. 4 © Bing Chen, 2007
¾ Derivative tests First derivative test Second derivative test
¾ Examples f(x) = x2 f(x) = x3/3 – x Etc. 5 © Bing Chen, 2007
¾ Stationary Point A stationary point is a point on the graph of a function where the tangent to the graph is parallel to the x-axis (in 2D) or the plane tangent to the surface is parallel to the XY plane (in 3D). An equivalent definition is where the derivative of the function equals zero.
¾ Inflection Point An inflection point is a point where the concavity changes. A point of inflection is not necessarily a stationary point. All inflection points have the property of f''(x) = 0 but the reverse is not necessarily true
¾ Saddle Point An inflection point in two or more dimension is called saddle point 6 © Bing Chen, 2007
¾ Strictly Convex/Concave A Strictly convex function is one for which a straight line drawn between any two points on the function will everywhere overestimate the function between the two points A strictly concave function is one for which a straight line drawn between any two points on the function will everywhere underestimate the function between the two points How to determine if a function is strictly convex or concave 9Check the second derivative or hessian 9Adding a constant or linear function does not change it 7 © Bing Chen, 2007
3. Unconstrained NLP ¾ A NLP programs does not have a constraint for the decision variables It can still have decision variables belong to subset of Real Numbers (such as integers)
Max or Min Z = f(X) s.t. No Constraint ¾ Condition of Optimality Functions of single variable Functions of two variables 8 © Bing Chen, 2007
¾ Condition of Optimality - Maxima
Necessary condition for functions of one variable to have a local maxima at x = x* is
Sufficient condition for functions of one variable to have a local maxima at x = x* is
9 © Bing Chen, 2007
¾ Condition of Optimality - Minima
Necessary condition for functions of one variable to have a local minima at x = x* is
Sufficient condition for functions of one variable to have a local minima at x = x* is
10 © Bing Chen, 2007
¾ Condition of Optimality - Maxima
Necessary condition for bivariate functions to have a local maxima at x = x* is
Sufficient Condition for bivariate functions to have a local Maxima at x = x* is (f11f22 - f12f21) > 0 and f11 and f22 < 0, where
11 © Bing Chen, 2007
¾ Condition of Optimality - Minima
Necessary condition for bivariate functions to have a local maxima at x = x* is
Sufficient Condition for bivariate functions to have a local Maxima at x = x* is (f11f22 - f12f21) > 0 and f11 and f22 > 0, where
12 © Bing Chen, 2007
¾Saddle Point If (f11f22 - f12f21) < 0 then it is a Saddle Point at x1 = x1*, x2 = x2*
13 © Bing Chen, 2007
Example 7.2 – Optimal Reservoir Size for Irrigation Total benefit (TB) from irrigation water with water supply requirement of q is estimated to be: TB = 100q – 0.0005q2 Total cost (TC) of the reservoir depends on q, given by TC = 44.42q0.90 + 0.098q1.45 Determine the optimal reservoir size (q) to maximize the net benefit.
14 © Bing Chen, 2007
Example 7.3 – Optimization of Sedimentation Process The cost of processing industrial waste by sedimentation depends on the retention time (t) adopted for the design of the plant. The cost depends on flow capacity (q) and is given by 1. A fixed charge of 3q cost unit 2. Plant cost defined as 0.8q2t3.25 3. A tax or penalty cost dependent on the quality of the effluent and can be given by the exponential term 14qe-t Minimize the cost of sedimentation process.
15 © Bing Chen, 2007
4. Constrained NLP ¾ A NLP programs does have constraints for the decision variables Max or Min Z = f(X1, X2, X3, …, Xn) S.t. g1 (X1, X2, X3, …, Xn) = b1 g2 (X1, X2, X3, …, Xn) = b2 … gn (X1, X2, X3, …, Xn) = bn
¾ Solution of constrained problem Calculus of Substitution Method of Lagrangian Multiplier 16 © Bing Chen, 2007
4.1 Calculus of Substitution Example 7.4 – Best Hydraulic Section For open channel flow, the Manning equation is commonly used:
where: Q = discharge (ft3/sec.); n = Manning roughness factor, a constant that depends on channel material; A = flow cross-sectional area (ft2) (assume rectangular section, width b and height h); R = hydraulic radius (ft), = A/P, where P is wetted cannel perimeter (ft); and S = slope of the energy grade line, also equal to channel slope for steady, uniform flow. The cost of the channel lining is proportional to total wetted perimeter (b + 2h). To minimize the cost of the channel lining. 17 © Bing Chen, 2007
4.1 Calculus of Substitution – Cont’d Example 7.5 – Optimal Tank Design A vertical cylindrical tank is open at the top which is used to hold k m3 of liquid. It is known that bottom must be twice as thick as the sides. To determine the most economic design (with an optimal shape, diameter-toheight ratio).
18 © Bing Chen, 2007
4.1 Lagrange Multiplier Max or Min Z = f(X1, X2, X3) S.t. g1 (X1, X2, X3) = b1 g2 (X1, X2, X3) = b2 We let λ1 and λ2 as the Lagrangian Multiplier associated with the first and second constraints respectively and form the new unconstrained objective as L= f (X1, X2, X3) + λ1 [ b1- g1 (X1, X2, X3)] + λ2 [ b2 - g2 (X1, X2, X3)] L is the Lagrangian Function that can be optimized by simple calculus by taking the partial derivatives Please recall – we talked this method in Lecture #1. 19 © Bing Chen, 2007
4.1 Lagrange Multiplier – Cont’d
20 © Bing Chen, 2007
4.1 Lagrange Multiplier – Cont’d Example 7.5 – Sheet Metal Forming We have a square of sheet metal with side S that is to be cut and folded into a topless box of maximum volume. Shaded areas will be cut off. To determine the dimensions of cutting, x, y, and z.
21 © Bing Chen, 2007
Related Documents
Non Linear Programming
May 2020 6
Non Linear Programming
November 2019 12
Linear Programming
December 2019 35
Linear Programming
December 2019 25
Linear Programming
May 2020 11