Optimization in Practice with MATLAB for Engineering Students and Professionals (2015)

PART 5

MORE ADVANCED TOPICS IN OPTIMIZATION

17

Methods for Pareto Frontier Generation/Representation

17.1 Overview

Multiobjective optimization plays an important role in engineering design, management, and decision making in general. In Chapter 6, the formulation of multiobjective optimization problems and the concept of Pareto frontier wereintroduced. Several approaches to obtain Pareto solutions, including the weighted sum method, compromise programming, goal programming, and physical programming, were introduced in Chapter 6.

In this chapter, new approaches used to obtain Pareto solutions are presented. These approaches can generate an evenly spaced set of Pareto points in the design space, with the objective of capturing the entire Pareto frontier. Thischapter is structured as follows. Section 17.2 presents the requisite mathematical preliminaries. Section 17.3 presents the Normal Boundary Intersection (NBI) method. In Sec. 17.4, the normalized Normal Constraint (NC) method isintroduced. Section 17.5 develops the Pareto filter concept, which eliminates dominated solutions from the generated set of points. Numerical examples are provided in Sec. 17.6, while the summary of this chapter is presented in Sec. 17.7.

17.2 Mathematical Preliminaries

This section provides the requisite mathematical preliminaries. A generic formulation of the multiobjective optimization problem is defined as follows. This problem is named Problem P1.

subject to

The vector x denotes the design variables and μ_i denotes the i_th generic design objective. Equation 17.2 and 17.3 denote the inequality and equality constraints, respectively, while Eq. 17.4 denotes the side constraint. The aboveproblem does not generally yield a unique solution.

Before the approaches used to obtain Pareto frontiers are introduced, several definitions need to be introduced.

Anchor point (μ^i*): The generic i^th anchor point (or end point of the Pareto frontier) is obtained when the generic i^th objective is minimized independently. When the global optimum is not unique, the one non-dominated is chosen. It is also called an optimum vertex.

Utopia line:The line joining two anchor points in bi-objective cases is called the Utopia line.

Utopia hyperplane: The plane that comprises all the anchor points in the multiobjective case is called the Utopia hyperplane.

Utopia point: It is defined by a vector where it’s generic i^th components is the value of the design objective minimum obtained by minimizing only the corresponding i^th design objective.

The word Utopia is used here to indicate that the plane contains the n optimum vertices, components of which form the Utopia point. We note that since the Utopia point is generally unattainable, it is not part of the Utopia plane.If the optimization problem has n objectives, it involves n anchor points. The i^th anchor points can be obtained by solving Problem PUi, which is defined as follows:

subject to

We now define the following quantities, which result from solving the above PUi problem:

x^i* :Optimal decision vector (x^i*∈ Rⁿ_x );

μ_i^* :Generic i^th optimal objective - specifically, μ_i^* = μ_i(x^i*)(μ _i^*∈ R);

μ^u :Utopia Point μ^u = [μ₁^*,μ ₂^*,...,μ _n^*]^T(μ^u ∈ Rⁿ);

μ^i* :i^th Anchor Point μ^i* = [μ₁(x^i*),μ ₂(x^i*),...,μ _n(x^i*)]^T, (μ^i*∈ Rⁿ);

P^u :Utopia Plane. Hyperplane in n-dimensions that comprises the n anchor points, μ^i*(i = 1,...,n).

We provide a Pareto frontier of a bi-objective optimization problem in Fig. 17.1. Anchor points and the Utopia point are illustrated in the figure. Please note that the design space is not normalized.

Figure 17.1. General Design Objective Space for a Bi-Objective Case

17.3 Normal Boundary Intersection Method

This section introduces the Normal Boundary Intersection (NBI) Method [1, 2] for finding several Pareto optimal points for a general nonlinear multiobjective optimization problem. This method is successful in producing an evenlydistributed set of points in the Pareto frontier, and it method can be applied to optimization problems with more than two objectives.

In Section 17.2, the Utopia point μ^u and the anchor point μ^i*are defined. We define the pay-off matrix, Φ, as follows: Φ is an n × n function whose i^th column is μ^i*-μ^u. The pay-off matrix has the following form:

