麻省理工学院：《Multidisciplinary System》Lecture 14 Lagrange Multipliers

MIest 16888 Today's Topics Multidisciplinary System Optimality Conditions Termination Design Optimization(MSDO) Gradient-based techniques Post-Optimality Analysis Heuristic techniques Lecture 14 · Lagrange multipliers 17 March 2004 Objective Function Beh Scaling Olivier de Weck Karen willcox e Massachusetts Institute of Technology -Prof de Weck and Prof Willcox G Massachusetts Insttute of Technology .Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics Engineering Systems Division and Dept of Aeronautics and Astronautics MIest Standard Problem Definition Kuhn-Tucker Conditions min J(x) If x is optimum, these conditions are satisfied st.g(x)≤0j=1…m 1.x is feasib h2(x)=0k=1m2 239(x)=0,=1…m1and320 V(x)+∑4g(x)+∑mnVh(x)=0 X≤X≤X=1…,n A:≥0 For now, we consider a single objective function, J(/x) Am.k unrestricted in sign There are n design variables, and a total of m constraints(m=m,+m2) The Kuhn-tucker conditions are necessary and The bounds are known as side constraints sufficient if the design space is convex e Massachusetts Institute of Technology- Prof de Weck and Prof Willcox etts Institute of Technology .Prof de Weck and Prof Willcox Engineening Systems Division and Dept of Aeronautics and Astronautics ngineering Systems Divsion and Dept of Aeronautics and Astronautics

1 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Post-Optimality Analysis Lecture 14 17 March 2004 Olivier de Weck Karen Willcox Multidisciplinary System Multidisciplinary System Design Optimization (MSDO) Design Optimization (MSDO) 2 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Today’s Topics Today’s Topics • Optimality Conditions & Termination – Gradient-based techniques – Heuristic techniques • Lagrange Multipliers • Objective Function Behavior • Scaling 3 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Standard Problem Definition Standard Problem Definition 1 2 min ( ) s.t. ( ) 0 1,.., ( ) 0 1,.., 1,.., j k u i ii J g jm h km x x xi n ≤ = = = ≤≤ = x x x A For now, we consider a single objective function, J(x). There are n design variables, and a total of m constraints (m=m1+m2). The bounds are known as side constraints. 4 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Kuhn-Tucker Conditions Tucker Conditions If x* is optimum, these conditions are satisfied: 1. x* is feasible 2. λj gj(x*) = 0, j=1,..,m1 and λj ≥ 0 3. The Kuhn-Tucker conditions are necessary and sufficient if the design space is convex. unrestrictedin sign 0 ( ) ( ) ( ) 0 1 2 1 1 1 * 1 * * m k j m k m k k m j j j J x g x h x + = + = ≥ ∇ + ∑ ∇ +∑ ∇ = λ λ λ λ

MIest Kuhn-Tucker Conditions 16888 Interpretation Mlesd Optimization for Engineering 50. 3 Problems Condition 1: the optimal design satisfies the constraints Most engineering problems have a complicated design space, usually with several local optima Condition 2: if a constraint is not precisely satisfied, then Gradient-based methods can have trouble converging to the the corresponding Lagrange multiplier is zero orrect solution the h Lagrange multiplier represents the sensitivity of the Heuristic techniques offer absolutely no guarantee of objective function to the h constraint optimality, neither global nor local can be thought of as representing the tightness"of the Your post-optimality analysis should address the question constraint How confident are you that you have found the global if i, is large, then constraint is important for this solution optimum? Condition 3: the gradient of the lagrangian vanishes at Do you actually care? the optimum @ Massachusetts Institute of Technology -Prof de Weck and Prof Willcox G Massachusetts Insttute of Technology .Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics Engineering Systems Division and Dept of Aeronautics and Astronautics Mlesd Optimization for Engineering 650 3 MleSaTermination Criteria: Gradient-Based 50. 3 Problems Gradient-based algorithm is terminated when Usually cannot guarantee that absolute optimum is found an acceptable solution is found local optima numerical ill-conditioning a gradient-based techniques should be started from Need to decide. several initial solutions when an acceptable solution is found o best solution from a heuristic technique should be checked with kt conditions or used as an initial when to stop the algorithm with no acceptable condition for a gradient-based algorithm solution Can determine mathematically if have relative minimum but when progress is unreasonably slow Kuhn- Tucker conditions are only sufficient if the problem is when a specified amount of resources have been used(time number of iterations, etc. It is very important to interrogate the"optimum" solution when an acceptable solution does not exist a Massachusetts Institute of Technology - Prof de Weck and Prof Willcox when the iterative process is cycling @Massachusetts Insttute of Technology. Prof de Weck and Prof Willcox Engineening Systems Division and Dept of Aeronautics and Astronautics Aeronautics and astronautics

