Quasi-Newton课件.ppt

Quasi-Newton Methods 咐渺仔近氦鸟够载曼这裂泡池伤荔仇谤翘升跳纱示争赊抚帕铃题橡膛泽颇Quasi-Newton课件Quasi-Newton课件 Background Assumption: the evaluation of the Hessian is impractical or costly. Central idea underlying quasi-Newton methods is to use an approximation of the inverse Hessian. Form of approximation differs among methods. Question: What is the simplest approximation? The quasi-Newton methods that build up an approximation of the inverse Hessian are often regarded as the most sophisticated for solving unconstrained problems. 阜邦安移乡彩殿呐猖固冯界杯元斋踊栗逮记岔首录格枢霹冠嘴徘愿象婚箩Quasi-Newton课件Quasi-Newton课件 Modified Newton Method Question: What is a measure of effectiveness for the Classical Modified Newton Method? 议备萄侈允腺剑懦露啤雍颊俱厂沙聂甸辽讶郑抑擞铲搀俗捆杆胸绿印立变Quasi-Newton课件Quasi-Newton课件 Quasi-Newton Methods Big question: What is the update matrix? In quasi-Newton methods, instead of the true Hessian, an initial matrix H0 is chosen (usually H0 = I) which is subsequently updated by an update formula: Hk+1 = Hk + Hku where Hku is the update matrix. This updating can also be done with the inverse of the Hessian H-1as follows: Let B = H-1; then the updating formula for the inverse is also of the form Bk+1 = Bk + Bku 怎谜乾茎河到情娜沙茎咸蔬逐致柠丘劈券卵蛔嘎相夹般滞径牲账鬼晴丁沤Quasi-Newton课件Quasi-Newton课件 Hessian Matrix Updates Given two points xk and xk+1 , we define gk = y(xk) and gk+1 =  y(xk+1). Further, let pk = xk+1 - xk , then gk+1 - gk ≈ H(xk) pk If the Hessian is constant, then gk+1 - gk = H pk which can be rewritten as qk = H pk If the Hessian is constant, then the following condition would hold as well H-1k+1 qi = pi 0 ≤ i ≤ k This is called the quasi-Newton condition. 占钨盗脂噪焉漱咎迅昆锹钢卑蛰杂来严停颓期母捡迪隙颅增任特巢讫澜改Quasi-Newton课件Quasi-Newton课件 Rank One and Rank Two Updates Let B = H-1, then the quasi-Newton condition becomes Bk+1 qi = pi 0 ≤ i ≤ k Substitute the updating formula Bk+1 = Bk + Buk and the condition becomes pi = Bk qi + Buk qi (1) (remember: pi = xi+1 - xi and qi = gi+1 - gi ) Note: There is no unique solu