资源描述:
《Lec13_Gradient_student.pdf》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、18-660:NumericalMethodsforEngineeringDesignandOptimizationXinLiDepartmentofECECarnegieMellonUniversityPittsburgh,PA15213Slide1Overview¢Lecture12:NonlinearEquationSolver{Newton-Raphsonmethod{BinarysearchBinarysearch¢Lecture13:UnconstrainedOptimization{Gradientmethod{NewtonmethodSlide2Unconstraine
2、dOptimization¢Linearregressionwithregularization2Aα=BminAα−B+λ⋅αα21¢Unconstrainedoptimization:minimizingacostfunctionwithoutanyconstraint{GoldensectionsearchNon-derivativemethod{Downhillsimplexmethod{GradientmethodRelyonderivatives(thislecture){NewtonmethodSlide3GradientMethod¢Ifacostfunctioniss
3、mooth,itsderivativeinformationcanbeusedtosearchoptimalsolutionf(x)minf(x)xxSlide4GradientMethod¢Forillustrationpurpose,westartfromaone-dimensionalcaseminf(x)xSlide5GradientMethod¢One-dimensionalcase(continued)()k(k+1)()k()kdf[()k+1][()k]df()kΔx=x−x=−λ⋅&fx≈fx+⋅Δxdxx()kdxx()kSlide6GradientMethod¢O
4、ne-dimensionalcase(continued)Derivativeiszeroatlocalopp(timum(ggradientΔx=−λ⋅dfdx=0methodconverges)f(()x)xSlide7GradientMethod¢Two-dimensionalcaseminf()x,x12x1,x2Slide8GradientMethod¢Two-dimensionalcase(continued)⎡(k)⎤Δx1()k[]()k()k⎢(k)⎥=−λ⋅∇fx1,x2Δx⎣Δ2⎦()k[]()()k+1k+1[]()k()k[]()k()kT⎡Δx1⎤fx1,x
5、2≈fx1,x2+∇fx1,x2⋅⎢()k⎥Δx⎣2⎦f[x(k+1)x(k+1)]f[x(k)x(k)](k)f[x(k)x(k)]Tf[x(k)x(k)]fx1,x2≈fx1,x2−λ⋅∇fx1,x2⋅∇fx1,x22f[x(k+1),x(k+1)]≈f[x(k),x(k)]−λ(k)⋅∇f[x(k),x(k)]λ(k)>01212122Thecostfunctionf(x1,x2))pkeepsdecreasinggifthegradientisnon-zeroSlide9GradientMethod¢N-dimensionalcaseminf()XXSlide10NewtonM
6、ethod¢Gradientmethodreliesonfirst-orderderivativeinformation{Eachiterationissimple,butitconvergestooptimumslowly{IerequirealargenumberofiterationstepsI.e.,requirealargenumberofiterationsteps(k)¢Thestepsizeλcanbeoptimizedbyone-dimensionalsearchforfastconvergence{(k)(k)[(k)]}minfX−λ⋅∇fX()kλ¢Altern
7、ativealgorithm:Newtonmethod{Relyonbothfirstonbothfirst-orderandsecondorderandsecond-orderderivativesorderderivatives{Eachiterationismoreexpensive{Butitconvergestooptimummorequickly,i.e.,requiresasmallernumberofiterationsmall