最優(yōu)化理論與方法lec1Introduction課件

1、Chapter 1 Introduction & Preliminaries2OptimizationOptimization models attempt to express, in mathematical terms(數(shù)學(xué)術(shù)語(yǔ)), the goal of solving a problem in the “best” wayrunning a business to maximize profit, minimize loss, maximize efficiency, or minimize riskdesigning a bridge to minimize weight or m

2、aximize strengthselecting a flight plan for an aircraft to minimize time or fuel useOptimization models have been used for centuries, as their purpose is so appealing, and in recent times, they have come to be essentialThe concept of optimization is well rooted as a principle underlying the analysis

3、 of many complex decision or allocation problemsOptimization Process3real world problemalgorithm, model, solution techniquecomputer implementationanalysisnumerical methodsverification驗(yàn)證validation,sensitivity analysis4OptimizationOne approaches a complex decision problem involvingselection of values

4、for a number of interrelated variables(關(guān)聯(lián)變量)focus attention on a single objective(單目標(biāo)) designed to quantify performance and measure the quality of the decision(衡量決策品質(zhì))the objective is maximized or minimized subject to the constraints that may limit the selection of decision variable values(決策變量值)A p

5、articular optimization formulation should be regarded only as an approximationLearn to identify and capture the important issues of a problem5Types of Problems Mathematical Programming (Optimization Problem)Linear Programming(線性規(guī)劃)Nonlinear Programming(非線性規(guī)劃)Unconstrained Problems(無(wú)約束最優(yōu)化方法)Constrain

6、ed Problems(約束最優(yōu)化方法) Variational Inequality (VI)(變分不等式)Monotone VINon-monotone VI6Optimization Problem (Mathematical) Optimization Problemoptimal solution(最優(yōu)解) x* has smallest value(最小值) of f among all vectors(矢量) that satisfy the constraints(滿足約束條件).(優(yōu)化變量)(目標(biāo)函數(shù))(約束函數(shù))7Optimization Problem: Examples

7、Portfolio optimization(投資組合優(yōu)化) variables: amounts invested in different assets constraints: budget, max./min. investment per asset, min. return objective: overall risk or return varianceDevice sizing in electronic circuits(電子電路中的設(shè)備選型) variables: device widths and lengths constraints: manufacturing l

8、imits, timing requirements, max. area objective: power consumptionData fitting(數(shù)據(jù)擬合) variables: model parameters constraints: prior information, parameter limits objective: measure of misfit or prediction error8Linear ProgrammingA linear programming model involves the optimization of a linear functi

9、on(線性函數(shù)) subject to linear constraints on the variables.Example 1 Suppose that a manufacturer of kitchen cabinets is trying to maximize the weekly revenue of a factory. Various orders have come in that the company could accept. They include bookcases(書(shū)櫥) with open shelves, cabinets with doors, cabin

10、ets with drawers, and custom-designed(定制的) cabinets. The following Table indicates the quantities of materials and labor required to assemble the four types of cabinets, as well as the revenue earned. Suppose that 5000 units of wood and 1500 units of labor are available. CabinetWoodLaborRevenueBooks

11、helf102100With Doors124150With Drawers258200Custom20124009Linear ProgrammingExample 2 Consider the assignment of jobs to workers. Suppose that an insurance office handles three types of work: requests for information, new policies, and claims. There are five workers. Based on a study of office opera

12、tions, the average work times (in minutes) for the workers are known (see the Table). The company would like to minimize the overall elapsed time(整體運(yùn)行時(shí)間) for handling a (long) sequence of tasks(處理一個(gè)任務(wù)序列), by appropriately assigning a fraction of each type of task to each worker.WorkerInformationPoli

13、cyClaim1102831215224231318354192529517233310Nonlinear ProgrammingA nonlinear programming model involves the optimization of a function subject to constraints, where any of the functions may be nonlinear.Example 1 Suppose that four buildings are to be connected by electrical wires. The positions of t

14、he buildings are illustrated in the Figure(如圖所示). The first two buildings are circular: one at (1,4)T with radius(半徑) 2, the second at (9,5)T with radius 1. The third building is square with sides of length 2 centered at (3,-2)T. The fourth building is rectangular with height 4 and width 2 centered

15、at (7,0)T. The electrical wires will be joined at some central point (x0 , y0)T, and will connect to building i at position (xi , yi)T. The objective(目標(biāo)) is to minimize the amount of wire used. 11Nonlinear ProgrammingExample 1(x* , y*)(x1 , y1)(x2 , y2)(x4 , y4)(x3 , y3)12Nonlinear ProgrammingExampl

16、e 2 The following network represents a set of road intersections(道路交叉口), and the arrows indicate the direction of traffic. If few cars are on the roads, the travel times between intersections can be considered as constant, but if the traffic is heavy the travel times can increase dramatically. The t

17、ravel time between intersections i and j could be modeled bySuppose that we wished to minimize the total travel time through the network for a volume of cars X. 123413Nonlinear ProgrammingExample 3 Nonlinear models are also used in finance to manage investment portfolios(投資組合). Suppose that an inves

18、tor desires to select a set of stocks so as to achieve a good return on the investment while at the same time controlling risks of losses. Suppose that a budget of $1,000,000 is available to invest. For the j-th investment, let the variable xj be the number of shares of investment that will be purch