The pay-off matrix translates anchor points in the design objective space. For a bi-objective design space, Fig. 17.2 shows the following: (i) in the translated coordinate system of the design objective space, the Utopia point is atthe origin, (ii) the two anchor points lie on the axes lines, and (iii) the coordinates of the two anchor points are determined by their distances from the Utopia point. For optimization problems with more than two design objectives, in the translated coordinate system of the design objective space, the Utopia point is at the origin. One coordinate of each anchor point is 0, and the other coordinates are determined by the distance between the anchor point and the Utopia point.

Figure 17.2. Translated Design Objective Space for a Bi-Objective Case

Using the pay-off matrix, the convex combinations of μ^i*-μ^u are {Φβ : β ∈ Rⁿ,∑ _i=1ⁿβ _i = 1,β_i ≥ 0}. For a bi-objective optimization problem, Φβ are the points on its Utopia line. For an optimization problem with more than twoobjectives, Φβ are the points on its Utopia hyperplane.

In the translated design objective space, let denote the unit normal to the points on the Utopia line (bi-objective) or the Utopia hyperplane (more than two objectives) toward the origin; then, Φβ +t,t ∈ R represents the set of points on that normal. The point of intersection of the normal and the Pareto frontier is the solution to the following subproblem:

subject to

The steps of the NBI method are:

1.Evaluate all the anchor points, μ^1* to μ^n*, by solving Problem PUi (i = 1, 2,...,n).

2.Generate the pay-off matrix using Eq. 17.9.

3.Generate the weights, β, so that Φβ samples the Utopia line for a bi-objective optimization problem, or samples the Utopia hyperplane for an optimization problem with more than two objectives.

4.For each set of weights, solve the optimization problem defined by Eq. 17.10 to Eq. 17.14.

Please refer to Section. 17.6 for examples.

17.4 Normalized Normal Constraint Method

This section provides the analytical development of the normalized normal constraint method [3] for multiobjective optimization problems. This section is divided into two subsections: bi-objective and multiobjective cases. Thisseparation of the bi-objective from the general multiobjective case is intended to promote clarity and simplicity of presentation.

Normalized Normal Constraint for Bi-objective Case

Figure 17.3 represents the normalized Pareto frontier in the normalized design space. In the normalized objective space, all the anchor points are one unit away from the Utopia point, and the Utopia point is at the origin. A bar over avariable implies that it is normalized.

Figure 17.3. Normalized Design Objective Space for a Bi-Objective Case

We begin with a graphical perspective of the normalized normal constraint method. Figure 17.1 illustrates the non-normalized design space and the Pareto frontier of a generic bi-objective problem. Figure 17.3 represents thenormalized Pareto frontier in the normalized design space. In the normalized objective space, all the anchor points are one unit away from the Utopia point, and the Utopia point is at the origin by definition.

We now present the normalized normal constraint method by defining a seven-step process for its application. To understand the idea of the NC method, consider Figs. 17.4 and 17.5 for the bi-objective case. In Fig. 17.4, weobserve the feasible region and the corresponding Pareto frontier. We also note that the two anchor points are obtained by successively minimizing the first and second design metrics (Problem PUi). A line joining the two anchorpoints is drawn, and is called the Utopia line. The Utopia line is divided into m₁ - 1 segments, resulting in m₁ points. In Fig. 17.5, one of the generic points intersecting the segments is used to define a normal to the Utopia line. Thisnormal line is used as an additional constraint that progressively reduces the feasible region, and generates successive Pareto solutions, as indicated in Fig. 17.5. If we minimize μ₂, the resulting optimum point is μ^*. By translatingthe normal line, a corresponding set of solutions will be generated.

Figure 17.4. A Set of Evenly Spaced Points on the Utopia Line for a Bi-Objective Problem

Figure 17.5. Graphical Representation of the Normalized Normal Constraint Method for Bi-Objective Problems

Importantly, we note that the generation of the set of Pareto points is performed in the normalized objective space, resulting in critically beneficial scaling properties. We now proceed to define the seven-step process thatformalizes the preceding description.

1.ANCHOR POINTS. Obtain the two anchor points, denoted by μ^1* and μ^2*, resulting from solving Problem PU1 and PU2, respectively. The line joining these two points is the Utopia line.

