运筹学与最优化方法第4章.ppt

、收敛性概念:考虑(fs)设迭代算法产生点列{x(k)}:设x*∈*∈{x(k)}或x(k)≠x*,k,满足时,称算法收敛到最优解x*。,实用中建立下列收敛性概念::定义解集S*={x|x具有某种性质}例:S*={x|x---}S*={x|x---}S*={x|f(x)=0}S*={x|f(x)≤β}(β为给定的实数,称为阈值)、收敛性概念:考虑(fs)(续)▲收敛性:设解集S*≠,{x(k)}为算法产生的点列。下列情况之一成立时,称算法收敛:1°x(k)∈S*;2°x(k)S*,k,{X(k)}任意极限点∈S*。▲全局收敛:对任意初始点x(1),算法均收敛。局部收敛:当x(1)充分接近解x*时,算法才收敛。、收敛速度设算法产生点列{x(k)},收敛到解x*,且x(k)≠x*,k,:当k充分大时成立。::﹥0,、收敛速度(续)定理:设算法点列{x(k)}超线性收敛于x*,且x(k)≠x*,k,那么证明只需注意|||x(k+1)–x*||-||x(k)–x*|||≤||x(k+1)–x(k)||≤||x(k+1)–x*||+||x(k)–x*||,除以||x(k)–x*||并令k→∞,利用超线性收敛定义可得结果。、二次终结性▲一个算法用于解正定二次函数的无约束极小时,有限步迭代可达最优解,则称该算法具有二次终结性。▲二次终结性=共轭方向+精确一维搜索。▲共轭方向·定义:设An×n对称正定,d(1),d(2)∈Rn,d(1)≠0,d(2)≠0,满足d(1)TAd(2)=0,称d(1),d(2)关于矩阵A共轭。·共轭向量组:d(1),d(2),…,d(m)∈Rn均非零,满足d(i)TAd(j)=0,(i≠j).、二次终结性(续)·当A=I(单位矩阵)时,d(1)TAd(2)=d(1)Td(2)=0,即正交关系。·当d(1),d(2),…,d(m)关于正定矩阵A两两共轭时,d(1),d(2),…,d(m)线性无关。proof:设d=1d(1)+2d(2)+…+md(m)=0,j=1,2,…,m,d(j)TAd=jd(j)TAd(j)=0∵d(j)TAd(j)>0,故j=0,即线性无关。超线性收敛和二次终结性常用来讨论算法的优点。、下降算法模型考虑(fs)常用一种线性搜索的方式来求解:迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。△下降方向:设∈S,d∈Rn,d≠0,若存在,使,称d为在点的下降方向。minf(x)∈、下降算法模型(续)△可行方向:设∈S,d∈Rn,d≠0,若存在,使,称d为点的可行方向。 同时满足上述两个性质的方向称下降可行方向。丈曲西忌洋犁南辨耐其致慰朔定畴肖渍钞呵宇燎荧地***链例即白矢阂胃渐运筹学与最优化方法第4章运筹学与最优化方法第4章