19、ased, let aj be the current purchase price, and let uj be its expected return. Let V be the matrix of variances and covariances(方差和協(xié)方差) associated with the risks of the investments. (Vj,j is the variance of investment j; Vi,j is the covariance of investments i and j). 14Unconstrained ProblemLook at

20、the quadratic model(二次模型): For the data points (2,1), (3,6), and (5,4) we obtained the linear system: It is common when collecting data to gather more data points than there are variables in the model. It is expected that each of the measurements will be in error, and that the observations will be u

21、sed collectively in the hope of obtaining a better result than any individual measurement provides. (剩余向量)15Unconstrained ProblemThe most commonly used approach is called “l(fā)east squares” data fitting, where we try to minimize the sum of the squares of the components of r: If the fourth data point wa

22、s (7, -14)T, then the least-squares approach would give x=(-21, 15, -2)T. If the fourth data point was (7, -15)T, then the least-squares approach would be “Linear Case”“Nonlinear” models are also possible. Some examples are 16Feasibility(可行性)We consider a set of constraints of the form(約束形式): A poin

23、t that satisfies all the constraints is said to be feasible(可行解). The set of all feasible points is termed the feasible region(可行域) or feasible set（可行集）. （不等性約束） All equality constraints are regarded as active at any feasible point. The active set at a feasible point is defined as the set of all con

24、straints that are active at that point.on the boundary of the constrainton the interior of the constraint17FeasibilityThe figure illustrates the feasible region defined by the constraints(可行域的約束定義): The set of feasible points for which at least one inequality is binding is called the boundary of the

25、 feasible region. All the other feasible points are interior points. xax3xcxbx2x118Optimality(最優(yōu)性) Not all functions have a finite(有限的) global minimizer, and even if a function has a global minimizer(全局最小化) there is no guarantee that it will have a strict global minimizer. 19Optimalitystrict global

26、minimizerno global minimizernon-strict global minimizer Without additional information or assumptions about the problem it will not be possible to guarantee that a global solution has been found. An important exception is in the case where the function f and the set S are convex(凸的).20Optimality If

27、we cannot find the global solution then at the least we would like to find a point that is better than its surrounding points. More precisely（精確地）, we would like to find a local minimizer(局部最小值) of f in S, a point satisfyingThe point x* is a strict local minimizer if In many important cases, strict

28、local minimizers can be identified using first and second derivative values(導(dǎo)數(shù)值) at x = x*. 21Optimalitystrict local minimizer (global)strict local minimizernon-strict local minimizer strict local minimizer It may seem troubling that a local but not global solution is often found, but in many practi

29、cal situations this can be acceptable if the local minimizer produces a satisfactory reduction in the value of the objective function.22Convexity(凸性)There is one important case where global solutions can be found, the case where the objective function is a convex function and the feasible region is

30、a convex set. 23Convex ProgrammingDefine a convex programming problem(凸規(guī)劃問(wèn)題 ) to be a problem of the formwhere S is a convex set and f is a convex function on S. Exercise A problem is a convex programming problem if f is convex, and the functions gi are concave. Theorem(定理) (Global Solutions of Conv

31、ex Programs) Let x* be a local minimizer of a convex programming problem. Then x* is also a global minimizer. If the objective function is strictly convex, then x* is the unique global minimizer. 24Derivatives(導(dǎo)數(shù)) and ConvexityThen the function is strictly convex.(sufficient but not necessary)25The

32、Gradient, Hessian and Jacobian(梯度,海賽矩陣,雅可比行列式)26The Gradient, Hessian and JacobianExampleConsider the function:The gradient of this function is:and the Hessian matrix is:At the point x0= ( -2, 3 ) these become27The Gradient, Hessian and JacobianTo define the Jacobian we will use a vector-valued func

33、tion:ExampleConsider the vector-valued function:28The General Optimization Algorithm(一般優(yōu)化算法) Despite the diversity of both algorithms and problems, all of the algorithms that we will discuss in any details will have the same general form.General Optimization Algorithm IOften the information obtained

34、 from the optimality test is the basis for the computation of the new point. For example, if we are trying to solve the one-dimensional problem without constraints 29The General Optimization AlgorithmMany algorithms will have a more specific form:General Optimization Algorithm II30The General Optimi

35、zation Algorithm31Rates of Convergence(收斂率)Many of the algorithms discussed in this course do not find a solution in a finite number of steps(一個(gè)有限的步驟)Instead these algorithms compute a sequence of approximate solutions that we hope get closer and closer to a solutionWhen discussing such an algorithm

36、 two questions are often asked:Does it converge?(是否收斂)How fast does it converge?If an algorithm converges in a finite number of steps, the cost of that algorithm is often measured by counting the number of steps requiredcounting the number of arithmetic operations(算術(shù)運(yùn)算) required 32Rates of Convergen

37、ceWhen the number of operations/steps required to find an exact solution is infinite, some other measure of efficiency(有效性測(cè)量) must be usedThe rate of convergence is one such measure that describes how quickly the estimates of the solution approach the exact solution33Rates of ConvergenceLet us assum

38、e that we have ideal convergence behavior 34Rates of ConvergenceIn many situations, people use a sort of shorthand(縮寫(xiě)) and only refer to the convergence rate without mention of the rate constant For quadratic rates of convergence this is not too misleadingHowever, in the linear case, the rate constant plays an important role (close to one, close to zero) Though it is generally true that higher rates of convergence often represent imp