高等应用数学问题的MATLAB求解06

1、星期四, 2008-4- 24, 22:08:13,Slide 1 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Chapter 6Nonlinear Equations and Optimization Problems,Solving Applied Mathematical Problems with MATLAB,CRC/Taylor good overview for the solutions Disadvantages

2、: Only applicable to 1D and 2D equations; not accurate; only real solutions Quasi-analytical methods, solve Advantages: Real/imaginary, more accurate Disadvantages: Only applies to polynomial type equations; not allowed to select initial point,星期四, 2008-4- 24, 22:08:13,Slide 30 (of 138) Dingy Xue an

3、d YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Pure numerical methods fsolve Advantages: Can be used to solve multi-dimensional nonlinear equations; freely select initial search point, accurate than graphical method Disadvantages: Imaginary solutions cannot be fo

4、und; for polynomial type equations, not so good Combination of algorithms, hints For 1D and 2D equations, use graphical method to spot an approximate solution Use the solution as an initial point, search for more accurate solutions with fsolve,星期四, 2008-4- 24, 22:08:13,Slide 31 (of 138) Dingy Xue an

5、d YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.1.4 Solutions to nonlinear matrix equations,Riccati equation in Chapter 4, exploration More nonlinear matrix equations, e.g., Generalized Riccati equation Modified Riccati equation Many many more matrix equations,星

6、期四, 2008-4- 24, 22:08:13,Slide 32 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,fsolve() can only solve , not vector , vector , no matrices involved Convert matrix equation into vector equations Vector to matrix math MATLAB Matrix to vector

7、math MATLAB,Riccati equation solver,星期四, 2008-4- 24, 22:08:13,Slide 33 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,M-function to describe Riccati equation in vector form A new function to solve Riccati equation,星期四, 2008-4- 24, 22:08:13,Sl

8、ide 34 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6.11,Solve the following Riccati equations: with,星期四, 2008-4- 24, 22:08:13,Slide 35 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Pre

9、ss, 2008,are() function may find one Repeated use of MATLAB commands: Another solution,星期四, 2008-4- 24, 22:08:13,Slide 36 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6.12,Given where find and verify all the possible solutions,星期四,

10、2008-4- 24, 22:08:13,Slide 37 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,For the Riccati-like equation Another M-function Another matrix equation solver,星期四, 2008-4- 24, 22:08:13,Slide 38 (of 138) Dingy Xue and YangQuan Chen, Solving Appl

11、ied Mathematical Problems with MATLAB, CRC Press, 2008,Repeated MATLAB command: Be patient, some of the solutions may be difficult to find. Run the function multiple times,星期四, 2008-4- 24, 22:08:13,Slide 39 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC

12、Press, 2008,Possible solutions, all passed verifications,星期四, 2008-4- 24, 22:08:13,Slide 40 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.2 Solving Unconstrained Optimization Problems,Analytical solutions and graphical solution methods Num

13、erical solution using MATLAB Global minima and local minima Solving optimization problems using gradient information Optimization problems with boundary constraints,星期四, 2008-4- 24, 22:08:13,Slide 41 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press,

14、2008,The mathematical description to unconstrained minimization problems Objective function is a scalar one vector decision variables, or optimum variables Physical meaning: find the vector that minimizes the objective function Maximization problem,Mathematical description,星期四, 2008-4- 24, 22:08:13,

15、Slide 42 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.2.1 Analytical solutions and graphical solution methods,The necessary conditions for an unconstrained optimization problem where is the optimum point Equation solution may be more diff

16、icult, also second-order derivatives needed,星期四, 2008-4- 24, 22:08:13,Slide 43 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6.13,Study the optimality of Plot of the first order derivative function of,星期四, 2008-4- 24, 22:08:13,Slide

17、44 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Draw the first-order derivative and verify positive 2nd-order derivative,星期四, 2008-4- 24, 22:08:13,Slide 45 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MAT

18、LAB, CRC Press, 2008,6.2.2 Numerical solution using MATLAB,The syntax of finding numerical solution simplest statement Or more general form Or,星期四, 2008-4- 24, 22:08:13,Slide 46 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Describing the ob

19、jective function M-function, Anonymous function Inline function, again not recommended No intermediate variable allowed in anonymous function or inline function,星期四, 2008-4- 24, 22:08:13,Slide 47 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008

