1、SECTION 2NUMERICAL OPTIMIZATIONTABLE OF CONTENTSPAGEMINIMIZATION OF FUNCTIONS OF A SINGLE VARIABLE 2-3GRADIENTS 2-8UNCONSTRAINED MINIMIZATION METHODS 2-11KUHN-TUCKER CONDITIONS FOR OPTIMALITY 2-16SIMPLE CANTILEVER EXAMPLE 2-18SERIES APPROXIMATIONS 2-21SEQUENTIAL LINEAR PROGRAMMING 2-26METHOD OF FEAS

2、IBLE DIRECTIONS 2-29MODIFIED METHOD OF FEASIBLE DIRECTIONS 2-33SQP METHOD2-40NUMERICAL IDENTIFICATION OF ACTIVE AND VIOLATED CONSTRAINTS2-43MINIMIZATION OF FUNCTIONS OF A SINGLE VARIABLEConsider the following function of a single variable Xextremum is defined for X* at which The numerical optimizer

3、“samples” this continuous function and uses this data to estimate an extremum. For example, if the following information is available:we could use a quadratic polynomial approximation of the form:MINIMIZATION OF FUNCTIONS OF A SINGLE VARIABLE (Cont.)to construct 3 equations in 3 unknowns:From which:

4、MINIMIZATION OF FUNCTIONS OF A SINGLE VARIABLE (Cont.)ThereforeMinimum at X* if a2 0Maximum at X* if a2 0MINIMIZATION OF FUNCTIONS OF A SINGLE VARIABLE (Cont.)Unconstrained minimum:MINIMIZATION OF FUNCTIONS OF A SINGLE VARIABLE (Cont.)Constrained minimumSide ConstraintGRADIENTSMultivariate function

5、minimization in MSC.NASTRAN is gradient-based.Let:i.e., a scalar function of n independent variables.Gradient of a scalar function is defined as:where e1,e2,en are unit vectors in the nth direction.GRADIENTS (Cont.)Gradient operator is defined as:or in tensor notation as:Gradient of a scalar vector

6、fieldExample:(Note that this is the equation for a family of circles in the X1, X2 plane with centers at the origin and radii of .)GRADIENTS (Cont.)orf and f are continuous functionsGraphically: Note that f points in the direction of increasing function values.UNCONSTRAINED MINIMIZATION METHODSExamp

7、le: Equilibrium of two-spring systemTheoretical solution:minimum occurs atThe corresponding two-variable design space is illustrated on the next page.UNCONSTRAINED MINIMIZATION METHODS (Cont.)Steepest descent:Reductions in the objective function are sought by searching in a direction given by the ne

8、gative of the gradient.UNCONSTRAINED MINIMIZATION METHODS (Cont.)Design updates given by:WhereThis method is intuitively attractive, but inefficient. In MSC.NASTRAN we only use it as the first iteration of other, more efficient methods.UNCONSTRAINED MINIMIZATION METHODS (Cont.)Conjugate direction me

9、thod(Bias the new search direction with previous information)UNCONSTRAINED MINIMIZATION METHODS (Cont.)This method is easy to code and is a dramatic improvement over the steepest descent method.KUHN-TUCKER CONDITIONS FOR OPTIMALITYKuhn-Tucker conditions for optimality follow directly from a generali

10、zation of Lagrange multipliers.An optimum design is at hand if:X* is feasible k + m unrestricted in sign, but not used in MSC.NASTRANKUHN-TUCKER CONDITIONS FOR OPTIMALITY (Cont.)SIMPLE CANTILEVER EXAMPLEProblem descriptionSIMPLE CANTILEVER EXAMPLE (Cont.)Minimize V = B H LSubject to:SIMPLE CANTILEVE

11、R EXAMPLE (Cont.)The Design SpaceSERIES APPROXIMATIONSFunction gradient information can be used to construct first-order Taylor Series approximationswhereSERIES APPROXIMATIONS (Cont.)Using the Simple Cantilever to illustrate:Minimize V = B H LDesign variables B and HSubject to:SERIES APPROXIMATIONS

12、(Cont.)First-order approximations:AtSERIES APPROXIMATIONS (Cont.)The resultant linearized design spaceSERIES APPROXIMATIONS (Cont.)In this case, the approximate optimum actually violates some of the true constraints. It does, however, form a good starting point for the next iteration. This is the ba

