数据库文化基础 (27).pdf

Numerical Optimization Algorithms15thweek/Optimization(IV)Understand the basic idea of numerical optimization algorithmObjectives of This WeekList the step-by-step procedure of some basic numerical optimization algorithms including gradient descent and Newtons algorithmsUnderstand why the nonlinear programming models are difficult to solveIntroduction by Example Single-variable case3local minimum global minimum =()Introduction by Example Observations Initial solution Sign of derivative(direction of ascent/descent from x)Step size(learning rate)4 Gradient descent algorithm:single-variable case Given a differentiable function:,a step size,and a stoppingthreshold ,the following algorithm provides an estimate of theminimum(or maximum)of the functionStep 2Gradient Descent Algorithm 5+1=()Step 0Choose a random point 0 and let =0Step 1ComputeIf the termination condition(e.g.,()is satisfied,stopOtherwise,let +1 and go to Step 1Gradient Descent Algorithm Gradient descent algorithm The step size influences the computational performance,i.e.,rate of convergence or number of iterations If the step size is too small,the algorithm can be slow slow progress If the step size is too large,the algorithm can be overshoot the minimum(zigzag)and it may fail to converge repeated overshooting of the minimum6Gradient Descent Algorithm Gradient descent algorithm Examples of choosing the step size(learning rate)Choose a small constant Start with a constant step size and keep track of the errors;aftersome specified number of iterations without an improvement,decrease the step size Take the decaying step size(e.g.,)Choose7=argmin0 ()Gradient Descent Algorithm Gradient descent algorithm:multi-variable case Given a differentiable function:,a step size,and a stoppingthreshold ,the following algorithm provides an estimate of theminimum(or maximum)of the function8Step 2+1=()Step 0Choose a random point 0 and let =0Step 1ComputeIf the termination condition(e.g.,2)is satisfied,stopOtherwise,let +1 and go to Step 1Newtons Algorithm Newtons algorithm:multi-variable case Searchthedirectiontowardtheminimumofthequadraticapproximation of a function at each point Iteratively minimize the(local)quadratic approximation of a function ateach point Remind that the quadratic approximation of at Assuming 2()is PD,the minimum of the function is the solution of +2 =09 =+12 2 =2 1 Newtons Algorithm Newtons algorithm:multi-variable case Given a differentiable function:,a step size,and a stoppingthreshold ,the following algorithm provides an estimate of theminimum(or maximum)of the function10Step 2Step 0Choose a random point 0 and let =0Step 1Let=2 1 and computeIf the termination condition(e.g.,2)is satisfied,stopOtherwise,let +1 and go to Step 1+1=+Factors that influence the computational performance:initial solution,step size(learning rate),gradient(or Hessian)SummaryGradient descent algorithm:use the fact that is thedirection of steepest descent from each pointNewtonsalgorithm:iterativelyminimizethequadraticapproximation of a function at each pointIntroduction to Mathematical Programming(Operations Research:Volume One),W.L.Winston&M.Venkataramanan,Thomson,4th editionReferencesNonlinear Programming:Theory and Algorithms,M.S.Bazaraa,H.D.Sherali&C.M.Shetty,Wiley-BlackwellNumerical Optimization,J.Nocedal&S.J.Wright,Springer