浙大数学建模附录 非线性规划(xin)ppt课件.ppt

《浙大数学建模附录 非线性规划(xin)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、非线性规划（NonlinearProgramming）第一章一般的非线性规划问题§1.1问题概论（模型）minf(x)s.t1（两类问题）无约束极值问题与约束极值问题（一些基本定义）梯度Hesse矩阵Jaccobi矩阵2§1.2最优解分类（注：不一定存在）定义1.2.1整体（全局）最优解定义1.2.2局部最优解（已有算法基本都是求局部最优解的）§1.3凸集与凸函数定义1.3.1凸集定义1.3.2（严格）凸函数称定义在凸集K上的实值函数f(x)为凸函数，若定义1.3.3凹函数3定义1.3.4凸规划（图集上凸函数的极

2、小化问题）定理1.3.1设、均为凸集，则也是凸集，对任意实数ß，是凸集。（证明）（推广）定理1.3.2有限个凸集的交集必是凸集定理1.3.3（分离定理）K为闭凸集，则定理1.3.4（支撑超平面定理）4定理1.3.5若均为凸集K上的凸函数，则也是K上的凸函数。（请证明）定理1.3.6设f(x)是凸集K上的凸函数，则实数C，水平集必为凸集。（请证明）定理1.3.7若f(x)在开集K中可微，则f是K上的（严格）凸函数当且仅当5证明（充分性）任取，记由条件，（必要性）6令此即需证。若f(x)两阶可微，则有以下的定理：定理1

3、.3.8设f(x)在开凸集K中二阶连续可微，f为凸函数的充要条件为：证明：（充分性）7此处从而，(必要性)任取将在x处展开：8令得定理1.3.9证明9此即说明f是严格凸函数。定理1.3.10证明当充分小时在的邻域中，从而导出矛盾，证毕10§1.4最优性条件无约束极小化问题（模型）mins.t（1.4.1)定理1.4.1（一阶必要条件）若是可微函数，是问题（1.4.1)的一个局部最小点的必要条件为：（无约束极小化问题求解）等价于（方程组求解）定理1.4.2（二阶必要条件）设为中的二阶连续可微函数，如果是的一个局部极小

4、点，则11证明：由定理1.4.1，。对任意的由于是局部极小点，故对于充分小的必有此式成立必须有，证毕。12定理1.4.3（二阶充分条件）设两阶可微，若满足则点的一个严格局部极小点，这里是的两阶Hesse矩阵定理1.4.4（两阶充分条件）设两阶连续可微，若满足证明：任取显然，由假设，，由的任意性，是13定理1.4.5证毕14具有等式与不等式约束的极小化问题(NP)mins.t定义1.4.1设x是满足(NP)约束条件的点，记称I为x处不等式约束中的积极约束的下标集合定义1.4.2（积极约束）称约束为x处的积极约束定义1

5、.4.3（正则点）若向量组线性无关，则称x为约束条件的一个正则点。15定理1.4.5（Kuhn-Tucker条件）设是(NP)的局部极小点且其中16例求下面问题的K-T点mins.t解：本问题的K-T条件为17（1）若（舍去）若（舍去）（2）（舍去）（3）18故有求得19§1.5迭代算法及收敛速度迭代算法记满足要求的点集为（如K-T点集，最优解集等）。算法一般采用迭代方法，即：任给一个初始点步1步2定义1.5.1（全局收敛性）设A是求解问题的一个算法，若对任意初始点在用算法A进行迭代时，或能在有限步求得最优解，或求

6、得一无穷点列，该点列的任意聚点均为需求的点。20例1求解问题mins.t算法迭代点列例2求解min算法21迭代点列若若定义1.5.1（闭映射）设X何Y分别是两个非空闭集，A是从X到Y的一个点到集的映射，即对任意有。设，且若（例1种的映射是闭的，而例2中的映射则是非闭的）显然，例2的最优解为取算法A为X到X的一个映射：定理1.5.1若对任意取定的：（1）（2）存在，（3）算法A在外是闭的则算法A必定是全局收敛的。（证明从略）22收敛速度定义1.5.2设实数列除有限个外除有限个外其他被称为商收敛因子定理1.5.2仅有以

7、下三种情况之一发生：（1）（2）（3），23定义1.5.3设，我们称为收敛到的阶。也称阶收敛到（对情况1，令，对情况2，令）显然，收敛的阶越大，收敛速度越快。当数列具有一阶收敛速度时越小数列收敛得越快。定义1.5.4若则称数列超线性收敛于例2（1）（2）24第二章一维极值问题的最优化方法在求解极值问题时我们经常会反复采用如下的一元函数求极值步骤：先求出一个搜索方向d，然后沿方向d作一维搜索。为此，我们先来介绍一下一维搜索的一些技巧和方法。问题：mins.t本问题实际上是一个一元函数求极值的问题，为方便起见，以下我们

8、讨论问题：mins.t这里a可以是，b可以是。25§2.1仅比较函数值的最优化方法定义2.1（下单峰函数）定义2.2（不定区间）包含下单峰函数最小点的区间[a,b]方法：按一定的方法在[a,b]区间中取若干个点，比较这些点上的函数值，不断缩小不定区间。定义2.3（最优搜索策略）总点数相同而能使不定区间缩得最小的搜索方法。（Fibonacci方法）Fibona