6.252 NONLINEAR PROGRAMMING LECTURE 4 …

NONLINEAR PROGRAMMINGLECTURE 4 convergence ANALYSIS OF GRADIENT METHODSLECTURE OUTLINE Gradient Methods - Choice of Stepsize Gradient Methods - convergence IssuesCHOICES OF STEPSIZE I Minimization Rule: kis such thatf(xk+ kdk) = min 0f(xk+ dk). Limited Minimization Rule: Min over [0,s] Armijo rule: f(xk)'dk f(xk)'dk0 Set of AcceptableStepsizes s sUnsuccessful StepsizeTrials 2sStepsize k = f(xk + dk) - f(xk) Start withsand continue with s, 2s, .., until msfallswithin the set of withf(xk) f(xk+ dk) f(xk) OF STEPSIZE II Constant stepsize: kis such that k=s:a constant Diminishing stepsize: k 0but satisfies the infinite travel condition k=0 k= GRADIENT METHODS WITH ERRORSxk+1=xk k( f(xk)+ek)whereekis an uncontrollable error vector Several special cases: eksmall relative to the gradient; , for allk, ek < f(xk) f(xk)ekgkIllustration of the descentproperty of the directiongk= f(xk)+ek. {ek}is bounded, , for allk, ek ,where is some scalar.

LECTURE 4 CONVERGENCE ANALYSIS OF GRADIENT METHODS LECTURE OUTLINE ... The idea of the convergence proof for a constant stepsize. Given xk and the descent direction dk, the cost differ-ence f(xk + αdk) − f(xk) is majorized by α∇f(xk) dk + 1 2

Loading..

Tags:

  Lecture, Programming, Convergence, Nonlinear, Nonlinear programming lecture 4, Lecture 4 convergence

Information

Related search queries