最优化方法第三章(可行方向法)

《最优化方法第三章(可行方向法)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、可行方向法简介一可二Zoutendijk法行方三梯度投影法向法四既约梯度法一、可行方向法简介可行方向法是求解约束优化问题的方法之一。通过在可行域内直接搜索最优解求解约束优化问题，它可看作无约束优化下降算法的自然推广。基本思想：从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点，直到满足终止条件，得到最优解x*.基本的迭代步骤0k1.从可行点x开始迭代，设已得到可行点xkk2.在x处用某种方法确定一可行下降方向d3.沿dk寻找新的迭代点xk1xkdkk1是可行点且k，使得x

2、k1kf(x)f(x)，令kk1,转2，直到满足终止条件。一、可行方向法简介可行方向法的分类可行方向法的核心是选择可行下降搜索方向和确定搜索步长。k搜索方向d的选择方式不同就形成不同的可行方向法：k通过求解一个线性规划来确定d，如Zoutendijk(约坦狄克)可行方向法、Frank-Wolfe方法等；k利用投影矩阵直接构造d，如梯度投影法；k利用既约矩阵直接构造d，如既约梯度法。最早的可行方向法是由Zoutendijk于1960年提出的。一、Zoutendijk法可行方向与改进方向定义下降

3、方向对min??，设?∈??是任给一点，?∈???≠0，若存在?>0，使得对任意的?∈(0,?),有?(?+??)0，使得对任意的?∈(0,?),有?+??∈S一、Zoutendijk法线性约束模型的可行方向min()fxAxbst..Cxe紧约束Ab11定理设xD，在点x处有AxbAx,b,其中A,b

4、，1122Ab22则非零向量dx是处的可行方向的充分必要条件是Ad0,Cd0.证明：1必要性。设非零向量dx是处的可行方向,则存在0，使得对任意的(0,)，xd仍是可行解。即Ax(d)b,Cx()deA1b11Adb1充分性同理可证。Ax(d)(xd)AAx22Adb22因为0，所以Ad0.而Cx(d)eCde,故Cd0.1一、Zoutendijk法minfx()非线性约束模型的可行方向s

5、tgx..()0,i1,,mi定理设?∈?，在点?处有???≤0，?=1,…?,?是?点紧约束的指标集，设目标函数和????∈?在?点可微，????∉?在?点连续，如果??(?)??<0,??(?)??<0,?∈??则d是一改进(下降)可行方向。22min()fx(x6)(x2)1212432x12st..110x02010一、Zoutendijk法线性约束可行下降方向确定方法Tfxd()0d是点x处的可行下降方向。A

6、d01Cd0Tminfxd()Ad0求解下列线性规划问题1st..Cd0

7、dj

8、1,j（1）d0是可行解，因此最优目标函数值不大于0。（20）如果线性规划的最优值小于，则得到可行下降方向。（3）如果线性规划的最优值等于0，则x是KT-点。一、Zoutendijk法线性约束下降步长确定方法kkk1kk已知迭代点x和可行下降方向d,可令xxd。k其中应满足：kkk（ix）d仍为可行解；（ii）使目标函数值下降。k利用下列辅助线性规划问题求:kkkmin(fxd)k

9、k可去除Ax()dbkkst..Cx(d)ed是可行方向0Ad0,Cd01kk因为d是可行下降方向，故Cd0，即约束条件kkkkkCx()dCxCdCxe总是成立。一、Zoutendijk法kkk设在点x处有AxbAx,,b其中1122Ab11Ab,，Ab22kkAx()dbkk11则约束条件Ax+db可改写为kk，Ax2()db2d是可行方向Ad0,Cd01kkk因为d是可行下降方向

10、，所以Ad0,又Axb,0，111故不等式约束kkAx()db自然成立。11所以步长求解问题简化为kkmin(fxd)kkAxAdb222st..0一、Zoutendijk法()kk()AxAdb移项，得222()kk()()kk()minfx(d)AdbAx222()kk()st..令bbAx,dAd，222()kk()