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 MATLAB^TM toolbox and the numerical results are presented.

Keywords:

Fuzzy Numbers, Quadratic Programming, Membership Function

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:

$\begin{array}{l}\text{maximaize}\left(\text{orminimize}\right){\displaystyle \sum }_{j=1}^n{c}_j{x}_j+\frac{1}{2}{\displaystyle \sum }_{i=1}^n{\displaystyle \sum }_{j=1}^n{q}_{ij}{x}_i{x}_j\\ \text{subject}\text{to}\{\begin{array}{l}{\displaystyle \sum }_{j=1}^n{a}_{ij}{x}_j\le b_i,i\in N_m\\ x_j\ge 0,i\in N_m\end{array}\end{array}$ (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\in N_n$ are called cost coefficients and the vector $c=\left(c_1,c_2,\cdots ,c_n\right)$ is called a cost vector. The vector $b^{\text{T}}=\left(b_1,b_2,\cdots ,b_m\right)$ is called a right-hand side vector and the matrix $A={\left[a_{ij}\right]}_{m\times n}$ , where $i\in N_m$ and $j\in N_n$ , is called a constraint matrix. The matrix $Q={\left[q_{ij}\right]}_{m\times n}$ , is called the matrix of quadratic form where $i\in N_n$ and $j\in N_n$ . Using this notation, the formulation of the problem can be simplified as:

$\begin{array}{l}\max z=cx+\frac{1}{2}{x}^{\text{T}}Qx\\ \text{s}\text{.t}.\{\begin{array}{l}Ax\le b\\ x\ge 0\end{array}\end{array}$ (1.2)

where $x={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{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:

$\begin{array}{l}\max z=2x_1+x_2+2x_1^2+x_1{x}_2+2x_2^2\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+x_2\le 2\\ 2x_1+3x_2\le 1\\ x_1,x_2\ge 0\end{array}\end{array}$ (1.3)

in which $Q=\left[\begin{array}{cc}4& 1\\ 1& 4\end{array}\right]$ , $c=\left(2,1\right)$ , $A=\left[\begin{array}{cc}1& 1\\ 2& 3\end{array}\right]$ and $b^{\text{T}}=\left(2,1\right)$ . Hence it can be

rewritten as

follows:

$\begin{array}{l}\max z=\left(2,1\right)\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]+\left[\begin{array}{cc}{x}_1& x_2\end{array}\right]\left[\begin{array}{cc}4& 1\\ 1& 4\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}\left[\begin{array}{cc}1& 1\\ 2& 3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\le \left[\begin{array}{c}2\\ 1\end{array}\right]\\ x_1,x_2\ge 0\end{array}\end{array}$ (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=\left\{\left(x,{\mu }_A\left(x\right)\right)|x\in R\right\}$ , where ${\mu }_A\left(x\right)$ 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:

$supp\left(A\right)=\left\{x\in R|{\mu }_A\left(x\right)>0\right\}$

Definition 2.3: The core of a fuzzy set is the set of all points x in $R$ with ${\mu }_A\left(x\right)=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\in R$ with ${\mu }_A\left(x\right)=1$ .

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

$A_{\alpha }=\left\{x\in R|{\mu }_A\left(x\right)>\alpha \right\}$ .

Definition 2.6: A fuzzy set A on $R$ is convex, if for any $x,y\in R$ and $\lambda \in \left[0,1\right]$ , we have

${\mu }_A\left(\lambda x+\left(1-\lambda \right)y\right)\ge \min \left\{{\mu }_A\left(x\right),{\mu }_A\left(y\right)\right\}$

Definition 2.7: A fuzzy number $\overline{a}$ is a fuzzy set on the real line that satisfies the condition of normality and convexity.

Definition 2.8: A fuzzy number $\tilde{a}$ on $R$ is said to be triangular fuzzy number, if there exist real numbers and $l,r\ge 0$ such that

$\tilde{a}\left(x\right)=\{\begin{array}{l}\frac{x}{l}+\frac{l-s}{l},x\in \left[s-l,s\right]\\ \frac{-x}{r}+\frac{s+r}{r},x\in \left[s,s+r\right]\\ 0,\text{o}\text{.w}\text{.}\end{array}$

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

Definition 2.9: Let $\tilde{a}=\langle s_a,l_a,r_a\rangle$ and $\tilde{b}=\langle s_b,l_b,r_b\rangle$ be two triangular numbers and $x\in R$ . Summation and multiplication of fuzzy numbers defined as [18] :

$x\tilde{a}=\{\begin{array}{l}\langle x{s}_a,x{l}_a,x{r}_a\rangle ,x\ge 0\\ \langle x{s}_a,-x{r}_a,-x{l}_a\rangle ,x<0\end{array}$

$\tilde{a}+\tilde{b}=\langle s_a+s_b,l_a+l_b,r_a+r_b\rangle$

$\tilde{a}-\tilde{b}=\langle s_a-s_b,l_a-r_b,r_a-l_b\rangle$

$\tilde{a}\le \tilde{b}$ if and only if $s_a\le s_b,s_a-l_a\le s_b-l_b,s_a+r_a\le s_b+r_b$

Definition 2.10: We let $\tilde{0}=\left(0,0,0\right)$ as a zero triangular fuzzy number.

Remark 2.1: $\tilde{a}\ge \tilde{0}$ if and only if $s_a\ge 0,s_a-l_a\ge 0,s_a+r_a\ge 0$ .

Remark 2.2: $\tilde{a}\le \tilde{b}$ if and only if $-\tilde{a}\ge -\tilde{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:

$\begin{array}{l}\max z={\displaystyle \sum }_{j=1}^n{\tilde{C}}_j{\tilde{X}}_j+\frac{1}{2}{\displaystyle \sum }_{i=1}^n{\displaystyle \sum }_{j=1}^n{\tilde{Q}}_{ij}{\tilde{X}}_i{\tilde{X}}_j\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \sum }_{j=1}^n{\tilde{A}}_{ij}{\tilde{X}}_j\le {\tilde{B}}_i,i\in N_m,\\ \tilde{X}\ge 0\end{array}\end{array}$ (3.1)

where ${\tilde{A}}_{ij}$ , ${\tilde{B}}_i$ , ${\tilde{C}}_j$ and ${\tilde{Q}}_{ij}$ are fuzzy numbers, and ${\tilde{X}}_j$ are variables whose states are fuzzy numbers $\left(i\in N_m,j\in N_n\right)$ ; 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.

$\begin{array}{l}\max z={\displaystyle \sum }_{j=1}^n{c}_j{x}_j+\frac{1}{2}{\displaystyle \sum }_{i=1}^n{\displaystyle \sum }_{j=1}^n{q}_{ij}{x}_i{x}_j\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \sum }_{j=1}^n{\tilde{A}}_{ij}{x}_j\le {\tilde{B}}_i,i\in N_m,\\ x\ge 0\end{array}\end{array}$ (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:

$\begin{array}{l}\max z={\displaystyle \sum }_{j=1}^n{c}_j{x}_j+\frac{1}{2}{\displaystyle \sum }_{i=1}^n{\displaystyle \sum }_{j=1}^n{q}_{ij}{x}_i{x}_j\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \sum }_{j=1}^n\langle a_{ij},l_{ij},r_{ij}\rangle x_j\le \langle b_i,u_i,v_i\rangle ,i\in N_m\\ x_j\ge 0,j\in N_n\end{array}\end{array}$ (3.3)

where ${\tilde{A}}_{ij}=\langle a_{ij},l_{ij},r_{ij}\rangle$ and ${\tilde{B}}_i=\langle b_i,u_i,v_i\rangle$ are fuzzy numbers. According to Definition 2.9, the constraint ${{\displaystyle \sum }}_{j=1}^n\langle a_{ij},l_{ij},r_{ij}\rangle x_j\le \langle b_i,u_i,v_i\rangle ,i\in N_m$ yields that:

${\displaystyle \sum }_{j=1}^n{a}_{ij}{x}_j\le b_i,{\displaystyle \sum }_{j=1}^n\left(a_{ij}-l_{ij}\right)x_j\le b_i-u_i\text{and}{\displaystyle \sum }_{j=1}^n\left(a_{ij}+r_{ij}\right)x_j\le b_i+v_i,i\in N_m$

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

$\begin{array}{l}\max z={\displaystyle \sum }_{j=1}^n{c}_j{x}_j+\frac{1}{2}{\displaystyle \sum }_{i=1}^n{\displaystyle \sum }_{j=1}^n{q}_{ij}{x}_i{x}_j\\ {\displaystyle \sum }_{j=1}^n{a}_{ij}{x}_j\le b_i,i\in N_m\\ {\displaystyle \sum }_{j=1}^n\left(a_{ij}-l_{ij}\right)x_j\le b_i-u_i,i\in N_m\\ {\displaystyle \sum }_{j=1}^n\left(a_{ij}+r_{ij}\right)x_j\le b_i+v_i,i\in N_m\\ x_j\ge 0,j\in N_n\end{array}$ (3.4)

However, since all numbers involved are real numbers, this is classical quadratic programming problem which can be solved using MATLAB^TM 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:

$\begin{array}{l}\text{minimize}J\left(x\right)\\ \text{subjected}\text{to}:{\psi }_i\left(x\right)\le 0,i=1,\cdots ,m\end{array}$ (3.5)

where $J\left(x\right)$ is the cost function and ${\psi }_i\left(x\right)$ stands for the constraint. In this regard a Lagrangian function $L\left(x,\lambda \right)$ is constructed in terms of the Lagrangian multiplier ${\lambda }_i$ . The cost function together with the above constraint is defined as follows:

$L\left(x,\lambda \right)=J\left(x\right)+{\displaystyle \sum }_{i=1}^m{\lambda }_i{\psi }_i\left(x\right)$ (3.6)

In fact the SQP consists of three main parts:

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

$\begin{array}{l}{H}_{k+1}=H_k+\frac{q_k{q}_k^{\text{T}}}{q_k^{\text{T}}{S}_k}-\frac{H_k^{\text{T}}{H}_k}{S_k^{\text{T}}{H}_k{S}_k}\\ H_0=I\\ S_k=X_{k+1}-X_k\\ q_k=\nabla f\left(X_{k+1}\right)+{\displaystyle \sum }_{i=1}^n{\lambda }_i\nabla g_i\left(X_{k+1}\right)-\left(\nabla f\left(X_k\right)+{\displaystyle \sum }_{i=1}^n{\lambda }_i\nabla g_i\left(X_k\right)\right)\end{array}$ (3.7)

2- Solve the quadratic programming sub-problem:

$\begin{array}{l}\min \frac{1}{2}{q}_k^{\text{T}}{H}_k{d}_k+\nabla f{\left(x_k\right)}^{\text{T}}{d}_k\\ \nabla {\psi }_i{\left(x_k\right)}^{\text{T}}{d}_k+{\psi }_i\left(x_k\right)=0,i=1,\cdots ,m\\ \nabla {\psi }_i{\left(x_k\right)}^{\text{T}}{d}_k+{\psi }_i\left(x_k\right)\ge 0,i=1,\cdots ,m\end{array}$ (3.8)

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

$X_{k+1}=X_k+\alpha 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 $\left(q_{ij}=q_{ji}\right)$ 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\left(x_1,x_2,\cdots ,x_n\right)$ is convex if and only if its $n\times n$ Hessian matrix is positive semi definite for all possible values of $\left(x_1,x_2,\cdots ,x_n\right)$ . That is for any $x\ge 0$ the following relation is satisfied:

$\left(x_1,x_2,\cdots ,x_n\right)\left[\begin{array}{ccc}\frac{{\partial }^{2}f}{\partial x_1^2}& \cdots & \frac{{\partial }^{2}f}{\partial x_n{x}_1}\\ ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_1{x}_n}& \cdots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right]\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right)\ge 0,\forall \left(x_1,x_2,\cdots ,x_n\right)\in {ℝ}^n$

in which $H\left(x\right)=\left[\begin{array}{ccc}\frac{{\partial }^{2}f}{\partial x_1^2}& \cdots & \frac{{\partial }^{2}f}{\partial x_n\partial x_1}\\ ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_1\partial x_n}& \cdots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right]={\left[\frac{{\partial }^{2}f}{\partial x_j\partial x_i}\right]}_{n\times n}$ is the Hessian matrix of

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

$x^{\text{T}}H\left(x\right)x\ge 0,\forall x\in {ℝ}^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 $\left(j=1,2,3\right)$ that maximize the total net benefits, ${\displaystyle {\sum }_{j}N{B}_j\left(x_j\right)}$ , 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\left(x_j\right)$ , derived from water $x_j$ allocated to each firm $j$ , are defined by:

$N{B}_1\left(x_1\right)=x_1+0.5x_1^2$ (4.1)

$N{B}_2\left(x_2\right)=2x_2+x_2^2$ (4.2)

$N{B}_3\left(x_3\right)=x_3+1.5x_3^2$ (4.3)

The problem is to find the allocations of water to each firm that maximize the total benefits $TB\left(X\right)$ :

$TB\left(X\right)=N{B}_1\left(x_1\right)+N{B}_2\left(x_2\right)+N{B}_3\left(x_3\right)$ (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\le 4$ (4.5)

Thus the problem is:

$\begin{array}{l}\max TB\left(X\right)=\left(x_1+0.5x_1^2\right)+\left(2x_2+x_2^2\right)+\left(x_3+1.5x_3^2\right)\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+x_2+x_3\le 4\\ x_1,x_2,x_3\ge 0\end{array}\end{array}$ (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 $\langle 4,2,1.5\rangle$ . Thus the problem turns to the fuzzy quadratic programming problem as follows:

$\begin{array}{l}\max TB\left(X\right)=\left(3x_1+x_1^2\right)+\left(2x_2+x_2^2\right)+\left(x_3+1.5x_3^2\right)\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+x_2+x_3\le \langle 4,2,1.5\rangle \\ x_1,x_2,x_3\ge 0\end{array}\end{array}$ (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:

$\begin{array}{l}\max TB\left(X\right)=\left(3x_1+x_1^2\right)+\left(2x_2+x_2^2\right)+\left(x_3+1.5x_3^2\right)\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+x_2+x_3\le 4\\ x_1+x_2+x_3\le 2\\ x_1+x_2+x_3\le 5.5\\ x_1,x_2,x_3\ge 0\end{array}\end{array}$

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=\left(2,0,0\right)$

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.M. and Nasseri, S.H. (2017) A Quadratic Programming with Triangular Fuzzy Numbers. Journal of Applied Mathematics and Physics, 5, 2218-2227. https://doi.org/10.4236/jamp.2017.511181

References