非线性及动态规划.ppt

《非线性及动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、优化问题三要素：决策变量decisionbariable；目标函数objectivefunction；约束条件constraints约束条件决策变量优化问题的一般形式目标函数等约束equalityconstraint不等约束inequalityconstraint一般优化问题概述7/25/20211要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件特点一般优化问题概述可行解feasiblesolution（满足约束）与可行域feasibleregion（可行解的集合）最优解optimalsolution（取

2、到最小minimum／大值maximum的可行解,对应最优值optimalvalue）局部最优解或相对最优解local/relativeoptimizer全局或整体最优解globaloptimizaer优化模型的基本类型无约束优化unconstrainedoptimization约束优化constrainedoptimization特殊：等式（不等式）方程组systemofequations(inequations)一般优化问题概述约束优化constrainedoptimization的简单分类数学规划mathematicalprogramming

3、或连续优化continuousoptmization线性规划(LP)目标和约束均为线性函数Linearprogramming非线性规划(NLP)目标或约束中存在非线性函数Nonlinearprogramming二次规划(QP)目标为二次函数、约束为线性Quadraticprogramming一般优化问题概述整数规划(IP)决策变量(全部或部分)为整数Integerprogramming整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)Pure(mixed)Integerprogramming一般整数规划，

4、0-1（整数）规划Zero-oneprogramming离散优化discreteoptimization或组合优化combinatorialoptimization一般优化问题概述求解y=f(x)极小值的数值迭代算法：一维搜索算法中的黄金分割法(0.618法).分割法原理：设函数f(x)在闭区间[a,b]上是下单峰函数,即在(a,b)内f(x)由唯一的极小点x*,在x*的左边f(x)严格单调下降,在x*的右边f(x)严格单调上升.那么对于(a,b)内任意两点x1＜x2,如果f(x1)＜f(x2),则x*∈[a,x2]；否则x*∈[x1,b].如右图

5、非线性规划－无约束问题给定下单峰区间[a,b]及控制误差＞0,黄金分割法(0.618法)的迭代步骤：①取x2=a+0.618(b-a),f2=f(x2),转向②.②取x1=a+0.382(b-a),f1=f(x1),转向③.③若

6、b-a

7、＜,则取x*=(a+b)/2,停.否则转向④.④若f1＜f2,则取b=x2,x2=x1,f2=f1,转向②;若f1＝f2,则取a=x1,b=x2,转向①;若f1＞f2,则取a=x1,x1=x2,f1=f2,转向⑤.⑤取x2=a+0.618(b-a),f2=f(x2),转向③.非线性规划－无约束问题下面我们再给出

8、一个求初始区间的进退算法,在所求出的区间上f(x)是下单峰函数.给定初始点x0和初始步长＞0,进退算法的迭代步骤：①取x1=x0+,计算f(x0),f(x1).若f(x0)≥f(x1),则转向②；否则转向④.②取=2,x2=x1+,计算f(x2).若f(x2)≥f(x1),则得到区间[x0,x2]为初始区间,停；否则转向③.③取x0=x1,x1=x2,f(x0)=f(x1),f(x1)=f(x2),转向②.④取=2,x2=x0-,计算f(x2).若f(x2)≥f(x0),则得到区间[x2,x1]为初始区间,停；否则转向⑤.⑤取x1=

9、x0,x0=x2,f(x1)=f(x0),f(x0)=f(x2),转向④.非线性规划－无约束问题下面给出一个基于最速下降方向的算法,是求无约束极值的最早的数值算法.给定控制误差＞0和初始点xk(k=0),最速下降法的迭代步骤：①计算g(xk).梯度②若

10、

11、g(xk)

12、

13、≤,则取x*=xk,停；否则,令pk=-g(xk),由一维搜索求步长k,使得f(xk+kpk)=min{f(xk+pk)

14、≥0}.③令xk+1=xk+kpk,k=k+1,转向①.由于选择方向时只考虑到当前下降最快，未顾及到总寻优快慢，因而又称“瞎子爬山法”。梯度法（最速

15、下降法）例：采用梯度法求解函数f(X)=x12+25x22的极小点。[解]设初始点为：X(0)=，则f[X(0)]=104