5 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Kuhn-Tucker Conditions: Tucker Conditions: Interpretation Interpretation Condition 1: the optimal design satisfies the constraints Condition 2: if a constraint is not precisely satisfied, then the corresponding Lagrange multiplier is zero – the jth Lagrange multiplier represents the sensitivity of the objective function to the jth constraint – can be thought of as representing the “tightness” of the constraint – if λj is large, then constraint j is important for this solution Condition 3: the gradient of the Lagrangian vanishes at the optimum 6 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Optimization for Engineering Optimization for Engineering Problems Problems • Most engineering problems have a complicated design space, usually with several local optima • Gradient-based methods can have trouble converging to the correct solution • Heuristic techniques offer absolutely 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. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Optimization for Engineering Optimization for Engineering Problems 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 KT conditions or used as an initial condition for a gradient-based algorithm • Can determine mathematically if have relative minimum but Kuhn-Tucker conditions are only sufficient if the problem is convex • It is very important to interrogate the “optimum” solution 8 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Termination Criteria: Gradient Termination Criteria: Gradient-Based Gradient-based algorithm is terminated when ... an acceptable solution is found OR algorithm terminates unsuccessfully Need 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 cycling

MIesa Termination Criteria: Gradient-Based 50 Mlesd Termination Criteria: Gradient-Based 5.7 Is x* an acceptable solution? Has the sequence x) converged? > does x almost satisfy the conditions for optimality? >has the sequence( x]converged? J|≤Eor ≤E Often the first question is difficult to test The tests are often approximate Often rely on the answer to the second question in practice: u*+136 or xx*1L6 lack of vergence to a non-optimal solution or extended lack of progress can look the same as convergence to the correct solution Also should check constraint satisfaction: 9^‖≤E No one set of termination criteria is suitable for all optimization problems and all methods @ Massachusetts Institute of Technology -Prof de Weck and Prof Willcox e Massachusetts Insttute of Technology. Prof de Weck and Prof. willcox Engineering Systems Division and Dept of Aeronautics and Astronautics Engineering Systems Division and Dept of Aeronautics and Astronautics Mlesd Termination Criteria: Heuristics 50. Mlsd Termination Criteria: Heuristics 5031 GA Termination ptimum (unknown) Results fast(mutation rate too small?) generation GEN= max(GEN): maximum of generations reached Stagnation in Fitness, no progress made on objective Dominant schema hay e Massachusetts Institute of Technology -Prof de Weck and Prof Willcox etts Institute of Technology . Prof de Weck and Prof. Willcox Engineening Systems Division and Dept of Aeronautics and Astronautics ystems Divsion and Dept of Aeronautics and Astronautics

9 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Termination Criteria: Gradient Termination Criteria: Gradient-Based • Is xk an acceptable solution? ¾does xk almost 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 methods 10 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Termination Criteria: Gradient Termination Criteria: Gradient-Based Has the sequence { xk } converged? * k J J − ≤ ε * k Ideally: or x x − ≤ ε k k 1 J J ε + − ≤ k k 1 ε + In practice: or x x − ≤ Also should check constraint satisfaction: k g ≤ ε 11 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Termination Criteria: Heuristics Termination Criteria: Heuristics Typical Results generation Converged too fast (mutation rate too small?) - GEN = max(GEN): maximum # of generations reached - Stagnation in Fitness, no progress made on objective - Dominant Schema have emerged GA Termination global optimum (unknown) 12 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Termination Criteria: Heuristics Termination Criteria: Heuristics

