系统优化调度.ppt

1、9/11/2001,Fall 2001, Copy Right P. B. Luh,1,Modeling and Optimization of Complex Networked Systems: Applications to Operations Scheduling and Supply Network Management,Peter B. Luh, Visiting Professor Center for Intelligent and Networked Systems Department of Automation Room 503, Main Building Tsing

2、hua University Phone: 6279-2438 Email: Peter.L,9/11/2001,Fall 2001, Copy Right P. B. Luh,2,Are you in the right classroom? What are complex networked systems?,Computer and communication networks Power systems Supply chains Why are we interested in complex networked systems?,As a person, a

3、 team, a department, or a company Mediocrity or excellence? Surviving or thriving? Need to accurately describe the system under consideration and prudent decision-making to maximize an objective(s),Major areas of development and advancement Why do we need to study their modeling and optimization?,9/

4、11/2001,Fall 2001, Copy Right P. B. Luh,3,The major segments in the course Mathematical optimization concepts and algorithms, focusing on methods that can solve practical large-scale problems (7 lectures) Operations scheduling for manufacturing and service sectors, making use of optimization methods

5、 learned in the first segment (4 lectures) Strategy, planning, and operations of modern supply networks, exploring distributed and collaborative decision-making and optimization within a networked environment (4 lectures) Participants who are interested in research can take part in extra discussion

6、sessions on mini research projects,9/11/2001,Fall 2001, Copy Right P. B. Luh,4,What do you expect to learn from this course?,Solid understanding of the above subjects Classroom participation experience Mini (or major) research opportunities Improved English What is the workload?,Slightly above avera

7、ge, and intensive in September (8 lectures) and October (7 lectures) (and in November and in December) Prerequisites: A first year graduate course on system theory How can we make it a fun course for all of us?,Preparation: Before and after each class Participation: In class,9/11/2001,Fall 2001, Cop

8、y Right P. B. Luh,5,Classes In September: Monday 8:00 9:35, Thursday 8:00 9:35, and Friday 13:30 15:05 In October: Monday 8:00 9:35 and Friday 13:30 15:05 Office Hours: Monday 16:00 17:00, Thursday 16:00 17:00 Time for voluntary discussion sessions to be arranged Major references Dimitri P. Bertseka

9、s, Nonlinear Programming, Second Edition, Athena Scientific, Belmont, MA, 1999 Michael Pinedo and Xiuli Chao, Operations Scheduling with Applications in Manufacturing and Services, McGraw-Hill, 1999 Sunil Chopra and Peter Meindl, Supply Chain Management: Strategy, Planning and Operations, Prentice H

10、all, 2000,9/11/2001,Fall 2001, Copy Right P. B. Luh,6,Tentative Outline 1.Introduction and Unconstrained Optimization (2.33 lectures) 2.Optimization over a Convex Set (2 lectures) 3.Duality and Dual Methods (2.66 lectures) 4.Operations Scheduling with Applications in Manufacturing and Services (1.33

11、 lectures) 5.Job Shop Scheduling (1.33 lectures) 6.Scheduling Models in Service Industries (1.33 lectures) 7.Supply Chain Management: Strategy, Planning, and Operations (2 lectures) 8.Distributed and Collaborative Decision-Making in Supply Networks (2 lectures),9/11/2001,Fall 2001, Copy Right P. B.

12、Luh,7,Grading: Homework45% Mid Term25% Term Project25% Classroom Participation 5% Total 100% General Rules: Term projects can be done individually or in teams of two on relevant optimization topics or applications. Topics should be based on at least two recent papers. Numerical implementation and te

13、sting are strongly encouraged. Term project proposals are due on Friday October 12. The date of presentations and the date of submitting the final reports will be determined later.,9/11/2001,Fall 2001, Copy Right P. B. Luh,8,Homework problems should be clear, concise, and complete. Not all the homew

14、ork problems will be graded. Grading will be based on some randomly selected problems. Late assignments will be discounted 10% a day, up to 5 days. This policy will be strictly enforced. Homework solutions will be provided on the web sites a week after the due date. Comments and discussions are enco

