搜索
1BeijingJiaotongUniversity第六章：求解约束优化问题的可行方向法侯忠生教授北京交通大学先进控制系统研究所电话：51688617电邮：houzhongsheng@china.com2BeijingJiaotongUniversity¾是解决约束优化问题的一种一般方法nmin()RfxxX∈⊂的极小点，其中X为闭集，f是连续的可微函数。求解¾问题的提法：3BeijingJiaotongUniversity¾基本思想：并且存在一常数，使得对任意的,均有对于k=0,1,2,…，给定一点,找一个方向向量,使kxX∈kp()0Tkkpfx∇kkkxtpX+∈kt0kktt≤≤可行方向法就是沿下降容许方向搜索并保持迭代点为可行点的一种迭代方法。4BeijingJiaotongUniversity然后按照某种准则决定，使得*kt*1kkkk关键两点：xxtpX+=+∈按这种方式进行，一直到满足某个算法停止条件为止。2、沿着这个可行的下降方向选择一个步长。1、选择一个可行的下降方向；5BeijingJiaotongUniversity使得是容许点且。置,然后转步2，直到某迭代点满足最优性条件为止。2、在处用某种方法确定一个下降的可行方向；3、在方向上寻找新迭代点kxk1、从容许点,开始迭代，设已迭代到；0xkx¾基本格式：pkp*1kkkkxxtp+=+1kx+1()()kkfxfx+1kk=+6BeijingJiaotongUniversity§1Zoutendijk可行方向法()min()..1fxstAxbCxd≥=mnA×lnC×1mb×1ld×f是连续可微函数。其中1.1线性约束情形7BeijingJiaotongUniversity2）适当调换A的行向量与b的相应分量，然后分解,相应地分解'下降可行方向的确定：AAA⎡⎤=⎢⎥⎣⎦'bbb⎡⎤=⎢⎥⎣⎦'',AxbAxb=使得1）x是（1）的某个容许点；定理1：假设那么，非零向量为从点出发的容许方向向量的充要条件是Px'0,0APCP≥=8BeijingJiaotongUniversity证明：必要性是容许方向，则存在，对任意的下式成立⇒Pδ0t(0,)∈δ()()AxtPbCxtPd+≥⎧⎨+=⎩已知是容许点，和，从而可得x''Axb=Cxd='0,0APCP≥=''''''()()()AxtPbAxtPbCxtPd⎧+≥⎪+≥⎨⎪+=⎩9BeijingJiaotongUniversityx是容许点，即⇐对任意和，利用已知条件0t0P≠''AxbCxd==AxbCxd≥⎧⎨=⎩'''()AxtPAxtAP+=+'''btAPb=+≥∵'0AP≥()充分性可得AxtPb+≥∵Axbt可以取得充分小。()CxtPCxtCPCxd+=+==10BeijingJiaotongUniversity容许性：'0AP≥0CP=()0TfxP∇下降性：'min()0..0TfxPAPstCP∇⎧≥⎨=⎩注：是起作用约束集合的梯度！'A问题：若满足，则对任意0，也满足，从而的极小值为！！直接求解次规划，不行。PβPP=β()TfxP∇−∞确定容许方向：11BeijingJiaotongUniversity从而，为了求解出可行下降方向，就必须要对的长度加以限制，可把P的各分量限制在[-1，1]之间！从而避免出现无穷大。PP'min()0..0111,2,...,TjfxPAPstCPPjn∇⎧≥⎪=⎨⎪−≤≤=⎩(2)由此可得到的有限的最优解。设为P*。12BeijingJiaotongUniversity显然0是(2)问题的可行解，所以问题(2)的最优解一定是非正的。若最优解为负，则就是点处的一个下降容许方向向量。*Px13BeijingJiaotongUniversity为了确定一个新的迭代点，可以从点出发沿下降容许方向做直线搜索，即直线搜索：即步长的确定xx*P*****()min()fxtPfxtPxxtP+=+=+问题：要保证新迭代点也必须是容许点！x最优步长的确定*t14BeijingJiaotongUniversity*min()tfxtP+**()..()0AxtPbstCxtPdt⎧+≥⎪+=⎨⎪≥⎩*()CxtPd+=*,0!CxdCP==多余！（因为）此规划问题可简化！*()AxtPb+≥分解成'*'*()()AxtPbAxtPb⎧+≥⎪⎨+≥⎪⎩'*()'AxtPb+≥(因为''多余Axb=*0AP≥)是容许方向！15BeijingJiaotongUniversity*min()..()0tfxtPstAxtPbt++≥≥最后简化成求可行区间**min()()..0fxtPAxtPbstt+⎧+≥⎨≥⎩*AxbtAPutv−≥−≥−[][]12*12,,...,,,...,TTuAxbuuuvAPvvvττ=−===令16BeijingJiaotongUniversity0uAxb（因为其中u和v都是与维数()相等。bτ从而成立，此种情况下•当时，对任意的，总成立，0v≥0t≥*AxbtAP−≥−t=+∞utv≥−z当时，(此时至少有一个0)，为使成立，：0v≤utv≥−）17BeijingJiaotongUniversity即对于总有1,2,...,iτ=iiutv≥−只须考虑的那些不等式。若取0iv1min|0iiiiutvvτ≤≤⎧⎫=−⎨⎬⎩⎭[0,]tt∈iiutv≥−则对，都有成立。从而*AxbtAP−≥−18BeijingJiaotongUniversity故，最优步长因子可由下述有约束的直线搜索求出*t*1min()..00min|00tiiiifxtPstttvtuvvvτ≤≤+≤≤+∞≥⎧⎪=⎧⎫⎨−≤⎨⎬⎪⎩⎭⎩（3）19BeijingJiaotongUniversity终止准则的确定：定理：在约束优化问题（1）中，()min()..1fxstAxbCxd≥=假设1）x是容许点；2）分解，相应地分解，使得'''''',AxbAxb='''AAA⎡⎤=⎢⎥⎣⎦'''bbb⎡⎤=⎢⎥⎣⎦20BeijingJiaotongUniversity4）是优化问题（2）的最优解，那么是Kuhn-Tucker点的充要条件是：3）和的行向量线性无关；'证明：必要性因为是Kuhn-Tucker点，必存在和，使得AC*Px*()0TfxP∇=xμ≥0λ'()TTfxAC∇)=(μ+λ21BeijingJiaotongUniversity又因为是规划问题（2）的最优解，故一定是可行解，所以*P*'**()0TfxPAPCPΤΤ∇=μ+λ≥*()0TfxP∇=但是规划问题（2）的最优值不能为正，因此有充分性：设，由规划问题（2）知，对于满足*()0TfxP∇='0,0APCP≥=22BeijingJiaotongUniversity令，于是有，即根据Farkas引理，存在使得的所有必有（注意其最小值已经为零，从而对于任意的一个可行解必有其值大于最小值）条件可改写成P()0TfxP∇≥P'0AP≥0CP−≥μ≥001λ≥02λ≥'()TTTfxACC12∇)=(μ+λ−λ12λ=λ−λ'()TTfxAC∇)=(μ+λx是Kuhn-Tucker点。,0CP≥CP=023BeijingJiaotongUniversity步1：选定容许点作为初始点，置已知：目标函数及梯度函数，不等式约束中矩阵A和向量b，等式约束中的矩阵C和向量d，终止精度为。(fx)(Zoutendijk法fx∇)ε0xk=0步2：把分解为和，相应地把分解为A'kAkA'kbbkb''kkkAxb=kkkAxbkbτ设的维数为；和，使得24BeijingJiaotongUniversity设其最优解为；'min()0..0111,2,...,TkpkifxPAPstCPpin∇⎧≥⎪=⎨⎪−≤≤=⎩kP步3：求解线性规划问题：步4：若，则就是所求的最优点，停。否则转步5；|()|TkkfxP∇εkx25BeijingJiaotongUniversity设其最优解为；计算，置，转步2。步7：计算，置，转步2，否则转步7；步6：若，则做直线搜索0v≥1(,)kkk步5：置；,kkkkkuAxbvAP=−=xlsxP+=1kk=+1min|0iiiiutvvτ≤≤⎧⎫=−⎨⎬⎩⎭min()..0kktfxtPsttt+≤≤kt1kkkkxxtP+=+1kk=+求解26BeijingJiaotongUniversity1.2非线性约束情形min()..()0,1,2,...,ifxstsxim≥=()0TfxP∇{}()0|()0,1,2,...,TjjsxPjJjsxjm∇∈===可行：下降：下降可行方向的确定：(4)27BeijingJiaotongUniversity设其最优解为；最优值为。即在（）限制下，使作规划问题min()..()11,1,2,...,TTjiyfxPystsxPyjJPin⎧∇≤⎪−∇≤∈⎨⎪−≤≤=⎩11iP−≤≤1,2,...,in=()TfxP∇()TjsxP−∇jJ∈**Py⎡⎤⎢⎥⎣⎦*y（5）的最大值(用y表示)取极小！，28BeijingJiaotongUniversity当时，就是点处的一个可行下降方向！*0y*Px问题：在用迭代方法求解规划问题（5）时，可能使算法失效！Topkis和Veinott(1967年)作如下改进：在点处的可行下降方向由下述规划问题（线性）来确定。x[]12,,...,TnPPPP=min()0..()(),1,2,...,11,1,2,...,TTiijyfxPystsxPysximPjn⎧∇−≤⎪−∇−≤=⎨⎪−≤≤=⎩(6)29BeijingJiaotongUniversity是处的一个可行下降方向。设为（6）的最优解，则当时，**Py因为，由规划问题（6）知⎡⎤⎢⎥⎣⎦*0y*Px*0y**()0TfxPy∇≤*PiJ∈***()()0,TiisxPysxy∇≥−−=−故可行。因为，对有故下降。30BeijingJiaotongUniversity由此定出最优解，从而得到新迭代点为确定新点，从出发沿方向作受约束的直线搜索，。xx*直线搜索：即最优步长的确定：P{}*max|()0,1,2,...,jttsxtPjm=+≥=*min()..0tfxtPsttt+≤≤*t**xxtP=+同时求解没有线性情况下的显式公式。31BeijingJiaotongUniversity终止准则*0y=具体方法略。32BeijingJiaotongUniversityFrank-Wolfe方法Frank和Wolfe于1956年提出求解线性约束问题的一种凸组合算法，通常称为F-W算法，是属于可行方向法的一种。问题的提法：是连续可微函数min()..0fxAxbstx=⎧⎨≥⎩mnA×()RankAm=1mb×()fx33BeijingJiaotongUniversity基本思想：在每次迭代中，将目标函数线性化，通过解线性规划来求得下降可行方向，进而沿此方向在可行域内作一维搜索，以得到新的迭代点。()fx目标函数：设已知可行点，将在处用一阶Taylor公式展开kx()fxkx()()()()()()()()[()()]kkTkkkTkTkkTkkTkfxfxfxxxfxfxxfxxfxxfxfxx≅+∇−=+∇−∇=∇+−∇34BeijingJiaotongUniversity原问题min()..0fxAxbstx=⎧⎨≥⎩min()[()()]..0kTkkTkfxxfxfxxAxbstx∇+−∇=⎧⎨≥⎩min()..0kTfxxAxbstx∇=⎧⎨≥⎩因为是常数！()()kkTfxfxx−∇35BeijingJiaotongUniversity求解此线性规划：min()..0kTfxxAxbstx∇=⎧⎨≥⎩设其存在有限最优解。ky可在某个极点处达到。此线性