20、,Example 6.14,Given , find its minimum. Using fminsearch(): Using fminunc():,星期四, 2008-4- 24, 22:08:13,Slide 48 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Draw the searching trajectory:,星期四, 2008-4- 24, 22:08:13,Slide 49 (of 138) Dingy Xu

21、e and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,星期四, 2008-4- 24, 22:08:13,Slide 50 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.2.3 Global minimums and local minimums,The necessary condition for a m

22、inimum point to exist is that . Using search method, only one such a point may be found from a given initial point. It is the global minimum.,星期四, 2008-4- 24, 22:08:13,Slide 51 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6.15,Given

23、 observe that different initial values give different minima. Construct objective function The initial search point is,星期四, 2008-4- 24, 22:08:13,Slide 52 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,The initial search point is Plot of for :

24、 Plot of for :,星期四, 2008-4- 24, 22:08:13,Slide 53 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.2.4 Solving optimization problems using gradient information,The optimums may not be obtained using the information provided in the objective f

25、unction alone, since the convergence speed for solving optimization problems may be very low. The gradient information can be used to solve the problem.,星期四, 2008-4- 24, 22:08:13,Slide 54 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example

26、 6.16,Solving unconstrained optimization problem for the Rosenbrock function: Plotting the 3D contour map:,星期四, 2008-4- 24, 22:08:13,Slide 55 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Without the gradient information Determine the gradie

27、nt matrix,星期四, 2008-4- 24, 22:08:13,Slide 56 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Prepare the objective function: Solve the optimization problem,星期四, 2008-4- 24, 22:08:13,Slide 57 (of 138) Dingy Xue and YangQuan Chen, Solving Applie

28、d Mathematical Problems with MATLAB, CRC Press, 2008,6.2.5 Optimization problems with boundary constraints,The mathematical description to boundary constraints problem is where the notation s.t. means subject to John DErrico, fminsearchbnd function, on CD,星期四, 2008-4- 24, 22:08:13,Slide 58 (of 138)

29、Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,The syntax of finding optimization problems with boundary constraints simplest statement more general form,星期四, 2008-4- 24, 22:08:13,Slide 59 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathemat

30、ical Problems with MATLAB, CRC Press, 2008,Example 6.17,Solving Rosenbrock problem where and . MATLAB command solutions:,星期四, 2008-4- 24, 22:08:13,Slide 60 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.3 Solving Constrained Optimization Pr

31、oblems,Constraints and feasibility regions Solving linear programming problems Solving quadratic programming problems Solving general nonlinear programming problems,星期四, 2008-4- 24, 22:08:13,Slide 61 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press,

32、2008,6.3.1 Constraints and feasibility regions,The general description of constrained nonlinear optimization problems: where All x satisfying the constraints form the so-called feasible region.,星期四, 2008-4- 24, 22:08:13,Slide 62 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Prob

33、lems with MATLAB, CRC Press, 2008,Example 6.18,Graphically solve: The objective function The feasible region,星期四, 2008-4- 24, 22:08:13,Slide 63 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Illustration of feasible region,星期四, 2008-4- 24, 22

34、:08:13,Slide 64 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.3.2 Solving linear programming problems,The general mathematical description to linear programming (LP) problems All linear Note, standard form,星期四, 2008-4- 24, 22:08:13,Slide 6

35、5 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,The syntaxes of solving LP problems:,星期四, 2008-4- 24, 22:08:13,Slide 66 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6.19,Sol

36、ve the following LP problem: Describing the problem in MATLAB,星期四, 2008-4- 24, 22:08:13,Slide 67 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Solutions via simple command Control precision,星期四, 2008-4- 24, 22:08:13,Slide 68 (of 138) Dingy X

37、ue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6.20,Solve the following LP problem: Convert the problem into minimization problem first,星期四, 2008-4- 24, 22:08:13,Slide 69 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems wit