2.OBJECTIVES MAPPING/Normalization. To avoid scaling deficiencies, the optimization takes place in the normalized design metric space (design objective space). Let μ be the normalized form of μ. We define the Utopiapoint, μ^u, as

and we let l₁ and l₂ be the distances between μ^2* and μ^1*, and the Utopia point, μ^u, respectively. We have

Using the above definitions, the normalized design metrics can be evaluated as

Following the normalization of the design metrics, we can generate the Pareto points, as indicated in Figs. 17.4 and 17.5.

3.UTOPIA LINE VECTOR. Define N₁ as the vector from μ^1* to μ^2*, yielding

4.NORMALIZED INCREMENTS. Compute a normalized increment, δ₁, along the direction of N₁ for a prescribed number of solutions, m₁, as

5.GENERATE UTOPIA LINE POINTS. Evaluate a set of evenly distributed points on the Utopia line as (see Fig. 17.4)

where

Please note that α_ij is incremented by δ₁ between 0 and 1 (Fig. 17.4), and we use values of j where j ∈{1, 2,...,m₁}.

6.PARETO POINTS GENERATION. Using the set of evenly distributed points on the Utopia line, generate a corresponding set of Pareto points by solving a succession of optimization runs of Problem P2. Each optimization runcorresponds to a point on the Utopia line. Specifically, for each generated point on the Utopia line, solve for the j^th point.

Problem P2 (for j^th point) is defined as follows:

subject to

7.PARETO DESIGN METRICS VALUES. Evaluate the non-normalized design metrics that correspond to each Pareto point. This evaluation can be done in two ways. First, since the function μ(x) is known, a direct evaluation ispossible. Alternatively, if the normalized design metrics were saved from Step 6, the non-normalized design metrics can be obtained through an inverse mapping of (12) by using the relation

Up to this point, we have not considered the possibility that some of the points generated in some pathological cases might be dominated by other points in the set. This important situation is examined in Sec. 17.5, where a Paretofilter is developed.

Normalized Normal Constraint for n-Objective Case

In this section, the development of the normalized normal constraint method is presented for a general multiobjective case. This development will be terse to avoid repetition with respect to the bi-objective case. The basic steps are similar to those of the bi-objective case.

1.ANCHOR POINTS. Obtain the anchor points, μ_i. for i ∈ {1, 2,..., n}, which are obtained by solving Problem PUi. We define the hyperplane, which is comprised of all the anchor points. This plane is called the Utopiahyperplane (or Utopia plane). Figure 17.6 illustrates the Utopia plane for three design metrics. Recall that the optimum design variables obtained from solving Problem PUi are denoted by x^i*.

Figure 17.6. Utopia Hyperplane for a Three-Objective Case

2.OBJECTIVES MAPPING/Normalization. To avoid scaling deficiencies, the optimization is performed in the normalized design metric space. In order to obtain the required mapping parameters, we need to define two points: theUtopia point and the Nadir point, which are respectively evaluated as follows:

where

We define the matrix L as

which leads to the normalized design metrics as

3.UTOPIA PLANE VECTORS. Define the direction, N_k from μ^k*to μ^n*for k ∈{1, 2,...,n-1} as

4.NORMALIZED INCREMENTS. Compute a normalized increment, δ_k, along the direction N_k for a prescribed number of solutions, m_k, along the associated N_k direction.

Care must be taken in choosing the number of points, m_k, for each direction N_k. To ensure an even distribution of points on the n-dimensional Utopia plane, the following relationship can be used. Given a specified number ofpoints, m₁, along the vector N₁, m_k is given as

5.GENERATE HYPERPLANE POINTS. Evaluate a set of evenly distributed points on the Utopia hyperplane as

where

Figure 17.6 describes how generic points are generated in the Utopia plane, where two planes serve as constraints (see Eq. 17.45). Figure 17.7 shows the resulting uniformly distributed points on the Utopia plane for a three-dimensional case in the normalized objective space.

Figure 17.7. Evenly Spaced Points on the Utopia Plane for a Three-Objective Case

6.PARETO POINTS GENERATION. We generate a set of well-distributed Pareto solutions in the normalized objective space. For each value of X_pj generated in Step 5, we obtain the corresponding Pareto solution by solvingProblem P3:

