文档介绍：高级运筹学非线性规划
第一页，本课件共有49页
第二页，本课件共有49页
第三页，本课件共有49页
Prisoner’s Dilemma
第四页，本课件共有49页
运筹学
运筹学的研究对用于一些非线性和线性方程组的求解以及代数方程求根等。LINDO中包含了一种建模语言和许多常用的数学函数，可供使用者建立规划问题时调用。
 一般用LINDO（Linear Interactive and Discrete Optimizer）解决线性规划（LP—Linear Programming）。整数规划（IP—Integer Programming）问题。其中LINDO 6 .1 学生版至多可求解多达300个变量和150个约束的规划问题。其正式版（标准版）则可求解的变量和约束在1量级以上。
第十七页，本课件共有49页
LINGO则用于求解非线性规划（NLP—NON—LINEAR PROGRAMMING）和二次规则（QP—QUARATIC PROGRAMING）其中LINGO ，其标准版的求解能力亦再10^4量级以上。虽然LINDO和LINGO不能直接求解目标规划问题,但用序贯式算法可分解成一个个LINDO和LINGO能解决的规划问题。
第十八页，本课件共有49页
非线性规划
Nonlinear Programming
第十九页，本课件共有49页
相关的数学知识
一、一般数学描述
可行域
特别当R=En, 称为无约束优化问题
第二十页，本课件共有49页
相关的数学知识
二、解的定义
全局最优解、严格全局最优解；
局部最优解（极值点、极小点）
三、多元函数的偏导
偏导数：指函数沿某个坐标轴方向的变化率；
梯度：由各个坐标轴方向组成的向量；
方向导数：指函数沿某个给定方向的变化率；
常用的求梯度公式
第二十一页，本课件共有49页
相关的数学知识
四、Hessian 矩阵（二阶导数矩阵）
几个常用的公式
五、正定矩阵
定义
正定二次函数
六、多元函数的Taylor展开
第二十二页，本课件共有49页
相关的数学知识
七、凸函数、凸规划
凸集(convex set)：
凸函数(convex )、凹函数(concave)：
定义
几何意义
性质
判别条件
特别：线性函数既是凸函数也是凹函数。
凸规划(convex programming)
第二十三页，本课件共有49页
解的最优性条件
一阶必要条件
在极值点的梯度=0
二阶充分条件
二阶导数矩阵为正定矩阵
第二十四页，本课件共有49页
目标函数的等值线（二维，等高线）
对二次函数，等值线是一族同心的椭圆；对于非二次函数，在极小点附近，等值线近似一族同心椭圆；
具有不同值的等值线不相交；
等值线稠密处目标函数变化快，稀疏处变化慢；
等值线上一点的梯度与该点的的等值线切线方向相互垂直。
第二十五页，本课件共有49页
算法：
给定一个初始点X0，然后按照一定的规则产生一个点列{Xk}，这种产生点列的规则称为算法；
下降算法的规则：
给定一个初始点X0 ，在点Xk选择一个方向 (向量) Pk, 并沿此方向选择一点Xk+1=Xk+tkPk使得f(Xk+1)<f(Xk)。
第二十六页，本课件共有49页
算法步骤中的关键要素：
给定初始点；
确定寻优方向；
确定一个步长；
判别是否满足终止条件
第二十七页，本课件共有49页
一维寻优方法
The One-Dimensional Search Procedure
第二十八页，本课件共有49页
一、“成功-失败”法
基本思想
“成功”则大步向前，“失败”则小步后退。
框图
特点
简单易行，对初始点选择无严格限制；
适用于不可微的函数；
在极小点附近收敛慢；
可用此方法来确定一个搜索区间。
第二十九页，本课件共有49页
二、牛顿法（切线法）
基本思想：
适合二阶连续可微的函数，求导数为0的方程根。
迭代公式
算法步骤
特点
适用于二阶可微函数；
最快的收敛速度，二阶收敛速度；
初始点要求接近极小点；
可与“成功-失败”法联合使用。
第三十页，本课件共有49页
序贯实验法
单峰函数（Unimodal Function,下单峰、单谷)
定义（在极小点左边单调下降，右边单调上升）
性质( Unimodality，单峰性)
基本思想：
通过选择实验点，计算其函数值，比较实验点的函数值大小，缩小包含极值点的区