附录4:《最优化方法》复习提要.doc
- 文档编号:4705652
- 上传时间:2023-05-07
- 格式:DOC
- 页数:33
- 大小:1.90MB
附录4:《最优化方法》复习提要.doc
《附录4:《最优化方法》复习提要.doc》由会员分享,可在线阅读,更多相关《附录4:《最优化方法》复习提要.doc(33页珍藏版)》请在冰点文库上搜索。
附录4《最优化方法》复习提要
第一章最优化问题与数学预备知识
§1.1模型
无约束最优化问题.
约束最优化问题()
即
其中称为目标函数,称为决策变量,称为可行域,
称为约束条件.
§1.2多元函数的梯度、Hesse矩阵及Taylor公式
定义设.如果维向量,,有
.
则称在点处可微,并称为在点处的微分.
如果在点处对于的各分量的偏导数
都存在,则称在点处一阶可导,并称向量
为在点处一阶导数或梯度.
定理1设.如果在点处可微,则在点处梯度
存在,并且有.
定义设.是给定的维非零向量,.如果
存在,则称此极限为在点沿方向的方向导数,记作.
定理2设.如果在点处可微,则在点处沿任何非零方向的方向导数存在,且,其中.
定义设是上的连续函数,.是维非零向量.如果,使得,有(>).则称为在点处的下降(上升)方向.
定理3设,且在点处可微,如果非零向量,使得(>)0,则是在点处的下降(上升)方向.
定义设.如果在点处对于自变量的各分量的二阶偏导数都存在,则称函数在点处二阶可导,并称矩阵
为在点处的二阶导数矩阵或Hesse矩阵.
定义设,记,如果
在点处对于自变量的各分量的偏导数
都存在,则称向量函数在点处是一阶可导的,并且称矩阵
为在点处的一阶导数矩阵或Jacobi矩阵,简记为.
例2设,求在任意点处的梯度和Hesse矩阵.
解设,则,
因,故得.
又因,则.
例3设是对称矩阵,,称为二次函数,求在任意点处的梯度和Hesse矩阵.
解设,则
,
从而.
再对求偏导得到,于是
.
例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)的可行点,和在点处可微,在点处具有一阶连续偏导数,在点处连续,并且向量组线性无关.若是问题
(1)的局部极小点,则,
这里,,
.
定理2设为问题
(1)的可行点,和在点处可微,在点处具有一阶连续偏导数,在点处连续.若为问题
(1)的局部极小点,则存在不全为0的数和,且,使
.(称为FritzJohn点)
若在点处也可微,则存在不全为0的数和,且,使
(称为FritzJohn点)
例1设试判断是否为FritzJohn点.
解,且,且,
因此为使FritzJohn条件成立,只有才行.所以取,即知是FritzJohn点.
定理3设为问题
(1)的可行点,和在点处可微,在点处具有一阶连续偏导数,在点处连续,且向量组线性无关.若是问题
(1)的局部极小点,则存在数和,使
.(称为K-T点)
如果在点处也可微,则存在数和,使
(称为K-T点)
令,
,
称与为广义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.
Step7置,转Step3.
定义Fibonacci数是指满足下述条件的数列:
(3.2.1)
用数学归纳法可以证明,Fibonacci数可由下式表示:
.(3.2.2)
算法3-3(Fibonacci法)
Step1选取初始数据.给定初始搜索区间和允许误差,辨别系数,求搜索次数,使
.
Step2计算最初两个试探点:
,求函数值和,并置.
Step3检查?
是,转Step4;否,转Step5.
Step4向左搜索.令.
并计算和,转Step6.
Step5向右搜索.令.
并计算和,转Step6.
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.4)式求得
.
第五次迭代:
令,
,
按(3.4.4)式求得
.
此时,,已满足精度要求,故得问题(3.4.5)的近似最优解
.
实际上问题(3.4.5)的最优解为.
§3.5Newton法
算法3-6(Newton法)
Step1选取初始数据.选取初始点,给定允许误差,令.
Step2检查是否满足终止准则.计算,若,迭代终止,为问题(3.4.1)的近似最优解;否则,转Step3.
Step3构造Newton方向.计算,取.
Step4求下一个迭代点.令,,返回Step2.
例2用Newton法求解问题(3.4.5),仍取初始点,允许误差.
解,,故
,,
.
由于,迭代结束,得为问题(3.4.5)的最优解.
算法3-7(阻尼Newton法)
Step1选取初始数据.选取初始点,给定允许误差,令.
Step2检查是否满足终止准则.计算,若,迭代终止,为问题(3.4.1)的近似最优解;否则,转Step3.
Step3构造Newton方向.计算,取.
Step4进行一维搜索.求和,使得
,
.
令,返回Step2.
例3用阻尼Newton法求解下面问题:
,(3.5.1)
其中.取初始点,允许误差.
解第一次迭代:
,
,
故,
.
于是,Newton方向,从出发沿作一维搜索,即求的最优解,得到.令
.
.
第二次迭代:
,
.
从出发沿作一维搜索,即求
的最优解,得到.令
.
.
此时,,得问题(3.5.1)的最优解为,这是惟一的最优解.
§3.6共轭梯度法
定义设为正定矩阵.若中的向量组满足
,
则称是共轭的.
算法3-8(共轭方向法)
给定一个正定矩阵.
Step1选取初始数据.选取初始点,给定允许误差.
Step2选取初始搜索方向.计算,求出,使,令.
Step3检查是否满足终止准则.若,迭代终止;否则,转Step4.
Step4进行一维搜索.求和,使得
,
.
Tep5选取搜索方向.求使
,
令,返回Step3.
如果用共轭方向法求解正定二次函数的无约束最优化问题
,(3.6.1)
其中为正定矩阵,(此时算法中的正定矩阵应与二次函数的正定矩阵一致),那么容易推出迭代公式为
.(3.6.2)
对于问题(3.4.1)的求解,我们还有如下一些方法.
Fletcher-Reeves(FR)公式:
;
Dixon-Myers(DM)公式:
;
Polak-Ribiere-Polyak(PRP)公式:
.
算法3-9(FR共轭梯度法)
Step1选取初始数据.选取初始点,给定允许误差.
Step2检查是否满足终止准则.计算,若,迭代终止,为(3.4.1)的近似最优解;否则,转Step3.
Step3构造初始搜索方向.计算.
Step4进行一维搜索.求和,使得
,
.
令,返回Step2.
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(坐标轮换法)
Step1选取初始数据.选取初始点,给定允许误差,令.
Step2进行一维搜索.从出发,沿坐标轴方向进行一维搜索,求和,使得
,
.
Step3检查迭代次数.若,转Step4;否则,令,返回Step2.
Step4检查是否满足终止准则.若,迭代终止,得为问题(3.7.1)的近似最优解;否则,令,返回Step2.
例4用坐标轮换法求解问题
,(3.7.2)
其中.取初始点,允许误差.
解从点出发沿进行一维搜索,易得
;
从点出发沿进行一维搜索,得
;
.
再从点出发沿进行一维搜索,得
;
从点出发沿进行一维搜索,得
;
.
再从点出发沿进行一维搜索,得
;
从点出发沿进行一维搜索,得
;
.
再从点出发沿进行一维搜索,得
;
从点出发沿进行一维搜索,得
;
.
迭代终止,得问题(3.7.2)的近似最优解为
.
其实问题(3.7.2)的最优解为.
§3.8Powell法
算法3-11(Powell法)
Step1选取初始数据.选取初始点,个线性无关的初始搜索方向,给定允许误差,令.
Step2进行基本搜索.令,依次沿进行一维搜索.对一切,记
,
.
Step3检查是否满足终止准则.取加速方向,若,迭代终止,得为问题的近似最优解;否则,转Step4.
Step4确定搜索方向.按
(3.8.1)
确定,若
(3.8.2)
成立,转Step5;否则,转Step6.
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)的近似最优解;否则,令,返回Step2.
二、内罚函数法
对于不等式约束问题(3.9.4),其可行域的内部
.
为了保持迭代点始终含于,我们引入另一种罚函数
,
其中是很小的正数,是上的非负实值连续函数,当点趋向可行域的边界时,.
显然,罚函数的作用是对企图脱离可行域的点给予惩罚,相当于在可行域的边界设置了障碍,不让迭代点穿越到可行域之外,因此也称为障碍函数.
的两种常用的形式为
,
及
分别称为倒数障碍函数和对数障碍函数.
算法3-13(内罚函数法或SUMT内点法)
Step1选取初始数据.给定初始内点,初始参数,缩小系数,允许误差,令.
Step2求解无约束问题.以为初始点,求解无约束问题
(3.9.8
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最优化方法 附录 优化 方法 复习 提要