subject to

In solving Problem P3 using a gradient-based algorithm, the initial point used contributes to the efficiency of the Pareto frontier generation. In the case of the normalized normal constraint method, a good choice for a startingpoint is the point X_pj. This automated scheme works well in practice.

7.PARETO DESIGN METRICS VALUES. The design metrics values for the Pareto solutions obtained in Step 6 can be obtained using the unscaling equation

17.5 Pareto Filter

As indicated earlier, under certain circumstances, the normal constraint method can generate non-Pareto solutions. This unfortunate situation can occur, for example, in the case of a feasible region depicted in Fig. 17.8. In such cases, we propose using a Pareto filter. A Pareto filter is an algorithm that, given a set of points in objective space, produces a subset of the given points for which none will be dominated by any other. That is, the filter eliminates alldominated points from the given set.

Figure 17.8. Normal Constraint Generates a Non-Pareto Solution Under a Contrived Feasible Region

To facilitate the ensuing discussion, it is important to differentiate between local Pareto optimality and global Pareto optimality. We note that a global Pareto optimal point is also a local Pareto optimal point, but the reverse is nottypically true. Two important definitions based on the concept of weak domination follow.

Definition 1: A design metric vector μ^* is globally Pareto optimal if there does not exist another design metric vector μ such that μ_j ≤ μ_j^* for all j ∈{1, 2,...,n}, and μ_j < μ_j^* for at least one index of j, j ∈{1, 2,...,n} in the feasibledesign space.

Definition 2: A design metric vector μ^* is locally Pareto optimal if there does not exist another design metric vector μ such that μ_j ≤ μ_j^* for all j ∈{1, 2,...,n}, and μ_j < μ_j^*, for at least one index of j, j ∈{1, 2,...,n} in a neighborhoodof μ^*.

Consider Fig. 17.8, in which a highly concave feasible region is depicted. Arcs AB and FG represent the (global) Pareto frontier. Regions BC and DE are local Pareto frontiers. Arcs CD and EF are neither globally nor locallyPareto. We now make the important note that generating Pareto points using the normal constraint method with the anchor points A and G will yield non-Pareto solutions. Point S, for example, a non-Pareto solution, would begenerated by the normal constraint method when the Line NU is used as the normal constraint. Using a different optimization starting point in a gradient-based scheme, we could obtain the point R. The NBI method would also suffer from this deleterious behavior.

In light of the fact that certain methods yield non-Pareto solutions, it is important to develop a means to avoid retaining dominated points in the set of solutions from which an optimum will be chosen. The Pareto filter does just that. The filter works by comparing a point on the Pareto frontier with every other generated point. If a point is not globally Pareto optimal, it is eliminated.

Figure 17.9 provides a functional diagram of the Pareto filter. A four-step process of the Pareto filter algorithm is presented in the following pseudo-code.

Figure 17.9. Pareto Filter

Figure 17.10. Flow Diagram of Pareto Filter

1.Initialize

Initialize the algorithm indices and variables: i = 0, j = 0, k = 1, and m= number of generated solutions; m = f(m_k).

2.Set i = i+ 1; j = 0.

3.(enclosed in the dashed box): Eliminate non-global Pareto points by doing the following: j = j+ 1

If i = j go to the beginning of Step 3

Else continue

If μⁱ ⁄= μ^j and (μⁱ- μ^j) _s ≥ 0,∀s

then μⁱ is not a global Pareto point.

Go to Step 4.

Else if j = m

Then i is a global Pareto point.
p^k = μⁱ
k = k+ 1
Go to Step 4.
Else go to the beginning of Step 3.

4.If i ≠ m, go to Step 2, else end.

17.6 Examples

In this section, we use the normalized normal constraint method to generate Pareto frontiers in three examples.

The first example deals with scaling issues when one design metric is orders of magnitude larger than the other, and compares the NC and (Weighted Sum) WS methods. The second example demonstrates a case in which non-Pareto points are generated, and compares the behaviors of the NC and NBI methods for the same problem. In the third example, a truss problem is used, in which we deal with a concave Pareto frontier and compare the relativebehaviors of the NC and WS methods.