38、h MATLAB, CRC Press, 2008,MATLAB command solutions:,星期四, 2008-4- 24, 22:08:13,Slide 70 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6.21,Find the solution to the LP problem Multiple subscripts,星期四, 2008-4- 24, 22:08:13,Slide 71 (of

39、138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Rearrange the variables into single subscript The original problem can then be rewritten as,星期四, 2008-4- 24, 22:08:13,Slide 72 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Probl

40、ems with MATLAB, CRC Press, 2008,MATLAB command solutions:,星期四, 2008-4- 24, 22:08:13,Slide 73 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.3.3 Solving quadratic programming problems,The general form of quadratic programming One should est

41、ablish the matrices first,星期四, 2008-4- 24, 22:08:13,Slide 74 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,The syntaxes of solving quadratic programming problems:,星期四, 2008-4- 24, 22:08:13,Slide 75 (of 138) Dingy Xue and YangQuan Chen, Solvi

42、ng Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6.22,Solve the following QP problem: Find relevant matrices first,星期四, 2008-4- 24, 22:08:13,Slide 76 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,The objective function i

43、s rewritten The matrices,星期四, 2008-4- 24, 22:08:13,Slide 77 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,MATLAB command solutions: where we omit the constant 30,星期四, 2008-4- 24, 22:08:13,Slide 78 (of 138) Dingy Xue and YangQuan Chen, Solvin

44、g Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.3.4 Solving general nonlinear programming problems,The general form of nonlinear programming where Physical interpretation: under the given constraints, find to minimize the objective function,星期四, 2008-4- 24, 22:08:13,Slide 79 (of 138)

45、Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,For simplicity Solving nonlinear programming problems,星期四, 2008-4- 24, 22:08:13,Slide 80 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6.

46、23,Solve the nonlinear programming problem Write M-functions, for objective function and constraints, the latter returns two variables,星期四, 2008-4- 24, 22:08:13,Slide 81 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Prepare the nonlinear con

47、straint function: Express the objective function,星期四, 2008-4- 24, 22:08:13,Slide 82 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Using fmincon() to get a solution: More accurate solutions,星期四, 2008-4- 24, 22:08:13,Slide 83 (of 138) Dingy Xu

48、e and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Simplifying the nonlinear constraint function: Get a solution:,星期四, 2008-4- 24, 22:08:13,Slide 84 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Example 6

49、.24,Using the gradient information to solve the following and compare the results.,星期四, 2008-4- 24, 22:08:13,Slide 85 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,The Jacobian matrix, can be derived Re-write the objective function,星期四, 2008

50、-4- 24, 22:08:13,Slide 86 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Using fmincon() to get a solution:,星期四, 2008-4- 24, 22:08:13,Slide 87 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press,

51、 2008,6.4 Solving Mixed Integer Programming Problems,Solving mixed integer programming problems Solving binary programming problems,星期四, 2008-4- 24, 22:08:13,Slide 88 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,6.4.1 Solving mixed integer

52、programming problems,One of the most frequently used algorithm for mixed integer programming problems is the branch-and-bound algorithm Free toolbox by Mr.Keort Kuipers The Toolbox is given on the CD Very light modifications by D Xue, for MATLAB R2008a,星期四, 2008-4- 24, 22:08:13,Slide 89 (of 138) Din

53、gy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Call the function vector to indicate the variable in should be an integer, and 0 for a real number Fun should be a quoted file name, not . If err returned is empty, successful,星期四, 2008-4- 24, 22:08:13,Slide

54、 90 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Fine tuning of the function Before call, After call, truncate the unwanted digits,星期四, 2008-4- 24, 22:08:13,Slide 91 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problem

55、s with MATLAB, CRC Press, 2008,Example 6.25,Assume , use bnb20() to solve ILP The objective function, no anonymous function,星期四, 2008-4- 24, 22:08:13,Slide 92 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Determine the ILP errmsg is empty, h

56、ence successful,星期四, 2008-4- 24, 22:08:13,Slide 93 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,For small-scale problems, the enumerate method can be used If n=20 is changed to 30, extremely large memory required for computers,星期四, 2008-4-

57、24, 22:08:13,Slide 94 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,The sub-optimum solutions If one requires to be integers, while the other two variables can be arbitrarily chosen,星期四, 2008-4- 24, 22:08:13,Slide 95 (of 138) Dingy Xue and YangQuan Chen, Solving Applied Mathematical Problems with MATLAB, CRC Press, 2008,Enumerate method summary,Advantages Ensure global optimum Apart from optimum, sub-optima also possible Simpl