Duality in Solving Multi-Objective Optimization (MOO) Problems

Chandra Sen

Department of Agricultural Economics, Institute of Agricultural Sciences, Banaras Hindu University, Varanasi, India.

DOI: 10.4236/ajor.2019.93006                

Abstract

Multi-Objective Optimization (MOO) techniques often achieve the combination of both maximization and minimization objectives. The study suggests scalarizing the multi-objective functions simpler using duality. An example of four objective functions has been solved using duality with satisfactory results.

Keywords

Duality, Multi-Objective Optimization (MOO), Scalarizing Techniques

1. Introduction

Multi-Objective Optimization helps in making decisions in presence of usually conflicting objectives. Scalarizing techniques have been popularly used for solving multi-objective optimization problems. Several new scalarizing techniques [1] - [11] have been proposed during recent years. These scalarizing techniques are not efficient [12] [13] in optimizing the multiple objectives simultaneously. An improved scalarizing technique is proposed for solving MOO problems. Duality can be used to formulate the multi-objective function easier. The present study explains the utility of duality in solving multi-objective optimization problem with a suitable example.

2. Sen’s Multi-Objective Optimization Technique

2.1. Primal Multi-Objective Function

The mathematical form of Sen’s MOO technique [12] [13] is described as:

Optimize $Z=\left[\text{Max}.Z_1,\text{Max}\text{.}{Z}_2,\cdots ,\text{Max}\text{.}{Z}_r,\text{Min}\text{.}{Z}_{r+1},\cdots ,\text{Min}\text{.}{Z}_s\right]$

Subject to:

$AX=b$ and $X\ge 0$

The individual optima are obtained by optimizing each objective separately as:

$Z_{\text{optima}}=\left[{\theta }_1,{\theta }_2,\cdots ,{\theta }_s\right]$

The Primal Multi-Objective Function is formulated as:

Maximize $Z=\frac{{\displaystyle {\sum }_{j=1}^r{Z}_j}}{\left|{\theta }_j\right|}-\frac{{\displaystyle {\sum }_{j=r+1}^s{Z}_j}}{\left|{\theta }_{r+1}\right|}$

Subject to:

$AX=b$ and $X\ge 0$

${\theta }_j\ne 0$ for $j=1,2,\cdots ,s$ .

where, ${\theta }_j$ is the optimal value of jth objective function.

2.2. Dual Multi-Objective Function

All the objective functions are converted into either maximizing or minimizing form as described below:

Maximize Z_j or Minimize Z_j

Subject to:

$AX=b$ and $X\ge 0$

The minimization objective function can be converted into maximization objective function by multiplying −1. Similarly the maximization objective can be converted into minimization objective function by multiplying −1. The Multi-Objective Function is formulated as:

Maximize $Z=\frac{{\displaystyle {\sum }_{j=1}^s{Z}_j}}{\left|{\theta }_j\right|}$

or

Minimize $Z=\frac{{\displaystyle {\sum }_{j=1}^s{Z}_j}}{\left|{\theta }_j\right|}$

Subject to:

$AX=b$ and $X\ge 0$

${\theta }_j\ne 0$ for $j=1,2,\cdots ,s$ .

where, ${\theta }_j$ is the optimal value of jth objective function.

3. Algorithm of Proposed Technique

Step I: Convert all the objective functions either maximization of minimization mode.

Step II: Formulate multi-objective function as explained in 2.2

Step III: Optimize the multi-objective function under the same constraints.

4. Multi-Objective Optimization Problem

The following example has been solved with duality technique.

Example

$\text{Max}.Z_1=12500X_1+25100X_2+16700X_3+23300X_4+20200X_5$

$\text{Max}.Z_2=21X_1+15X_2+13X_3+17X_4+11X_5$

$\text{Min}.Z_3=370X_1+280X_2+350X_3+270X_4+240X_5$

$\text{Min}.Z_4=1930X_1+1790X_2+1520X_3+1690X_4+1720X_5$

Subject to:

$X_1+X_2+X_3+X_4+X_5=4.5$

$2X_1\ge 1.0$

$3X_4\ge 1.5$

The above problem can be converted with all the four objective functions either maximization of minimization mode as detailed below:

$\text{Max}.Z_1=12500X_1+25100X_2+16700X_3+23300X_4+20200X_5$

$\text{Max}.Z_2=21X_1+15X_2+13X_3+17X_4+11X_5$

$\text{Max}.Z_3=-370X_1-280X_2-350X_3-270X_4-240X_5$