Example: Consider the multiobjective optimization problem below. Generate its Pareto frontier using the normalized normal constraint method.

subject to

The normalized normal constraint method leads to the following single criterion optimization problem:

subject to

The following MATLAB code generates 21 evenly distributed points on the Pareto frontier (included in the book website www.cambridge.org/Messac).

1.Main file

clear;clc;
%Define side-constraints
lb=[];ub=[];
%Define initial guess
x0=[20 1];
%Numbers of evenly distributed points
m=21;
%Define options for FMINCON
options=optimset(’display’,’on’,’algorithm’,’active-set’);

%Initialize points for normalized NC Method
xp=[0,0];
N=[1,1];
%Optimization for separate objectives
x1=fmincon(@NNC_obj1_eg1,x0,[],[],[],[],lb,ub, ...
@NNC_con_eg1,options,xp,N);
x2=fmincon(@NNC_obj2_eg1,x0,[],[],[],[],lb,ub, ...
@NNC_con_eg1,options,xp,N);

A1=NNC_obj1_eg1(x1,xp,N);B1=NNC_obj2_eg1(x1,xp,N);
A2=NNC_obj1_eg1(x2,xp,N);B2=NNC_obj2_eg1(x2,xp,N);
N=[A2-A1 B2-B1];
delta=1/(m-1);

%initial index
k=1;
for i=0:m-1
alpha=i*delta;
xp=[alpha*A1+(1-alpha)*A2,alpha*B1+(1-alpha)*B2];
x=fmincon(@NNC_obj2_eg1,x0,[],[],[],[],lb,ub, ...
@NNC_con_eg1,options,xp,N);
x0=x;
A(k)=abs(N(1))*NNC_obj1_eg1(x,xp,N);
B(k)=abs(N(2))*NNC_obj2_eg1(x,xp,N);
k=k+1;
end
%%%%%%%%%%% Plot Pareto Frontier %%%%%%%%%%%%%
figure
plot(A,B,’.’)
axis([-1 20 -.05 1])
xlabel(’\mu1’)
ylabel(’\mu2’)

1.First Objective function file

function f=NNC_obj1_eg1(x,xp,N)
f=x(1)/abs(N(1)); %Normalized Form
end

1.Second Objective function file

function f=NNC_obj2_eg1(x,xp,N)
f=x(2)/abs(N(2)); %Normalized Form
end

1.Constraint function file

function [c,ceq]=NNC_con_eg1(x,xp,N)
x1=x(1);
x2=x(2);
c(1)=((x1-20)/20)^8+((x2-1)/1)^8-1;
ceq=[];
if xp(1)~=0
c(2)=[1,-1]*(([x1 x2]-xp)./abs(N))’;
end

Figure 17.11 shows the Pareto frontier generated by the above MATLAB code.

Figure 17.11. Pareto Frontier Using Normalized Normal Constraint

Example: Consider the multiobjective optimization problem below. Use the normalized normal constraint method and the Pareto filter to generate the Pareto frontier.

subject to

The NBI method is used to generate points on the Pareto frontier. A total of 60 evenly spaced points on the Utopia line are used. Figure 17.12(a) depicts the points on the Pareto frontier. In the figure, some points are not globallyPareto optimal.

Figure 17.12. Pareto Frontier Generated Using Normal Boundary Intersection and Normalized Normal Constraint

1.Main file

clear;clc;
%Define side-constraints
lb=[0 0 -inf];ub=[5 5 inf];
%Define initial guess
x0=[5 0 1];
%Numbers of evenly distributed points
m=61;
%Define options for FMINCON
options=optimset(’display’,’off’,’algorithm’,’active-set’);

%Initialize points for NC Method
xp=[0,0];
N=[1,1];
%Optimization for separate objectives
x1=fmincon(@NNC_obj1_eg2,x0,[],[],[],[],lb,ub, ...
@NNC_con_eg2,options,xp,N);
x2=fmincon(@NNC_obj2_eg2,x0,[],[],[],[],lb,ub, ...
@NNC_con_eg2,options,xp,N);

