16888 eSd ES077 Multidisciplinary System Design Optimization(MSDo) Numerical Optimization ll Lecture 7 25 February 2004 Karen willcox o Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division 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 Multidisciplinary System Multidisciplinary System Design Optimization (MSDO) Design Optimization (MSDO) Numerical Optimization II Lecture 7 25 February 2004 Karen Willcox
Today,'s Topics 16888 eSd ES077 Sequential Linear Programming Penalty and Barrier Methods Sequential Quadratic Programming Mixed Integer Programming o Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
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 • Sequential Linear Programming • Penalty and Barrier Methods • Sequential Quadratic Programming • Mixed Integer Programming
Technique Overview 16888 ES077 Steepest Descent UNCONSTRAINED Conjugate Gradient Quasi-Newton Newton Simplex -linear CONSTRAINED SLP -often not effective SQP-nonlinear, expensive, common in engineering applications Exterior Penalty-nonlinear, discontinuous design spaces Interior Penalty -nonlinear Generalized Reduced Gradient-nonlinear Method of Feasible Directions -nonlinear Mixed Integer Programming o Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
3 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Technique Overview Technique Overview Steepest Descent Conjugate Gradient Quasi-Newton Newton Simplex – linear SLP – often not effective SQP – nonlinear, expensive, common in engineering applications Exterior Penalty – nonlinear, discontinuous design spaces Interior Penalty – nonlinear Generalized Reduced Gradient – nonlinear Method of Feasible Directions – nonlinear Mixed Integer Programming UNCONSTRAINED CONSTRAINED
Mesd Standard Problem Definition 16888 min J(x st.g/(x)≤0j=1…,m h(x)=0k=1.,m2 ≤X1≤j=1 For now, we consider a single objective function, J(x) There are n design variables and a total of m constraints(m=,+m2) For now we assume all x are real and continuous o Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
4 © 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 i i J g j m h k m x x x i 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 = m 1 + m 2). For now we assume all xi are real and continuous
Optimization Process 16888 eSd q=0 Calculate VJ(xg) Calculate sq Perform 1-D search xq=xq-1+a sq no Converged? es Done o Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
5 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Optimization Process Optimization Process x 0 , q=0 Calculate ∇ J ( x q ) Calculate S q Perform 1-D search x q = x q-1 + α S q Converged? q=q+1 no yes Done
Constrained Optimization 16888 eSd ES077 Definitions Feasible design a design that satisfies all constraints Infeasible design: a design that violates one or more constraints Optimum design the choice of design variables that minimizes the objective function while satisfying all constraints In general, constrained optimization algorithms try to cast the problem as an unconstrained optimization and then use one of the techniques we looked at in Lecture 6 o Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
6 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Constrained Optimization Constrained Optimization Definitions: • Feasible design: a design that satisfies all constraints • Infeasible design: a design that violates one or more constraints • Optimum design: the choice of design variables that minimizes the objective function while satisfying all constraints In general, constrained optimization algorithms try to cast the problem as an unconstrained optimization and then use one of the techniques we looked at in Lecture 6
Linear Programming 16888 Most engineering problems of interest are nonlinear Can often simplify nonlinear problem by linearization LP is often the basis for developing more complicated NLP algorithms Standard LP problem min√(x)=∑cX minJ(x)=c′x Ax=b ∑aX=bj=1…m X≥0 X≥0=1.…,n All LP problems can be converted to this form o Massachusetts Institute of Technology -Prof. de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
7 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Linear Programming Linear Programming Most engineering problems of interest are nonlinear • Can often simplify nonlinear problem by linearization • LP is often the basis for developing more complicated NLP algorithms Standard LP problem: All LP problems can be converted to this form. = = = = = ≥ = ∑ ∑ 1 1 mi n ( ) 1,.., 0 1,..., n i i i n ij i j i i J c x a x b j m x i n x min ( ) 0 1,..., T i J x i n = = ≥ = x c x Ax b
Linear Programming 16888 To convert inequality constraints to equality constraints, use additional design variables ∑ax≤ b. becomes∑ax+Xn=b Where x+1≥0 x. is called a slack variable e.g. the constraint X1+X,≤1 can be written ifx=0. this X1+X2-X2=1 constraint is X≥0,产=1,2,3 active o Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
8 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Linear Programming Linear Programming To convert inequality constraints to equality constraints, use additional design variables: where xn+1 ≥ 0 xn+1 is called a slack variable e.g. the constraint x1+x 2 ≤ 1 can be written x1+x 2-x 3=1 xi ≥0, i=1,2,3 1 1 1 b ecom e s n n ji i j ji i n j i i a x b a x x + b = = ∑ ∑ ≤ + = if x3=0, this constraint is active
Simplex Method 16888 eSd ES077 Solutions at the vertices" of the design space are called basic feasible solutions The Simplex algorithm moves from BFS to BF S so that the objective always improves feasible region basic feasible solution o Massachusetts Institute of Technology -Prof de Weck and Prof Willcox Engineering Systems Division 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 Simplex Method Simplex Method Solutions at the “vertices” of the design space are called basic feasible solutions. The Simplex algorithm moves from BFS to BFS so that the objective always improves. feasible region basic feasible solution
esd Sequential Linear Programming 16888 Consider a general nonlinear problem linearized via first order Taylor series min√(x)≈√(x0)+VJ(x)yδx stg(x)≈g(x)+Vg(x)x≤0 h(x)≈h(x)+Vh2(x)x=0 X≤x1+x1≤x Where Sx=X-X This is an lp problem with the design variables contained in sx. the functions and gradients evaluated at X are constant coefficients o Massachusetts Institute of Technology -Prof. de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
10 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Sequential Linear Programming Sequential Linear Programming Consider a general nonlinear problem linearized via first order Taylor series: 0 0 0 0 0 0 mi n ( ) ( ) ( ) s.t. ( ) ( ) ( ) 0 ( ) ( ) ( ) 0 T T j j j T k k k u i i i i J J J g g g h h h x x x x δ δ δ δ ≈ + ∇ ≈ + ∇ ≤ ≈ + ∇ = ≤ + ≤ x x x x x x x x x x x x A 0 where δ x x = − x This is an LP problem with the design variables contained in δ x. The functions and gradients evaluated at x 0 are constant coefficients