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:
(1.1)
The function to be minimized (or maximized) is called an objective function; let us denote it by
. The numbers
are called cost coefficients and the vector
is called a cost vector. The vector
is called a right-hand side vector and the matrix
, where
and
, is called a constraint matrix. The matrix
, is called the matrix of quadratic form where
and
. Using this notation, the formulation of the problem can be simplified as:
(1.2)
where
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:
(1.3)
in which
,
,
and
. Hence it can be
rewritten as
follows:
(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
be the real line, then a fuzzy set A in
is defined to be a set of ordered pairs
, where
is called the membership function for the fuzzy set. The membership function maps each element of
to a membership value between 0 and 1.
Definition 2.2: The support of a fuzzy set A is defined as fallow:
Definition 2.3: The core of a fuzzy set is the set of all points x in
with
.
Definition 2.4: A fuzzy set A is called normal if its core is nonempty. In other words, there is at least one point
with
.
Definition 2.5: The α-cut or α-level set of a fuzzy set is a crisp set defined by
.
Definition 2.6: A fuzzy set A on
is convex, if for any
and
, we have
Definition 2.7: A fuzzy number
is a fuzzy set on the real line that satisfies the condition of normality and convexity.
Definition 2.8: A fuzzy number
on
is said to be triangular fuzzy number, if there exist real numbers and
such that
We denote a triangular fuzzy number
by three real numbers
and
as
, whose meaning are defined in Figure 1. We also denote the set of all triangular fuzzy numbers with F(R).
Definition 2.9: Let
and
be two triangular numbers and
. Summation and multiplication of fuzzy numbers defined as [18] :
if and only if
Definition 2.10: We let
as a zero triangular fuzzy number.
Remark 2.1:
if and only if
.
Remark 2.2:
if and only if
.
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:
(3.1)
where
,
,
and
are fuzzy numbers, and
are variables whose states are fuzzy numbers
; 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.
(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:
(3.3)
where
and
are fuzzy numbers. According to Definition 2.9, the constraint
yields that:
Substituting these relations in to (3.3) the conventional quadratic program is derived as follows:
(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:
(3.5)
where
is the cost function and
stands for the constraint. In this regard a Lagrangian function
is constructed in terms of the Lagrangian multiplier
. The cost function together with the above constraint is defined as follows:
(3.6)
In fact the SQP consists of three main parts:
1- Update the Hessian of the Lagrangian function according to:
(3.7)
2- Solve the quadratic programming sub-problem:
(3.8)
3- A linear search to find a solution for the next iteration:
(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
is supposed symmetric
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,
is convex if and only if its
Hessian matrix is positive semi definite for all possible values of
. That is for any
the following relation is satisfied:
in which
is the Hessian matrix of
function
. Hence the above relation can be rewritten as follow:
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
and their water allocations by
. Assume the problem is to determine the allocations
of water to each of three firms
that maximize the total net benefits,
, obtained from all three firms. The total amount of water available is constrained or limited to a quantity of Q. Assume the net benefits
, derived from water
allocated to each firm
, are defined by:
(4.1)
(4.2)
(4.3)
The problem is to find the allocations of water to each firm that maximize the total benefits
:
(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,
, is 4. The crisp optimization problem is to maximize Equation (4.4) subject to the resource constraint:
(4.5)
Thus the problem is:
(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,
, is not certainly known and is represented by an interval
. Thus the problem turns to the fuzzy quadratic programming problem as follows:
(4.7)
This problem is in the form of model (3.2). Hence it can be solved using the proposed method. Since the parameter
, 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:
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:
The value of objective function is also achieved
.
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.