A new algorithm for resolution of the quadratic programming problem with fuzzy relation inequality constraints

Highlights

• A minimization problem of quadratic function with fuzzy relation inequality constraints is studied.

• Its objective function is not necessarily convex.

• We use properties of symmetric matrices, Cholesky’s decomposition, and least square technique.

• The problem is converted into a separable problem and an algorithm is proposed to solve it.

• An application is given to illustrate the problem.

Abstract

The minimization problem of a quadratic objective function with the max-product fuzzy relation inequality constraints is studied in this paper. In this problem, its objective function is not necessarily convex. Hence, its Hessian matrix is not necessarily positive semi-definite. Therefore, we cannot apply the modified simplex method to solve this problem, in a general case. In this paper, we firstly study the structure of its feasible domain. We then use some properties of n × n real symmetric indefinite matrices, Cholesky’s decomposition, and the least square technique, and convert the problem to a separable programming problem. Furthermore, a relation in terms of a closed form is presented to solve it. Finally, an algorithm is proposed to solve the original problem. An application example in the economic area is given to illustrate the problem. Of course, there are other application examples in the area of digital data service and reliability engineering.

Introduction

Fuzzy Relation Equations (FRE), Fuzzy Relation Inequalities (FRI), and the problems associated to them have many applications in different areas such as fuzzy control (Czogala & Predrycz, 1981), fuzzy decision-making (Di Nola et al., 1989, Nobuhara et al., 2006b, Pedrycz, 1985, Peeva and Kyosev, 2004), fuzzy symptom diagnosis (Vasantha Kandasamy & Smarandache, 2004), fuzzy medical diagnosis (Vasantha Kandasamy & Smarandache, 2004), image processing (Di Nola and Russo, 2007, Loia and Sessa, 2005, Nobuhara et al., 2006a) and so on. The problems have been studied by many researchers in both theoretical and applied areas since the resolution of FRE was proposed by Sanchez in 1976. An interesting extensively investigated kind of such problems is the optimization of the objective functions on the region whose set of feasible solutions have been defined as FRE (Guu et al., 2011, Khorram and Zarei, 2009, Li et al., 2012, Lin et al., 2009, Shieh, 2011, Thapar et al., 2009) or FRI (Abbasi Molai, 2010, Freson et al., 2013, Gavalec and Zimmermann, 2013, Ghodousian and Khorram, 2012, Guo et al., 2011) constraints. Comprehensive review of the works up to 2007 can be found in (Li & Fang, 2008). The optimization problem of a linear objective function subject to FRE with the max–min composition has firstly been studied by Fang and Li (1999). The problem was equivalently converted to a 0–1 integer programming problem and solved by the branch-and-bound approach. Wu et al., 2002, Wu and Guu, 2005 accelerated Fang and Li’s approach by providing the upper bounds for the branch-and-bound procedure. Then the optimization problem with the max-product composition was investigated by Loetamonphong and Fang (2001) and a similar idea was applied to solve the problem. Also, a necessary condition for its optimal solution in terms of the maximum solution of FRE was presented by Guu and Wu (2002). We can find other generalizations on these kinds of problems with FRE constraints, for example, see references (Chang and Shieh, 2013, Guu and Wu, 2010, Hassanzadeh et al., 2011, Lu and Fang, 2001, Thapar et al., 2012, Zhou and Ahat, 2011).

The linear objective function optimization problem with the max–min FRI was considered by Zhang, Dong, and Ren (2003). Guo and Xia (2006) presented an approach to solve the problem based on a necessary condition of optimality. Moreover, another condition was provided to accelerate Guo and Xia’s approach by Mashayekhi and Khorram (2009). Ghodousian and Khorram (2008) studied the problem in which the fuzzy inequality replaces the ordinary inequality in the constraints and then suggested a method to solve it. However, the optimization of nonlinear objective functions with FRI has been developing very slowly. The initial research about this topic can be found in Lu and Fang (2001). Since the resolution of these kinds of problems, in a general case, is difficult using traditional nonlinear optimization methods, many researchers focused on the fuzzy relation inequality programming with nonlinear objective functions in different forms such as the latticized linear programming problem with the max–min FRI constraints (Wang, Zhang, Sachez, & Lee, 1991), fuzzy relational geometric programming with the max–min and max-product FRE (Singh et al., 2012, Wu, 2006, Yang and Cao, 2005a, Yang and Cao, 2005b, Yang and Cao, 2007, Zhou and Ahat, 2011), linear fractional programming problem with the max-Archimedean t-norm FRE (Wu et al., 2007, Wu et al., 2008), monomial geometric programming problem with the max-product FRI (Shivanian & Khorram, 2009), quadratic programming problem with the max-product FRI (Abbasi Molai, 2012) and so on. With regard to the importance of quadratic programming and the fuzzy relation inequality in both theory and application, Abbasi Molai (2012) proposed a fuzzy relation quadratic programming with the max-product composition. He showed that the minimal solutions and the maximum solution of its feasible domain cannot guarantee the resolution of the problem, in a general case. In the paper, some sufficient conditions were presented to simplify the problem. However, the simplified problem has been solved in a special case where the objective function is convex or equivalently its Hessian matrix, i.e., matrix Q, is positive semi-definite. In this case, we can only apply the modified simplex method to solve the simplified problem. Hence, we are motivated to propose a new algorithm to solve the problem when the objective function is not convex or the (reduced) matrix Q is not semi-positive definite. In this paper, some sufficient conditions are presented to simplify the resolution process of the fuzzy relation quadratic programming problem in the recent case. Under the sufficient conditions and applying Cholesky’s factorization, a suitable variable change is proposed to convert the quadratic objective function to a separable quadratic objective function including only expressions as $x_i\text{,}{x}_i^2$, and $y_i^2$. In this case, we use a linear approximation instead of functions $y_i^2$ by the least square technique. Then applying the variable change between two variable vectors x and y, we obtain a separable quadratic programming problem with respect to x. This problem is easily solved and the optimal solutions of the original problem are found in x-space.

The organization of this paper is as follows. Section 2 is formed by two subsections. The first subsection introduces the quadratic programming problem with FRI constraints and its feasible solution set is investigated in the second subsection. Section 3 presents some sufficient conditions to convert the problem to a special form of quadratic programming including only expressions as $x_i\text{,}{x}_i^2$, and $y_i^2$ by a suitable variable change and Cholesky’s factorization. A linear approximation is then used instead of functions $y_i^2$ by the least square technique. Moreover, with regard to relation between variable vectors x and y, we obtain a separable quadratic programming problem with respect to x. This problem is easily solved and the approximate optimal value of original problem is found in x-space. With attention to the above points, an algorithm is designed to solve the quadratic programming problem when the objective function is not convex in a general case. In Section 4, the proposed algorithm is compared with the previous works. In Section 5, an application example is presented to illustrate the problem. Of course, we point to other application examples that they can be modeled as the quadratic programming problem with FRI constraints. Finally, conclusions are given in Section 6.