MIed Termination Criteria: Heuristics:| MIest Termination in iSIGHT幽甥 Simulated Annealing-cooling schedule: T(k=f(k, To) Be careful with iSIGHT: the last solution is not necessarily the best one Search stops when Need to look back over all the solutions in the monitor to T(k)≤,wheeε>0, find the"optimum but smal Feasibility paramete 3= infeasible search broadly search locally Tabu search termination 8= feasible and equal to the best design found so fal Usually after a predefined number of iterations 9=feasible and the best design found so far Best solution found is reported No guarantee of optimality The "optimum" will be the last solution with feasibility=9 Experimentation gives confidence e Massachusetts Institute of Technology- Prof de Weck and Prof Willcox e Massachusetts Insttute of Technology. Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics Engineering Systems Division and Dept of Aeronautics and Astronautics Mlesd Post-Optimality Analysis E07 Mlesd Lagrange Multipliers 507 The values of the Lagrange multipliers at the optimal Already talked about sensitivity analysis( Lecture 9) solution, i, give information on the constraints How does optimal solution change as a parameter is varied? If y is zero, then constraint j is inactive How does optimal solution change as a design If a is positive then constraint is active variable value is varied? The value of the /h Lagrange multiplier tells you by How does optimal solution change as constraints how much the objective function will change if the are varied? constraint is varied by a small amount Also would like to understand key drivers in optimal 0(x)=-4g(x) i is a vector containing the m LMs g is a vector containing all m constraints(inequality+equality) a Massachusetts Institute of Technology -Prof de Weck and Prof Willcox e Massachusetts Insttute of Technology. Prof de Weck and Prof Willcox Engineening Systems Division and Dept of Aeronautics and Astronautics Engineering Systems DiMsion and Dept of Aeronautics and Astronautics

13 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Termination Criteria: Heuristics Termination Criteria: Heuristics • Simulated Annealing - cooling schedule: T(k)=f(k, To) To 0 Search stops when T(k)<ε , where ε>0, but small • Tabu search termination • Usually after a predefined number of iterations • Best solution found is reported • No guarantee of optimality • Experimentation gives confidence search broadly search locally 14 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Termination in Termination in iSIGHT • Be careful with iSIGHT: the last solution is not necessarily the best one • Need to look back over all the solutions in the monitor to find the “optimum” • Feasibility parameter: 3 = infeasible 7 = feasible 8 = feasible and equal to the best design found so far 9 = feasible and the best design found so far • The “optimum” will be the last solution with feasibility=9 15 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Post-Optimality Analysis 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 16 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Lagrange Multipliers Lagrange Multipliers • The values of the Lagrange multipliers at the optimal solution, λj*, give information on the constraints. • If λj* is zero, then constraint j is inactive. • If λj* is positive, then constraint j is active. • The value of the jth Lagrange multiplier tells you by how much the objective function will change if the constraint is varied by a small amount: T ∂ =− ∂ J g ( *) ( *) x x λ – λ is a vector containing the m LMs – is a vector containing all g m constraints (inequality+equality)

Mlesd Objective Function Behavior 16888 M歌 d Objective Function Behavior男 Consider the quadratic function (i+ap)=a(x)+ap(HX+c)+=a'p Consider the neighborhood of the optimal solution The behavior of a(x)in the neighborhood of a local minimum is determined by the eigenvalues of H a(X+ap)=C(X+ap)+C(X+ap)(X+ap VO(x* )=Hx*+c=0 or HX=C ci+XHA+acp+-a'p'Hp+Hp+pHX op(X*+ap)=(x)+=ap'Hp o(X+ap)=(x)+ap(HX+c)+-a'p Hp The behavior of qp in the neighborhood of x' is determined by h e Massachusetts Institute of Technology -Prof de Weck and Prof Willcox e Massachusetts Institute of Technology. Prof de Weck and Prof. willcox Engineering Systems Division and Dept of Aeronautics and Astronautics Engineering Systems Division and Dept of Aeronautics and Astronautics Mlesd Objective Function Behavior esd Objective Function Behavior Let v, i, be the Ah eigenvector and eigenvalue of H d(x*+av)=(x)+a2 and v; v =di since H is symmetric 2>0. p increases If 1<0. p decreases Consider the case when p=v If 2=0. p remains constant a(x*+av)=a(x*)+av When all 2>0.x* is a minimum of p The contours of p are ellipsoids Φ(x) principal axes in directions of eigenvector lengths of principal axes inversely proportional to guare roots of eigenvalues As we move away from x* along the direction v;, the change in the objective depends on the sign of i e Massachusetts Institute of Technology -Prof de Weck and Prof Willcox e Massachusetts Insttute of Technology. Prof de Weck and Prof Willcox Engineening Systems Division and Dept of Aeronautics and Astronautics Engineering Systems DiMsion and Dept of Aeronautics and Astronautics

17 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Objective Function Behavior Objective Function Behavior Consider the quadratic function: 1 ( ) 2 Φ= + T T x c x x Hx The behavior of Φ(x) in the neighborhood of a local minimum is determined by the eigenvalues of H. 1 ( ) ( ) ( )( ) ˆ ˆ ˆˆ 2 Φ+ = + + + + α α αα T T x p c x p x p Hx p 1 1 2 ˆ ˆˆ ˆ ˆ 2 2 22 α α =+ + + + + α α TT T T T T c x x Hx c p p Hp x Hp p Hx 1 2 ( ) () ( ) ˆ ˆˆ 2 T Φ + =Φ + + + αα α T x p x p Hx c p Hp 18 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Objective Function Behavior Objective Function Behavior 1 2 ( ) () ( ) ˆ ˆˆ 2 T Φ + =Φ + + + αα α T x p x p Hx c p Hp Consider the neighborhood of the optimal solution: x x ˆ = * ∇Φ = + = ( *) * 0 x Hx c or Hx c * = − 1 2 ( * ) ( *) 2 Φ + =Φ + α α T x p x p Hp The behavior of Φ in the neighborhood of x* is determined by H. 19 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Objective Function Behavior Objective Function Behavior Let vj, λj be the jth eigenvector and eigenvalue of H: and since H is symmetric. Consider the case when p=vj: Hv v j = λ j j T i j ij v v = δ 2 2 1 ( * ) ( *) 2 1 *) 2 j j j j α α α λ Φ + =Φ + = Φ( + T x v x v Hv x As we move away from x* along the direction vj, the change in the objective depends on the sign of λj. 20 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Objective Function Behavior Objective Function Behavior 1 2 ( * ) *) 2 Φ + = Φ( + xv x α j α λ j • If λj>0, Φ increases • If λj<0, Φ decreases • If λj=0, Φ remains constant • When all λj>0, x* is a minimum of Φ • The contours of Φ are ellipsoids – principal axes in directions of eigenvectors – lengths of principal axes inversely proportional to square roots of eigenvalues