15、uraged in class, after class, during office hours or by appointment. NO CHEATING!,9/11/2001,Fall 2001, Copy Right P. B. Luh,9,Reading Assignment: Bertsekas Sections 1.1, 1.2, and Appendices A and B Today: Introduction and Unconstrained Optimization Motivation and Course Overview Problem Classificati

16、on Optimality Conditions for Unconstrained Optimization Gradient Methods Framework Tomorrow: Bertsekas Sections 2.3 2.6,9/11/2001,Fall 2001, Copy Right P. B. Luh,10,Mathematical Optimization Concepts and Algorithms1.2 Problem Classification,General Formulation Minimize f(x), subject to x X Rn f(x):

17、Cost function x: Decision variable X: Constraint set Example 1 A small shop specializes in making 2 types of auto parts,9/11/2001,Fall 2001, Copy Right P. B. Luh,11,How to decide the best quantities? What is the model?,Max x1, x2 30 x1 + 40 x2, or Min x1, x2 (30 x1 + 40 x2), subject to x1 + 5x2 160,

18、(C1) x1 + 1.5x2 60,(C2) 2x1 + x2 80, and(C3), x1 0, x2 0 (now treated as continuous variable) What kind of problems is this?,9/11/2001,Fall 2001, Copy Right P. B. Luh,12,Linear cost function with linear constraints A Linear Programming (LP) problem Generic LP formulation Minimize f(x) cx subject to

19、x X x Rn, Ax = b, x 0 with c Rn, b Rm, A Rmxn given,9/11/2001,Fall 2001, Copy Right P. B. Luh,13,Example 2 Same as Example 1 except that,Max x1, x2 (50 x1) x1 + (64 x2) x2 subject to the same set of constraints Nonlinear cost function and/or nonlinear constraints Nonlinear programming (NLP), with di

20、minishing return,9/11/2001,Fall 2001, Copy Right P. B. Luh,14,Other types of problems: Integer Programming (IP) With integer variables, e.g., if x1 and x2 are integers, or manufacturing scheduling problems to be discussed later Mixed Integer Programming (MIP) With both integer and continuous variabl

21、es, e.g., power system unit commitment and economic dispatch Minimize the total generation cost Subject to system demand and reserve constraints By selecting unit up/down and generation levels Although many lectures will be on nonlinear programming, many results will be applicable to integer program

22、ming and mixed integer programming,9/11/2001,Fall 2001, Copy Right P. B. Luh,15,1.3 Optimality Conditions for Unconstrained Optimization,Problem Formulation Minimize f(x), with x X Rn, f(x): Continuously differentiable for most of this chapter Shall briefly go over the following: Local and global mi

23、nimum Necessary conditions for optimality The case of a convex cost function Sufficient conditions for optimality Existence of optimal solutions,9/11/2001,Fall 2001, Copy Right P. B. Luh,16,Which of the above is a local minimum point? Global minimum? How to mathematically define these terms? Local m

24、inimum: A, B, and C. Global: C f(x*) f(x) x with |x x*| x* is a local minimum f(x*) f(x) x X x* is a global minimum Minimum is strict if “” is replaced by “”,Local and Global Minimum,9/11/2001,Fall 2001, Copy Right P. B. Luh,17,What are the necessary conditions for a point to be a local minimum? Glo

25、bal minimum?,Necessary Conditions Local Optimality,Prop. 1.1.1: First order: f(x*) = 0 a stationary point Second order: 2f(x*) 0, i.e., positive semi-definite, if f(x) is twice continuously differentiable What are f(x) and 2f(x)?,9/11/2001,Fall 2001, Copy Right P. B. Luh,18, Gradient,Hessian ,Proof:

26、 Define g() = f(x* + d) for a direction d and scalar . Then,This should be true for any d f(x*) = 0.,9/11/2001,Fall 2001, Copy Right P. B. Luh,19,Also, to have f(x* + d) = f(x*) + f(x*)d + 0.52d2f(x*)d + o(2) = f(x*) + 0.52d2f(x*)d + o(2) f(x*) we need 2f(x*) 0 Example: Minimize f(x1, x2) x12 + 2x22

