Introduction to Optimization!Robert Stengel! Robotics and Intelligent Systems, MAE 345, Princeton University, 2013"• Optimization problems and criteria"• Cost functions"• Static optimality conditions"• Examples of static optimization"Copyright 2013 by Robert Stengel. All rights reserved. For educational use only.!http://www.princeton.edu/~stengel/MAE345.html!Typical Optimization Problems"• Minimize the probable error in an estimate of the dynamic state of a system"• Maximize the probability of making a correct decision"• Minimize the time or energy required to achieve an objective"• Minimize the regulation error in a controlled system"• Estimation• ControlOptimization Implies Choice"• Choice of best strategy"• Choice of best design parameters"• Choice of best control history"• Choice of best estimate"• Optimization provided by selection of the best control variable"Criteria for Optimization"• Names for criteria"– Figure of merit"– Performance index"– Utility function"– Value function"– Fitness function"– Cost function, J!• Optimal cost function = J*!• Optimal control = u*"• Different criteria lead to different optimal solutions"• Types of Optimality Criteria"– Absolute"– Regulatory"– Feasible"Minimize Absolute Criteria"Achieve a specific objective, such as minimizing the required time, fuel, or financial cost to perform a task"What is the control variable?"Optimal System Regulation"Cruise Ship, Anyone?"http://www.youtube.com/watch?v=bVUFj35BNKM&list=PLCF1F89084A30FBED"• Find feedback control gains that minimize tracking error, Δx, in presence of random disturbances"Feasible Control Logic"Find feedback control structure that guarantees stability (i.e., that prevents divergence)"Double Inverted Pendulum"http://www.youtube.com/watch?v=8HDDzKxNMEY"Single Inverted Pendulum"http://www.youtube.com/watch?v=mi-tek7HvZs"Desirable Characteristics of a Cost Function"• Scalar"• Clearly defined (preferably unique) maximum or minimum"– Local"– Global"• Preferably positive-definite (i.e., always a positive number)"Static vs. Dynamic Optimization"• Static"– Optimal state, x*, and control, u*, are fixed, i.e., they do not change over time: J* = J(x*, u*)"• Functional minimization (or maximization)"• Parameter optimization"• Dynamic"– Optimal state and control vary over time: J* = J[x*(t), u*(t)]"• Optimal trajectory"• Optimal feedback strategy"• Optimized cost function, J*, is a scalar, real number in both cases"Deterministic vs. Stochastic Optimization"• Deterministic"– System model, parameters, initial conditions, and disturbances are known without error"– Optimal control operates on the system with certainty "• J* = J(x*, u*)"• Stochastic"– Uncertainty in system model, parameters, initial conditions, disturbances, and resulting cost function"– Optimal control minimizes the expected value of the cost: "• Optimal cost = E{J[x*, u*]}"• Cost function is a scalar, real number in both cases"Cost Function with a Single Control Parameter"• Tradeoff between two types of cost: Minimum-cost cruising speed"– Fuel cost proportional to velocity-squared"– Cost of time inversely proportional to velocity"• Control parameter: Velocity"Tradeoff Between Time- and Fuel-Based Costs"• Nominal Tradeoff"• Fuel Cost Doubled"• Time Cost Doubled"Cost Functions with Two Control Parameters"• Minimum"• Maximum"3-D plot of equal-cost contours (iso-contours)"2-D plot of equal-cost contours (iso-contours)"Real-World Topography"Local vs. global maxima/minima"Robustness of estimates"Cost Functions with Equality Constraints"Must stay on the trail"Equality constraint may allow control dimension to be reduced"c u1,u2( )= 0 → u2= fcn u1( )thenJ u1,u2( )= J u1, fcn u1( )⎡⎣⎤⎦= J ' u1( )Cost Functions with Inequality Constraints"Must stay to the left of the trail"Must stay to the right of the trail"Necessary Condition for Static Optimality"Single control"dJduu =u*= 0i.e., the slope is zero at the optimum point"Example:"J = u − 4( )2dJdu= 2 u − 4( )= 0 when u* = 4Necessary Condition for Static Optimality"Multiple controls"i.e., all slopes are concurrently zero at the optimum point"Example:"∂J∂uu= u*=∂J∂u1∂J∂u2...∂J∂um⎡⎣⎢⎢⎤⎦⎥⎥u= u*= 0J = u1− 4( )2+ u2− 8( )2dJdu1= 2 u1− 4( )= 0 when u1* = 4dJdu2= 2 u2− 8( )= 0 when u2* = 8∂J∂uu=u*=∂J∂u1∂J∂u2⎡⎣⎢⎢⎤⎦⎥⎥u=u*=48⎡⎣⎢⎤⎦⎥= 0 0⎡⎣⎤⎦Gradient!… But the Slope can be Zero for More than One Reason"Minimum" Maximum"Either"Inflection Point"Sufficient Condition for Static Optimum"• Single control"d2Jdu2u = u *> 0i.e., curvature is positive at optimum"Example:"J = u − 4( )2dJdu= 2 u − 4( )d2Jdu2= 2 > 0Minimum"Satisfy necessary condition plus"d2Jdu2u = u *< 0i.e., curvature is negative at optimum "Example:"J = − u − 4( )2dJdu= −2 u − 4( )d2Jdu2= −2 < 0Maximum"Satisfy necessary condition plus"Sufficient Condition for Static Minimum"∂2J∂u2u=u*=∂2J∂u12∂2J∂u1∂u2...∂2J∂u1∂um∂2J∂u2∂u1∂2J∂u22...∂2J∂u2∂um... ... ... ...∂2J∂um∂u1∂2J∂u2∂um...∂2J∂um2⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥u=u*> 0• Satisfy necessary condition"– plus"Hessian matrix!• … what does it mean for a matrix to be greater than zero ?"∂J∂uu=u*=∂J∂u1∂J∂u2...∂J∂um⎡⎣⎢⎢⎤⎦⎥⎥u=u*= 0Multiple controls" ∂2J∂u2 Q > 0 if Its Quadratic Form, xTQx, is Greater than Zero xTQx  Quadratic formQ :Defining matrix of the quadratic form1 × n( )n × n( )n × 1( )⎡⎣⎤⎦= 1 × 1( )⎡⎣⎤⎦• dim(Q) = n x n"• Q is symmetric"• xTQx is a scalar"Q =q11q12q13q21q22q23q31q32q33⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥q11> 0,q11q12q21q22> 0,q11q12q13q21q22q23q31q32q33> 0• Q is positive-definite if"– All leading principal minor determinants are positive"– All eigenvalues are real and positive"• 3 x 3 example"det sI − Q( )= s −λ1( )s −λ2( )s −λ3( )λ1,λ2,λ3≥ 0Quadratic Form of Q is Positive* if Q is Positive Definite"* except at x = 0!ΔJ u *( )= ΔuT∂J∂uu=u*= 0Δ2J u *( )=12ΔuT∂2J∂u2u=u*⎡⎣⎢⎤⎦⎥Δu ≥ 0Minimized Cost Function,