Back
 JAMP  Vol.5 No.11 , November 2017
A Quadratic Programming with Triangular Fuzzy Numbers
Abstract: Quadratic Programming (QP) is a mathematical modeling technique designed to optimize the usage of limited resources and has been widely applied to solve real world problems. In conventional quadratic programming model the parameters are known constants. However in many practical situations, it is not reasonable to require that the constraints or the objective function in quadratic programming problems be specified in precise, crisp terms. In such situations, it is desirable to use some type of Fuzzy Quadratic Programming (FQP) problem. In this paper a new approach is proposed to derive the fuzzy objective value of fuzzy quadratic programming problem, where the constraints coefficients and the right-hand sides are all triangular fuzzy numbers. The proposed method is solved using MATLABTM toolbox and the numerical results are presented.

1. Introduction

Quadratic programming is a particular kind of nonlinear programming. There are several classes of problems that are naturally expressed as quadratic problems. Examples of such problems can be found in game theory, engineering modeling, design and control, problems involving economies of scale, facility allocation and location problems, etc. Several applications and test problems for quadratic programming can be found in [1] [2] [3] [4] [5] . Some traditional methods are available in the literature [6] [7] for solving such problems. Among the several applications, the portfolio selection problem is an important research field in modern finance. This problem was first introduced by Markowitz [8] [9] , and provided a risk investment analysis. Some works about portfolio selection problem by using fuzzy approaches can be found in [10] [11] [12] [13] [14] .

The classical quadratic programming problem is to find the minimum or maximum values of a quadratic function under constraints represented by linear inequality or equations. The most typical quadratic programming problem is:

maximaize ( orminimize ) j = 1 n c j x j + 1 2 i = 1 n j = 1 n q i j x i x j subject to { j = 1 n a i j x j b i , i N m x j 0 , i N m (1.1)

The function to be minimized (or maximized) is called an objective function; let us denote it by z . The numbers c j , j N n are called cost coefficients and the vector c = ( c 1 , c 2 , , c n ) is called a cost vector. The vector b T = ( b 1 , b 2 , , b m ) is called a right-hand side vector and the matrix A = [ a i j ] m × n , where i N m and j N n , is called a constraint matrix. The matrix Q = [ q i j ] m × n , is called the matrix of quadratic form where i N n and j N n . Using this notation, the formulation of the problem can be simplified as:

max z = c x + 1 2 x T Q x s .t . { A x b x 0 (1.2)

where x = ( x 1 , x 2 , , x n ) T is a vector of variables and s.t. stands for “subject to”. In the following example, a quadratic programming problem is addressed:

Example 1.1: Consider a problem which is formulated as follows:

max z = 2 x 1 + x 2 + 2 x 1 2 + x 1 x 2 + 2 x 2 2 s .t . { x 1 + x 2 2 2 x 1 + 3 x 2 1 x 1 , x 2 0 (1.3)

in which Q = [ 4 1 1 4 ] , c = ( 2 , 1 ) , A = [ 1 1 2 3 ] and b T = ( 2 , 1 ) . Hence it can be

rewritten as

follows:

max z = ( 2 , 1 ) [ x 1 x 2 ] + [ x 1 x 2 ] [ 4 1 1 4 ] [ x 1 x 2 ] s .t . { [ 1 1 2 3 ] [ x 1 x 2 ] [ 2 1 ] x 1 , x 2 0 (1.4)

The paper is organized in 5 sections. In the next section some necessary notations and definitions of fuzzy set theory and fuzzy arithmetic are given. In Section 3, we first define a quadratic programming problem and then give a new approach to solve these problems. In Section 4, a numerical example is presented to illustrate how to apply the concept of this paper for solving such quadratic programming problems. Finally we conclude in Section 5.

2. Arithmetic on Fuzzy Numbers

Here, we first give some necessary definitions of fuzzy set theory which is taken from [15] [16] [17] .

Definition 2.1: Let R be the real line, then a fuzzy set A in R is defined to be a set of ordered pairs A = { ( x , μ A ( x ) ) | x R } , where μ A ( x ) is called the membership function for the fuzzy set. The membership function maps each element of R to a membership value between 0 and 1.

Definition 2.2: The support of a fuzzy set A is defined as fallow:

s u p p ( A ) = { x R | μ A ( x ) > 0 }

Definition 2.3: The core of a fuzzy set is the set of all points x in R with μ A ( x ) = 1 .

Definition 2.4: A fuzzy set A is called normal if its core is nonempty. In other words, there is at least one point x R with μ A ( x ) = 1 .

Definition 2.5: The α-cut or α-level set of a fuzzy set is a crisp set defined by

A α = { x R | μ A ( x ) > α } .

Definition 2.6: A fuzzy set A on R is convex, if for any x , y R and λ [ 0 , 1 ] , we have

μ A ( λ x + ( 1 λ ) y ) min { μ A ( x ) , μ A ( y ) }

Definition 2.7: A fuzzy number a ¯ is a fuzzy set on the real line that satisfies the condition of normality and convexity.

Definition 2.8: A fuzzy number a ˜ on R is said to be triangular fuzzy number, if there exist real numbers and l , r 0 such that

a ˜ ( x ) = { x l + l s l , x [ s l , s ] x r + s + r r , x [ s , s + r ] 0 , o .w .

We denote a triangular fuzzy number a ˜ by three real numbers s , l and r as a ˜ = s , l , r , whose meaning are defined in Figure 1. We also denote the set of all triangular fuzzy numbers with F(R).

Definition 2.9: Let a ˜ = s a , l a , r a and b ˜ = s b , l b , r b be two triangular numbers and x R . Summation and multiplication of fuzzy numbers defined as [18] :

x a ˜ = { x s a , x l a , x r a , x 0 x s a , x r a , x l a , x < 0

Figure 1. Fuzzy Triangular Number.

a ˜ + b ˜ = s a + s b , l a + l b , r a + r b

a ˜ b ˜ = s a s b , l a r b , r a l b

a ˜ b ˜ if and only if s a s b , s a l a s b l b , s a + r a s b + r b

Definition 2.10: We let 0 ˜ = ( 0 , 0 , 0 ) as a zero triangular fuzzy number.

Remark 2.1: a ˜ 0 ˜ if and only if s a 0 , s a l a 0 , s a + r a 0 .

Remark 2.2: a ˜ b ˜ if and only if a ˜ b ˜ .

3. Fuzzy Numbers Quadratic Programming

Here we first define the model and then propose a novel method for solving the mentioned problem.

3.1. Definition of Model

Several studies have developed efficient and effective algorithms for solving quadratic programming when the value assigned to each parameter is a known constant. However, quadratic programming models usually are formulated to find some future course of action so the parameter values used would be based on a prediction of future conditions which inevitably involves some degree of uncertainty [19] [20] . The most general type of this programming is formulated as follows:

max z = j = 1 n C ˜ j X ˜ j + 1 2 i = 1 n j = 1 n Q ˜ i j X ˜ i X ˜ j s .t . { j = 1 n A ˜ i j X ˜ j B ˜ i , i N m , X ˜ 0 (3.1)

where A ˜ i j , B ˜ i , C ˜ j and Q ˜ i j are fuzzy numbers, and X ˜ j are variables whose states are fuzzy numbers ( i N m , j N n ) ; the operations of addition and multiplication are operations of fuzzy arithmetic, and denotes the ordering of fuzzy numbers. Here instead of discussing this general type, we consider a special case of fuzzy quadratic programming problem in which only the right-hand side parameters and constraint coefficient are triangular fuzzy numbers.

max z = j = 1 n c j x j + 1 2 i = 1 n j = 1 n q i j x i x j s .t . { j = 1 n A ˜ i j x j B ˜ i , i N m , x 0 (3.2)

3.2. The New Approach

In this case we assume that all fuzzy numbers are triangular. According to Definition 2.8, the fuzzy quadratic programming (3.2) is rewritten as follows:

max z = j = 1 n c j x j + 1 2 i = 1 n j = 1 n q i j x i x j s .t . { j = 1 n a i j , l i j , r i j x j b i , u i , v i , i N m x j 0 , j N n (3.3)

where A ˜ i j = a i j , l i j , r i j and B ˜ i = b i , u i , v i are fuzzy numbers. According to Definition 2.9, the constraint j = 1 n a i j , l i j , r i j x j b i , u i , v i , i N m yields that:

j = 1 n a i j x j b i , j = 1 n ( a i j l i j ) x j b i u i and j = 1 n ( a i j + r i j ) x j b i + v i , i N m

Substituting these relations in to (3.3) the conventional quadratic program is derived as follows:

max z = j = 1 n c j x j + 1 2 i = 1 n j = 1 n q i j x i x j j = 1 n a i j x j b i , i N m j = 1 n ( a i j l i j ) x j b i u i , i N m j = 1 n ( a i j + r i j ) x j b i + v i , i N m x j 0 , j N n (3.4)

However, since all numbers involved are real numbers, this is classical quadratic programming problem which can be solved using MATLABTM toolbox. The SQP algorithm is used as an optimization method to minimize the nonlinear constrained optimization problem. This method is described as follow:

3.3. The SQP Algorithm

SQP is an iterative analytical nonlinear programming method. This technique begins from an initial point to find a solution using the gradient based information. This optimization method is found [21] faster than other population based search algorithms. Although the SQP method is highly dependent on the initial estimate of the solution [22] [23] , this has successfully been applied in some [24] [25] optimal control problems. The SQP method is based on an iterative formulation together with the solution of some other quadratic programming sub-problems. An optimization problem in the SQP method is considered as follows:

minimize J ( x ) subjected to : ψ i ( x ) 0 , i = 1 , , m (3.5)

where J ( x ) is the cost function and ψ i ( x ) stands for the constraint. In this regard a Lagrangian function L ( x , λ ) is constructed in terms of the Lagrangian multiplier λ i . The cost function together with the above constraint is defined as follows:

L ( x , λ ) = J ( x ) + i = 1 m λ i ψ i ( x ) (3.6)

In fact the SQP consists of three main parts:

1- Update the Hessian of the Lagrangian function according to:

H k + 1 = H k + q k q k T q k T S k H k T H k S k T H k S k H 0 = I S k = X k + 1 X k q k = f ( X k + 1 ) + i = 1 n λ i g i ( X k + 1 ) ( f ( X k ) + i = 1 n λ i g i ( X k ) ) (3.7)

2- Solve the quadratic programming sub-problem:

min 1 2 q k T H k d k + f ( x k ) T d k ψ i ( x k ) T d k + ψ i ( x k ) = 0 , i = 1 , , m ψ i ( x k ) T d k + ψ i ( x k ) 0 , i = 1 , , m (3.8)

3- A linear search to find a solution for the next iteration:

X k + 1 = X k + α d k (3.9)

The algorithm is repeated until a stopping criterion (either maximum iteration or convergence criterion) is met. It must be mentioned that the SQP algorithm is a gradient based algorithm. Generally gradient based methods have the possibility of getting trapped at local optimum depending on the initial guess of the solution. In order to achieve a good final result, these methods require very good initial guesses of the solution. Since the matrix Q is supposed symmetric ( q i j = q j i ) and semidefinite, the objective function is convex and thus the SQP algorithm yields the global optimum solution. The corresponding theorem is presented as follows:

Theorem 3.1: In mathematical terminology, f ( x 1 , x 2 , , x n ) is convex if and only if its n × n Hessian matrix is positive semi definite for all possible values of ( x 1 , x 2 , , x n ) . That is for any x 0 the following relation is satisfied:

( x 1 , x 2 , , x n ) [ 2 f x 1 2 2 f x n x 1 2 f x 1 x n 2 f x n 2 ] ( x 1 x 2 x n ) 0 , ( x 1 , x 2 , , x n ) n

in which H ( x ) = [ 2 f x 1 2 2 f x n x 1 2 f x 1 x n 2 f x n 2 ] = [ 2 f x j x i ] n × n is the Hessian matrix of

function f . Hence the above relation can be rewritten as follow:

x T H ( x ) x 0 , x n

Proof: See in [26] .

4. An Example

In this section, we utilize an example to illustrate the solution method proposed in this paper. Consider a river from which diversions are made to three water- consuming firms that belong to the same corporation, as illustrated in Figure 1 Each firm makes a product, and is the critical resource. Water is needed in the process of making that product, and it is critical resource. The three firms can be denoted by the index j = 1 , 2 , 3 and their water allocations by x j . Assume the problem is to determine the allocations x j of water to each of three firms ( j = 1 , 2 , 3 ) that maximize the total net benefits, j N B j ( x j ) , obtained from all three firms. The total amount of water available is constrained or limited to a quantity of Q. Assume the net benefits N B j ( x j ) , derived from water x j allocated to each firm j , are defined by:

N B 1 ( x 1 ) = x 1 + 0.5 x 1 2 (4.1)

N B 2 ( x 2 ) = 2 x 2 + x 2 2 (4.2)

N B 3 ( x 3 ) = x 3 + 1.5 x 3 2 (4.3)

The problem is to find the allocations of water to each firm that maximize the total benefits T B ( X ) :

T B ( X ) = N B 1 ( x 1 ) + N B 2 ( x 2 ) + N B 3 ( x 3 ) (4.4)

These allocations cannot exceed the amount of water available, Q, less any that must remain in the river, R. Assuming the available flow for allocations, Q R , is 4. The crisp optimization problem is to maximize Equation (4.4) subject to the resource constraint:

x 1 + x 2 + x 3 4 (4.5)

Thus the problem is:

max T B ( X ) = ( x 1 + 0.5 x 1 2 ) + ( 2 x 2 + x 2 2 ) + ( x 3 + 1.5 x 3 2 ) s .t . { x 1 + x 2 + x 3 4 x 1 , x 2 , x 3 0 (4.6)

The precise quantification of many system performance criteria and parameter and decision variables is not always possible, nor is it always necessary. When the values of variable cannot be precisely specified, they are said to be uncertain or fuzzy. If the values are uncertain, probability distributions may be used to quantify them. Alternatively, if they are best described by qualitative adjectives, such as dry or wet, hot or cold, clean or dirty, and high or low, fuzzy membership function can be used to quantify them. Both probability distribution and fuzzy membership functions of these uncertain or qualitative variables can be included in quantitative optimization models. Now we illustrate how fuzzy descriptors can be incorporated into optimization models of water resources systems. Assuming the available flow for allocations, Q R , is not certainly known and is represented by an interval 4 , 2 , 1.5 . Thus the problem turns to the fuzzy quadratic programming problem as follows:

max T B ( X ) = ( 3 x 1 + x 1 2 ) + ( 2 x 2 + x 2 2 ) + ( x 3 + 1.5 x 3 2 ) s .t . { x 1 + x 2 + x 3 4 , 2 , 1.5 x 1 , x 2 , x 3 0 (4.7)

This problem is in the form of model (3.2). Hence it can be solved using the proposed method. Since the parameter b 1 , is triangular fuzzy number, thus the objective value of the problem should be fuzzy number as well. According to the proposed method the fuzzy solution obtained by solving the following program:

max T B ( X ) = ( 3 x 1 + x 1 2 ) + ( 2 x 2 + x 2 2 ) + ( x 3 + 1.5 x 3 2 ) s .t . { x 1 + x 2 + x 3 4 x 1 + x 2 + x 3 2 x 1 + x 2 + x 3 5.5 x 1 , x 2 , x 3 0

where parameter values are all known constant. Thus this model is conventional quadratic programming problems. By solving this problem using SQP algorithm the global optimum solution is obtained as:

X = ( 2 , 0 , 0 )

The value of objective function is also achieved z * = 10 .

5. Conclusion

This paper generalized the conventional quadratic programming of constant parameters to fuzzy parameters and the range of optimal objective values produced from the fuzzy parameters, including constraint coefficient and right-hand sides. The idea is to transform the defined fuzzy quadratic programming problem in to a conventional quadratic problem. Then the classical programming problem is solved using SQP algorithm and as a result, the optimal solution and the optimal value of the objective function are obtained. We emphasize that this work can be extended to the other practical situations as well as water resource management and etc. Also, as we mentioned in our study, in the mentioned model we assumed the type of fuzzy number is triangular while in the many real situations it is a limitation for our study and hence we suggest the interested readers focus on the other kinds of fuzzy numbers and then they may achieve some new results. Our other suggestion is establishing a new rule for fuzzy ordering.

Acknowledgements

The authors would like to thank the anonymous referees for their valuable comments that help us to improve the earlier version of this work.

Cite this paper: Mirmohseni, S. and Nasseri, S. (2017) A Quadratic Programming with Triangular Fuzzy Numbers. Journal of Applied Mathematics and Physics, 5, 2218-2227. doi: 10.4236/jamp.2017.511181.
References

[1]   Floudas C.A., Pardalos P., Adjiman C., Esposito W.R., Gumus Z.H., Harding S.T., Klepeis J.L., Meyer C.A. and Sshweiger, C.A. (1999) Handbook of Test Problems in Local and Global Optimization. Non convex Optimization and its Applications, Vol. 33, Kluwer Academic Publishers, Dordrecht.

[2]   Gould, N.I.M. and Toint, P.L. (2000) A Quadratic Programming Bibliography. RAL Numerical Analysis Group Internal Report 2000-1, Department of Mathematics, University of Namur, Bruxelles, Belgium.

[3]   Hock, W. and Schittkowski, K. (1981) Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, Vol. 187, Spring-Verlag, Berlin.

[4]   Maros, I. and Meszaros, C. (1997) A Repository of Convex Quadratic Problems. Department Technical Report DOC 97/6, Department of Computing, Imperial College, London, UK.

[5]   Schittkowski, K. (1987) More Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, Vol. 282, Spring-Verlag, Berlin.

[6]   Beale, E. (1959) On Quadratic Programming. Naval Research Logistics Quarterly, 6, 227-244.
https://doi.org/10.1002/nav.3800060305

[7]   Bellman, R.E. and Zadeh, L.A. (1970) Decision-Making in a Fuzzy Environment. Management Science, 17, 164.
https://doi.org/10.1287/mnsc.17.4.B141

[8]   Markowitz, H. (1952) Portfolio Selection. The Journal of Finance, 7, 77-91.

[9]   Markowitz, H.M. (1991) Portfolio Selection: Efficient Diversification of Investments. 2nd Edition, Blackwell Publisher.

[10]   Inuiguchi, M. and Ramik, J. (2000) Possibilistic Linear Programming: A Brief Review of Fuzzy Mathematical Programming and a Comparison with Stochastic Programming in Portfolio Selection Problem. Fuzzy Sets and Systems, 111, 3-28.

[11]   Leon, T. and Liercher, E. (2000) Viability of Infeasible Portfolio Selection Problems: A Fuzzy Approach. European Journal of Operational Research, 139, 178-189.

[12]   Tanaka, H., Guo, P. and Turksen, B. (2000) Portfolio Selection Based on Fuzzy Probabilities and Possibility Distributions. Fuzzy Sets and Systems, 111, 387-397.

[13]   Verchur, E., Bermudez, J.D. and Segura, J.V. (2007) Fuzzy Portfolio Optimization under Downside Risk Measures. Fuzzy Sets and Systems, 158, 769-782.

[14]   Watada, J. (1997) Fuzzy Portfolio Selection and Its Applications to Decision Making. Tatra Mountains Mathematics Publications, 13, 219-248.

[15]   Mahdavi-Amiri, N., Nasseri, S.H. and Yazdani Cherati, A. (2009) Fuzzy Primal Simplex Algorithm for Solving Fuzzy Linear Programming Problems. Iranian Journal of Operational Research, 2, 68-84.

[16]   Nasseri, S.H. and Ebrahimnejad, A. (2010) A Fuzzy Primal Simplex Algorithm and Its Application for Solving Flexible Linear Programming Problems. European Journal of Industrial Engineering, 4, 327-389.
https://doi.org/10.1504/EJIE.2010.033336

[17]   Nasseri, S.H. and Mahdavi-Amiri, N. (2009) Some Duality Results on Linear Programming Problems with Symmetric Fuzzy Numbers. Fuzzy Information and Engineering, 1, 59-66.
https://doi.org/10.1007/s12543-009-0004-2

[18]   Nasseri, S.H., Attari, H. and Ebrahimnejad, A. (2012) Revised Simplex Method and Its Application for Solving Fuzzy Linear Programming Problems. European Journal of Industrial Engineering, 6, 259-280.
https://doi.org/10.1504/EJIE.2012.046670

[19]   Lio, S.T. (2009) Quadratic Programming with Fuzzy Parameters. Chaos, Solitons and Fractals, 40, 237-245.

[20]   Lio, S.T. (2009) A Revisit to Quadratic Programming with Fuzzy Parameters. Chaos, Solitons and Fractals, 41, 1401-1407.

[21]   Modares, H. and NaghibiSistani, M.B. (2011) Solving Nonlinear Optimal Control Problems using a Hybrid IPSO-SQP Algorithm. Journal of Engineering Applications of Artificial Intelligence, 24, 476-484.

[22]   Bayon, L., Grau, J.M., Ruiz, P.M. and Suarez, M.M. (2010) Initial Guess of the Solution of Dynamic Optimization of Chemical Processes. Journal of Mathematical Chemistry, 48, 27-38.
https://doi.org/10.1007/s10910-009-9614-5

[23]   Costa, C.B.B., Maciel, A.C. and Filho, R. (2005) Mathematical Modeling and Optimal Control Strategy Development for an Acidic Crystallization Process. Chemical Engineering and Processing, 44, 737-753.

[24]   Hu, G. and Xu, S. (2009) Optimization Design of Microchannel Heat Sink Based on SQP Method and Numerical Simulation. Applied Conference on Superconductivity and Electromagnetic Devises, ASEMD, 89-92.

[25]   Wang, R., Wang, P. and Zhu, Y. (2011) Study on Optimization of Isolated Heat Pipe Heat Exchange System Based on SQP. International Conference on Electric Information and Control Engineering.

[26]   Luenberger, G.D. (2008) Linear and Nonlinear Programming. 3rd Edition, Springer, New York.

 
 
Top