A1=NNC_obj1_eg2(x1,xp,N);
B1=NNC_obj2_eg2(x1,xp,N);
A2=NNC_obj1_eg2(x2,xp,N);
B2=NNC_obj2_eg2(x2,xp,N);
N=[A2-A1 B2-B1];
delta=1/(m-1);

k=1; %initial index
for i=0:m-1
alpha=i*delta;
xp=[alpha*A1+(1-alpha)*A2,alpha*B1+(1-alpha)*B2];
x=fmincon(@NNC_obj2_eg2,x0,[],[],[],[],lb,ub, ...
@NNC_con_eg2,options,xp,N);
x0=x;
A(k)=NNC_obj1_eg2(x,xp,N);
B(k)=NNC_obj2_eg2(x,xp,N);
k=k+1;
end
figure
plot(A,B,’.’);
xlabel(’\mu1’);
ylabel(’\mu2’);
title(’Normal Boundary Intersection’);

2.First Objective function file

function f=NNC_obj1_eg2(x,xp,N)
f=x(1);
end

3.Second Objective function file

function f=NNC_obj2_eg2(x,xp,N)
f=x(2);
end

4.Objective function file for subproblem

function f=NNC_obj3_eg2(x,xp,N)
t=x(3);
f=-t;
end

5.Constraint function file

function [c,ceq]=NNC_con_eg2(x,xp,N)
x1=x(1);
x2=x(2);
t=x(3);
c(1)=5*exp(-x1)+2*exp(-0.5*(x1-3)^2)-x2;
ceq=[];
if xp~=0
ceq=xp+t.*[-1, N(1)/N(2)]-[NNC_obj1_eg2(x,xp,N), ...
NNC_obj2_eg2(x,xp,N)];
end

This example can also be solved by the normalized normal constraint method, with or without using the Pareto filter. Figures 17.6 and 17.6 are generated using the normalized normal constraint method. Figure 17.6 shows the pointsgenerated before the Pareto filter is used. Some points are not globally Pareto optimal. Figure 17.6 shows the points on the Pareto frontier after the Pareto filter is used. The points on Fig. 17.6 are globally Pareto optimal.

1.Main file

clear;clc;
%Define side-constraints
lb=[0 0];ub=[5 5];
%Define initial guess
x0=[5 0];
%Numbers of evenly distributed points
m=61;
%Define options for FMINCON
options=optimset(’display’,’off’,’algorithm’,’active-set’);

%Initialize points for NC Method
xp=[0,0];
N=[1,1];
%Optimization for separate objectives
x1=fmincon(@NNC_obj1_eg2,x0,[],[],[],[],lb,ub, ...
@NNC_con_eg2,options,xp,N);
x2=fmincon(@NNC_obj2_eg2,x0,[],[],[],[],lb,ub, ...
@NNC_con_eg2,options,xp,N);

A1=NNC_obj1_eg2(x1,xp,N);B1=NNC_obj2_eg2(x1,xp,N);
A2=NNC_obj1_eg2(x2,xp,N);B2=NNC_obj2_eg2(x2,xp,N);
N=[A2-A1 B2-B1];
delta=1/(m-1);

k=1; %initial index
for i=0:m-1
alpha=i*delta;
xp=[alpha*A1+(1-alpha)*A2,alpha*B1+(1-alpha)*B2];
x=fmincon(@NNC_obj2_eg2,x0,[],[],[],[],lb,ub, ...
@NNC_con_eg2,options,xp,N);
x0=x;
A(k)=abs(N(1))*NNC_obj1_eg2(x,xp,N);
B(k)=abs(N(2))*NNC_obj2_eg2(x,xp,N);
k=k+1;
end
figure
plot(A,B,’.’);
xlabel(’\mu1’);
ylabel(’\mu2’);
title(’Normal Constraint Method without Using Pareto
Filter’);
%%%%%%%%%%% Pareto Filtering %%%%%%%%%%%%%%%%%
[mA,mB]=pareto_filter(A,B);
%%%%%%%%%%% Plot Pareto Frontier %%%%%%%%%%%%%
figure
plot(mA,mB,’.’);
xlabel(’\mu1’);
ylabel(’\mu2’);
title(’Normal Constraint Method Using Pareto Filter’);

2.First Objective function file

function f=NNC_obj1_eg2(x,xp,N)
f=x(1)/abs(N(1)); %Normalized Form
end

