附录4:《最优化方法》复习提要Word下载.doc
- 文档编号:6852676
- 上传时间:2023-05-07
- 格式:DOC
- 页数:33
- 大小:1.90MB
附录4:《最优化方法》复习提要Word下载.doc
《附录4:《最优化方法》复习提要Word下载.doc》由会员分享,可在线阅读,更多相关《附录4:《最优化方法》复习提要Word下载.doc(33页珍藏版)》请在冰点文库上搜索。
例4设,其中二阶可导,,试求.
解由多元复合函数微分法知.
定理4设,且在点的某邻域内具有二阶连续偏导数,则在点处有Taylor展式
证明设,则.按一元函数Taylor公式在处展开,有
从例4得知.
令,有.
根据定理1和定理4,我们有如下两个公式
1.3最优化的基本术语
定义设为目标函数,为可行域,.
(1)若,都有,则称为在上的全局(或整体)极小点,或者说,是约束最优化问题的全局(或整体)最优解,并称为其最优值.
(2)若,都有,则称为在上的严格全局(或整体)极小点.
(3)若的邻域使得,都有,则称为在上的局部极小点,或者说,是约束最优化问题的局部最优解.
(4)若的邻域使得,都有,则称为在上的严格局部极小点.
第二章最优性条件
2.1无约束最优化问题的最优性条件
定理1设在点处可微,若是问题的局部极小点,则.
定义设在处可微,若,则称为的平稳点.
定理2设在点处具有二阶连续偏导数,若是问题的局部极小点,则,且半正定.
定理3设在点处具有二阶连续偏导数,若,且正定,则是问题的严格局部极小点.
注:
定理2不是充分条件,定理3不是必要条件.
例1对于无约束最优化问题,其中,显然
,令,得的平稳点,而且
易见为半正定矩阵.
但是,在的任意邻域,总可以取到,使,即不是局部极小点.
例2对于无约束最优化问题,其中,
易知,从而得平稳点,并且
显然不是正定矩阵.但是,在处取最小值,即为严格局部极小点.
例3求解下面无约束最优化问题,
其中,
解因为
所以令,有
解此方程组得到的平稳点.
从而
由于和是不定的,因此和不是极值点.是负定的,故不是极值点,实际上它是极大点.是正定的,从而是严格局部极小点.
定理4设是凸函数,且在点处可微,若,则为的全局极小点.
推论5设是凸函数,且在点处可微.则为的全局极小点的充分必要条件是.
例4试证正定二次函数有唯一的严格全局极小点,其中为阶正定矩阵.
证明因为为正定矩阵,且,所以得的唯一平稳点.又由于是严格凸函数,因此由定理4知,是的严格全局极小点.
2.2等式约束最优化问题的最优性条件
定理1设在点处可微,在点处具有一阶连续偏导数,向量组线性无关.若是问题
的局部极小点,则,使得
称为Lagrange函数,其中.
称为Lagrange乘子向量.
易见,这里.
定理2设和在点处具有二阶连续偏导数,若,使得,并且,,只要,便有,则是问题
的严格局部极小点.
例1试用最优性条件求解
解Lagrange函数为,则,
从而得的平稳点和,对应有
和.
由于.
因此
并且,有.
利用定理2,所得的两个可行点和都是问题的严格局部极小点.
2.3不等式约束最优化问题的最优性条件
定义设,若,使得,,
则称为集合在点处的可行方向.
这里.
令,
定理1设是非空集合,在点处可微.若是问题的局部极小点,则.
对于
(1)
其中.
令,其中是上述问题
(1)的可行点.
定理2设是问题
(1)的可行点,和在点处可微,在点处连续,如果是问题
(1)的局部极小点,则,
定理3设是问题
(1)的可行点,和在点处可微,在点处连续,若是问题
(1)的局部极小点,则存在不全为0的非负数,使
.(称为FritzJohn点)
如果在点处也可微,则存在不全为0的非负数,使
(称为FritzJohn点)
例1设试判断是否为FritzJohn点.
解因为,且,
所以为使FritzJohn条件成立,只有才行.取即可,因此是FritzJohn点.
定理4设是问题
(1)的可行点,和在点处可微,在点处连续,并且线性无关.若是问题
(1)的局部极小点,则存在,使得
.(称为K-T点)
如果在点处也可微,则存在,使得
(称为K-T点)
例2求最优化问题的K-T点.
解因为,所以K-T条件为
若,则,这与矛盾.故,从而;
由于,且为问题的可行点,因此是K-T点.
定理5设在问题
(1)中,和是凸函数,是可行点,并且和在点处可微.若是问题
(1)的K-T点,则是问题
(1)的全局极小点.
2.4一般约束最优化问题的最优性条件
考虑等式和不等式约束最优化问题
并把问题
(1)的可行域记为..
定理1设为问题
(1)的可行点,和在点处可微,在点处具有一阶连续偏导数,在点处连续,并且向量组线性无关.若是问题
(1)的局部极小点,则,
这里,,
定理2设为问题
(1)的可行点,和在点处可微,在点处具有一阶连续偏导数,在点处连续.若为问题
(1)的局部极小点,则存在不全为0的数和,且,使
若在点处也可微,则存在不全为0的数和,且,使
例1设试判断是否为FritzJohn点.
解,且,且,
因此为使FritzJohn条件成立,只有才行.所以取,即知是FritzJohn点.
定理3设为问题
(1)的可行点,和在点处可微,在点处具有一阶连续偏导数,在点处连续,且向量组线性无关.若是问题
(1)的局部极小点,则存在数和,使
如果在点处也可微,则存在数和,使
令,
称与为广义Lagrange乘子向量或K-T乘子向量.
令为广义Lagrange函数.称为广义Lagrange函数.则K-T条件为
定理4设在问题
(1)中,和是凸函数,是线性函数,是可行点,并且和在点处可微.若是问题
(1)的K-T点,则是问题
(1)的全局极小点.
例2求解最优化问题
解广义Lagrange函数为
因为,.
所以K-T条件及约束条件为
下面分两种情况讨论.
(1)设,则有
由此可解得,但不是可行点,因而不是K-T点.
(2)设,则有
由此可得,解得或。
从而或.于是或(这与矛盾).或.由此可知是问题的K-T点,但不是问题的K-T点.
易见,是上的凸函数,是上的凹函数,是线性函数,因此由定理4知,是问题的全局最优解.
定理5设为问题
(1)的可行点,和在点处具有二阶连续偏导数,并且存在乘子向量和使K-T条件成立,即
若对于任何满足
的向量,都有,则是问题
(1)的严格局部极小点.
例3求解最优化问题
其中常数.
解该问题的广义Lagrange函数为
因为.
所以问题的K-T条件及约束条件为
由第1式、第3式知,从而由第二式解得.于是再由第1式知,且,
即得,从而,解得,
于是.
所以是问题的K-T点.
又由于在点处关于的Hesse矩阵是一个阶对角矩阵,其对角线上第个元素为
因此是正定矩阵.根据定理5,为问题的严格局部极小点.
第三章常用优化算法介绍
3.1一维搜索
给定,令.
定义如果求得步长,使得
(3.1.1)
则称这样的一维搜索为最优一维搜索或精确一维搜索.叫做最优步长.
定理1对于问题,设是可微函数,是从出发沿方向作最优一维搜索得到的,则有.
定义如果选取,使目标函数沿方向取得适当的可接受的下降量,即使得下降量是我们可接受的,则称这样的一维搜索为可接受一维搜索或非精确一维搜索.
定义设,并且.如果对于有,那么称是问题的搜索区间.
定义设,若存在,使得在上严格单调减少,在上严格单调增加,则称是的单谷区间,是上的单谷函数或单峰函数.
定理2设为的单谷区间,,且,那么
(1)若,则是的单谷区间;
(2)若,则是的单谷区间.
算法3-1(进退法)
Step1选取初始数据。
给定初始点,初始步长,加倍系数(一般取),计算,置.
Step2试探.令,计算.
Step3比较目标函数值.若,转Step4,否则,转Step5.
Step4加步探索.令,转Step2.
Step5反向搜索.若,转换搜索方向,,转Step2;
否则,停止迭代.令.输出搜索区间.
3.20.618法与Fibonacci法
考虑.假定的一个搜索区间已确定,并设在上为单谷函数.
算法3-2(0.618法)
Step1选取初始数据.确定初始搜索区间和允许误差.
Step2计算最初两个试探点:
,求出,并置.
Step3检查?
是,停止计算,输出;
否则,转Step4.
Step4比较函数值.若,转Step5;
若,转Step6.
Step5向左搜索.令.
并计算,转Step7.
Step6向右搜索.令.
Step7置,转Step3.
定义Fibonacci数是指满足下述条件的数列:
(3.2.1)
用数学归纳法可以证明,Fibonacci数可由下式表示:
.(3.2.2)
算法3-3(Fibonacci法)
Step1选取初始数据.给定初始搜索区间和允许误差,辨别系数,求搜索次数,使
.
,求函数值和,并置.
是,转Step4;
否,转Step5.
Step4向左搜索.令.
并计算和,转Step6.
Step5向右搜索.令.
Step6置,若,转Step3;
若,转Step7.
Step7令,计算和。
若,则令
;
否则,令,停止计算,极小点含于区间.
3.3Newton法
考虑.假定具有三阶连续导数.
算法3-4(Newton法)
Step1给定初始点,允许误差,置.
Step2检查?
是,输出,停止计算;
否,转Step3.
Step3计算点,置,转Step2.
3.4最速下降法
考虑无约束最优化问题
,(3.4.1)
其中具有一阶连续偏导数.
算法3-5(最速下降法)
Step1选取初始数据.选取初始点,给定允许误差,令.
Step2检查是否满足终止准则.计算,若,迭代终止,为问题(3.4.1)的近似最优解;
否则,转Step3.
Step3进行一维搜索.取,求和,使得
令,返回Step2.
特别地,考虑
,(3.4.2)
其中为正定矩阵,.
设第次迭代点为,从点出发沿作一维搜索,得
其中为最优步长.根据定理3.1.1,有.而,
所以,从而,而正定,即,故由上式解出
(3.4.3)
于是
(3.4.4)
这是最速下降法用于问题(3.4.2)的迭代公式.
例1用最速下降法求解问题
,(3.4.5)
其中.取初始点,允许误差.
解问题(3.4.5)中的是正定二次函数,且
在点处的梯度.
第一次迭代:
令搜索方向,
从点出发沿作一维搜索,由(3.4.3)式和(3.4.4)式有
第二次迭代:
令,
从点出发沿作一维搜索,按(3.4.4)式得
第三次迭代:
按(3.4.4)式求得
第四次迭代:
第五次迭代:
此时,,已满足精度要求,故得问题(3.4.5)的近似最优解
实际上问题(3.4.5)的最优解为.
3.5Newton法
算法3-6(Newton法)
Step3构造Newton方向.计算,取.
Step4求下一个迭代点.令,,返回Step2.
例2用Newton法求解问题(3.4.5),仍取初始点,允许误差.
解,,故
,,
由于,迭代结束,得为问题(3.4.5)的最优解.
算法3-7(阻尼Newton法)
Step4进行一维搜索.求和,使得
例3用阻尼Newton法求解下面问题:
,(3.5.1)
解第一次迭代:
故,
于是,Newton方向,从出发沿作一维搜索,即求的最优解,得到.令
从出发沿作一维搜索,即求
的最优解,得到.令
此时,,得问题(3.5.1)的最优解为,这是惟一的最优解.
3.6共轭梯度法
定义设为正定矩阵.若中的向量组满足
则称是共轭的.
算法3-8(共轭方向法)
给定一个正定矩阵.
Step1选取初始数据.选取初始点,给定允许误差.
Step2选取初始搜索方向.计算,求出,使,令.
Step3检查是否满足终止准则.若,迭代终止;
Tep5选取搜索方向.求使
令,返回Step3.
如果用共轭方向法求解正定二次函数的无约束最优化问题
,(3.6.1)
其中为正定矩阵,(此时算法中的正定矩阵应与二次函数的正定矩阵一致),那么容易推出迭代公式为
.(3.6.2)
对于问题(3.4.1)的求解,我们还有如下一些方法.
Fletcher-Reeves(FR)公式:
Dixon-Myers(DM)公式:
Polak-Ribiere-Polyak(PRP)公式:
算法3-9(FR共轭梯度法)
Step2检查是否满足终止准则.计算,若,迭代终止,为(3.4.1)的近似最优解;
Step3构造初始搜索方向.计算.
Tep5检查是否满足终止准则.计算,若,迭代终止,为(3.4.1)的近似最优解;
否则,转Step6.
Step6检查迭代次数.若,令,返回Step3;
否则,转Step7.
Step7构造共轭方向.用FR公式取
令,返回Step4.
注意,如果算法3-9的Step7中的形式改为DM公式或PRP公式,则分别得到DM共轭梯度法和PRP共轭梯度法.
例4用FR共轭梯度法求解问题(3.5.1),仍取初始点,允许误差.
所以
令,从出发,沿进行一维搜索,得
由FR公式有
,
因此,新的搜索方向为
从出发,沿进行一维搜索,得
此时
得问题(3.5.1)的最优解为.
3.7坐标轮换法
,(3.7.1)
算法3-10(坐标轮换法)
Step2进行一维搜索.从出发,沿坐标轴方向进行一维搜索,求和,使得
Step3检查迭代次数.若,转Step4;
否则,令,返回Step2.
Step4检查是否满足终止准则.若,迭代终止,得为问题(3.7.1)的近似最优解;
例4用坐标轮换法求解问题
,(3.7.2)
解从点出发沿进行一维搜索,易得
从点出发沿进行一维搜索,得
再从点出发沿进行一维搜索,得
迭代终止,得问题(3.7.2)的近似最优解为
其实问题(3.7.2)的最优解为.
3.8Powell法
算法3-11(Powell法)
Step1选取初始数据.选取初始点,个线性无关的初始搜索方向,给定允许误差,令.
Step2进行基本搜索.令,依次沿进行一维搜索.对一切,记
Step3检查是否满足终止准则.取加速方向,若,迭代终止,得为问题的近似最优解;
Step4确定搜索方向.按
(3.8.1)
确定,若
(3.8.2)
成立,转Step5;
Step5调整搜索方向.从点出发沿方向作一维搜索.求出,使得
令,再令,,返回Step2.
Step6不调整搜索方向.令,,返回Step2.
例5用Powell法求解问题(3.7.2),仍取初始点,初始搜索方向组
给定允许误差.
同例1一样,得
。
因为,所以要确定调整方向.由于
按(3.8.1)式有
因此,并且
又因,故(3.8.2)式不成立.于是,不调整搜索方向组,并令.
取,从点出发沿作一维搜索,得
接着从点出发沿方向作一维搜索,得
由此有加速方向
因为,所以要确定调整方向.因
故按(3.8.1)式易知,并且
由于
因此(3.8.2)式成立。
于是,从点出发沿作一维搜索,得
同时,以替换,即下一次迭代的搜索方向组取为
取,类似地可求得
因为,所以迭代终止,得问题(3.7.2)的最优解为.
3.9罚函数法
一、外法函数法
考虑约束非线性最优化问题
(3.9.1)
其中都是定义在上的实值连续函数.记问题(3.9.1)的可行域为.
对于等式约束问题
(3.9.2)
定义罚函数
其中参数是很大的正常数.这样,可将问题(3.9.2)转化为无约束问题
.(3.9.3)
对于不等式约束问题
(3.9.4)
其中是很大的正数.这样,可将问题(3.9.4)转化为无约束问题
.(3.9.5)
对于一般的约束最优化问题(3.9.1),定义罚函数
,
其中是很大的正数,具有下列形式:
和是满足下列条件的实值连续函数:
函数和的典型取法为
其中和是给定的常数,通常取作1或2.
这样,可将约束问题(3.9.1)转化为无约束问题
,(3.9.6)
其中是很大的正数,是连续函数.
算法3-12(外罚函数法)
Step1选取初始数据.给定初始点,初始罚因子,放大系数,允许误差,令.
Step2求解无约束问题.以为初始点,求解无约束问题
,(3.9.7)
设其最优解为.
Step3检查是否满足终止准则.若,则迭代终止,为约束问题(3.9.1)的近似最优解;
二、内罚函数法
对于不等式约束问题(3.9.4),其可行域的内部
为了保持迭代点始终含于,我们引入另一种罚函数
其中是很小的正数,是上的非负实值连续函数,当点趋向可行域的边界时,.
显然,罚函数的作用是对企图脱离可行域的点给予惩罚,相当于在可行域的边界设置了障碍,不让迭代点穿越到可行域之外,因此也称为障碍函数.
的两种常用的形式为
及
分别称为倒数障碍函数和对数障碍函数.
算法3-13(内罚函数法或SUMT内点法)
Step1选取初始数据.给定初始内点,初始参数,缩小系数,允许误差,令.
(3.9.8
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最优化方法 附录 优化 方法 复习 提要