$\text{Max}.Z_4=-1930X_1-1790X_2-1520X_3-1690X_4-1720X_5$

or

$\text{Min}.Z_1=-12500X_1-25100X_2-16700X_3-23300X_4-20200X_5$

$\text{Min}.Z_2=-21X_1-15X_2-13X_3-17X_4-11X_5$

$\text{Min}.Z_3=370X_1+280X_2+350X_3+270X_4+240X_5$

$\text{Min}.Z_4=1930X_1+1790X_2+1520X_3+1690X_4+1720X_5$

The problem was solved with multi-objective function of both maximization and minimization mode. It is very clear from Table 1 that all the four individual optimizations are all different and do not achieve all the objectives simultaneously.

This necessitates the need of multi-objective optimization. Both the solutions of multi-objective optimization are exactly the same and achieving all the four objectives simultaneously. Hence the multi-objective optimization problems can be solved by formulating multi-objective function after converting all the objective functions in either maximizing or minimizing mode.

Table 1. Individual and multi-objective optimization.

5. Conclusion

One of the important advantages of the duality theory is presented in the paper for solving MOO problems. It is established that duality makes easier the formulation of multi-objective function. However, it is needed only when optimization is done for a set of both maximization and minimization objective functions.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Sulaiman, N.A. and Hamadameen, A.-Q.O. (2008) Optimal Transformation Technique to Solve Multi-Objective Linear Programming Problem (MOLPP). Journal of Kirkuk University Scientific Studies, 3, 158-168.
[2]	Suleiman, N.A. and Nawkhass, M.A. (2013) Transforming and Solving Multi-Objective Quadratic Fractional Programming Problems by Optimal Average of Maximin & Minimax Techniques. American Journal of Operational Research, 3, 92-98.
[3]	Sulaiman, N.A. and Mustafa, R.B. (2016) Using Harmonic Mean to Solve Multi-Objective Linear Programming Problems. American Journal of Operations Research, 6, 25-30. https://doi.org/10.4236/ajor.2016.61004
[4]	Sulaiman, N.A. and Mustafa, R.B. (2016) Transform Extreme Point Multi-Objective Linear Programming Problem to Extreme Point Single Objective Linear Programming Problem by Using Harmonic Mean. Applied Mathematics, 6, 95-99.
[5]	Huma, A., Geeta, M. and Sushma, D. (2017) Transforming and Optimizing Multi-Objective Quadratic Fractional Programming Problem. International Journal of Statistics and Applied Mathematics, 2, 01-05.
[6]	Nahar, S. and Alim, A. (2017) A New Statistical Averaging Method to Solve Multi-Objective Linear Programming Problem. International Journal of Science and Research, 6, 623-629.
[7]	Huma, A., Modi, G. and Duraphe, S. (2017) An Appropriate Approach for Transforming and Optimizing Multi-Objective Quadratic Fractional Programming Problem. International Journal of Mathematics Trends and Technology, 50, 80-83. https://doi.org/10.14445/22315373/IJMTT-V50P511
[8]	Nawkhass, M.A. and Birdawod, H.Q. (2017) Transformed and Solving Multi-Objective Linear Programming Problems to Single-Objective by Using Correlation Technique. Cihan International Journal of Social Science, 1, 30-36.
[9]	Akhtar, H. and Modi, G. (2017) An Approach for Solving Multi-Objective Fractional Programming Problem and It’s Comparison with Other Techniques. International Journal of Scientific and Innovative Mathematical Research, 5, 1-5. https://doi.org/10.20431/2347-3142.0511001
[10]	Nahar, S. and Alim, A. (2017) A New Geometric Average Technique to Solve Multi-Objective Linear Fractional Programming Problem and Comparison with New Arithmetic Average Technique. IOSR Journal of Mathematics (IOSR-JM), 13, 39-52. https://doi.org/10.9790/5728-1303013952
[11]	Sohag, Z.I. and Asadujjaman, Md. (2018) A Proposed New Average Method for Solving Multi-Objective Linear Programming Problem Using Various Kinds of Mean Techniques. Mathematics Letters, 4, 25-33. https://doi.org/10.11648/j.ml.20180402.11
[12]	Sen, C. (2018) Multi Objective Optimization Techniques: Misconceptions and Clarifications. International Journal of Scientific and Innovative Mathematical Research, 6, 29-33.
[13]	Sen, C. (2018) Sen’s Multi-Objective Programming Method and Its Comparison with Other Techniques. American Journal of Operational Research, 8, 10-13.