Multidisciplinary System Multidisciplinary System Design Optimization (MSDO) Design Optimization (MSDO)How to Break “Robust” Optimizers Recitation 6 Andrew March © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics 1TodayToday’’s Topics s Topics• fmincon – What the options are – What it’s doing – How to break it • GA toolbox on Stellar • MATLAB® GA Toolbox – Some options – How to break it • Questions © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics 2Sequential Quadratic Programming • Create Quadratic Approximation: B(x )≈∇ L(x ); B(x ) f 0k xx k k sk = xk +1 − xk ineq eq ineq eq⎛ m m ⎞ ⎛ m m ⎞ qk = ⎜⎜∇f (xk +1) + ∑λi∇gi (xk +1) +∑λj∇hj (xk +1)⎟⎟−⎜⎜∇f (xk ) + ∑λi∇gi (xk ) +∑λj∇hj (xk )⎟⎟ ⎝ i=1 j=1 ⎠ ⎝ i=1 j=1 ⎠ B = B + qkqkT − BkTskTskBk k +1 kT T qk sk sk Bksk • Solve Quadratic Program: min 1 d TBkd + ∇f (xk )Td d∈ℜn 2 s.t. A d = beq eq Ad ≤ b meq mineq • Evaluate merit function: Ψ(x) = f (x) +∑rihi (x) +∑ri ⋅ max[gi (x),0] i=1 i=1 αk = arg min Ψ(xk +αd• Compute step length: α∈A(αd )≤bk ) • Take step: x = x +α dk +1 k k k • Repeat until αkdk≤εInterior Point Algorithm • Two equivalent optimization problems: min f (x) mineq nx,s∈ℜ min f (x) −μ∑log si s.t. h(x) = 0 x,s∈ℜni=1 g(x) + s = 0 s.t. h(x) = 0 s ≥ 0 g(x) + s = 0 • KKT Conditions: mineq meq mineq meq ∇f (x) +∑zi∇gi (x) +∑ yj∇hj (x) ∇f (x) +∑zi∇gi (x) +∑ yj∇hj (x) i=1 j=1 i=1 j=1 sz −μe = 0 −μS −1e + z = 0 h(x) = 0 h(x) = 0 g(x) + s = 0 g(x) + s = 0 • Solve KKT system with Newton’s method, for directions. • Compute step length:αs = max{0 <α≤ 1: s +αds ≥ (1 −τ)s}(τ~0.995) αz = max{0 <α≤ 1: z +αdz ≥ (1 −τ)z} • Take step: xk +1 = xk +αsdx sk +1 = sk +αsds yk +1 = yk +αzdy zk +1 = zk +αzdz • Repeat until KKT Conditions satisfied to within μk • Repeat entire process with μk+1=σμk ,0<σ<1Genetic AlgorithmGenetic AlgorithmInitialize Population (initialization) Select individual for mating (selection) Mate individuals and produce children (crossover) Mutate children (mutation) Insert children into population (insertion) Are stopping criteria satisfied ? n y Finish Ref: Goldberg (1989) next generation © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics 5GA Toolbox • BUG!!! • Add into genetic.m – Line 118: stats=[];Fitness Function • Only has Roulette Wheel selection – You can add others… • Roulette Wheel f (xk )Ρ = ∑()f xk k • Are there any restrictions on f(x)?Matlab GA Toolbox • Constraint Handling • Augmented Lagrangian/Penalty method: mineq min f (x) −∑λisi log(gi (x) − si ) x∈ℜn i=1 gi (x) − sk < 0 sk = 1 λk μk – μ0≥1 – σ>1; μk+1=σμk • Disclaimer: this is one of three papers referenced, it may not be exactly what’s in MATLABSummary • There are many optimization toolboxes available to you. • Everyone of them has limitations. • Know what they are doing. • Assure your problem fits within the assumptions that algorithm makes!MIT OpenCourseWarehttp://ocw.mit.edu ESD.77 / 16.888 Multidisciplinary System Design Optimization Spring 2010 For information about citing these materials or our Terms of Use, visit: