Numerical Optimization!Robert Stengel! Robotics and Intelligent Systems MAE 345, Princeton University, 2013"• Gradient search"• Gradient-free search"– Grid-based search"– Random search""– Downhill simplex method"• Monte Carlo evaluation"• Simulated annealing"• Genetic algorithms"• Particle swarm optimization"Copyright 2013 by Robert Stengel. All rights reserved. For educational use only.!http://www.princeton.edu/~stengel/MAE345.html!Numerical Optimization"• What if J is too complicated to find an analytical solution for the minimum?"• … or J has multiple minima?"• Use numerical optimization to find local and/or global solutions"Two Approaches to Numerical Minimization"Evaluate cost, J , and search for smallest value"Evaluate gradient , ∂J/∂u, and search for zero"Jo= J uo( )= starting guessJ1= Jo+ ΔJ1uo+ Δu1( )such that J1< JoJ2= J1+ ΔJ2u1+ Δu2( )such that J2< J1Stop when difference between Jn and Jn–1 is negligible"∂J∂u⎛⎝⎜⎞⎠⎟o=∂J∂uu=u0= starting guess∂J∂u⎛⎝⎜⎞⎠⎟n=∂J∂u⎛⎝⎜⎞⎠⎟n−1+ Δ∂J∂u⎛⎝⎜⎞⎠⎟n=∂J∂uu=unsuch that∂J∂un<∂J∂un−1… until gradient is close enough to zero"Cost Function and Gradient Searches"• Evaluate J and search for smallest value"Jo= J uo( )= starting guessJ1= Jo+ ΔJ1uo+ Δu1( )such that J1< JoJ2= J1+ ΔJ2u1+ Δu2( )such that J2< J1∂J∂u⎛⎝⎜⎞⎠⎟o=∂J∂uu=u0= starting guess∂J∂u⎛⎝⎜⎞⎠⎟n=∂J∂u⎛⎝⎜⎞⎠⎟n−1+ Δ∂J∂u⎛⎝⎜⎞⎠⎟n=∂J∂uu=unsuch that∂J∂un<∂J∂un−1• J is a scalar"• J provides no search direction"• ∂J/∂u is a vector"• ∂J/∂u indicates feasible search direction"… until gradient is close enough to zero"Stop when difference between Jn and Jn–1 is negligible"• Evaluate ∂J/∂u and search for zero"Gradient/Hessian Search to Minimize a Quadratic Function"J =12u − u *( )TR u − u *( ), R > 0=12uTRu − uTRu * −u *TRu + u *TRu *( )∂J∂u= u − u *( )TR = 0 when u = u *∂2J∂u2= R = symmetric constantCost function, gradient, and Hessian matrix"Guess a starting value of u, uo"∂J∂uu=uo= uo− u *( )TR = uo− u *( )T∂2J∂u2u=uouo− u *( )T=∂J∂uu=uoR−1row( )u* = uo− R−1∂J∂uu=uo⎡⎣⎢⎢⎤⎦⎥⎥Tcolumn( )Optimal Value Found in a Single Step"• For a quadratic cost function"• Gradient establishes general search direction"• Hessian fine-tunes direction and tells exactly how far to go"u* = uo− R−1∂J∂uu=uo⎡⎣⎢⎢⎤⎦⎥⎥T= uo−∂2J∂u2u=uo⎡⎣⎢⎢⎤⎦⎥⎥−1∂J∂uu=uo⎡⎣⎢⎢⎤⎦⎥⎥TNumerical Example"J =12u1u2⎛⎝⎜⎜⎞⎠⎟⎟−13⎛⎝⎜⎞⎠⎟⎡⎣⎢⎢⎤⎦⎥⎥T1 22 9⎡⎣⎢⎤⎦⎥u1u2⎛⎝⎜⎜⎞⎠⎟⎟−13⎛⎝⎜⎞⎠⎟⎡⎣⎢⎢⎤⎦⎥⎥⎧⎨⎪⎩⎪⎫⎬⎪⎭⎪∂J∂u⎛⎝⎜⎞⎠⎟T=u1u2⎛⎝⎜⎜⎞⎠⎟⎟−13⎛⎝⎜⎞⎠⎟⎡⎣⎢⎢⎤⎦⎥⎥T1 22 9⎡⎣⎢⎤⎦⎥; R =1 22 9⎡⎣⎢⎤⎦⎥• Cost function and derivatives"• First guess at optimal control (details of the actual cost function are unknown)"u1u2⎛⎝⎜⎜⎞⎠⎟⎟0=47⎛⎝⎜⎞⎠⎟• Derivatives at starting point"∂J∂uu = u0=47⎛⎝⎜⎞⎠⎟−13⎛⎝⎜⎞⎠⎟⎡⎣⎢⎢⎤⎦⎥⎥T1 22 9⎡⎣⎢⎤⎦⎥=1142⎛⎝⎜⎞⎠⎟; R =1 22 9⎡⎣⎢⎤⎦⎥• Solution from starting point"u* =u1u2⎛⎝⎜⎜⎞⎠⎟⎟*=47⎛⎝⎜⎞⎠⎟−9 / 5 −2 / 5−2 / 5 1 / 5⎡⎣⎢⎤⎦⎥1142⎛⎝⎜⎞⎠⎟=47⎛⎝⎜⎞⎠⎟−34⎛⎝⎜⎞⎠⎟=13⎛⎝⎜⎞⎠⎟u* = uo− R−1∂J∂uu = uo⎡⎣⎢⎢⎤⎦⎥⎥TNewton-Raphson Iteration"• Many cost functions are not quadratic"• However, the surface is well-approximated by a quadratic in the vicinity of the optimum, u*"Optimal solution requires multiple steps"J u * +Δu( )≈ J u *( )+ ΔJ u *( )+ Δ2J u *( )+ ...ΔJ u *( )= ΔuT∂J∂uu=u*= 0Δ2J u *( )= ΔuT∂2J∂u2u=u*⎡⎣⎢⎤⎦⎥Δu ≥ 0Newton-Raphson Iteration"Newton-Raphson algorithm is an iterative search using both the gradient and the Hessian matrix "uk +1= uk−∂2J∂u2u = uk⎡⎣⎢⎢⎤⎦⎥⎥−1∂J∂uu = uk⎡⎣⎢⎢⎤⎦⎥⎥TDifficulties with Newton-Raphson Iteration"• Good when close to the optimum, but …"• Hessian matrix (i.e., the curvature) may be"– Difficult to estimate, e.g., large effects of small errors"– Locally misleading, e.g., wrong curvature"• Gradient searches focus on local minima"uk +1= uk−∂2J∂u2u = uk⎡⎣⎢⎢⎤⎦⎥⎥−1∂J∂uu = uk⎡⎣⎢⎢⎤⎦⎥⎥TSteepest-Descent Algorithm Multiplies Gradient by a Scalar Constant"uk +1= uk−ε∂J∂uu = uk⎡⎣⎢⎢⎤⎦⎥⎥T• Replace Hessian matrix by a scalar constant"• Gradient is orthogonal to equal-cost contours"Choice of Steepest-Descent Constant"If gain is too small"Convergence is slow"If gain is too large"Convergence oscillates or may fail"Solution: Make gain adaptive"Optimal Steepest-Descent Constant"• Use optimal gain on each iteration"• Find optimal step size by evaluating cost, J, for intermediate solutions (with same dJ/du) "• Adjustment rule (partial) for "– Starting estimate, Jo"– 1st estimate, J1, using ε"– 2nd estimate, J2, using 2ε"– If J2 > J1"• Quadratic fit through 3 points"– Else"• 3rd estimate using 4ε"• etc."Gradient Search Issues"• Need to evaluate gradient (and possibly Hessian matrix)"• Not global: gradient searches focus on local minima"• Convergence may be difficult with noisy or complex cost functions"uk+1= uk−ε∂J∂uu=uk⎡⎣⎢⎢⎤⎦⎥⎥Tuk+1= uk−∂2J∂u2u=uk⎡⎣⎢⎢⎤⎦⎥⎥−1∂J∂uu=uk⎡⎣⎢⎢⎤⎦⎥⎥TSteepest Descent"Newton Raphson"Gradient-Free Search: Grid-Based Search"Jo= J uo( )= starting guessJ1= Jo+ ΔJ1uo+ Δu1( )such that J1< JoJ2= J1+ ΔJ2u1+ Δu2( )such that J2< J1Gradient-Free Search: Random Search"*"Select control parameters using a random number generator"Jo= J uo( )= starting guessJ1= Jo+ ΔJ1uo+ Δu1( )such that J1< JoJ2= J1+ ΔJ2u1+ Δu2( )such that J2< J1Three-Parameter Grid Search"n = 125" n = 1000"• Regular spacing"• Fixed resolution"• Trials grow as mn, where"– n = Number of parameters"– m = Resolution"Three-Parameter Random Field Search"Variable spacing and resolution"Arbitrary number