A min–max method with adaptive weightings for uniformlyspaced Pareto optimum pointsW.H. Zhang* , T. GaoSino-French Laboratory of Concurrent Engineering, Northwestern Polytechnical University, P.O. Box 552, Xi’an, Shaanxi 710072, ChinaReceived 11 January 2005; accepted 27 April 2006Available online 7 September 2006AbstractThis work aims at obtaining uniformly spaced Pareto optimum points in the objective space when multicriteria optimization problemsare solved. An original adaptive scheme is proposed to update automatically weighting coefficients involved in the min–max method. Bymeans of a novel bilevel approach, it is shown that with the calculation of the tangent and normal directions of the Pareto curve, Paretooptimum points can be obtained sequentially with a uniformly spaced distribution. Meanwhile, the distance between two adjacent Paretooptimum points is controllable depending upon the prescribed step length along the tangent direction. To validate the method, numericalbicriteria examples are solved to show its effectiveness.? 2006 Elsevier Ltd. All rights reserved.Keywords: Multicriteria optimization; Pareto optimum; Min–max method1. IntroductionNowadays, multicriteria optimization is widely appliedat the design stage of mechanical structures and dynamicsystems. Due to the basic nature of conflict among objectivefunctions, a set of compromising solutions called Paretooptima exists. This solution set is essential for decision-making of designers including the selection of preferabledesign results and the reveal of the trade-off relationship.Usually, multicriteria optimization problems are solved bytransforming the original vector-valued problem into a sca-lar one by means of scalarization methods such as theweighting method, the trade-off method and the min–maxmethod. However, an effective method is expected to gener-ate Pareto points that are representative and able to capturethe shape and all parts of the Pareto optimum curve in theobjective space. In this regard, Pareto points obtained aredesired to be uniformly spaced with equal distance betweenadjacent points. In fact, this issue has received much atten-tion since a long time. As indicated by Koski [1], the weight-ing method is based on a linear combination of objectivecriteria and unable to capture non-convex parts of the Par-eto curve. Lin [2], Das and Dennis [3] indicated that Paretooptimum solutions obtained by the weighting method areoften found to be so few, or the distribution is so extremeand that it seems to exist no middle ground for any compro-mise although such a ground may actually exist. Hence, theattainment of a uniform distribution of Pareto optimumpoints is a property that the weighting method lacks eventhough weightings are uniformly discretized and used.Actually, the normal-boundary intersection method (NBI)proposed by Das and Dennis [4] is devised to address theproblem of uniform distribution of Pareto points.In this paper, the min–max method is preferable andstudiedindetail.Firstly,itisshownthatallcriteriainthesca-larizing formulation are decoupled and transformed intoseparable inequality constraints so that problems can besolved as easily as single objective problems. Secondly, anadaptiveweightingschemeisproposedtoensureauniformlyspaced distribution of generated Pareto points. By compar-ison,theNBImethodupdatesonlythereferencepointonthe0045-7949/$ - see front matter ? 2006 Elsevier Ltd. All rights reserved.doi:10.1016/j.compstruc.2006.04.007*Corresponding author. Tel./fax: +86 29 88495774.E-mail address: zhangwh@nwpu.edu.cn (W.H. Zhang).www.elsevier.com/locate/compstrucComputers and Structures 84 (2006) 1760–1769
so-called parameterized convex hull of individual minima(CHIM) and keeps the search direction unchanged whereasthe proposed min–max method searches for Pareto opti-mumsstepbystepwithanupdatingofboththesearchdirec-tion and the reference point to ensure their uniform spacing,i.e., equal distance during the iteration process. Therefore,when the search direction is maintained to be unchangedwith constant weighting coefficients, both methods togetherwith that of Schy et al. [5] become identical. To illustrate theproposed method, Some typical numerical tests are carriedout. It is shown that the adaptive weighting procedure is arigorous and reliable scheme to ensure a uniform distribu-tion of Pareto optimum points.2. Statement of multicriteria optimization problemsConsider a multicriteria optimization problem of thefollowing mathematical programming statementMin FðXÞg j ðXÞ 6 0 j ¼ 1;mð1Þwhere F(X) = [f 1 (X),f 2 (X),...,f r (X)] T is composed of robjective functions to be minimized; g j (X) denotes the jthconstraint. Due to the conflicting nature of the objectivefunctions, solutions of the above problem are multipleand Pareto optimal. By definition, a feasible solution X *is Pareto optimal if there is no other improved feasiblepoint X such that f k (X) 6 f k (X * ) with strict inequality forat least one condition. Mathematically, the K-T optimalityconditions satisfied by the Pareto optimum X * are givenbelow:Xkw k rf k ðX ? Þ þXjk j rg j ðX ? Þ ¼ 0 ð2-1Þk j g j ðX ? Þ ¼ 0; k j P 0 ð2-2Þwhere {w k } is a set of known positive weightings normal-ized by the sum relationPk w k¼ 1 and k j denotes thenon-negative Lagrangian multiplier associated with thejth inequality constraint. These optimality conditions areobviously identical to those for the following weightingproblem of one scalarized objective functionMinXkw k f kg j ðXÞ 6 0 j ¼ 1;mð3Þ3. The min–max method with adaptive weightings3.1. The min–max methodThe min–max method is a scalarization approach thattransforms the original multicriteria problem (1) into a sin-gle objective problem of the general formMin bf k ðXÞ ? f k 6 c k b k ¼ 1;rg j ðXÞ 6 0 j ¼ 1;mð4ÞIn this formulation, all r criteria are considered as addi-tional inequality constraints and the substituted objectivefunction is defined by an additional design variable b act-ing as a sort of upper bound to each criterion. To have ageometrical interpretation, let us consider a bicriteria caseshown in Fig. 1. Vector ff k g designates a reference pointin the objective space and {c k } is a normalized vector ofpositive weighting coefficients withPk c k¼ 1 defining thesearch direction originating from ff k g. Note that both vec-tors of ff k g and {c k } have to be specified in advance in theabove formulation. Clearly, the min–max method searchesfor such a Pareto optimum {f k (X * )} that minimizes the dis-tance to the reference point ff k g along the prescribed direc-tion {c k }. Therefore, a set of Pareto optimum points willbe hopefully generated by varying {c k }. Adaptive weigh-tings consist in using proper {c k } that will be able to giverise to Pareto points of uniform distribution in the objec-tive space. From this point of view, the min–max methodcan be regarded as a secant method whereas the classicalweighting method can be regarded as a tangent method.Meanwhile, the min–max formulation can hold the con-vexity of the original problem (1) if the latter has. This per-mits direct applications of convex programming methodsto solve problem (4) as carried out by Olhoff and Bendsøeet al. [6,7].Here, it is necessary to remark that the min–maxmethod is also convenient to deal with nesting problemsin which some criterion is itself identified as the maximiza-tion of other functions, e.g., the problem associated withthe minimization of stress concentration over a structure.The corresponding problem takes the following form:Min ff k ðXÞ;maxpfh p ðXÞgg k ¼ 1;r; p ¼ 1;sg j ðXÞ 6 0 j ¼ 1;mð5Þ{ f k }{kc }1f2f{ *) (X f k }Fig. 1. Illustration of the min–max method.W.H. Zhang, T. Gao / Computers and Structures 84 (2006) 1760–1769 1761
This is a non-differentiable problem. In this case, it can betransformed into the standard formMin bf k ðXÞ ? f k 6 c k b k ¼ 1;rh p ðXÞ ? f rþp 6 c rþ1 b p ¼ 1;sg j ðXÞ 6 0 j ¼ 1;mð6ÞNow, it is interesting to reveal the underlying relationshipbetween the min–max method (4) and the classical weight-ing method (3). By writing the Lagrangian function of Eq.(4)LðX;bÞ ¼ b þXkc k ðf k ðX ? Þ ? f k ? c k bÞ þXj1 j g j ðX ? Þð7Þwith c k and 1 j to be Lagrangian multipliers, the Kuhn–Tucker optimality conditions are then expressed asr X LðX;bÞ ¼Xkc k rf k ðX ? Þ þXj1 j rg j ðX ? Þ ¼ 0 ð8-1Þr b LðX;bÞ ¼ 1 ?Xkc k c k ¼ 0 ð8-2Þwithc k ðf k ðX ? Þ ? f k ? c k bÞ ¼ 01 j g j ðX ? Þ ¼ 0c k ;1 j P 0ð9ÞFrom Eq. (8-2), it follows thatXkc k c k ¼ 1 ð10ÞDenotingc ¼Xkc k ð11Þthe multiplication of Eq. (8-1) by1cproduces1c? ?r X L ¼Xkc kc? ?rf k ðX ? Þ þXj1 jc? ?rg j ðX ? Þ ¼ 0ð12Þin which relative weighting coefficients of all criteria arenormalized to a unit sum.The comparison between Eqs. (2-1) and (12) confirmsthat if the min–max method and the weighting method pro-duce the same Pareto optimum solution, following rela-tions have to hold.• For Lagrangian multipliers:k j ¼1 jcð13-1Þ• For weightings:w k ¼c kcð13-2ÞWeighting vector {w k } is directly related to Lagrangianmultipliers of constraints defined by the objective criteriain the min–max problem. Hence, if min–max problem (4)is solved by the dual approach, Lagrangian multipliers thatare automatically given rise to as by-products can be usedin turn to deduce weightings from Eq. (13-2). In the recentwork of Zhang et al. [8], it was proved that the min–maxformulation is a degenerate form of the multibound formu-lation of the weighting method.3.2. Determination of the tangent and normal directionsof the Pareto curveIn the proposed min–max method, the adaptive updat-ing of {c k } and ff k g is employed to generate uniformlyspaced Pareto optimum points. That is, obtained Paretopoints will be spaced approximately with equal distancealong the search trajectory on the Pareto curve/surface.To do this, the normal direction at the current optimumpoint of the Pareto curve/surface is adopted for the defini-tion of {c k }. In the search of next optimum point, the ref-erence point ff k g is defined by translating {c k } along thespecified tangent direction with a predefined step length.The scheme is illustrated in Fig. 2.Geometrically, weighting vector {w k } involved in Eq.(2-1) represents the normal direction of the Pareto curveat X * in the objective space. However, when X * is anon-differentiable Pareto point, i.e., the left-hand deriva-tive does not equal the right-hand derivative for thePareto curve/surface at X * in the objective space, onlydirectional derivatives exist. This case may happen whenX * is a singular point (see point A in Fig. 12 of Section4.3) or a discontinuous point (see points B and C inFig. 20 of Section 4.5) of the Pareto curve/surface. As aresult, multiple {w k } satisfying Eq. (2-1) exist at X * . Thor-ough discussions were made on this issue in [9–11] and itwas shown that only the extreme one of {w k } correspondsto the normal direction.1 t+ FW t1f2f1( *)tF+X( *)tF XαC = W tTt FtαFig. 2. Illustration of the min–max method with adaptive weightingprocedure.1762 W.H. Zhang, T. Gao / Computers and Structures 84 (2006) 1760–1769
To evaluate sequentially Pareto optimum points, a gen-eral bilevel approach is proposed to determine the normaland tangent directions in this paper.Level 1: Evaluation of the weighting vector {w k }From the theory of multicriteria optimization [12,13], itis known that under the normalized condition of weightingcoefficientsPk w k¼ 1, the bigger the value of some weight-ing component w q related to f q in the weighting method, thesmaller the objective criterion f q obtained after the minimi-zation of Eq. (3). Hence, if multiple {w k } exist at a knownPareto optimum X * , the extreme weighting vector {w k } thathas the biggest component w q corresponds to the solutionof the following linear problem.Max w qXrk¼1w k rf k ðX ? Þ þXmj¼1k j rg j ðX ? Þ ¼ 0Xrk¼1w k ¼ 1 k j ;w k P 0ð14Þor the equivalent minimization form isMin ? w qXrk¼1w k rf k ðX ? Þ þXmj¼1k j rg j ðX ? Þ ¼ 0Xrk¼1w k ¼ 1 k j ;w k P 0ð15ÞThis is a linear programming problem of single objectivefunction w q . In Eqs. (14) and (15), $f k (X * ) and $g j (X * )are known. Involved unknowns are the weighting vector{w k } and Lagrangian multipliers {k j } to be determined.Constraints refer to K-T optimality conditions (2-1) that{w k } has to satisfy at the known Pareto optimum X * . Tofind all extreme weighting vectors for all objective criteria,a set of q = 1, r linear optimization problems will be repeat-edly solved. Physically, the obtained {w k } means that thecomponent w q attains its upper bound beyond which anyother {w k } will cause a diminution of f q and then the cur-rent optimum X * will shift to a new solution point. Morediscussions can be also found in [9–11].With the existence of Pareto optimum X * satisfying Eq.(2-1), it is known that a feasible solution of {w k } and {k j }of Eq. (15) always exists. Particularly, the solution of {w k }will be unique when X * is a differentiable Pareto optimum.Otherwise, {w k } different from that in Eq. (2-1) may befound when X * is a non-differentiable Pareto optimum.Level 2: Evaluation of the tangent direction of the Paretooptimum curveTo have an easy understanding, let us have a look atFig. 2, suppose that vector T represents the tangent direc-tion of the Pareto optimum curve at X t * in the objectivespace. In the design variable space of X, the correspondingvarying direction at X t * is supposed to be S. Thus, the var-iation of design variable along S can be expressed asDX ¼ hS ð16Þwith h to be the step. Following Taylor expansion, thevariation of the kth criterion is therefore approximatedbyDf k ¼ hrfTkS ð17ÞIt can be regarded as a mapping of vector S defined in thedesign variable space to the objective space. Naturally, T isa composition of Df k ¼ hrf TkS. With the elimination of thecommon scalar term h that doesn’t influence the orienta-tion of T, it follows thatT ¼ frfTkSg k ¼ 1;r ð18ÞIn Fig. 2, one can see that T represents the descent direc-tion of f 1 at point X t * , that defines the left-hand derivative.In other words, T is the direction along which a maximumdiminution of f 1 will produce for a given augmentation off 2 . This is the condition satisfied by T. Note that if X t *was a non-differentiable Pareto optimum, the right-handderivative would be not aligned with T. Generally speak-ing, because Pareto optimum points are non-inferior solu-tions according to the definition of Pareto optimality, Twill be the descent direction depending upon the concernedobjective criterion, e.g., f 1 in Fig. 2.With the above analysis, the evaluation of the tangentdirection T can be reduced to the determination of S. Thelatter has to be such a feasible direction along which a max-imum diminution of the considered objective criterion willproduce. To do this, consider the evaluation of the descentdirection S associated with the qth objective criterion f q .It can be obtained by solving the following problemMin rfTq Sq ¼ 1;rrg Tj S 6 0j ¼ 1;JXrk¼1w k ðrfTkSÞ ¼ 0Xrk¼1;k6¼qðrfTkSÞ 2 6 1ð19ÞThis formulation can be interpreted in the following way.The objective function means that S is the steepest direc-tion making the maximum diminution of f q locally. Thefirst inequality constraint means that S is a feasible searchdirection with regard to all active constraints. The secondequality requires that in the objective space, the weightingvector {w k } derived from Eq. (15) should be orthogonal tothe tangent direction defined by Eq. (18). The last con-straint added refers to the limitation of the allowable sacri-fices of other objective criteria. It is normalized inmagnitude to make sure the solution uniqueness of thesearch direction S when problem (19) is solved. With theseconstraints, T defined by S will be not only the tangentdirection of the Pareto curve/surface but also the directionthat ensures the maximum diminution of f q .W.H. Zhang, T. Gao / Computers and Structures 84 (2006) 1760–1769 1763
In summary, the whole computing procedure can beorganized below. At an initial Pareto optimum, one getsfirstly the desired weighting vector {w k } by performingthe minimization task (15) of the first level. Then, with itssubstitution into Eq. (19) of the second level, a quadraticproblem will be solved to get the desired search directionS. Finally, the tangent direction T will be evaluated bymeans of Eq. (18).This is, in fact, a general scheme of computing T. In thespecial case of bicriteria problems (r = 2), a closed expres-sion can be obtained for T. For example, consider q = 1,Problem (19) becomesMin rfT1 Srg Tj S 6 0j ¼ 1;JX2k¼1w k ðrfTkSÞ ¼ 0ðrfT2 SÞ26 1ð20Þwhose Lagrangian function is expressed asLðSÞ ¼ rfT1 S þXJj¼1a j rg Tj S þ b 1X2k¼1w k ðrfTkSÞþ b 2 ½ðrfT2 SÞ2? 1? ð21Þwith a j , b 1 and b 2 to be Lagrangian multipliers. The K-Toptimality condition that S has to satisfy corresponds tor S LðSÞ¼rf 1 þXJj¼1a j rg j þb 1X2k¼1w k rf k þ2b 2 ðrfT2 SÞrf 2 ¼0ð22ÞWith the consideration of active constraints in Eq. (20), themultiplication of (22) by S results inrfT1 S þ 2b 2 ðrfT2 SÞrfT2 S ¼ 0ð23ÞDenoting T ¼ ½T 1 ;T 2 ? ¼ ½rf T1 S;rfT2 S? and retaining theequality constraint in Eq. (20), it follows thatT 1 þ 2b 2 T22¼ 0; w 1 T 1 þ w 2 T 2 ¼ 0 ð24ÞThe tangent direction can be directly deduced asT ¼ ½T 1 ;T 2 ? ¼ ?12b 2w 2w 1? ? 2;12b 2w 2w 1" #ð25ÞIt can be further normalized asT ¼ ½T 1 ;T 2 ? ¼ ½?w 2 ;w 1 ? ð26ÞThis result can be also obtained from the orthogonalitycondition between the normal and the tangent directionof a plane curve. After obtaining the weighting vector{w k } from Eq. (15), one can get both left-hand and right-hand tangent directions by means of the vectored productsuch thatT ¼ ?f0;0;1g ? fw 1 ;w 2 ;0g ð27ÞNote that values of weighting coefficients in Eq. (27) maybe different in the calculation of left-hand and right-handtangent directions.3.3. Optimization procedure with adaptive weightingsWith the availability of {w k } and T from above comput-ing, uniformly distributed Pareto optima can be readilyobtained. Now, let us focus on a bicriteria optimizationproblem with r = 2 in Eq. (4). The procedure associatedwith Fig. 2 is described below:I. Initialization: Set t = 1 and predefine a step length awhose value defines the distance between two neigh-bouring optimum points and determines the distribu-tion density of generated optimum points.II. Find the extreme right-hand Pareto optimum point,noted X t * , by solving a single objective problemMin bf 2 ðXÞ 6 bg j ðXÞ 6 0 j ¼ 1;mð28ÞIII. Determine the normal direction W t = {w k } in virtueof Eq. (15) and tangent direction T at X * t in virtueof Eqs. (18) and (19) or Eq. (27).IV. Move ahead vector W t = {w k } perpendicularly to thetangent direction T with step length a (see Fig. 2) andassign the currently retained vector W t = {w k } to theweighting vector {c k } used in Eq. (4).V. Along {c k }, define the reference point F tþ1 . Whosecomponents are specified to be small enough com-pared with the Pareto optimum being found.VI. Solve the min–max problem (4) by an available con-vex programming optimizer and find a new optimumpoint X t+1 * .VII. Set t = t + 1. Return to step III. Continue the loopuntil obtaining all discrete solutions of the Paretooptimum set.In this procedure, Pareto optimum points are determinedsequentially along tangent directions that are updated toreflect the shape of the Pareto curve. As the step a is rela-tively small, obtained optimum points as shown in the fol-lowing section attain a uniform distribution as expected.4. Numerical examplesNumerical bicriteria examples are solved here to high-light the method proposed above. To have a clear idea,illustrative tests such as unconstrained problem, con-strained problems with equality and inequality constraintsare carried out and two structural optimisation problemsare solved. For each test, the minimum of each individualobjective function is firstly calculated to determine twoextremities of the Pareto curve. One is used as the startingpoint in the generation of the Pareto optimum curve; theother is an ending point controlling the search iterationprocedure. To study the uniformity of the Pareto optimumdistribution, results obtained by the min–max method withadaptive weightings are compared with those obtained by1764 W.H. Zhang, T. Gao / Computers and Structures 84 (2006) 1760–1769
using a uniform discretization of {c k } with the origin of thecoordinate system being the reference point, i.e., c 1 ¼0;1n ;2n ;...;1? ? ;c2 ¼ 1;n?1n;n?2n;...;0? ?with n being an inte-ger partition number and f 1 ¼ f 2 ¼ 0. More importantly,the comparison with the classical weighting method showsthe significant improvement.4.1. Unconstrained problemMin ff 1 ¼ coshðxÞ;f 2 ¼ x 2 ? 12x þ 35gAs shown in Fig. 3, with the min–max method using a uni-form discretization of weightings, optimum points are un-evenly distributed and mainly concentrated in the middleregion where the Pareto optimum curve has a considerableslope variation. In contrast, based on the adaptive weigh-tings, Pareto optimum points are sequentially generatedfrom left to right and are uniformly distributed, as shownin Fig. 4. Due to the absence of constraints, the tangentdirection used is just the negative gradient of the secondobjective function, f 2 , in this problem. Here, the step lengthis set to be a = 10. It may also be estimated as a fractionpercentage of the distance between two extremity optimumpoints. It is found that the real distances between twoadjacent solution points are bounded within 10 6 dist 610.082. Fig. 5 shows the value variation of the adaptiveweighting component, c 2 , at each optimum point. Clearly,the variation is nonlinear.4.2. Problem with equality and inequality constraints [3]Minf 1 ¼ x 21 þ x22 þ x23 þ x24 þ x25f 2 ¼ 3x 1 þ 2x 2 ?13x 3 þ 0:01ðx 4 ? x 5 Þ 38<:9=;g 1 ¼ x 21 þ x22 þ x23 þ x24 þ x25 6 10g 2 ¼ 4x 1 ? 2x 2 þ 0:8x 3 þ 0:6x 4 þ 0:5x 25¼ 0g 3 ¼ x 1 þ 2x 2 ? x 3 ? 0:5x 4 þ x 5 ? 2 ¼ 0This problem was solved by Das and Dennis [3] using theNBI method. The particularities are that apart from twoequality constraints, the inequality constraint is the sameas the first objective function. As seen in Figs. 6 and 7, setsof optimum points obtained by using either the min–maxmethod or the weighting method with the uniform weight-ing discretization are unevenly distributed, especially in thesecond one. In contrast, a uniform distribution is producedin Fig. 8 where Pareto optimum points are generated fromleft to right using adaptive weightings. The variation of theadaptive weighting component, c 2 , is illustrated in Fig. 9.Its maximum value smaller than 1 at the right extremityoptimum implies that this is a non-differentiable optimumwith multiple weightings due to the shifting of the activeinequality constraint.Fig. 3. Pareto optimum results with a uniform discretization of {c k }.Fig. 4. Pareto optimum results with adaptive weightings (a = 10,10 6 dist 6 10.082).Fig. 5. Variation of the adaptive weighting parameter c 2 .W.H. Zhang, T. Gao / Computers and Structures 84 (2006) 1760–1769 1765
4.3. Problem with non-differentiable Pareto optimumThe problem is stated asMin ff 1 ðXÞ¼ðx 1 ?2Þ 2 þðx 2 ?1Þ 2 ; f 2 ðXÞ¼x 21 þðx 2 ?6Þ2 gg 1 ðXÞ¼x 21 ?x 2 60g 2 ðXÞ¼5x 21 þx 2 610g 3 ðXÞ¼x 2 65g 4 ðXÞ¼?x 1 60The design variable space and Pareto optimum tracking(dotted line) along the domain frontier are described inFig. 10. Solutions obtained are shown in Figs. 11 and 12,respectively. Here, it is interesting to note that point A isa singular point in the design variable space. Its mappingin the objective space corresponds to a non-differentiablePareto optimum since two different normal directions existFig. 6. Pareto optimum results with a uniform discretization of weightingparameters.-5-4-3-2-101230 2 4 6 8 10 12f1f2Fig. 7. Pareto optimum results by weighting method.Fig. 9. Variation of the adaptive weighting parameter c 2 .Fig. 10. Pareto optimum tracking in the design variable space.Fig. 8. Pareto optimum results with adaptive weightings (a = 1,1 6 dist 6 1.0706).1766 W.H. Zhang, T. Gao / Computers and Structures 84 (2006) 1760–1769
with a shifting represented by the jump of the componentc 2 in Fig. 13.4.4. Three-bar weight-rigidity optimisation problemThe truss is shown in Fig. 14. Suppose that bar 1 andbar 3 have the same section areas. The structural weightand the mean compliance will be simultaneously minimizedsubject to constraints imposed on axial stresses in all bars.Two design variables are defined by bar sections.The optimisation problem can be analytically formu-lated as follows:Min f 1 ðx 1 ;x 2 Þ¼P 2 lðffiffiffi2px 1 þx 2 ÞEx 1 ðx 1 þffiffiffi2px 2 Þ ;f2 ðx 1 ;x 2 Þ¼qlð2ffiffiffi2px 1 þx 2 Þ( )g 1 ðx 1 ;x 2 Þ¼P2x 1x 2 þffiffiffi2px 1x 1 þffiffiffi2px 2?r þ 60;g 2 ðx 1 ;x 2 Þ¼Px 1 þffiffiffi2px 2?r þ 60;g 3 ðx 1 ;x 2 Þ¼Pffiffiffi2px 1x 2x 1 þffiffiffi2px 2?r ? 60; 0:00016x 1 ;x 2 60:01Initial data are given belowP ¼ 10 6 N; l ¼ 0:5 m; E ¼ 2:1 ? 10 11 Pa;r þ ¼ 1:6 ? 10 8 Pa; r ? ¼ 10 8 Pa; q ¼ 7:8 ? 10 6 kg=m 3Fig. 11. Pareto optimum results with a uniform discretization ofweightings.Fig. 13. Variation of the adaptive weighting parameter c 2 .l45°45°45°321APFig. 14. Three-bar problem.Fig. 15. Pareto optimum results with a uniform weighting discretization.Fig. 12. Pareto optimum results with adaptive weightings (a = 1,1 6 dist 6 1.0079).W.H. Zhang, T. Gao / Computers and Structures 84 (2006) 1760–1769 1767
Results are compared now in Figs. 15 and 16. For the min–max method with adaptive weighting procedure, 31 Paretooptimum points are generated with the step length a = 1.The real distance is bounded within 0.9997 6 dist 6 1.0004confirming the predicted control precision of uniformity bya (Fig. 17). Correspondingly, tracking the Pareto optimumset generation in the design variable space is illustrated inFig. 18. This is helpful to understand the change of the ac-tive constraint set during the iteration procedure.4.5. Three-bar optimisation problem Koski [1]The truss is shown in Fig. 19. Initial data are F = 20 kN,Young’s modulus is E = 200 GPa, L = 100 cm. Allowablestresses r = ?200 MPa and r ¼ 200 MPa. Cross-sectionareas of three bars are assigned as design variables withlower and upper bounds of a = 0.1 cm 2 and a ¼ 2 cm 2 ,respectively. Two objective functions will be simulta-neously minimized: the total truss volume V, a linear com-bination of horizontal and vertical displacements of node 4with D = 0.75u 4 + 0.25v 4 . The bicriteria optimization prob-lem is then as follows:Fig. 16. Pareto optimum results with adaptive weightings.Fig. 17. Variation of the adaptive weighting component c 2 .Fig. 18. Pareto optimum tracking in the design variable space.xyFFLL3 LFig. 19. Three-bar problem.Fig. 20. Pareto optimum results with adaptive weightings.1768 W.H. Zhang, T. Gao / Computers and Structures 84 (2006) 1760–1769
Min fD;V ðaÞgr 6 r j ðaÞ 6 r j ¼ 1;3a 6 a i 6 a i ¼ 1;3The basic characteristic lies in that the whole Pareto curveis discontinuous and one of two portions is partially non-convex so that it is unattainable by the traditional weight-ing method. By means of the proposed method, the set ofPareto points is sought iteratively from the left extremepoint A to the right end point D with a step length ofa = 0.25. As shown in Fig. 20, obtained discrete optimumpoints are uniformly spaced as expected. The correspond-ing weighting at each Pareto optimum is given in Fig. 21.The fact that weighting c 2 increases and then decreases overthe portion AB indicates that AB varies from the convexityto concavity. A sudden jump of c 2 implies the singularity atB. Thereafter, a monotonous increase means that portionCD is convex.5. ConclusionsTo have a good shape representation of the Pareto opti-mum curve, a new min–max method with adaptive weigh-tings is developed to generate uniformly spaced Paretooptimum points. This method is based on the successiveupdating of normal and tangent directions that are evalu-ated by solving a bilevel optimization problem. Althoughall tested examples are bicriteria problems, it is demon-strated that the proposed adaptive weighting procedure isgeneral and efficient to obtain uniformly distributed Paretooptimum points. Besides, the proposed method is superiorto the classical weighting method without suffering fromthe flatness of the Pareto optimum curve. It works no mat-ter what the differentiability and convexity of the Paretooptimum curve are. Compared to the NBI method, thismethod does not need to introduce additional equality con-straints that are often difficult to deal with in structuraloptimization. From the viewpoint of computing cost, thedetermination of adaptive weightings only constitutes avery small post-processing after each Pareto optimum isobtained.AcknowledgementsThis work is supported by the National Natural ScienceFoundation of China (Grant No. 10372083, 90405016), 973Program (2006CB601205) and the Aeronautical Founda-tion (Grant No. 04B53080).References[1] Koski J. Defectiveness of weighting methods in multicriterionoptimization of structures. Commun Appl Numer Methods1985;1:333–7.[2] Lin JG. Multiple-objective problems: Pareto-optimal solutions bymethod of proper equality constraints. IEEE Trans Automat Control1976;AC-21:641–50.[3] Das I, Dennis JE. A closer look at drawbacks of minimizing weightedsums of objectives for Pareto set generation in multicriteria optimi-zation problems. Struct Optim 1997;14:63–9.[4] Das I, Dennis JE. Normal-boundary intersection: a new method forgenerating the Pareto surface in nonlinear multicriteria optimizationproblems. SIAM J Optim 1998;8(3):631–57.[5] Schy AA, Giesy DP, Johnson KG. Pareto-optimal multi-objectivedesign of an airplane control systems. Proceedings of the 1980 jointautomatic control conference. New York: ASME; 1980. WP1-A.[6] Olhoff N. Multicriterion structural optimization via bound formula-tion and mathematical programming. Struct Optim 1989;1:11–7.[7] Bendsøe MP, Olhoff N, Taylor JE. A variational formulation formulticriteria structural optimization. J Struct Mech 1983;11:523–44.[8] Zhang WH, Domaszewski M, Fleury C. An improved weightingmethod with multibounds formulation and convex programming formulticriteria structural optimization. Int J Num Methods Eng2001;52:889–902.[9] Zhang WH, Yang HC. A study of the weighting method for a certaintype of multicriteria structural optimization problems. Comput Struct2001;79:2741–9.[10] Zhang WH, Yang HC. Efficient gradient calculation of the Pareto-optimal curve in multicriteria optimization. Struct Multidiscip Optim2002;23(4):311–9.[11] Zhang WH. On the Pareto optimum sensitivity analysis in multicri-teria optimization. Int J Numer Methods Eng 2003;58(6):955–77.[12] Eschenauer H, Koski J, Osyczka A. Multicriteria design optimiza-tion. Berlin, New York: Heidelberg, Springer-Verlag; 1990.[13] Stadler W. Multicriteria optimization in engineering and in sci-ences. New York: Plenum Press; 1988.Fig. 21. Variation of the adaptive weighting component c 2 .W.H. Zhang, T. Gao / Computers and Structures 84 (2006) 1760–1769 1769