线性规划及非线性规划算法以及软件求解 课件.ppt

,最优化方法,线性规划问题,非线性规划问题,非约束优化问题,约束优化问题,优化问题的分类,基本概念最优性条件线性规划问题的求解非线性规划问题的求解,最优化问题的数学模型,最优化问题的数学模型,(*),最优化问题的基本概念,最优化问题的基本概念,最优化问题的基本概念,最优化问题的基本概念,最优化问题的基本概念,最优化问题的基本概念,预备知识-多元函数的导数,一元函数有一阶导数，二阶导数（假设存在），多元函数的一阶导数、二阶导数（假设存在）又是什么呢？,Questions,多元函数的一阶导数-梯度,多元函数的一阶导数-梯度,梯度的几何意义,多元函数的一阶导数-梯度,梯度的几何意义,多元函数的一阶导数-梯度,Definition,若x*满足 ，则称x* 为稳定点（平稳点）。,Remark,多元函数的二阶导数-Hesse矩阵,Jacobian矩阵,Jacobian矩阵,Jacobian矩阵,Jacobian矩阵,基本概念最优性条件线性规划问题的求解非线性规划问题的求解,最优性条件,无约束最优化问题的最优性条件 （凸函数极值的最优性条件）约束最优化问题的最优性条件,无约束优化问题的一阶必要性条件,（*）,约束优化问题的一阶必要性 条件,Kuhn-Tucker 条件,Kuhn-Tucker 条件,等式和不等式约束下的Kuhn-Tucker 条件,等式和不等式约束下的Kuhn-Tucker 条件,Lagrange函数 vs 广义Lagrange函数,（*）,等式和不等式约束下的Kuhn-Tucker 条件,等式和不等式约束下的Kuhn-Tucker 条件,基本概念最优性条件线性规划问题的求解非线性规划问题的求解,数学模型 如何求解（单纯形算法） 灵敏度分析 软件实现（LINGO、MATLAB）,线性规划及其软件实现,线性规划的数学模型,线性规划的数学模型,目标函数,约束条件,决策变量,最优值,最优解,线性规划的数学模型,目标函数,约束条件,决策变量,一般形式,线性规划的数学模型,标准形式,线性规划的数学模型,标准形式,如果矩阵A的秩小于m,怎么办？,如果（增广）矩阵的秩小于m，则行向量组线性相关，可以通过方程组的的初等变换把相关的方程组去掉，仅剩下线性无关的行向量组,非标准形式化为标准形式,Example,非标准形式化为标准形式,非标准形式化为标准形式,单纯形算法,单纯形算法,基解基可行解,线性规划解的定义,Remark,最优解一定可在极点处取得，而极点和基可行解是一一对应的，所以求线性规划问题最优解的思路仅在基可行解里寻找最优解！,线性规划解的定义,Questions,为什么不在极点里找，而在基可行解里找呢？,单纯形算法,线性规划问题的最优解一定可以在基可行解处取得，理论上可以用枚举法比较所有的基可行解，得到最优解。但在n，m较大时，在实际中可行吗？,Questions,单纯形算法,单纯形算法,单纯形算法不是比较所有的基可行解，每次只寻找比当前基可行解更好的基可行解，从而大大减少了计算量！,用单纯形算法求解线性规划问题,用单纯形算法求解线性规划问题,用单纯形算法求解线性规划问题,用LINGO 软件求解线性规划问题,LINDO: Linear INteractive and Discrete Optimizer LINGO: Linear INteractive General Optimizer,用LINGO 软件求解线性规划问题,model:Title example 1 LINGO模型;max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=12;end,用LINGO 软件求解线性规划问题,Global optimal solution found. Objective value: 14.00000 Total solver iterations: 2 Model Title: example 1 LINGO模型 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price 1 14.00000 1.000000 2 0.000000 1.500000 3 0.000000 0.1250000 4 4.000000 0.000000,灵敏度分析,为什么灵敏度分析？,灵敏度分析,灵敏度分析所要解决的问题系数在什么范围内变化，不会影响已获得的最优解。如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解。当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。,问题：若该厂从其它处抽调4台时用于生产产品I、II。求该厂的最优生产计划。,最优单纯形表,的变化分析,的变化分析,的变化分析,解：,的变化分析,的变化分析,的变化分析,最优解不变，最优值变化！,用LINGO 软件进行灵敏度分析,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 8.000000 2.000000 4.000000 3 16.00000 16.00000 8.000000 4 12.00000 INFINITY 4.000000,用LINGO 软件进行灵敏度分析,注：仅是最优基不变，最优解、最优值有可能变化！,用LINGO 软件进行灵敏度分析,model:Title LINGO模型;max=2*x1+2*x2;x1+2*x2=8;4*x1=16;4*x2=12;end,X2的价值系数在范围内变化,用LINGO 软件进行灵敏度分析,Global optimal solution found. Objective value: 12.00000 Total solver iterations: 1 Model Title: LINGO模型 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price 1 12.00000 1.000000 2 0.000000 1.000000 3 0.000000 0.2500000 4 4.000000 0.000000,最优解不变，最优值变化！最优基不变！,用LINGO 软件进行灵敏度分析,model:Title LINGO模型;max=2*x1+5*x2;x1+2*x2=8;4*x1=16;4*x2=12;end,X2的价值系数在范围外变化,用LINGO 软件进行灵敏度分析,Global optimal solution found. Objective value: 19.00000 Total solver iterations: 1 Model Title: LINGO模型 Variable Value Reduced Cost X1 2.000000 0.000000 X2 3.000000 0.000000 Row Slack or Surplus Dual Price 1 19.00000 1.000000 2 0.000000 2.000000 3 8.000000 0.000000 4 0.000000 0.2500000,最优解、最优值、最优基都变化！,用LINGO 软件进行灵敏度分析,model:Title LINGO模型;max=2*x1+3*x2;x1+2*x2=9;4*x1=16;4*x2=12;end,第一个资源在范围内变化,用LINGO 软件进行灵敏度分析,Global optimal solution found. Objective value: 15.50000 Total solver iterations: 2 Model Title: LINGO模型 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.500000 0.000000 Row Slack or Surplus Dual Price 1 15.50000 1.000000 2 0.000000 1.500000 3 0.000000 0.1250000 4 2.000000 0.000000,最优解、最优值都变化！最优基不变！,用LINGO 软件进行灵敏度分析,model:Title LINGO模型;max=2*x1+3*x2;x1+2*x2=11;4*x1=16;4*x2=12;end,第一个资源在范围外变化,用LINGO 软件进行灵敏度分析,Global optimal solution found. Objective value: 17.00000 Total solver iterations: 0 Model Title: LINGO模型 Variable Value Reduced Cost X1 4.000000 0.000000 X2 3.000000 0.000000 Row Slack or Surplus Dual Price 1 17.00000 1.000000 2 1.000000 0.000000 3 0.000000 0.5000000 4 0.000000 0.7500000,最优解、最优值、最优基都变化！,用MATLAB 软件求解线性规划问题 linprog,求解线性规划问题,求解线性规划问题,Linprog,Input Arguments,Output Arguments,Linprog,Input Arguments,Optimization Parameters,Options,求解线性规划问题,Linprog,Optimset,求解线性规划问题,Linprog,Examples,求解线性规划问题,Linprog,Examples,options = optimset(fminbnd),求解线性规划问题,Linprog,options = optimset(options, Display, Iter, TolX,1e-8),ActiveConstrTol: DerivativeCheck: Diagnostics: DiffMaxChange: DiffMinChange: Display: iter GoalsExactAchieve: GradConstr: GradObj: Hessian: HessMult: HessPattern: HessUpdate: Jacobian: JacobMult: JacobPattern: LargeScale: LevenbergMarquardt: ,LineSearchType: MaxFunEvals: 500MaxIter: 500MaxPCGIter: MaxSQPIter: MeritFunction: MinAbsMax: NonlEqnAlgorithm: Preconditioner: PrecondBandWidth: ShowStatusWindow: TolCon: TolFun: TolPCG: TolX: 1.0000e-008TypicalX: ,Output Arguments,求解线性规划问题,Linprog,求解线性规划问题,Linprog,求解线性规划问题,Linprog,求解线性规划问题,linprog,求解线性规划问题,linprog,求解线性规划问题,linprog,求解线性规划问题,linprog,求解线性规划问题,linprog,求解线性规划问题,linprog,求解线性规划问题,linprog,Preconditioned Conjugate Gradients method,求解线性规划问题,linprog,求解线性规划问题,linprog,求解线性规划问题,linprog,Nonzero elements of the vectors in the fields of lambda indicate active constraints at the solution. In this case, the second and third inequality constraints (in lambda.ineqlin) and the first lower bound constraint (in lambda.lower) are active constraints (i.e., the solution is on their constraint boundaries).,用MATLAB 软件求解线性规划问题 linprog,f = -2; -3A = 1 2 4 0 0 4b = 8; 16; 12lb = 0;0 x,fval,exitflag,output,lambda = linprog(f,A,b,lb)lambda.ineqlinlambda.lower,Optimization terminated successfully.x = 4.0000 2.0000fval = -14.0000exitflag = 1output = iterations: 7 cgiterations: 0 algorithm: lipsol,lambda = ineqlin: 3x1 double eqlin: 0 x1 double upper: 2x1 double lower: 2x1 doubleans = 1.5000 0.1250 0.0000ans = 1.0e-008 * 0.0915 0.1342,基本概念最优性条件线性规划问题的求解非线性规划问题的求解,基本迭代格式下降方向与可行下降方向迭代算法的一般步骤迭代终止条件迭代算法的收敛速度,解非线性规划的基本思路,基本迭代格式,下降方向与可行下降方向,下降方向与可行下降方向,非线性规划迭代算法的一般步骤,非线性规划迭代算法的一般步骤,迭代的终止条件,迭代的终止条件,迭代的终止条件,迭代的终止条件,迭代的终止条件,迭代的终止条件,迭代的收敛速度,迭代的收敛速度,一维搜索,一维搜索的方法,单谷函数的定义,单谷函数的定义,单谷函数的定义,单谷函数的定义,单谷函数的定义,单谷函数的定义,单谷函数的定义,单谷函数的定义,单谷函数的定义,Questions,单谷函数的性质有什么用？,0.618 法,利用单谷函数性质求极小值点的一种方法,0.618 法,Questions,两个点如何选取？,0.618 法,0.618 法,0.618 法,Questions,为什么选黄金分割点和其对称点作为缩小搜索区间的2个计算点？,0.618 法,0.618 法,黄金分割法的例子,如在炼钢时需要加入某种化学元素来增加钢材的强度，假设已知在每吨钢中需加某化学元素的量在1000 2000克之间，为了求得最恰当的加入量，需要在1000克与2000克这个区间中进行试验。0.618法只需要试验几次就能达到理想的结果。,优选学中的黄金分割法或0.618法，是由美国数学家基弗于1953年首先提出的，70年代在中国推广，代表人物是华罗庚。,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法,解非线性规划问题的一般方法,最速下降法,步长因子,搜索方向,最速下降法,最速下降法,最速下降法,最速下降法,最速下降法,缺点：在极小点附近，出现锯齿现象，收敛较慢。,最速下降法,优点：对初始点要求不高，可以比较快地达到极小点附近。,共轭方向法,共轭方向法,共轭方向法,F-R共轭梯 度法(Fletcher & Reeves 1964),牛顿法,牛顿法,牛顿法,牛顿法,修正牛顿法,牛顿法,优点：具备二次终止性 应用于正定二次函数时，只需一次迭代 即可达到无约束全局极小点，表明 Newton法具备二次终止性。收敛速度快 当初始点接近于极小点时， Newton法 很有效，产生的点列收敛于平稳点， 且收敛速度是2阶。,牛顿法,缺点：进行Hesse矩阵、 矩阵求逆的运算。当初始点离极小点较远时，Hesse矩阵 常常是奇异的，Newton方向不存在。,拟牛顿法,基本思想 (Davidon-1959),拟牛顿法,BFGS变尺度法（Broyden Fletcher Goldfarb Shanno）1970,DFP变尺度法 和BFGS变尺度法的比较,BFGS变尺度法具有DFP变尺度法的所有优点；数值稳定性要比DFP变尺度法。,被公认为目前最好的一种算法之一,无约束最优化算法比较,约束优化问题的求解方法,惩罚函数法起作用集方法序列二次规划法,惩罚函数法,外罚函数法内罚函数法（障碍函数法）广义Lagrange乘子法,外罚函数法,(*),外罚函数法,(*),外罚函数法,外罚函数法,(*),外罚函数法,外罚函数法,(*),外罚函数法,外罚函数法,Example,外罚函数法,外罚函数法,外罚函数法,外罚函数法,外罚函数法,外罚函数法,外罚函数法的优点：,对初始点要求低。把问题转化为一系列无约束优化问题，结 构简单，可以利用求解无约束优化问题的 算法。,外罚函数法,外罚函数法的缺点：,中间结果不是可行点。,外罚函数法,内罚函数法的出发点,内罚函数法,内罚函数法,内罚函数法,内罚函数法,内罚函数法,内罚函数法,Example,内罚函数法,内罚函数法,内罚函数法,内罚函数法,广义Lagrange乘子法,广义Lagrange乘子法的出发点,广义Lagrange乘子法,等式约束下的广义Lagrange乘子法不等式约束下的广义Lagrange乘子法等式和不等式约束下的广义Lagrange乘子法,(*),等式约束下的广义Lagrange乘子法,等式约束下的广义Lagrange乘子法,等式约束下的广义Lagrange乘子法,(*),等式约束下的广义Lagrange乘子法,Theorem,等式约束下的广义Lagrange乘子法,Remark,等式约束下的广义Lagrange乘子法,约束优化问题的求解方法,惩罚函数法起作用集方法序列二次规划法,二次规划,Definition,二次规划,（*）,二次规划,起作用集方法,正定二次规划,（*）,序列二次规划法（Sequential Quadratic Programming),（约束拟牛顿法约束变尺度法）,序列二次规划法,序列二次规划法,序列二次规划法,序列二次规划法,序列二次规划法,Remark,序列二次规划法,Remark,序列二次规划法,Example,序列二次规划法,序列二次规划法,序列二次规划法,序列二次规划法,Matlab Optimization Tool Box,Linprog,fminbnd,fmincon,quadprog,fminimax,一维搜索问题,一维搜索问题,一维搜索问题,一维搜索问题,一维搜索问题,一维搜索问题,一维搜索问题,一维搜索问题,一维搜索问题,一维搜索问题,一维搜索问题,x,fval,exitflag,output = fminbnd(f, 0, 2),f = inline(x3-2*x-5);,一维搜索问题,无约束优化问题,无约束优化问题,无约束优化问题,Input Arguments,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,Output Arguments,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,不考虑梯度,无约束优化问题,无约束优化问题,function f,g = myfun(x)f = 3*x(1)2 + 2*x(1)*x(2) + x(2)2; % Cost functionif nargout 1 g(1) = 6*x(1)+2*x(2); g(2) = 2*x(1)+2*x(2);end,考虑 梯度,无约束优化问题,options = optimset(GradObj,on);x0 = 1,1;x,fval,exitflag,output,grad,hessian = fminunc(myfun,x0,options),x = 1.0e-015 * 0.1110 -0.8882fval = 6.2862e-031exitflag = 1output = iterations: 2 funcCount: 2 cgiterations: 1firstorderopt: 1.5543e-015 algorithm: large-scale: trust-region Newton,grad = 1.0e-014 * -0.1110 -0.1554,hessian = (1,1) 6 (2,1) 2 (1,2) 2 (2,2) 2,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,无约束优化问题,x = 1.0000 1.0000fval = 8.1777e-010,约束优化问题,约束优化问题,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,Input Arguments,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,Output Arguments,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,Algorithm Large-Scale Optimization. By default fmincon will choose the large-scale algorithm if the user supplies the gradient in fun (and GradObj is on in options) and if only upper and lower bounds exist or only linear equality constraints exist. This algorithm is a subspace trust region method and is based on the interior-reflective Newton method .Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG).,约束优化问题,fmincon,Medium-Scale Optimization fmincon uses a Sequential Quadratic programming (SQP) method. In this method, a Quadratic Programming (QP) subproblem is solved at each iteration. An estimate of the Hessian of the Lagrangian is updated at each iteration using the BFGS formula.,约束优化问题,fmincon,A line search is performed using a merit function similar to that proposed by 4, 5, and 6. The QP subproblem is solved using an active set strategy similar to that described in 3.,约束优化问题,fmincon,约束优化问题,fmincon,约束优化问题,fmincon,Warning: Large-scale (trust region) method does not currently solve this type of problem,switching to medium-scale (line search).Optimization terminated successfully:No Active Constraintsx = 0.0000 -0.0000 14.2124fval = 2.7069e-009,约束优化问题,fmincon,exitflag = 1output = iterations: 5 funcCount: 31 stepsize: 1 algorithm: medium-scale: SQP, Quasi-Newton, line-searchfirstorderopt: 1.4794e-004 cgiterations: ,lambda = lower: 3x1 double upper: 3x1 double eqlin: 0 x1 double eqnonlin: 0 x1 double ineqlin: 2x1 double ineqnonlin: 0 x1 double,约束优化问题,fmincon,grad = 1.0e-003 * 0.1479 0.0006 0hessian = 6.0076 2.0257 0.3049 2.0257 2.0055 0.0700 0.3049 0.0700 0.8900,二次优化问题,二次优化问题,二次优化问题,quadprog,二次优化问题,quadprog,二次优化问题,quadprog,Output Arguments,二次优化问题,quadprog,Output Arguments,二次优化问题,quadprog,Output Arguments,二次优化问题,quadprog,When the problem has only upper and lower bounds, Or, if the problem has only linear equalities, the default algorithm is the large-scale method.,Algorithm Large-Scale Optimization.,二次优化问题,quadprog,This method is a subspace trust-region method based on the interior-reflective Newton method described . Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG).,二次优化问题,quadprog,Medium-Scale Optimization. quadprog uses an active set method, which is also a projection method. It finds an initial feasible solution by first solving a linear programming problem.,二次优化问题,quadprog,二次优化问题,quadprog,二次优化问题,quadprog,二次优化问题,quadprog,x = 0.6667 1.3333fval =-8.2222exitflag = 1output = iterations: 3 algorithm: medium-scale: active-set firstorderopt: cgiterations: ,二次优化问题,quadprog,lambda.ineqlinans = 3.1111 0.4444 0lambda.lowerans = 0 0,极小极大问题,极小极大问题,极小极大问题,fminimax,x = fminimax(fun,x0)x = fminimax(fun,x0,A,b)x = fminimax(fun,x0,A,b,Aeq,beq)x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub)x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options),Syntax,极小极大问题,fminimax,x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,.)x,fval = fminimax(.)x,fval,maxfval = fminimax(.)x,fval,maxfval,exitflag = fminimax(.)x,fval,maxfval,exitflag,output = fminimax(.)x,fval,maxfval,exitflag,output,lambda = fminimax(.),Syntax,极小极大问题,Example,Find values of x that minimize the maximum value of f1(x),f2(x),f3(x) Where f1(x)=2x f2(x)=4x f3(x)=1-x 0=x=1,极小极大问题,clear for i=1:180 x(i)=1/180*i f1(i)=2*x(i);f2(i)= x(i)*4;f3(i)=1-x(i); end plot(x,f1) hold onplot(x,f2) hold onplot(x,f3) hold on,极小极大问题,极小极大问题,function f = myfun(x)f(1)= 2*x ; f(2)=4*x;f(3)= 1-x;,clear x0 = 0.2; % Make a starting guess at solutionx,fval = fminimax(myfun,x0,0,1),极小极大问题,Optimization terminated: magnitude of search direction less than 2*options.TolX and maximum constraint violation is less than options.TolCon.Active inequalities (to within options.TolCon = 1e-006): lower upper ineqlin ineqnonlin 2 3x = 0.2000fval = 0.4000 0.8000 0.8000,极小极大问题,极小极大问题,极小极大问题,极小极大问题,演示函数,大型方法的演示函数,演示函数,中型方法的演示函数,