3.Second Objective function file

function f=NNC_obj2_eg2(x,xp,N)
f=x(2)/abs(N(2)); %Normalized Form
end

4.Constraint function file

function [c,ceq]=NNC_con_eg2(x,xp,N)
f1=x(1);f2=x(2);
c(1)=5*exp(-x(1))+2*exp(-0.5*(x(1)-3)^2)-x(2);
ceq=[];
if xp~=0
c(2)=[1,-1]*(([f1 f2]-xp)./abs(N))’;
end

5.Pareto Filter

function [mA,mB]=pareto_filter(A,B)
k=1;
m=length(A);
for i=1:m
for j=i+1:m
if A(i)<A(j)||B(i)>B(j)
break;
end
end
if j==m
p(k)=i;
k=k+1;
end
end
mA=A(p);
mB=B(p);

17.7 Summary

This chapter presents two Pareto frontier generation methods: the normal boundary intersection (NBI) method and the normalized normal constraint (NNC) method. These two methods have the ability to generate a well distributedset of Pareto points even in numerically demanding (illconditioned) situations. It is shown that, in non-convex Pareto frontier cases, the NBI method may generate non-Pareto point where the NNC method will avoid these points. All Pareto points generated by NBI will also be generated by NNC. In addition, NBI involves equality constraints while NNC involves inequality constraints, which are generally computationally favorable. This chapter also introducesthe notion of a Pareto filter, which performs the function of eliminating all but the global Pareto solutions when given a set of candidate solutions.

17.8 Problems

17.1Consider the first multiobjective optimization problem given in Sec. 17.6. Reproduce the results using the normalized normal constraint method. Also solve it using the weighted sum method. Show the figures of the Paretofrontier generated by the two methods. Turn in your M-file and results.

17.2Consider the second multiobjective optimization problem given in Sec. 17.6. Reproduce the results using the normalized normal constraint method and the Pareto filter. Turn in your M-file and results.

17.3Solve the following three-bar truss optimization problem.

We consider a three-bar truss structure from the following paper written by J Koski in 1985: Defectiveness of weighting methods in multicriterion optimization of structures. Commun. Appl. Numer. Methods 1, 333^..C337.

The structure and the loading conditions of the problem is provided in Fig. 17.13. For this particular problem, the design metrics are: (1) the volume of the structure, and (2) a linear combination of the displacements at nodeP, Δ. The design metrics are to be minimized.

Figure 17.13. Three-Bar Truss Under Static Loading

The cross sectional areas of the three-bar truss are the design variables, which are allowed to vary between 0.1 and 2 cm². The stresses in each bar are limited to 200 MPa. The length L is fixed to 100 cm. The forces, F, whichare applied at node P, have the same value of 20 kN. The modulus of elasticity of the material used is 200 GPa. Koski (1985) used a linear combination of the displacement design metric, Δ, at node P to yield nonconvexity.The coefficients of δ₁ and δ₂ are 0.25 and 0.75, respectively.

Generate the Pareto frontier using the normalized normal constraint method with the Pareto filter.

17.4Understand how the normalized normal constraint method [3] works, and use that method to duplicate the Pareto frontier shown in Fig. 16.8(a) from Chapter 16.

17.5Solve Problem 17.4 using a new version of the NNC method recently reported in Ref. [4]. Discuss any possible benefits or drawbacks.

BIBLIOGRAPHY OF CHAPTER 17

[1] I. Das and J. E. Dennis. Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM J. OPTIM., 8(3):631-657, August 1998.

[2] F. Logist and J. Van Impe. Novel insights for multi-objective optimisation in engineering using Normal Boundary Intersection and (Enhanced) Normalised Normal Constraint. Structural and Multidisciplinary Optimization, 45(3):417-431, 2012.

[3] A. Messac, A. Ismail-Yahaya, and C. A. Mattson. The normalized normal constraint method for generating the Pareto Frontier. Structural and Multidisciplinary Optimization, 25(2):86-98, 2003.

[4] B. J. Hancock and C. A. Mattson. The smart normal constraint method for directly generating a smart Pareto set. Structural and Multidisciplinary Optimization, 48(4):763-775, 2013.