Skip to content

9. Multiobjective optimization problems

Jump to bottom
Marsha Gómez edited this page May 25, 2023 · 12 revisions

Exercises Chapter 9

9.1 Linear Programming

Exercise 9.1. Consider the linear multiobjective problem:

$$\left\lbrace \begin{array}{ll} \mathrm{minimize} & \left(x_1 +2x_2 -3x_3 \right),\left({-x}_1 -x_2 -x_3 \right),\left(-4x_1 -2x_2 +x_3 \right)\\ \mathrm{subject}\ \mathrm{to} & x_1 +x_2 +x_3 \le 10\\ \ & x_3 \le 5\\ \ & -x_1 \le 0\\ \ & -x_2 \le 0\\ \ & -x_3 \le 0 \end{array}\right.$$

Check if the points u = (5, 0, 5), v = (4, 4, 2) and w = (1, 4, 4) are minima or weak minima by solving the corresponding auxiliary problems.

close all;
clear;
clc;

matlab.lang.OnOffSwitchState = 1;

x1 = -10:0.1:10;
x2 = -10:0.1:10;

[X1,X2] = meshgrid(x1,x2);

X3 = (X1+2.*X2)/3;
X4 = (-X1-X2);
X5 = (4.*X1+2.*X2);
surface(X1,X2,X3, 'FaceAlpha',0.5);
hold on
surface(X1,X2,X4,'FaceAlpha',0.2);
surface(X1,X2,X5, 'FaceAlpha',0.7);
view(3);
hold off

Output

% Environment Variables
C = [ 1  2 -3
     -1 -1 -1
     -4 -2  1];

A = [ 1  1  1
      0  0  1
     -1  0  0
      0 -1  0
      0  0 -1];

b = [10
      5
      0
      0
      0];

u = [5
     0
     5];

v = [4
     4
     2];

w = [1
     4
     4];

y = v;

% Variables number
n = size(C,2);
% Functions number
p = size(C,1);
% Constraints number
m = size(A,1);

% Calculate the linear Problem

c = [zeros(n,1)
    -ones(p,1)];

P = [C           eye(p)
     A           zeros(m,n)
     zeros(p,n) -eye(p)];

q = [C*y
     b
     zeros(p,1)];

% Solve the Linear Programming check minimum
options = optimset('Display', 'off');
[~, minimum] = linprog(c,P,q, [],[],[],[],options)

% Solve the Linear Programming check weak minimum

c = [zeros(n,1)
     zeros(p,1)
     -1];

P = [zeros(p,n)  -eye(p)    ones(p,1)
     C           eye(p)     zeros(p,1)
     A           zeros(m,n) zeros(m,1)
     zeros(p,n) -eye(p)     zeros(p,1)];

q = [zeros(p,1)
     C*y
     b
     zeros(p,1)];

[~, minimum_weak] = linprog(c,P,q, [],[],[],[],options)
Point Minimum Weak Minimum
(4,4,2) -13.00 0.00
(5,0,5) 0.00 0.00
(1,4,4) -16.75 -1.00

Alternative and Manual verification

Check the point $x^{\star } =\left(5,0\ldotp 5\right)$. Calculate $f\left(x^{\star } \right)$

x1 = 5;
x2 = 0;
x3 = 5;

f1 = x1+2.*x2-3.*x3;
f2 = -x1-x2-x3;
f3 = -4.*x1-2.*x2+x3;

f_xopt = [f1 f2 f3]

The corresponding auxiliary problem with $f\left(x^{\star } \right)=\left(-10,-10,-15\right)$

$$\left\lbrace \begin{array}{lll} -\mathrm{minimize} & -v & \\ s\ldotp t & x_1 +2x_2 -3x_3 +\varepsilon_1 & \le -10\\ & -x_1 -x_2 -x_3 +\varepsilon_2 & \le -10\\ & -4x_1 -2x_2 +x_3 +\varepsilon_3 & \le -15\\ & x_1 +x_2 +x_3 & \le 10\\ & x_3 & \le 5\\ & x_1 \ldotp x_2 ,x_3 & \ge 0\\ & \varepsilon_1 ,\varepsilon_2 ,\varepsilon_3 & \ge 0\\ & -v & \le \varepsilon_i \end{array}\right.$$

A = [ 1  2 -3  1  0  0  0
     -1 -1 -1  0  1  0  0
     -4 -2  1  0  0  1  0
      1  1  1  0  0  0  0
      0  0  1  0  0  0  0
      0  0  0 -1  0  0  0
      0  0  0  0 -1  0  0
      0  0  0  0  0 -1  0
     -1  0  0  0  0  0  1
      0 -1  0  0  0  0  1
      0  0 -1  0  0  0  1];

b = [-10
     -10
     -15
      10 
       5
       0 
       0
       0
       0
       0
       0];

f = [0
     0
     0
     0
     0
     0
    -1];

lb = [0
      0
      0
      0
      0
      0
     -inf];

[x, fval] = linprog(f,A,b, [], [], lb);
x
fval

Output


f_xopt = 1×3    
   -10   -10   -15


Optimal solution found

