最优化理论与方法lec1Introduction课件

1、Chapter 1 Introduction & Preliminaries2OptimizationOptimization models attempt to express, in mathematical terms(数学术语), 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验证validation,sensitivity analysis4OptimizationOne approaches a complex decision problem involvingselection of values

4、for a number of interrelated variables(关联变量)focus attention on a single objective(单目标) designed to quantify performance and measure the quality of the decision(衡量决策品质)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(线性规划)Nonlinear Programming(非线性规划)Unconstrained Problems(无约束最优化方法)Constrain

6、ed Problems(约束最优化方法) Variational Inequality (VI)(变分不等式)Monotone VINon-monotone VI6Optimization Problem (Mathematical) Optimization Problemoptimal solution(最优解) x* has smallest value(最小值) of f among all vectors(矢量) that satisfy the constraints(满足约束条件).(优化变量)(目标函数)(约束函数)7Optimization Problem: Examples

7、Portfolio optimization(投资组合优化) 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(电子电路中的设备选型) variables: device widths and lengths constraints: manufacturing l

8、imits, timing requirements, max. area objective: power consumptionData fitting(数据拟合) 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(线性函数) 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(书橱) 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(整体运行时间) for handling a (long) sequence of tasks(处理一个任务序列), 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(目标) 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(方差和协方差) 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 “least 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(最优性) 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(导数值) 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(凸规划问题 ) 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(导数) 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(一般优化算法) 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(一个有限的步骤)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(算术运算) required 32Rates of Convergen

37、ceWhen the number of operations/steps required to find an exact solution is infinite, some other measure of efficiency(有效性测量) 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(缩写) 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