27、 + 2x1 - x1x2, x* = (-8/7, -2/7). Also,9/11/2001,Fall 2001, Copy Right P. B. Luh,20,The above are for local minimum. What can be said about global optimal conditions?,Difficult to investigate global optimal conditions, except for the convex case to be discussed next or by using stochastic optimizati

28、on such as simulated annealing or genetic algorithms,9/11/2001,Fall 2001, Copy Right P. B. Luh,21,The Case of a Convex Cost Function,What is a convex set? How about a convex function? How are convex sets and convex functions related? Convex Sets,Def. B.1: Set X in Rn is convex iff x1 + (1-)x2 X, x1,

29、 x2 X, 0,1 Convex Functions,A: Convex B: Not convex,A: Not convex B: Convex,9/11/2001,Fall 2001, Copy Right P. B. Luh,22,Def. B.2: X a convex set in Rn. f(x): X R is convex iff f(x1+(1-)x2) f(x1) + (1-)f(x2) x1, x2 X, 0,1 这里的CONVEX指的是下凸的“” Linear combination is an over estimate Convex is strict if “

30、” is replaced by “” Relationship between convex functions and convex sets: Read yourself Theorem. f(x) is convex iff the linear approximation at an arbitrary point x+ based on the gradient is an under-estimate of f(x), i.e., f(x) f(x+) + f(x+) (x - x+), x Implications: f(x*) = 0 x* is a global minim

31、um,9/11/2001,Fall 2001, Copy Right P. B. Luh,23,Theorem. A function f(x) is convex iff the Hessian is positive semi-definite for all x, i.e., 2f(x) 0 x Prop. 1.1.2: For a convex function f(x) over a convex set X A local minimum is a global minimum; If f(x) is strictly convex, then there exists at mo

32、st one global minimum; and If X is open, then f(x*) = 0 is a necessary and sufficient condition for x* to be a global minimum,9/11/2001,Fall 2001, Copy Right P. B. Luh,24,Sufficient Conditions for Optimality,Previously necessary conditions for optimality: f(x*) = 0 and 2f(x*) 0. Are they sufficient

33、conditions also?,Prop. 1.1.3: Let f(x) be twice continuously differentiable in an open set S. Suppose x* S satisfies f(x*) = 0 and 2f(x*) 0, then x* is a strict unconstrained local minimum Proof: f(x*+d) - f(x*) = f(x*)d + 0.5 d 2f(x*) d + o(|d|2) 0. Local minima that do not satisfy the above suffic

34、ient conditions are called singular, otherwise non-singular. Singular local minima are difficult to deal with,9/11/2001,Fall 2001, Copy Right P. B. Luh,25,Existence of Optimal Solutions,Does a minimum always exist? Examples: f1(x) = 1/x, f2(x) = ex Prop. A.8: If f(x) is continuous and X is compact (

35、closed and bounded), then x* always exists. If f(x) is continuous and X is closed, and f is coercive (i.e., f(x) when |x| ), then x* always exists. Why bother necessary, sufficient, and existence conditions?,Help understand what is really going on Can be used to terminate an algorithm when these con

36、ditions are satisfied Can be used to develop or improve algorithms Move x in a direction so that these conditions are “more” satisfied,9/11/2001,Fall 2001, Copy Right P. B. Luh,26,1.4 Gradient Methods Framework,Iterative Descent Algorithms Minimize f(x), with x X Rn f(x): Continuously differentiable

37、 Analogy: A blind person with a stick goes down a hill Knows the current elevation and the slope Can measure a few more points, one at a time and at a cost Wants to decide which direction to go, and by how far to reach the top,9/11/2001,Fall 2001, Copy Right P. B. Luh,27,Mathematically Start with an

38、 initial point x0, evaluate f(x0), f(x0) (and possibly 2f(x0) Based on the information, select a search direction “d” emanating from x0 Find the next point x1 along the direction d, and evaluate f(x1), f(x1) (and possibly 2f(x1) Repeat the above, and successfully generate x2, x3, ., such that f(x) is decreased at each iteration Iterative descent Key Questions?,x1,Which direction to go? How far? Is the algorithm guaranteed to reach x*? How fast to reach x*?,9/11/2001,Fall 2001, Copy Right P. B. Luh,28,Gradient Type Methods,Key Ideas Gradient f(x