非线性规划等课件.ppt
《非线性规划等课件.ppt》由会员分享,可在线阅读,更多相关《非线性规划等课件.ppt(126页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、非线性规划等1第1页,此课件共126页哦(两类问题)无约束极值问题与约束极值问题(两类问题)无约束极值问题与约束极值问题(一些基本定义)(一些基本定义)(一些基本定义)(一些基本定义)梯度梯度梯度梯度 HesseHesse矩阵矩阵矩阵矩阵 JaccobiJaccobi矩阵矩阵矩阵矩阵 2 2第2页,此课件共126页哦 1.2 1.2 最优解分类最优解分类 (注:不一定存在)(注:不一定存在)定义定义定义定义1.2.1 整体(全局)最优解整体(全局)最优解整体(全局)最优解整体(全局)最优解 定义定义定义定义1.2.2 局部最优解局部最优解局部最优解局部最优解 (已有算法基本都是求局部最优解(已
2、有算法基本都是求局部最优解(已有算法基本都是求局部最优解(已有算法基本都是求局部最优解的)的)的)的)1.3 1.3 凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数定义定义定义定义1.3.1 1.3.1 凸集凸集凸集凸集定义定义定义定义1.3.2(严格)凸函数(严格)凸函数(严格)凸函数(严格)凸函数 称定义在凸集称定义在凸集称定义在凸集称定义在凸集K K上的实值函数上的实值函数上的实值函数上的实值函数f f(x)(x)为凸函数,若为凸函数,若 定义定义1.3.3 1.3.3 凹函数凹函数凹函数凹函数 3 3第3页,此课件共126页哦定义定义定义定义1.3.4 1.3.4 凸规划凸规划凸规划
3、凸规划(图集上凸函数的极小化问题)(图集上凸函数的极小化问题)定理定理定理定理1.3.11.3.1 设设 、均为凸集,均为凸集,则则则则 也是凸也是凸也是凸也是凸集集集集 ,对任意实数对任意实数,是凸集是凸集是凸集是凸集。(证明)(推广)(证明)(推广)定理定理定理定理1.3.21.3.2 有限个凸集的交集必是凸集有限个凸集的交集必是凸集定理定理定理定理1.3.31.3.3 (分离定理)(分离定理)K K为闭凸集,为闭凸集,则则 定理定理定理定理1.3.4 1.3.4(支撑超平面定理)(支撑超平面定理)(支撑超平面定理)(支撑超平面定理)4 4第4页,此课件共126页哦 定理定理定理定理1.3
4、.5 1.3.5 若若若若 均为凸集均为凸集均为凸集均为凸集K K上的凸函数,则上的凸函数,则上的凸函数,则上的凸函数,则 也是也是也是也是K K上的凸函数。上的凸函数。上的凸函数。上的凸函数。(请证明)(请证明)(请证明)(请证明)定理定理定理定理1.3.61.3.6 设设设设f(x)f(x)是凸集是凸集是凸集是凸集K K上的凸函数,则上的凸函数,则上的凸函数,则上的凸函数,则 实数实数实数实数C C,水平集,水平集,水平集,水平集 必为凸集。必为凸集。必为凸集。必为凸集。(请证明)(请证明)(请证明)(请证明)定理定理定理定理1.3.7 1.3.7 若若若若f(x)f(x)在开集在开集在开
5、集在开集K K 中可微,则中可微,则中可微,则中可微,则f f 是是是是K K上的(严格)凸函上的(严格)凸函上的(严格)凸函上的(严格)凸函数当且仅当数当且仅当数当且仅当数当且仅当 5 5第5页,此课件共126页哦证明证明(充分性)充分性)任取任取 ,记,记由条件,由条件,(必要性)(必要性)6 6第6页,此课件共126页哦令令此即需证。此即需证。若若 f(x)f(x)两阶可微,则有以下的定理:两阶可微,则有以下的定理:定理定理1.3.8 1.3.8 设设f(x)f(x)在开凸集在开凸集K K中二阶连续可微,中二阶连续可微,f f 为凸函数的充要为凸函数的充要条件为:条件为:证明证明:(:(
6、充分性)充分性)7 7第7页,此课件共126页哦此处从而,(必要性)任取将 在 x 处展开 :8 8第8页,此课件共126页哦令 得定理1.3.9 证明 9 9第9页,此课件共126页哦此即说明此即说明f f 是严格凸函数。是严格凸函数。定理定理1.3.101.3.10证明证明 当当 充分小时充分小时 在在 的邻域中,从而导出矛盾,的邻域中,从而导出矛盾,证毕证毕 1010第10页,此课件共126页哦1.4 1.4 最最最最优优性条件性条件性条件性条件无约束极小化问题 (模型)(模型)minmin s.t s.t (1.4.1)1.4.1)定理定理1.4.1 1.4.1 (一阶必要条件)若(一
7、阶必要条件)若 是可微函数,是可微函数,是问题(是问题(1.4.1)1.4.1)的一个局部最小点的必要条件为:的一个局部最小点的必要条件为:(无约束极小化问题求解)等价于(方程组求解)(无约束极小化问题求解)等价于(方程组求解)定理定理1.4.2 1.4.2 (二阶必要条件)设(二阶必要条件)设 为为 中的二阶连续可微函中的二阶连续可微函数,如果数,如果 是是 的一个局部极小点,则的一个局部极小点,则 1111第11页,此课件共126页哦证明:由定理证明:由定理1.4.11.4.1,。对任意的。对任意的由于由于 是局部极小点,故对于充分小的是局部极小点,故对于充分小的 必有必有此式成立必须有此
8、式成立必须有 ,证毕。,证毕。1212第12页,此课件共126页哦定理定理1.4.3 1.4.3(二阶充分条件)设(二阶充分条件)设 两阶可微,若两阶可微,若 满足满足则点则点 的一个严格局部极小点,这里的一个严格局部极小点,这里 是是 的两阶的两阶HesseHesse矩阵矩阵定理定理1.4.41.4.4(两阶充分条件)设(两阶充分条件)设 两阶连续可微,若两阶连续可微,若 满足满足 证明:任取证明:任取显然,显然,由假设,由假设,由,由 的任意的任意性,性,是是 1313第13页,此课件共126页哦定理定理1.4.51.4.5证毕证毕 1414第14页,此课件共126页哦具有等式与不等式约束
9、的极小化问题具有等式与不等式约束的极小化问题 (NP)min (NP)min s.t s.t 定义定义 1.4.1 1.4.1 设设x x是满足是满足(NP)(NP)约束条件的点,记约束条件的点,记 称称I I 为为x x处不等式约束中的积极约束的下标集合处不等式约束中的积极约束的下标集合 定义定义1.4.2 1.4.2(积极约束)(积极约束)称约束称约束为为x x处的积极约束处的积极约束定义定义1.4.3 1.4.3(正则点)若向量组(正则点)若向量组线性无关,则称线性无关,则称x x为约束条件的一个正则点。为约束条件的一个正则点。1515第15页,此课件共126页哦定理定理1.4.5 1.
10、4.5(Kuhn-TuckerKuhn-Tucker条件)设条件)设 是是(NP)(NP)的局部极小点且的局部极小点且 其中其中 1616第16页,此课件共126页哦例例 求下面问题的求下面问题的 K-T K-T 点点 min min s.t s.t 解:本问题的解:本问题的 K-TK-T条件为条件为1717第17页,此课件共126页哦(1 1)若若 (舍去)(舍去)若若 (舍去)(舍去)(2 2)(舍去)(舍去)(3 3)1818第18页,此课件共126页哦故有 求得 1919第19页,此课件共126页哦1.5 迭代算法及收迭代算法及收敛速度速度 迭代算法迭代算法 记满足要求的点集为记满足要
11、求的点集为 (如(如 K-T K-T 点集,最优解集等)。算法一般采用迭点集,最优解集等)。算法一般采用迭代方法,即:任给一个初始点代方法,即:任给一个初始点步步1 1步步2 2 定义定义1.5.1 1.5.1(全局收敛性)设(全局收敛性)设A A是求解问题的一个算法,若对任意初始点是求解问题的一个算法,若对任意初始点 在用算法在用算法A A进行迭代时,或能在有限步求得最优解,或求得一无穷点列进行迭代时,或能在有限步求得最优解,或求得一无穷点列 ,该点列的任意聚点均为需求的点。,该点列的任意聚点均为需求的点。2020第20页,此课件共126页哦例例1 1 求解问题求解问题 minmin s.t
12、 s.t 算法算法 迭代点列迭代点列例例2 2 求解求解 minmin 算法算法 2121第21页,此课件共126页哦迭代点列迭代点列 若若 若若定义定义定义定义 1.5.11.5.1 (闭映射)设(闭映射)设X X何何Y Y分别是两个非空闭集,分别是两个非空闭集,A A是从是从X X到到Y Y的一个点到集的映射,的一个点到集的映射,即对任意即对任意 有有 。设。设 ,且且 若若 (例(例1 1种的映射是闭的,而例种的映射是闭的,而例2 2中的映射则是非闭的)中的映射则是非闭的)显然,例显然,例2 2的最优解为的最优解为 取取算法算法A A为为X X到到X X的一个映射:的一个映射:定理定理定
13、理定理1.5.11.5.1 若对任意取定的若对任意取定的 :(1 1)(2 2)存在)存在 ,(3 3)算法)算法 A A 在在 外是闭的外是闭的则算法则算法 A A 必定是全局收敛的。(证明从略)必定是全局收敛的。(证明从略)2222第22页,此课件共126页哦收敛速度收敛速度定义定义1.5.2 1.5.2 设实数列设实数列 除有限个除有限个 外外 除有限个除有限个 外外 其他其他 被称为商收敛因子被称为商收敛因子定理定理1.5.2 1.5.2 仅有以下三种情况之一发生:仅有以下三种情况之一发生:(1 1)(2 2)(3 3),2323第23页,此课件共126页哦定义定义1.5.3 1.5.
14、3 设设 ,我们称,我们称 为为 收敛到收敛到 的阶。也称的阶。也称 阶阶收敛到收敛到 (对情况对情况1 1,令,令 ,对情况,对情况2 2 ,令,令 )显然,收敛的阶越大,收敛速度越快。当数列具有一阶收敛速度时显然,收敛的阶越大,收敛速度越快。当数列具有一阶收敛速度时 越小数列收敛得越快。越小数列收敛得越快。定义定义1.5.4 1.5.4 若若 则称数列则称数列 超线性收敛于超线性收敛于例例2 2 (1 1)(2 2)2424第24页,此课件共126页哦第二章第二章第二章第二章 一维极值问题的最优化方法一维极值问题的最优化方法一维极值问题的最优化方法一维极值问题的最优化方法 在求解极值问题时
15、我们经常会反复采用如下的一元函数求极值步骤:在求解极值问题时我们经常会反复采用如下的一元函数求极值步骤:先求出一个搜索方向先求出一个搜索方向 d d,然后沿方向,然后沿方向 d d 作一维搜索。为此,我们先来介作一维搜索。为此,我们先来介绍一下一维搜索的一些技巧和方法。绍一下一维搜索的一些技巧和方法。问题:问题:min s.t本问题实际上是一个一元函数求极值的问题,为方便起见,以下我们讨论问本问题实际上是一个一元函数求极值的问题,为方便起见,以下我们讨论问题:题:min s.t这里这里 a a 可以是可以是 ,b b 可以是可以是 。2525第25页,此课件共126页哦2.1 2.1 仅仅比比
16、比比较较函数函数函数函数值值的最的最的最的最优优化方法化方法化方法化方法定义定义定义定义2.12.1 (下单峰函数)(下单峰函数)定义定义定义定义2.22.2 (不定区间)包含下单峰函数最小点的区间(不定区间)包含下单峰函数最小点的区间a,ba,b方法:按一定的方法在方法:按一定的方法在 a,b a,b 区间中取若干个点,比较这些点上的函数值,不断区间中取若干个点,比较这些点上的函数值,不断缩小不定区间。缩小不定区间。定义定义定义定义2.32.3 (最优搜索策略)总点数相同而能使不定区间缩得最小的搜索方法。(最优搜索策略)总点数相同而能使不定区间缩得最小的搜索方法。(FibonacciFibo
17、nacci 方法)方法)FibonacciFibonacci数数 1 1,1 1,2 2,3 3,5 5,8 8,1313,2121,3434,2626第26页,此课件共126页哦方法:设目前的不定区间为方法:设目前的不定区间为 a,b a,b,尚有,尚有 r r 个试验点。个试验点。令令比较比较(1 1)若)若(2 2)若)若(3 3)若)若最后,当只剩下还有一个试验点时,不定区间的中点最后,当只剩下还有一个试验点时,不定区间的中点 为一试验点,最后一为一试验点,最后一个试验点可取个试验点可取2727第27页,此课件共126页哦定理定理定理定理2.12.1 利用利用FibonacciFibo
18、nacci法作一维搜索,经过法作一维搜索,经过 n n 次试验后,最后的不定区间长度次试验后,最后的不定区间长度不超过不超过步骤:先根据步骤:先根据FibonacciFibonacci 法的近似方法法的近似方法0.6180.618法法 设初始不定区间为设初始不定区间为 a,b a,b,取,取2828第28页,此课件共126页哦例(1)(2)(3)取从头开始。2.1 牛顿方法2929第29页,此课件共126页哦2.22.2 牛顿方法牛顿方法牛顿方法牛顿方法迭代公式:步1若若 3030第30页,此课件共126页哦定理定理定理定理2.22.2 设设 是是a,ba,b上的两阶连续可导函数,且上的两阶连
19、续可导函数,且则任取则任取 ,由迭代公式,由迭代公式产生的点列产生的点列产生的点列产生的点列 收敛到收敛到收敛到收敛到(证明从略)(证明从略)(证明从略)(证明从略)3131第31页,此课件共126页哦第三章第三章第三章第三章 无约束极值问题的最优化方法无约束极值问题的最优化方法无约束极值问题的最优化方法无约束极值问题的最优化方法问题 min s.t3.1 最速下降法 步骤1 取初始点 ,令k=0 步骤2 计算 步骤3 若 停,输出 否则进入下一步 步骤4 求 使得 步骤5 令 3232第32页,此课件共126页哦定理3.1 设 一阶连续可导,集合有界,则由上述算法求得的点列 有如下的性质(1
20、)严格单调下降 (2)的任一极限点 处必有 令 定理3.2 设 是由最速下降法产生的点列,则对每一步 k,成立:其中A与a为Q的最大特征值与最小特征值 3333第33页,此课件共126页哦据此可知据此可知(1 1)若)若A=aA=a,即目标函数的等值面为园,即目标函数的等值面为园,则用最速下降法一步就可求得最优解。(则用最速下降法一步就可求得最优解。(2 2)A A与与a a的的差越小,则用最速下降法求得的点列收敛得越慢。差越小,则用最速下降法求得的点列收敛得越慢。3.2 3.2 牛顿法牛顿法先看二次严格凸函数先看二次严格凸函数 解得:解得:对一般的函数对一般的函数 有:有:3434第34页,
21、此课件共126页哦牛顿法迭代步骤牛顿法迭代步骤定理定理3.3 3.3 3535第35页,此课件共126页哦3.3 3.3 共共轭轭方向法方向法定理定理3.4 3.4 若若3636第36页,此课件共126页哦(设计具有二次有限终止性的共轭方向法)(设计具有二次有限终止性的共轭方向法)仍取仍取取初始点取初始点定理定理3.5 3.5 则迭代可在至多则迭代可在至多n n步内终止并求得步内终止并求得 的极小点。的极小点。(共轭方向法的一种实现方法)(共轭方向法的一种实现方法)步步1 1 设已有设已有3737第37页,此课件共126页哦步步2 2 若若 作一维搜索:作一维搜索:定理定理3.4 3.4 用上
22、面方法构造出来的向量组用上面方法构造出来的向量组为为 共轭的。共轭的。(用于一般函数的共轭方向法)令(用于一般函数的共轭方向法)令Step 1.Step 1.取初始点取初始点 ,允许误差,允许误差 2.2.检验是否满足检验是否满足 ,若满足,停;否则到下一步,若满足,停;否则到下一步 3.3.令令 3838第38页,此课件共126页哦 4.4.5.5.6.6.检验检验 ,若满足,停;否则检查,若满足,停;否则检查若是,令若是,令 7.7.(算法完)(算法完)3939第39页,此课件共126页哦定理3.5 设 是具有一阶连续偏导数的凸函数,是由上述算法产生的无穷点列,水平集 (1)为严格单调下降
23、数列 (2)的任意聚点均为问题的最优解3.4 变尺度法 (略)3.5 直接法 (略)4040第40页,此课件共126页哦第四章第四章第四章第四章 有约束极值问题有约束极值问题有约束极值问题有约束极值问题问题 min s.t求解约束极值问题的主要途径:(1)可行下降法(无约束问题下降方向法的推广)(2)罚函数法或障碍函数法(将约束加入目标)(3)解一系列线性规划(4)直接法4141第41页,此课件共126页哦4.1 zoutendijk可行方向法 问题 min s.t 定定义4.1(不等式约束中的积极约束的下标集合)设 为问题的可行解,称为不等式约束中的积极约束集合。定定义4.2(积极约束)此问
24、题的积极约束有:4242第42页,此课件共126页哦定定义4.3(可行方向)设 x 是 min s.t (4.1)的可行点,即 ,称方向 d 为 x 处的可行方向,若存在定理定理4.1 设 x 是(4.1)的一个可行解,则 d 为 x 处的一个可行方向的充要条件为:(证明)4343第43页,此课件共126页哦定义定义4.4(下降方向)设 x 是(4.1)的可行解,称非零向量 d 为 x 处的一个下降方向,若存在 定理定理4.2 设 则 d 为 x 处的一个下降方向的充要条件为:(证明)定义4.5(可行下降方向)既可行又下降的方向 4444第44页,此课件共126页哦具体算法算法1 求解线性规划
25、 min s.t (4.2)算法2 求解 min s.t (4.3)4545第45页,此课件共126页哦算法3 min s.t (4.4)定理 4.3 设(证明)4646第46页,此课件共126页哦(zoutendijk(zoutendijk算法)算法)任取初始点任取初始点(2 2)求解对应)求解对应若若(3 3)令)令(4 4)求解)求解 4747第47页,此课件共126页哦例4.1用Zoutendijk方法求解 min s.t(取初始点 迭代一次)s.t4848第48页,此课件共126页哦4949第49页,此课件共126页哦Zoutendijk方法不具有全局收敛性(例从略)4.2 带非线性
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 非线性 规划 课件
限制150内