《试验优化设计数学建模非线性规划6》由会员分享,可在线阅读,更多相关《试验优化设计数学建模非线性规划6(24页珍藏版)》请在金锄头文库上搜索。
1、非线性规划非线性规划 (Nonlinear Programming) 第六章第六章 一般的非一般的非线性性规划划问题6.1 问题概概论(模型)(模型) min f (x) s .t 1 1(两类问题)无约束极值问题与约束极值问题(两类问题)无约束极值问题与约束极值问题(两类问题)无约束极值问题与约束极值问题(两类问题)无约束极值问题与约束极值问题(一些基本定义)(一些基本定义) 梯度梯度 Hesse矩阵矩阵 Jaccobi矩阵矩阵 2 2 6.2 6.2 最优解分类最优解分类最优解分类最优解分类 (注:不一定存在)(注:不一定存在)(注:不一定存在)(注:不一定存在) 定义定义6.2.1 整体
2、(全局)最优解整体(全局)最优解 定义定义6.2.2 局部最优解局部最优解 (已有算法基本都是求局(已有算法基本都是求局部最优解的)部最优解的) 6.3 凸集与凸函数凸集与凸函数定义定义6.3.1 凸集凸集定义定义6.3.2 (严格)凸函数(严格)凸函数 称定义在凸集称定义在凸集K上的实值上的实值函数函数f (x)为凸函数,若为凸函数,若 定义定义6.3.3 凹函数凹函数 3 3定义定义6.3.4 凸规划凸规划(图集上凸函数的极小化问题)定理定理6.3.1 设 、 均为凸集,则则 也是凸也是凸集集 ,对任意实数, 是凸集是凸集。 (证明)(推广)定理定理6.3.2 有限个凸集的交集必是凸集定理
3、定理6.3.3 (分离定理)K为闭凸集, 则 定理定理6.3.4 (支撑超平面定理)(支撑超平面定理)4 4 定理定理6.3.5 若若 均为凸集均为凸集K上的凸函数,则上的凸函数,则 也是也是K上的凸函数。上的凸函数。 (请证明)(请证明)定理定理6.3.6 设设f (x)是凸集是凸集K上的凸函数,则上的凸函数,则 实数实数C,水平集,水平集 必为凸集。必为凸集。定理定理6.3.7 若若f (x) 在开集在开集K 中可微,则中可微,则f 是是K上的(严格)上的(严格)凸函数当且仅当凸函数当且仅当 5 5证明(充分性) 任取 ,记由条件, (必要性) 6 6令此即需证。若 f (x) 两阶可微,
4、则有以下的定理:定理6.3.8 设f (x)在开凸集K中二阶连续可微,f 为凸函数的充要条件为:证明:(充分性)7 7此处从而, (必要性) 任取将 在 x 处展开 : 8 8令 得定理1.3.9 证明 9 9此即说明f 是严格凸函数。定理6.3.10证明 当 充分小时 在 的邻域中,从而导出矛盾,证毕 10106.4 6.4 最最优优性条件性条件无约束极小化问题 (模型) min s .t (6.4.1)定理6.4.1 (一阶必要条件)若 是可微函数, 是问题(6.4.1)的一个局部最小点的必要条件为: (无约束极小化问题求解)等价于(方程组求解)定理6.4.2 (二阶必要条件)设 为 中的
5、二阶连续可微函数,如果 是 的一个局部极小点,则 1111证明:由定理6.4.1, 。对任意的由于 是局部极小点,故对于充分小的 必有此式成立必须有 ,证毕。1212定理6.4.3 (二阶充分条件)设 两阶可微,若 满足则点 的一个严格局部极小点,这里 是 的两阶Hesse矩阵定理6.4.4(两阶充分条件)设 两阶连续可微,若 满足 证明:任取显然, 由假设, ,由 的任意性, 是 1313定理6.4.5证毕 1414具有等式与不等式约束的极小化问题 (NP) min s .t 定义 6.4.1 设x是满足(NP)约束条件的点,记 称I 为x处不等式约束中的积极约束的下标集合 定义6.4.2
6、(积极约束) 称约束为x处的积极约束定义6.4.3 (正则点)若向量组线性无关,则称x为约束条件的一个正则点。1515定理6.4.5 (Kuhn-Tucker条件)设 是(NP)的局部极小点且 其中 1616例 求下面问题的 K-T 点 min s .t 解:本问题的 K-T条件为1717(1)若 (舍去)若 (舍去)(2) (舍去)(3) 1818故有 求得 19196.5 迭代算法及收敛速度 迭代算法 记满足要求的点集为 (如 K-T 点集,最优解集等)。算法一般采用迭代方法,即:任给一个初始点步1步2 定义1.5.1 (全局收敛性)设A是求解问题的一个算法,若对任意初始点 在用算法A进行
7、迭代时,或能在有限步求得最优解,或求得一无穷点列 ,该点列的任意聚点均为需求的点。2020例1 求解问题 min s .t 算法 迭代点列例2 求解 min 算法 2121迭代点列 若 若定义定义 6.5.1 (闭映射)设X何Y分别是两个非空闭集,A是从X到Y的一个点到集的映射,即对任意 有 设 ,且 若 (例1种的映射是闭的,而例2中的映射则是非闭的) 显然,例2的最优解为 取算法A为X到X的一个映射:定理定理6.5.1 若对任意取定的 :(1) (2)存在 , (3)算法 A 在 外是闭的则算法 A 必定是全局收敛的。(证明从略)2222收敛速度定义6.5.2 设实数列 除有限个 外 除有限个 外 其他 被称为商收敛因子定理1.5.2 仅有以下三种情况之一发生: (1) (2) (3) ,2323定义6.5.3 设 ,我们称 为 收敛到 的阶。 也称 阶收敛到 ( 对情况1 ,令 ,对情况2 ,令 ) 显然,收敛的阶越大,收敛速度越快。当数列具有一阶收敛速度时 越小数列收敛得越快。定义6.5.4 若 则称数列 超线性收敛于例2 (1) (2)2424