13、sis of a “sequential linearization” method of solution.SEQUENTIAL LINEAR PROGRAMMINGFirst linearize:Solve this linear approximate problem using Simplex or other optimizer.Relinearize and repeat to convergence.This option is available in MSC.NASTRAN. (Set METHOD to 2 on the DOPTPRM Bulk Data entry.)j

14、 J, (J set of active constraints)SEQUENTIAL LINEAR PROGRAMMING (Cont.)Typical design cycle history:Boxes around each design represent move limits.SEQUENTIAL LINEAR PROGRAMMING (Cont.)Why move limits are necessary:Move limits are required because higher order terms have been ignoredMETHOD OF FEASIBLE

15、 DIRECTIONSIn contrast with SLP, the method of feasible directions treats active, nonlinear constraints directly (See Figure a)Usable search direction:Feasible search direction:Figure (a)Figure (b)METHOD OF FEASIBLE DIRECTIONS (Cont.)Determination of s (direction finding subproblem)To maintain feasi

16、bility:where j is the push-off factorTo maintain usability:A nonzero j and b ensure a search direction that reduces the objective function without violating the jth constraint for some finite move in that direction.It is apparent that we would like to maximize b in order to make the greatest possibl

17、e reductions in the objective.METHOD OF FEASIBLE DIRECTIONS (Cont.)Sequence of iterations using cantilever design space as an example:METHOD OF FEASIBLE DIRECTIONS (Cont.)The problem with the method is that it may tend to zigzag between active and inactive constraints as the optimum is approached.In

18、 structural applications, unnecessary function evaluations must be kept to a minimum.Faster convergence can usually be obtained if the constraint surfaces are “followed” to the optimum.MODIFIED METHOD OF FEASIBLE DIRECTIONSCombines best features of the method of feasible directions and generalized r

19、educed gradients. This method is the MSC.NASTRAN defaultIn the direction-finding problem, all push-off factors j are set to zeroMaximizeSubject to:MODIFIED METHOD OF FEASIBLE DIRECTIONS (Cont.)Search direction s (inequality constrained problem)If all gj 0, j = 1,.,muse or direction of steepest desce

20、nt. Use conjugate direction if unconstrained for more than one iterationIf some gj = 0, j J, within a specified tolerance (J = set of active constraint), use direction s that is obtained by solving the following sub-problem:Maximize Subject toMODIFIED METHOD OF FEASIBLE DIRECTIONS (Cont.)If design i

21、s not feasible, use a large push-off factor for violated constraints and find the search direction as in the method of feasible directions.MODIFIED METHOD OF FEASIBLE DIRECTIONS (Cont.)One-dimensional Search ModificationsA move in direction S will go into the infeasible region for nonlinear convex c

22、onstraints. Using the gradients of the active constraints, a step back to the constraint boundary is taken, so the design “follows” the constraints.First take a step an Evaluate the constraints and perturb the proposed design back to the constraint boundary by:where contains the gradients of the act

23、ive constraints and G contains the constraint values.This is effectively a “minimum norm” move back to the constraint boundary and may need several applications.MODIFIED METHOD OF FEASIBLE DIRECTIONS (Cont.)FeaturesRapidly obtains an optimum designDeals with both inequality and equality constraintsU

24、sually satisfies the constraints with high precision at the optimumMODIFIED METHOD OF FEASIBLE DIRECTIONS (Cont.)Sequence of iterations using cantilever design space as an exampleMODIFIED METHOD OF FEASIBLE DIRECTIONS (Cont.)Recovery from infeasible designsMinimize Objective FunctionCompromise Direc

25、tionSQP METHODThe basic concept is very similar to Sequential Linear Programming. A quadratic approximation for the objective function and a linear approximation for constraint functions. The following sub-problem is solved using the Modified Method of Feasible Directions to find search direction S

26、minimize subject to Matrix B is a positive definite matrix which is initially the identity matrix. At the optimum of this problem, B is updated to approach the Hessian of the Lagrangian functions. SQP METHOD(Cont.)At the optimum for this problem, the Lagrange multipliers j j = 1, m can be calculated. The