1 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsPost-Optimality AnalysisLecture 16Olivier de WeckKaren WillcoxMultidisciplinary System Design Optimization (MSDO)2 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsToday’s Topics• Optimality Conditions & Termination– Gradient-based techniques– Heuristic techniques• Objective Function Behavior• Scaling3 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsStandard Problem Definition 12min ( )s.t. ( ) 0 1,.., ( ) 0 1,.., 1,..,jkui i iJg j mh k mx x x i nxxxFor now, we consider a single objective function, J(x).There are n design variables, and a total of mconstraints (m=m1+m2).The bounds are known as side constraints.4 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsKarush-Kuhn-Tucker ConditionsIf x* is optimum, these conditions are satisfied:1. x* is feasible2. jgj(x*) = 0, j=1,..,m1and j03. The KKT conditions are necessary and sufficient if the design space is convex.sign in edunrestrict00)()()(12111*1**kmjmkkkmmjjjxhxgxJ5 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsKarush-Kuhn-Tucker Conditions: InterpretationCondition 1: the optimal design satisfies the constraintsCondition 2: if a constraint is not precisely satisfied, then the corresponding Lagrange multiplier is zero– the jthLagrange multiplier represents the sensitivity of the objective function to the jthconstraint– can be thought of as representing the “tightness” of the constraint– if jis large, then constraint j is important for this solutionCondition 3: the gradient of the Lagrangian vanishes at the optimum6 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsOptimization for Engineering Problems• Most engineering problems have a complicated design space, usually with several local optima• Gradient-based methods can have trouble converging to the global optimum, and sometimes fail to find even a local optimum• Heuristic techniques offer no guarantee of optimality, neither global nor local• Your post-optimality analysis should address the question:– How confident are you that you have found the global optimum?– Do you actually care?7 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsOptimization for Engineering Problems• Usually cannot guarantee that absolute optimum is found– local optima– numerical ill-conditioning gradient-based techniques should be started from several initial solutions best solution from a heuristic technique should be checked with KKT conditions or used as an initial condition for a gradient-based algorithm• Can determine mathematically if have relative minimum but KKT conditions are only sufficient if the problem is convex• It is very important to interrogate the “optimum” solution8 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsTermination Criteria: Gradient-BasedGradient-based algorithm is terminated when ...an acceptable solution is foundORalgorithm terminates unsuccessfullyNeed to decide:• when an acceptable solution is found• when to stop the algorithm with no acceptable solution– when progress is unreasonably slow– when a specified amount of resources have been used (time, number of iterations, etc.)– when an acceptable solution does not exist– when the iterative process is cycling9 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsTermination Criteria: Gradient-Based• Is xkan acceptable solution? does xkalmost satisfy the conditions for optimality? has the sequence { xk } converged?• Often the first question is difficult to test• The tests are often approximate• Often rely on the answer to the second question• But convergence to a non-optimal solution or extended lack of progress can look the same as convergence to the correct solution!• No one set of termination criteria is suitable for all optimization problems and all methods10 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsTermination Criteria: Gradient-BasedHas the sequence { xk } converged?*kJJ*kxxIdeally: or1kkJJ1kkxxIn practice: orAlso should check constraint satisfaction:kg11 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsTermination Criteria: HeuristicsTypical ResultsgenerationConverged toofast (mutation ratetoo small?)- GEN = max(GEN): maximum # of generations reached- Stagnation in Fitness, no progress made on objective- Dominant Schema have emergedGA Terminationglobaloptimum(unknown)12 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsTermination Criteria: Heuristics• Simulated Annealing - cooling schedule: T(k)=f(k, To)To0Search stops whenT(k)< where >0,but small• Tabu search termination• Usually after a predefined number of iterations• Best solution found is reported• No guarantee of optimalitysearch broadlysearch locally13 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsPost-Optimality Analysis• Already talked about sensitivity analysis (Lecture 9)– How does optimal solution change as a parameter is varied?– How does optimal solution change as a design variable value is varied?– How does optimal solution change as constraints are varied?• Also would like to understand key drivers in optimal design• We also saw in Lecture 9 that the values of the Lagrange multipliers at the optimal solution give information on how modifying the constraints affects