x = 7×1    
    5.0000
         0
    5.0000
         0
         0
         0
         0

fval = 0

9.4 Linear Programming. Scalarization Method

Exercise 9.4. Consider the linear multiobjective problem:

$$\left\lbrace \begin{array}{ll} \mathrm{minimize} & \left(x_1 -x_2 \right),\left(x_1 +x_2 \right)\\ \mathrm{subject}\ \mathrm{to} & -2x_1 +x_2 \le 0\\ \ & -x_1 -x_2 \le 0\\ \ & 5x_1 -x_2 \le 6 \end{array}\right.$$

Find the set of minima and weak minima by means of the scalarization method:

close all;
clear;
clc;

matlab.lang.OnOffSwitchState = 1;


% Plot Graph

x1 = -10:0.1:10;
x2 = -10:0.1:10;

[X1,X2] = meshgrid(x1,x2);

X3 = X1-X2;
X4 = X1+X2;

surface(X1,X2,X3);
hold on
surface(X1,X2,X4);
view(3)
hold off

Output

% 2D plot X1
x1 = x2;
plot(x1,x2);

Output

% 2D plot X2
x2 = -x1;
plot(x1,x2);

Output

% Feasible Area
x1 = -10:0.1:10;
x2 = -10:0.1:10;

[X1, X2] = meshgrid(x1,x2);

condition_x1 = X1((X2 <= 2*X1) & (-X1 - X2 <= 0) & (5*X1 - X2 <= 6));
condition_x2 = X2((X2 <= 2*X1) & (-X1 - X2 <= 0) & (5*X1 - X2 <= 6));

plot(condition_x1, condition_x2, '.');
hold on
plot([0 2],[0 4],'-k');
plot([2 1],[4 -1],'-k');
plot([1 0],[-1 0],'-k');

Output

% Linear Multiobjective problem. Scalarization Method

C = [1 -1
     1  1];

A = [-2  1
     -1 -1
      5 -1];

b = [0
     0
     6];

% Calculate different Alpha
options = optimset('Display', 'off');
for alpha = 0.001:0.001:0.999
    f = [1
         1-2*alpha];
  
    x = linprog(f,A,b, [], [], [],[], options);
    plot(x(1),x(2), 'r.');
end

fprintf('Alpha 0 \n');
alpha = 0;
f = [1
     1-2*alpha];

x0 = linprog(f,A,b, [], [], [],[], options);
plot(x0(1), x0(2), 'ko');


alpha = 1;

f = [1
    1-2*alpha];

x1 = linprog(f,A,b, [], [], [], [], options);
plot(x1(1), x1(2), 'bo');
hold off

Output

9.5 Nonlinear Programming. Scalarization Method

Exercise 9.5. Consider the nonlinear multiobjective problem:

$$\left\lbrace \begin{array}{ll} \mathrm{minimize} & \left(x_1 \right),\left(x_1^2 +x_2^2 -2x_1 \right)\\ \mathrm{subject}\ \mathrm{to} & -x_1 \le 0\\ \ & -x_2 \le 0\\ \ & x_1 +x_2 \le 2 \end{array}\right.$$

  • a) Find the set of weak minima by means of the scalarization method.
  • b) What is the set of minima?
close all;
clear;
clc;

matlab.lang.OnOffSwitchState = 1;

x1 = 0:0.1:10;
x2 = 0:0.1:10;

[X1, X2] = meshgrid(x1,x2);

X3 = X1;
X4 = X1.^2 + X2.^2 -2.*X1;

surface(X1,X2,X3);
hold on
surface(X1,X2,X4);
view(3);
hold off

Output

% 2D
x4 = sqrt(-x1.^2 + 2.*x1);
x3 = x1;

plot(x1,x4);
hold on
plot(x1,x3);
hold off

Output

condition_x1 = X1((-X1<=0) & (-X2<=0) & (X1+X2<=2)); 
condition_x2 = X2((-X1<=0) & (-X2<=0) & (X1+X2<=2));

plot(condition_x1, condition_x2, 'b.');

hold on

Q = [2 0
     0 2];

c = [-2
      0];

A = [ -1  0
       0 -1
       1  1];

b = [0
     0
     2];

options = optimset('Display', 'off');

for alpha = 0.001:0.001:0.999
    Q_alpha = Q*alpha;
    c_alpha = [1-3*alpha ; 0];
    x = quadprog(Q_alpha, c_alpha, A,b,[],[],[],[],[],options);
    plot(x(1), x(2), 'r.');
end

% Alpha 0
alpha = 0;
Q_alpha = Q*alpha;
c_alpha = [1-3*alpha ; 0];
x = quadprog(Q_alpha, c_alpha, A,b,[],[],[],[],[],options);
plot(x(1), x(2), 'ro');

% Alpha 1
alpha = 1;
Q_alpha = Q*alpha;
c_alpha = [1-3*alpha ; 0];
x = quadprog(Q_alpha, c_alpha, A,b,[],[],[],[],[],options);
plot(x(1), x(2), 'go');

hold off

Output

9.6 Noninear Programming. Scalarization Method

Exercise 9.6. Consider the nonlinear multiobjective problem:

$$\left\lbrace \begin{array}{ll} \mathrm{minimize} & \left(x_1^2 +x_2^2 +2x_1 -2x_2 \right),\left(x_1^2 +x_2^2 -6x_1 -4x_2 \right)\\ \mathrm{subject}\ \mathrm{to} & -x_2 \le 0\\ \ & -2x_1 +x_2 \le 0\\ \ & 2x_1 +x_2 \le 4 \end{array}\right.$$

Find the set of minima and weak minima by means of the scalarization method.

close all;
clear;
clc;

matlab.lang.OnOffSwitchState = 1;

% Plot of data 
x1 = -10:0.1:10;
x2 = -10:0.1:10;


[X1,X2] = meshgrid(x1,x2);

X3 = X1.^2 + X2.^2 + 2.*X1 - 4.*X2;
X4 = X1.^2 + X2.^2 - 6.*X1 - 4.*X2;

surface(X1,X2,X3);
hold on
surface(X1,X2,X4);
view(3);
hold off

Output

% Check convexity
Q1 = [2 0
      0 2];

f1 = [2
     -4];

Q2 = [2 0
      0 2];

f2 = [-6
      -4];

eigenvalue_1 = eig(Q1)
eigenvalue_2 = eig(Q1)
eigenvalue_1 eigenvalue_2
2 2
2 2 
% Feasible region
x1 = -10:0.02:10;
x2 = -10:0.02:10;


[X1,X2] = meshgrid(x1,x2);

condition_x1 = X1((-X2<=0) & (-2.*X1 + X2<=0) & (2.*X1+X2<=4));
condition_x2 = X2((-X2<=0) & (-2.*X1 + X2<=0) & (2.*X1+X2<=4));

plot(condition_x1, condition_x2, 'b.');

Output

% Set the environment values
A = [0 -1
    -2  1
     2  1];

b = [0
     0
     4];

% Set the problem
options = optimset('Display', 'off');

hold on
for alpha = 0.001:0.001:0.999
    f = [8*alpha-6
         -4];
    x = quadprog(Q1,f, A, b, [], [], [], [], [], options);
    plot(x(1), x(2), 'r.');
end

% Extreme alpha
% alpha = 0;
x0 = quadprog(Q2, f2, A, b, [], [], [], [], [], options);
plot(x0(1), x0(2), 'go');

%alpha = 1;
x1 = quadprog(Q1, f1, A, b, [], [], [], [], [], options);
plot(x1(1), x1(2), 'ko');

hold off

Output

9.7 Linear Programming. Goal Method

Exercise 9.7. Consider the linear multiobjective problem:

$$\left\lbrace \begin{array}{ll} \mathrm{minimize} & \left(x_1 +2x_2 -3x_3 \right),\left(-x_1 -x_2 -x_3 \right),\left(-4x_1 -2x_2 +x_3 \right)\\ \mathrm{subject}\ \mathrm{to} & x_1 +x_2 +x_3 \le 10\\ \ & x_3 \le 5\\ \ & x_1 \ge 0\\ \ & x_2 \ge 0\\ \ & x_3 \ge 0 \end{array}\right.$$

  • a) Find the ideal point.
  • b) Apply the goal method with s = 1.
  • c) Apply the goal method with s = 2.
  • d) Apply the goal method with s = +∞. Is the found point a minimum?
close all;
clear;
clc;
matlab.lang.OnOffSwitchState = 1;


C = [ 1  2 -3
     -1 -1 -1
     -4 -2  1];

A = [ 1  1  1
      0  0  1
     -1  0  0
      0 -1  0
      0  0 -1];

b = [10
      5
      0
      0
      0];

n = size(C,2); 
p = size(C,1);
m = size(A,1);

% Find the ideal point

options = optimset('Display', 'off');
z = zeros(p,1);

for i = 1:p
    [~,z(i)] = linprog(C(i,:), A, b, [],[],[],[],options);
end
% Apply the goal method with s = 1. 

c = [zeros(n,1)
     ones(p,1)];

P = [C -eye(p)
    -C -eye(p)
     A zeros(m,p)];

q = [z
    -z
     b];

solution_1 = linprog(c, P,q, [],[],[],[],options);
y_1 = solution_1(1:n);
% Apply the goal method with s = 2. 
H = C'*C;
f = C'*z;

solution_2 = quadprog(H,f,A,b, [], [], [],[],[],options);
y_2 = solution_2(1:n);
% Apply the goal method with s = +∞. Is the found point a minimum?
c = [zeros(n,1)
     1];

P = [C -ones(p,1)
    -C -ones(p,1)
     A zeros(m,1)];

q = [z
    -z
     b];

solution_inf = linprog(c,P,q,[],[],[],[],options);
y_inf = solution_inf(1:n);

c = [zeros(n,1) ; -ones(p,1)] ;
P = [C eye(p); 
     A zeros(m,p) ; 
     zeros(n,n) -eye(p)] ;
q = [C*y_inf ; b ; zeros(p,1)] ;
[~,v_minimum] = linprog(c,P,q,[],[],[],[],[],options)
Clone this wiki locally